Ф.П. Васильев - Методы оптимизации (1125241), страница 47
Текст из файла (страница 47)
— ( „. *, * ункций Г(х) имеем Яи.) ( Яи„+ сг(х — и,)) ( 7(и„) + сз(7(х) — 7(и.)) или < ы(Г(х) — 7"(и„)). Сокращая на сг > О, отсюда получаем 7"(х) > Г(и.) при любом х е Х. Следовательно, и, е Х,. Пусть теперь и, е Е Х„т. е. 7'(и) = 7(е) = Г„, и, е Е Х. Тогда < Г(схи -!- (1 — сс)е) < сх7(и) + (1 — а)Г(е) = 7„, (3) т. е. Г(аи+(1 — сс)е) =7", при всех сг, 0( сз ~(1.
Следовательно, сги+(!в — сх)е Е Х„О < а < 1. Выпуклость Х, доказана. Если и ф е, то для строго выпуклых функций неравенства (3) не могут обратиться в равенства при 0 < о < 1, Следовательно, строго выпуклая функция может достигать своей нижней грани на выпуклом множестве не более чем в одной точке. П Примеры 1.11.1, 1,11.3 — 1.11.5 показывают, что у выпуклых функций множество Х„может быть пустым, может содержать одну или бесконечно много точек. 3.
Далее, остановимся на одном характеристическом свойстве гладких выпуклых функций. Т е о р е м а 2. Пусть Х вЂ” выпуклое множество. Если функция 7(х) выпукла на Х и диффвренцируема в точке е Е Х, то Г(и) > Г(е) + (~'(е), и — е) |7и Е Х. (4) Если Г(х) е С'(Х), то 7(х) выпукла на Х тогда и только тогда, когда неравенство (4) выполняется при всех и, е е Х. Доказательство. Необходимость.
Пусть 7(х) выпукла на Х и дифференцируема в точке е е Х. Перепишем неравенство (1) в виде 7(е + сх(и — е)) — 7(е) < а(Г(и) — Г(е)) Ча Е [О, 1[, Чи, е Е Х. С учетом дифференцируемости 7(х) в точке е отс|ода имеем (Г'(е), о(и — е)) + о(а[и — е[) < сх(7(и) — 1(е)) Деля обе части этого неравенства на сх > 0 и устремляя а — +О, получим неравенство (4). Если 7'(х) е С'(Х), то неравенство (4) верно для всех и, е Е Х. Достаточность. Пусть 7"(х) е С'(Х), Х вЂ” выпуклое множество и пусть неравенство (4) выполняется при всех и, е е Х.
Покажем, что тогда Г(х) выпукла на Х. Возьмем произвольные точки и, е Е Х и число сс, 0'< < а < 1. Положим и = схи + (1 — сс)е. Из (4) получим 7(и) — Г(и ) > (Г'(и ), и — и ), Г(е) — Г(и ) > (Г'(и ), е — и„). 161 4 2. Выпуклые Функции (7'(х,), х — х„) > О Чх Е Х, '[.' или (5) которое в случае х, е !п| Х преврасцается в равенство: Г'(х„) =О. Если, кроме того, функция Г(х) выпукла на Х, то условие (5) является достаточным для того, чтобы х, е Х„.
Д о к а з а т е л ь с т в о. Н е о б х о д н м о с т ь. Пусть х, е Х,. Тогда при любых х Е Х и сс Е [0,1] с учетом дифференцируемости функции 7'(х) в точке х. имеем 0 < 7" (х. + сг(х — х,)) — 7'(х,) = сз (г"(х,), х — х„) + о(сх) 0( (7'(х,), х — х„) +о(а)/сг, ЧхЕ Х, сгсг Е(0, 1[. отсюда при сх — +О получим условие (5). если х, е !п| х, то для че е Я" найдется гг > 0 такое, что х = х, + ге Е Х прн всех г, !г[ ( гх Полагая в (5) х = х, + ге, получим г(Г'(х,), е) > 0 при всех г, [г[ < г, что возможно только при (~'(х,), е) = О, Пользуясь произволом в выборе е, здесь можем взять е = ~'(х,), что приводит к равенству 7'(х,) = О. 3 а м е ч а н и е 1.
Несколько подправив приведенное доказательство необходимости, нетрудно убедиться, что если х„— точка локального минимума 7(х) на множестве Х, то мы также придем к условию (5). До с т а т о ч н о с т ь. Пусть функция Г(х) выпукла на Х, пусть для некоторой точки х, е Х выполнено условие (5). Тогда из неравенства (4) при е= х, получим Г(х) — 7(х) > (1(х), х — х) >О или 7(х) >Г(х) Чх ЕХ.
Следовательно, х„е Х„. Теорема 3 доказана. С! Условие (5) имеет йростой геометрический смысл и означает неотрицателъность производной по направлению е = * функции Г(х) в точке [х — х ! „— об этом подробнее см. ниже в п, 6. Если Х = Я", то условалентно равенству 7'(х,) =О. Таким образом, условие (5) являенным обобщением условия стационарности (2.2.6) для задач экстремум с выпуклым мнохсеством Х.
Заметим, что если х.— очка множества Х, то равенство Г'(х,~ =0 может выполняться, ыполняться. Например, если Г(х) = х, Х = (х е Е '; 1 < х < 2), (х,) =2, н условие (5) в точке х„конечно, выполняется. Если ию 7" (х) = х' рассматривать на отрезке Х = (х Е Е ': 0 < х < 2), (х,) = О, хотя х„= 0 — граничная точка Х. минимумах вие (5) экви ется естеств на условный граничная т может и не в то х.=1, Г' ту же функц то х,=О, ~' Умножим первое из этих неравенств на сс, а второе — на 1 — а и сложим. Получим ссГ(и)+(1 — сс) 7(е) — 7(и ) > (7'(и ), и — и ) =О, что равносильно неравенству (1).
П Неравенство (4) имеет простой геометрический смысл. Как известно [327; 350; 352; 534[, гипеРплоскость Г = ((и, Т) Е Е"~ '. и Е Е", Т = 7"(е) + + (7"'(е),и — е)) является касательной плоскостью к графику функции Т = Г(х) в точке е. Поэтому неравенство (4) означает, что график выпуклой функции лежит не ниже касательной плоскости к этому графику в любой точке е е Х, в которой существует производная 7"'(е) (ср. с теоремой 1.8.4). 4. Следующая теорема, называемая критерием оптимальности для выпуклых функций, дает необходимое и достаточное условие минимума гладких функций на выпуклом множестве.
Т е о р е м а 3. Пусть Х вЂ” выпуклое множество, Մ— множество точек минимума функции 7(х) на Х. Если в точке х„е Х„функция Г(х) диффврвнцируема, то необходимо выполняется неравенство 162 Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА 163 э 2. ВЪ|ПУКЛЫЕ ФУНКЦИИ Неравенство (5), как и условие стационарности (2.2.6), вообще говоря, может быть записано в виде системы и уравнений с и неизвестными х„= = (х,',..., х„"). Поясним это на примере.
Пример 1. Рассмотрим задачу: 7(х)- !и1, хеХ=Е„'=(х=(х', х')е Е Е'. х' > О, х' > О), предполагая, что 7(х) дифференцируема на Е'. Тогда условие (5) равносильно системе уравнений х,'~,,(х,) = О, » = 1, 2. В этом нетрудно убедиться, последовательно анализируя возможности: 1) х„= (О, 0); 2) х„= (х„', хз) > 0; тогда х„е !п! Е' и 7"'(х„) =0; 3) х„' =О, х„' > 0; тогда )',,'(х„) ) О, )',,'(х,) = 0; 4) х„' > О, х,' = 0; тогда 7",,'(х.) = О, 7",,'(х„) ) О, Если Х = Е„" = (х Е Е"; х = (х',..., х") > О), то условие (5) аналогично сводится к системе уравнений х„'~„,(х,) = О, « = 1,..., и.
В общем случае для множеств Х с «хорошей» границей неравенство (5) также может быть записано в виде системы уравнений, составленной из условий принадлежности х. границе множества Х и условий равенства ну- лю производных функции 7(х) по некоторым касательным направлениям к границе в точке х„; правда, получающаяся при этом система может оказать- ся громоздкой и сложной для исследования. Не вдаваясь в детали, заметим, что для некоторых классов задач минимизации на множествах вида (2.3.10) условие (5) тесно связано с правилом множителей Лагранжа (подтвержде- ние этим соображениям читатель найдет ниже, в $9). Так как неравенство (5) при х = х, обращается в равенство, то условие (5) можно записать в равносильном виде ш!п(~'(х„), х — х,) = О.
»сх Неравенства вида (5) называются вариацаонныма неравенствами, они по- дробно рассмотрены в [31; 227; 378; 397; 407; 536; 640], 5. Сформулируем и докажем ниже два критерия выпуклости для гладких функций. Т е о р е м а 4. Пусть Х вЂ” выпуклое множество, 7(х) е С'(Х), Тогда для выпуклости функции 7(х) на Х необходимо и достаточно, чтобы (7 (и) — 7'(и), и — и) > 0 сСи, е Е Х (6) Доказательство. Необходимость. Пусть 7(х) выпукла на Х.
Тогда для любых и, е Е Х имеет место неравенство (4). Поменяв в (4) переменные и и и ролями, получим 7" (е) > Т(и) + (|'(и), е — и). Сложив это неравенство с (4), придем к условию (6). Д о с т а т о ч н о с т ь, Пусть для некоторой функции 7" (и) е С'(Х) выпол- нено условие (6). Тогда с помощью формулы конечных приращении (2.6,2) для любых и, и Е Х и а Е [О, 1] имеем а7(и) + (1 — о )7(и) — 7(ои + (1 — а)е) = = а[7(и) — 7(аи + (1 — а)е)]+ (1 — а)[)(и) — У(аи + (1 — а)е)] = = а ~(~'(аи+(1 — а)и+с(и — ои — (1 — а)е)), и — аи — (1-а)и)с!1+ о +(1 — а) ~ (~'(аи+(1 — а)и+»(и — аи — (1 — а )и)), и — ои — (1 — а) е) дг = о 1 = а(1 — а) [(1'(аи + (1 — а)и + |(1 — а)(и — и))— — 7'(аи + (1 — а)и+»а(и — и)), и — и) ссг« или ау(и)+(1 — аЩе) — 7(ои+(1 — а)е) = = а(1 — )]'(Г(х,) — Г(г,), хс — х,)-,с14, (7) о где х, = аи+(1 — а)е+ с(1 — а)(и — е), г» = аи+ (1 — а)е+ са(е — и).
Поскольку г, = 7)и + (1 —,3)и, д = С + а(1 — с) е [О, 1], х, = .уи + (! — 7)и, 7 = а(1 — с) е [О, 1] и множество Х выпукло, то х„х, е Х. Отсюда и из условия (6) имеем (7'(г,) — 7'(х,), х, — г ) > 0 при всех с, 0 < с < 1. Это значит, что правая часть (7) н, следовательно, левая часть (7) нсотрицательна при любом выборе и, е Е Х, а я [0, 1], т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
