Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 40
Текст из файла (страница 40)
В силу теоремы 5 функция (11) выпукла на Е'. Согласно теореме 3 для того, чтобы функция (11) достигала своей нижней грани на Е" в точке и, необходимо и достаточно, чтобы и удовлетворяла системе линейных алгебраических уравнений А'Аи = А'Ь. [гл. 4 170 ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА 6. Посмотрим, нак влияют на выпуклость сложение, умноженне на число и некоторые другие операции над выпуклыми функцнямн. Легко доказывается Теорема 6.
Если функции У,(и) (1=1, ..., 1п) выпукльг на выпуклом множестве, то функция У(и) = я,У, (и)+... + я У„(и) выпукла па этом множестве при любых сц > 0 (1= 1, ..., т). Те о р е м а 7. Пусть У,(и) (1ж У) — произвольное семейство функций, выпуклых на выпуклом множестве П, пусть У(и) = зпрУ1(и), ия П.
1Н1 Тогда функция У(и) выпукла на П. Д о к а з а т е л ь с т в о. Возьмем пронзвольпые точки и, и ж П н числа я я[0, 1), е >О. Положим и„=яи+(1 — я)о. По определеппю веркнен грани найдется индекс 1 = 1(е, я) 4И 1 такой, что У(и„) — в<У;(и„).
С учетом выпуклостн У,(и) тогда имеем У(и„) < У,(и„)+ е < яУ,(и)+(1 — я) У,(о)+ е < < яУ(и)+ (1 — я) У(о)+ е нлн У(и„) < яУ(и)+(1 — сс)У(о)+ е при любом е >О. Отсюда прп е — +О следует выпуклость У(и), что и требовалось. Следствие 1. Пусть функция д(и) выпукла на выпуклом множестве П. Тогда функция д+(и) = жах (у(и); 0) выпукла на П.
Теорема 8. Пусть функция ф(1) одной переменной выпукла и не убывает на отрезке [а, Ь[ (возможность а= — и.ли Ь = здесь не исключается), пусть функция д(и) выпукла на выпуклом мнолсестве П':-Е", причем у(и)~и[а, Ь[ при всех и ж П. Тогда функция У(и) = ф(у(и) ) выпукла на Г Доказательство. Возьмем произвольные и, о4я П н яж ~ [О, 1). Тогда У(яи+ (1 — я) и) = = ф (д(яи+ (1 — я) о) ) < ф (яд(и)+ (1 — я) у(о) )— < яф(у(и) )+(1 — я) ф(д(о) ) = яУ(и)+ (1 — я) У(о), что и требовалось.
Иногда удобнее пользоваться другим вариантом этой теоремы: если функция ф(1) выпукла я не возрастает на отрезке [а, Ь). а д(и) вогнута на выпуклом множестве П Е", д(и)4н аз[а, Ь[ при иж П, то функция У(и)=ф(у(и)) выпукла на П. ВЫПУКЛЫЕ ФУНКЦИИ Следствие 1. Если функция у(и) выпукла и неотрицательна на выпуклолг множестве Н, то функция у(и) = (у(и))' выпукла на Н при всех р > 1. Следствие 2. Если функция д(и) выпукла на выпуклом множестве Н, то функция г (и1=(шах (О; д(и))) э =(у+(и) )' вьлгукла на Н при всех р ~ 1. Следствие 3.
Если функция д(и) выпукла на выпуклом гшожестве Г, причем д(и)<0 при всех и«Н, то функции г(и)= — 1/д(и), г(и)=шах( — 1п( — д(и)); 0)э, р~1, в ььпу ьлы на Н. Как увидим ниже, функции, указанные в следствиях к теоремам 7, 8, будут использованы прп описании различных методов мннптшзацпи (например, в методах штрафных и барьерных функций н др.). 7. Выпуклые функции являются удобным средством задания выпуклых множеств.
Это связано с тем, что надграфик всякой выпуклой функции является выпуклым множеством. О и р е де л е н и е 2. Надграфиком (пли эпиграфом) всякой функции 7(и), определенной на множестве Н вЂ” Е", называется множество (рпс. 4.5) ер1г =((и, 7)«Е"+" и«Г, 7~7(и)). Те о р е и а 9. Для того чтобы функция г'(и), определенная на выпуклом множестве Н, была выпуклой на Г, необходимо и достаточно, чтобы ее надграфик был выпуклым множеством. Доказательство. Не обходи-;;~~'~,; ~,,,':~ И ность. Пусть функция Х(и) выпукла на ",',:, ',',|гжр выпуклом множестве Н. Возьмем две произвольные точки г, =(и, Ъ), гг=(им 7 )« ' ' ':"~;!~ «ер17 и составим пх выпуклую комбинацпю г„= иг, + (1 — и) г, = (ии, + (1— — и) и„иц~+(1 — а)цг) (О < а < 1). Из э г"~ г г выпУклости ь слелует, что и„= аи, + Ркс.
4.5. (Надграфвк) +(1 — а)и,«ь'. Из выпуклости функции у(и), учитывая, что г„г,«ер1г', имеем г(и„) <аг(и,) + (1— — а)г(и,)<иц,+(1 — и)цы Следовательно, г «ер1г при всех сг «[О, 1). Выпуклость ер1 Х доказана. Д о с т а т о ч н о с т ь. Пусть ер1 г — выпуклое множество. Возьмем произвольные и„и, «Н и и «[О, 1). Тогда г~ = =(ин г(и,)), г,=(им У(иг))«еР1г. В силУ выпУклости еР1г сгл.
ь ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА 172 точка г„= аг, +(1 — а) г, си ер1Х. Зто значит, что аз (и,)+ + (1 — а) з (из) < з (аи, + (1 — а) и,) . Выпуклость з (и) доказана. Теорема 10. Пусть П вЂ” выпуклое множество, а функция в'(и) выпукла на К Тогда множество М(с)= (и: иск П, з'(и)< < с) выпукло при любом с. Д о к а з а т е л ь с т в о. Возьмем произвольные и, и ш М(с), а си [О, 1). Испольауя выпуклость мноксества сл' и функции в'(и), имеем в(аи+(1 — а) и) < аз(и)+(1 — а)в(п) < с, т.
е. аи+(1— — а) п ш М(с), что и требовалось. Загнетки, что обратное утверждение здесь неверно: пз выпуклости множества М(с) при любом с, вообще говоря, не следует выпуклость функции з(и1. Например, мнонсество М(с)= (и: иш шЕ', и'<с) выпукло прн любом с, а функция з(и)=и' невыпукла на Е' (см. упражнение 33). Т е о р е м а 11. Пусть слв — выпуклое множество, функции у,(и) (1=1, ..., т) выпуклы на У„а е,(и)- <аь и> — Ь, (з = т+ 1, ..., г), где а, — заданные векторы из Е", Ьс — заданные числа (с = т+ 1, ..., г). Тогда выпукло множество Г = (и: и си Пв, д,(и) < О, с = 1, ..., т; у,(и) = О, с=т+1, ..., г). (12) Доказательство.
В силу теоремы 10 ъсножество бтс= = (и: и ш П„д,(и) < 0) выпукло при всех 1= 1, ..., т. Выпукло также множество М = (и ш Е": <аь и> — Ьс = О, 1 = т + 1, ..., г)— см. пример 1.4. Тогда множество (12), являющееся пересечением выпуклых мнохсеств По ..., П, М, само будет выпуклым. 8.
Рассмотренное в теореме 3 условие оптимальности сформулировано для непрерывно-дифференцируемых функций. Однако апалогпчное условие можно получить при гораздо меньших ограничениях на функцию, используя лишь существование производных по направлениям. Напоминаем, чтО производной фуннуии в'(и) в топив и пв направлению в ([в[ = т) называется число дл (и) Р л (и+ Св] — л (и) дв с тв с (т3) Заметим, что для определения производной по направленпю в точке и нужно, чтобы и+ Св принадлежало области определения з'(и) при 0 < с < св хотя бы при малом св ) О.
О п р е д е л е н и е 3. Пусть <à — некоторое множество из Е", пусть и ш <с. Направление в чь 0 называется возможным в точке и, если существует число св ) 0 такое, что и + св ш й' при всех с (О < с < св). Иначе говоря, достаточно малое перемещение из точки и по возможному направлению не выводит за пределы множества бс.
Очевидно, если и си гпт <с, то любое направление в чь 0 является возможным в этой точке. В граничных точках множества возможнее направление может и пе существовать. Пример 5. Пусть <г = (х = (х, у) шЕз: х) О, хз< у <2х'). Нетрудно вплетен что в граничной точке (О, 0) нет ни одного возможного направления. Для выпуклых множеств о', содержащих не менее двух точек, приведенлая в примере 5 ситуация невозможпа: в любой точке и такого выпук- й 2) ВЫПУКЛЫЕ ФУНКЦИИ лого множества (/ имеется хотя бы одно возможное направление, причем направление е Ф 0 будет возможным в точке и тогда и только тогда, когда существуют точка о щ (( (о чь и) и число т ) 0 такие, что е = Т(о — и).
Таким образом, если функции У(и) определена на множестве (/, а направление е()е] = 1) является возможным в точке и(н (/, то функция /(() = У(и+(е) определена на отрезке [О, (,], где (з ) О, и д/(и)/де = = /'(+ 0) — правая производная /(() в точке ( = О. Заметим, что если функция У(и) определена в некоторой е-окрестности точки и и дпфференцируема в этой точке, то Х(и) имеет производные по всем направленпям, причем дХ (и) — =<Х'(и), е), ]е]=1 (14) (ср. с (2.3И) прп (- + 0). Однако обратное неверно: из того, что функция в неноторой точке имеет производные но всем направлениям, вообще говоря, не следует ее дифференцируемость в этой точке, и более того, нельзя гарантировать давке ее непрерывность.
Пример 6. Пусть ( х у Х (и) = Х (х у) = ~ в ] г (О, и = (О, 0) = О. Возьмем произвольное направление е = (сов а, в(п а). Тогда У (О + се) — Х (0) 1 сов а в1п а = — Х(г сова, (гйпа) = г а г, (>О. ( сов а+ в(п а Отсюда имеем дХ (О) ] сове а/в(п а, в(п а ~ О, се [О в(па = О. Однако эта функция раарывна в точке и = О. В самом деле, устремим точку и = (х, у) к нулю по параболе у = х'. Тогда У(х, х') = 1/2 т У(0, 0) = О. Таким образом, требование существования производных по направлению существенно менее зкесткое, чем требование днфференцируемости. В связи с этим представляет интерес получить условия оптимальности в терминах производных по направлению. Те ар ем а 12.
Пусть (( — выпуклое множество, ((а — множество точек минимума функции У(и) на (/, пусть в точке изщ(У функция Х(и) имеет производные по всем возможным направлениям, Тогда необходилсо выполняется условие дХ(и ) — )О де для всех возможных направлений е(]е] = 1) е точке из. Если, кроме того, функция У(и) выпукла на (/, то условие (15) достаточно для того, чтобы и ги (/. Докаватель ство. Необходимость. Пусть и, щ(/п е (]е( = = 1) — воаможное направление в точке иа.
Тогда Х (и + (е) ) Х (и ) или (У (и + (е) — Х(и,))/() 0 при всех достаточно малых ( > О. Отсюда при /-т+ 0 получпм условие (15). Достаточность. Пусть У(и) — выпуклая функция на (/, пусть в некоторой точке из ги (/ выполпяется условие (15). Возьмем любую точку иск (((иФ иа) п положим е= (и — и )/] и — и,].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
