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