Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 47
Текст из файла (страница 47)
отсюда при о — +О получим условие (5). Если х, е!и! Х, то для !Уе Е Ь™ найдется гр > 0 такое, что х = х„+ ге Е Х при всех г, [г] < гр. Полагая в (5) х =х,+ге, получим г(Г'(х,), е) >О при всех г, [г[< г„что возможно только при (Г"'(х„), е) = О, Пользуясь произволом в выборе е, здесь можем взять е = у'(х,), что приводит к равенству !'(х,) = О. Замечание 1. Несколько подправив приведенное доказательство необходимости, нетрудно убедиться, что если х, — точка локального минимума Г'(х) на множестве Х, то мы также придем к условию (5). Достаточность.
Пусть функция Г(х) выпукла на Х, пусть для некоторой точки х, е Х выполнено условие (5). Тогда из неравенства (4) при е = х, получим у(х) — у(х,) > (у'(х„), х — х,) > 0 или у(х) 3 у(х„) !ух Е Х. Следовательно, х, Е Х,. Теорема 3 доказана. С! Условие (5) имеет йростой геометрический смысл и означает неотрицательность производной по направлению е = [ ' функции у(х) в точке минимума х. — об этом подробнее см. ниже в п.
8. Если Х = Е", то условие (5) эквивалентно равенству у'(х,) =О. Таким образом, условие (5) является естественным обобщением условия стационарности (2.2.6) для задач на условный экстремум с выпуклым множеством Х. Заметим, что если х„— граничная точка множества Х, то равенство г(х,~ =0 может выполняться, может и не выполняться. Например, если Г(х)=х, Х =(хЕЬ': 1 < х(2), то х„= 1, У'(х,) = 2, и условие (5) в точке х„, конечно, выполняется. Если ту же функцию у(х) = хр рассматривать на отрезке Х = (х Е Ь': 0( х < 2), то х, = О, Г"'(х,) = О, хотя х, = 0 — граничная точка Х.
которое в случае х, Е !и! Х превращается в равенство: Г'(х,) =О. Если, кроме того, функция у'(х) вьтукла на Х, то условие (5) является достаточным для того, чтобы х, 6 Х,. Доказательство. Необходимость. Пусть х„ЕХ,. Тогда при любых х Е Х и а Е [О, 1] с учетом дифференцнруемости функции Г(х) в точке х, имеем 0 < У(х. + о(х — х„)) — Г(х,) = о (у'(х„), х — х„) + о(а) 162 Гл. 4.
ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА Е 2. ВЫПУКЛЫЕ ФУНКЦИИ 163 или (Ул(и)с, с) > 0 (8) « Неравенство (5), как и условие стационарности (2.2.6), вообще говоря, может быть записано в виде системы и уравнений с п неизвестными х, = = (х,',..., х„"). Поясним это на примере. П р и м е р 1. Рассмотрим задачу: 7(х) — !п1, х Е Х = Е,' = [х = (х', х') Е Е Е'.
х' > О, х' > 0), предполагая, что 7(х) дифференцируема на Е,'. Тогда условие (5) равносильно системе уравнений х,'~'., (х,) = О, » = 1, 2. В этом нетрудно убедиться, последовательно анализируя возможности: 1) х, = (О, 0); 2) х, = (х,', х,') > 0; тогда х„Е !и! Е,' и 7'(х„) = 0; 3) х,' = О, х,' > 0; тогда 7;,'(х„) > О, 7;,'(х„) = 0; 4) х,' ) О, х.' = 0; тогда [,,'(х,) = О, 7'„,'(х,) ) О. Если Х = Е„" = (х Е Е": х = (х',..., х") > О), то условие (5) аналогично сводится к системе уравнений х„'7,,(х,) = О, » = 1,..., и. В общем случае для множеств Х с «хорошей» границей неравенство (5) также может быть записано в виде системы уравнений, составленной из условий принадлежности х, границе множества Х и условий равенства ну- лю производных функции 7'(х) по некоторым касательным направлениям к границе в точке х„; правда, получающаяся при этом система может оказать- ся громоздкой и сложной для исследования, Не вдаваясь в детали, заметим, что для некоторых классов задач минимизации на множествах вида (2.3.10) условие (5) тесно связано с правилом множителей Лагранжа (подтвержде- ние этим соображениям читатель найдет ниже, в $9).
Так как неравенство (5) при х = х, обращается в равенство, то условие (5) можно записать в равносильном виде ш!п(7'(х„), х — х,) =-О. Неравенства вида (5) называются вариацаонныма неравенствами, онн по- дробно рассмотрены в [31; 227; 378; 397; 407; 536; 640], 5. Сформулируем и докажем ниже два критерия выпуклости для гладких функций.
Т е о р е м а 4. Пусть Х вЂ” выпуклое множество, 7(х) Е С'(Х). Тогда для выпуклости функции 7(х) на Х необходимо и достаточно, чтобы (7'(и) — У'(и), и — и) > 0 Чи, и Е Х. (6) Доказательство. Необходимость. Пусть 7(х) выпукла на Х. Тогда для любых и, и Е Х имеет место неравенство (4). 1!оменяв в (4) переменные и и и ролями, получим 7"(и) > 7(и) + (Г'(и), и — и). Сложив это неравенство с (4), придем к условя!о (6). Достаточность. Пустьдля некоторой функции 7"(и)еС'(Х) выпол- нено условие (6). Тогда с помощью формулы конечных приращений (2.6.2) для любых и, и е Х и а е [0,1] имеем а7(и) + (1 — а)7'(и) — 7(аи + (1 — а)и) = = о[7(и) — 1(аи+ (1 — а)и)]+ (1 — а)[7(и) — 7(аи + (1 — а)и)] = = а ) (у'(ои+(1 — о)и+с(и — ои — (1 — о)и)), и — ои — (1 — о)и) с1«+ о +(1 — а ) $ (Х'(о и+(1 — а ) и+ ! (и — аи — (1 — о )и) ), и — ои — (1 — а ) и) ~й = о 1 = а(1 — а) !с (7'(аи + (1 — а)и + г(1 — а)(и — и))— — г'(аи + (1 — а)и + со(и — и)), и — и) с!с, ау (и) + (1 — ахи) — у(аи + (1 — а)и) = = а(1 — о)1'(7"'(г,) — Г"'(х,), х, — х,)-,М, (7) о где х, = аи+(1 — а)и+ с(1 — а)(и — и), хз = аи+(1 — о)и+ са(и — и).
Поскольку х, = да+(1 — д)и, д = ! + а(1 — !) Е [О, 1], х, = уи+(! — 7)и, у = о(! — !) Е [О, 1] и множество Х выпукло, то х„х, Е Х. Отсюда и из условия (6) имеем (7'(г, ) — 7"'(х,), х, — ха) > 0 при всех с, О < ! < 1. Это значит, что правая часть (7) и, следовательно, левая часть (7) неотрицательна при любом выборе и, и е Х, а е [О, 1], т. е. 7"(х) выпукла на Х. П Заметим, что для функций одной переменной неравенство (6) равносильно неубыванию производной !'(х).
Это значит, что доказанная теорема 4 является естественным обобщением теоремы 1.8.8 на случай гладких функций многих переменных. Следующий критерий выпуклости обобщает теорему 1.8.9. Т е о р е м а 5. Пусть Х вЂ” выпуклое множество из Е', 7(х) Е С~(Х). Тогда для вьспуклости 7'(х) на Х необходимо и достаточно, чтобы пра всех и Е Х и всех С" = (С ',..., С "), принадлежащих подпространству Е = Е!и Х, параллельному аффинной оболочке множества Х (в частности, если !и! Х ~о, то (8) выполняется при всех С Е Е" ). Доказательство.
Необходимость, Пусть 7(х) выпукла на Х. Пусть аН Х = (и Е Е": Аи = Ь), где А — некоторая матрица размера тп х п, а Ь Е Е" (см. пример 1.5). Тогда подпространство 5, параллельное аН Х, имеет вид 7, = (С Е Е": АС =О). Далее, согласно теореме 1.11 г! Х ф ~о. Возьмем произвольные С Е7, и Ег1Х, Тогда А(и+гС) =Аи+гАС = = Аи = Ь, т. е. и + гд Е аН Х при всех г. По определению 1.10 относительно внутренней точки множества найдется такое число г > О, что и + гс е х при всех г, ]г] < г,. поскольку для гладкой выпуклой функции справедливо неравенство (6), то из него с учетом формулы (2.6А) имеем (у'(и+гб) — Г'(и), с)г=(у«(и+де~)8, с)г'>О, 0< 0 <1, или (7»(и+дгб)С, С) > О для всех г, 0<[в] < гы Отсюда, пользуясь непрерывностью 7«(х), при г -«О получим условие (8) для всех и е и' Х.
Если и е Х 1Н Х, то существует последовательность (и,,) е и' Х, сходящаяся к и. По доказанному (Гл(и»)С, 5) > 0 при всех С Е.5. Отсюда при к — «оо получим неравенства (8) и для точек и Е Х !г!Х. Достаточность. Пусть|(х)ЕС'(Х) н выполнено условие(8). Возьмем произвольные точки и, и Е Х.
Тогда С = и — и Е Е. Пользуясь формулой (2.6.4) и неравенством (8) при с = и — и, получим (7'(и) — 7'(и), и — и) = (7«(и+ 0(и — и))(и — и), и — и) > 0 Чи, и Е Х. Е 2. ВЫПУКЛЫЕ ФУНКЦИИ 165 164 Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА АтАи = АтЬ Х(и) = а,1,(и)+...-1-а Г (и) и Таким образом, для функции 1(х) выполнено условие (6). Из теоремы 4 следует выпуклость 1(х) на Х. П 3 а м е ч а н и е 2.
Следующий пример показывает, что при !и! Х = 0 условие (8) может и не выполняться при каждом 5 Е Е". Пример 2. Пусть 1(и) =х' — у', Х=(и=(х, у) ЕЕ'. у=О~. Ясно, что 1(и) выпукла на Х. Но условие (Х"(и)4, с) = 2(5')' — 2(5') > 0 не выполняется, например, для С =(О, 1). Здесь !и! Х =Ю, а(1Х = Х = 1 . За меча н и е 3. Условие (8] при !и! ХФИ представляет собой условие неотрицательности квадратичнои формы (Г(.К, В = К вЂ” "Р~5'5 ;у=! на Е". Как было отмечено в замечании 2.2.1, для того чтобы (1"(и)5, 5) > > 0 при всех с = (с ',..., 5"), необходимо и достаточно, чтобы все главные миноры матрицы были неотрицательны.
Напомним также, что неотрицательность квадратичной формы (Х" (и)~, с ) равносильна тому, что собственные числа Л,(и),..., Л„(и) матрицы 1"(и) (т. е. решения уравнения бе! ] 1"(и) — ЛЦ =О, 1„— едийичная матрица раз- мера и х п) неотрицательны при всех и Е Х. Пример 3. Определим, при каких а,б,с функция 1(и) = хз+ 2аху+ Ьуз+ схз, и =(х, у, х), будет выпуклой на Е". Здесь !2 а 01! Х"(и)= ~2а 2Ь 0 ~ 0 0 2с Условие неотрицательности всех главных миноров этой матрицы дает иско- мые условия на а, Ь, с: Ь вЂ” а'> О, с >О.
Пример 4. Пусть 1(и) = -(Аи и) — (6, и), и Е Е", (9) где А — симметричная неотрицательно определенная матрица размера и х х п, Ь е Е". В частности, если А = 2Х„ — единичная матрица, 6 = О, то 1(и) = (и, и) = !и!з. Приращение функции (9) нетрудно записать в виде 1(и + Ь) — 1(и) = (Аи — Ь, Ь) + -(АЬ, Ь) (10) при любых и, Ь Е Е".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
