Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 26
Текст из файла (страница 26)
Тогда в этой точке реализуется строгии локальный минимум функции 7(х) на множестве (1). Если Л (о) Фо (см. замечания 3.1, 3.2) и, кроме того, $ 5. ДОСТАТОЧНЫЕ УСЛОВИЯ ЭКСТРЕМУМА 85 84 Гл. 2. КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА можем считать, что (4Ц вЂ” 4?о, ~ф = 1. С учетом (4) и дифференцируемости функций 1(х), д!(х) в точке х= е имеем 0 > 1(х») — 1(е) = (1'(е), 41») а„+ о(1»), 0 > да(х») — да(е) = (д,'(е), 41») 1 + о(й»), а Е 1(е) П (а; 1 < а < т), 0 = д!(х„) — д!(е) = (д,'(е), 41») й» + о(Ф»), а = т + 1,..., з, й = 1, 2, Разделив эти соотношения на а» > 0 и устремив й — оо, получим (1'(е),аго) <О, (д (е),44о) <О, а Е1(е)ь!Та! 1 < а' < т), (д,.'(е), 4(о) =О, а' = па+1,..., о, )4(о(= 1 Это означает, что 4?о пРинаДлежит конУсУ К,(е) = (е Е К(е), (1'(е), 4?о) < 0) и ь?о ф О.
Если конус К,(е) состоит лишь из точки О, то уже получим противоречие. Пусть К (е)ф(0). Возьмем точку Л = Л(4?о)еЛ(е) )Л(4о)(=1, в которой достигается максимум в (2) при Ь = 4!о. Тогда (Е„„(е, Л(4?о))4?о, !ао) >О. С другой стороны, учитывая (4), неравенства Л! > О, а' =О,..., т, и соотношения д!(е) = 0 !»'а' Е 1(е) П (а: 1 < а < т), да(е) < 0 и Л, = 0 при а «Х 1(е), Л, д,. (е) = О, а = 1,..., «п, д, (е) = О, а = т + 1,..., з, имеем: ~(х» Л(д.)) = Л»Х(х»)+ Е Л;д;(х») < Лоу(ха) ~ Л»У( ) = «=! = Л»1(е) + 2„ Льд (е) = х,(е Л(4(,)) й = 1 2 ь ! Отсюда с помощью формулы Тейлора с учетом равенства х, (е, Л(!?о)) =0 получаем 0 >.С(х,, Л(П",,)) — х(еь Л(41 )) = — а»а(х, (е, Л(4?о))41„41»)+о(1»а), й = 1, 2, Разделив это неравенство на 1»а > 0 и устремив й — оо, будем иметь (х,.(е, Л(!?о))4?о, 4?о) < О, что пРотивоРечит (2) и опРеделению Л(4?о).
Следо- вательно, е — точка строгого локального минимума функции 1(х) на мно- жестве (1), Аналогично доказывается, что если для точки е выполнены условия (3), то е — точка строгого локального максимума функции 1(х) на множест- ве (1). Теорема 1 доказана. П Для иллюстрации теоремы 1 приведем пример. Пример 1. Задача: требуется найтиточки экстремума функции1(х)= )х — х,.(а на шаре Х = (х е Е": (х!а < ц; здесь х„..., х, — заданные ь=! точки из Б".
Эта задача была исследована в примере 4,3 с учетом конкретных особен- ностей задачи. Убедимся, что использование теоремы 1 упрощает анализ точек, подозрительных на экстремум. Поучительно также и то, что в неко- торых точках теорема 1 «не работает» — с ее помощью не удается распо- знать характер экстремума точки. В этой задаче С (х, Л) = 2(Лор + Л,)1„, где 1„ — единичная матрица и х и. Переберем точки, подозрительные на экстремум, в том порядке, как они перечислены в примере 4,3, » 1) точка е, = х = — 2; ха при ~хо~ < 1.
Нам известны соответствующие "4=! е, два набора нормированных множителей Лагранжа: Л,, = (Ло —— 1, Л, = 0) и Л, =(Л = — 1,Л, =0). Набор Л,, =(1,0) принадлежит конусу Л(е,); для него имеем (х, (е„Л,,)Ь, Ь) = 2р(Ь)а > 0 ЧЬ а Ж', Ь ф О, в частно- сти, для УЬ е К(е), (1'(е), Ь) < О. Отсюда следует, что условие (2) вы- полняется. Следовательно, е, — точка строгого локального минимума. А что мы получим, если точку е, аналогично проанализируем, используя набор Л,, = ( — 1,0)? Набор Л,, принадлежит конусу Л (е,); для него (х,„(е„Л ! а)Ь, Ь) = — 2р(Ь)а < 0 «Ь ф О.
В этом случае конус Л (е,) = (Л = = аЛ! „а > 01. Отсюда видно, что условие (3) не будет выполняться на конусе Л (е,). Это означает, что, используя набор Л, „с помощью теоре- мы 1 нам не удалось распознать характер экстремума точки е,. Впрочем, нетрудно проверить, что здесь Л„(е,) = !Э и согласно теореме 4.3 н замеча- нию 4.3 точка е, не может быть точкой локального максимума, 2) еа = ~ ~ при )хо( > 1, Ла —— (Ло — — 1, Л, =р(1Ц вЂ” 1) > 0).
Здесь Л, е Л(еа) Ь~ и (х, (е„Л,)Ь, Ь) =2р/х ЦЬ/а > 0 аГЬ фО. Таким образом, здесь условие (2) выполнено, и е, — точка строгого локального минимума. 3) еа = ~~ при 0 < )хо( < 1, Ло = ( — 1, Л, = р(1 — )хо0 > 0) е Л (еа). Здесь з !„,~ («", (еа, Л,)Ь, Ь) = — 2р(х (~Ь!а <О «УЬРО. Отсюда и из того, что здесь конус Лагранжа Л (ео) = (Л = 1 Ло, й > О), заключаем, что условие (3) не выпол- няется, Таким образом, в точке е теорема 1 «не работает».
В примере 4.3 из других соображений было выяснено, что е не является точкои экстрему- ма. К такому же выводу мы придем, показав, что точка е, не удовлетворяет необходимым условиям второго порядка (теорема 4.3, замечание 4:3). 4) е« = — ~ при )хо) > О, Л 4 — — (Л, = — 1, Л, = р(1+ ) хо!) > 0) Е Л (е4). Здесь ~ а~ .С (е„Л,)Ь, Ь) = 2р)Ь(а > 0 !?Ь ф О, Условие (3) заведомо выполняется. ледовательно, е, — точка строгого локального максимума, 5) при х =0 все точки еа, (еа! = 1, подозрительны на экстремум; им соот- ветствует нормированный множитель Лагранжа Л, = (Л, = — 1, Л, = р > 0).
Здесь Л, ЕЛ (е ) и (4",„(еа, Л,)Ь, Ь) =0 !УЬ Е Я" и «УЛ ЕЛ (е,). Отсюда ясно, что условие (3~ не вйполняется, и пользуясь лишь теоремой 1, мы не мо- жем судить о характере экстремулаа в точках е,. Здесь нам не могут помочь и необходимые условия второго порядка (теорема 4.3, замечание 4.3), кото- рые, как нетрудно проверить, выполняются для всех точек е,.
В примере 4.3 из других соображений было выяснено, что при т„=О все точки единичной сферы ~х) = 1 являются точкой глобального максимума и 1(х) = 1„. При сравнении теорем 1 и 4.3 возникает интересный вопрос, насколь- ко велик «зазор» между необходимыми и достаточными условиями второго порядка? Не вдаваясь в подробности, отметим, что исследования, проведен- ные в 143; 44), показывают, что для широких классов экстремальных задач этот «зазор» является минимально возможным при использовании вариа- ций, имеаощих второй порядок малости.
В заключение этой главы заметим, что с помощью изложенных выше условий экстремума лишь в редких задачах удается найти и проанализиро- вать все точки экстремума. Поэтому может создаться впечатление, что эти 86 Гл. 2. КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА условия имеют лишь теоретическое значение. Однако это не так. Как увидим ниже, многочисленные методы в той или иной степени представляют собой итерационные процессы, подсказанные условиями экстремума и предназначенные для решения систем уравнений и неравенств, составляющих суть этих условий.
Нередко даже беглый теоретический анализ условий оптимальности позволяет получить немало информации о свойствах решений конкретной задачи, которая может быть использована при конструировании и реализации численных методов. Упражнения !. Применить теорему 1 для исследования задач из упражнений к 44 2-4. 2. Пусть точка о принадлежит множеству (1), пусть фуннции д.(х), ! = !,...,з, дважды непрерывно дифференцнруемы в окрестности точки о. Пусть конус А(о) = (Л = (Л!,..., Л,): Л фо, Л! )О,..., Л РО, 2,' Лзд (о)=О)~о и гпак ([ ) Л!д!(о)) Ь, А) >О !уйфо, з=! лез!т), )л1= ! гн= ! Ь е е (о)=(6 е Е" ! (ду(о), Ь) < О, ! е Г(о) и (т; 1 < ъ < и!), (д, (о), ь)=О, !=т + 1,..., з).
Доказать, что тогда о — изолированная точка множества 11), У к а з з н и е: рассмотреть задачу минимизации функции 7"(я)= — )я-о[~ на множестве (1) и применить к ней теорему 1 (см. упражнения 4.7, 4.8). у 6. Вспомогательные предложения Ниже приводятся некоторые формулы и различные другие сведения, ко; торые будут использованы в дальнейшем изложении. 1. Сначала напомним некоторые формулы для конечнь)х приращений ф нкций конечного числа переменных.
Будем пользоваться обозначенияфу ми: С'(Х) — множество всех функций, непрерывно дифференцируемых на множестве Х, С'(Х) — множество всех функций, дважды непрерывно дифференцируемых на множестве Х. Возьмем какую-либо функцию 7(х), определенную на множестве Х с Е", Пусть точки х, х+6 еХ таковы, что 6~0, х+46 ЕХ при всех 1, 0< 2 <1. Тогда можно рассматривать функцию одной переменной 9(т) = 7"(х+ вЬ) при 1 Е ']О, 1]. Оказывается, если 7"(х) Е С'(Х) при р = 1 или р = 2, то д(() Е С [О, 1], причем д'(4) = (7'(х+ й), Ь), да(1)= (у"(х+ 16)6, Ь) О < 2 < 1. (1) В самом деле, если, например, 7" (х) Е С'(Х), то, заменив в формуле (2.5) х на х+ 1)ь, Ь на сьсЬ, получим ~(1+Л2)-~(т)=Л((у (Х+!6), 6)+-,'(Лт)'(ул(Х+ 16) 6, 6>+О([61~ [ ).
Такое разде>кение означает, что д(2) Е С'[О, 1], и указывает на справедли вость формул (1). Для функции одной переменной имеют место формулы д(4) — д(О) = д'(д!1)1 = ) д'(т)с(т = д'(О)! + -дз(дят)2', о д'(в) — д'(0) = дз(дза)1, 0 ~< д!, дя! дз < 4 б. ЕСПОМОГАТЕЛЪНЪ4Е ПРЕДЛОЖЕНИЯ 87 рмулах 2 = 1 и пользуясь равенствами (1), получаем раз- ля конечных приращений ф]нкции многих переменных: ) — У(х) = (У'(х+ д Ь), 6) = ](У'(х+ (1!), 6)сй, (2) о 6) )(х) (у (х) 6> + 2 (з (х + 926)6 6> (3) '(х+ 6) — У'(х), 6) = (Уа(х+ 9,6) Ь., 6), (4) .
Далее, так как , (У'(х + 16)) = уз(х + (6) 6, 0 < 2 < 1, равенство по в на отрезке [О, 1], получаем ! ! — у'(х) = ] уа(х+ 4)!)Ьг(с = (» уа(х+ 16)с(2) 6. (5) о о раз, что в формулах (1) — (5) подразумевается, что точки жат множеству Х вместе с отрезком х + 26, 0 < 2 < 1, ормулы верны на любых выпуклых множествах — мно- содержат вместе с любыми двумя своими точками ы и н оо = !ты + (1 — ст)н, 0 < ст < Ц, соединяющий эти точки клых множествах см. Э 4.1). и и исследовании методов минимизации нам часто при- с функциями, градиент которых удовлетворяет условию е 1. Пусть |(х) Е С'(Х).
Скажем, что градиент г'(х) летворяет условию Липиаица на множестве Х с посто- [7'(х) — 7'(у)[ < ы ~х — у[, х, у Е Х. (6) Полагая в этих фо личные формулы д У(х+ 6 у(х+ (У где 0< д„д„д, <1 8 то, интегрируя это у'(х+ 6) Подчеркнем еще х, х+ 6 принадле В частности, эти ф жествах, которые и отрезок [ы, н] = ( (подробнее о выпу 2.
При описани дется иметь дело Липшица. Определени этой функции удов янной 5 > О, если 'Класс таких функций будем обозначать через С' '(Х). Л е м ма 1. Пусть Х вЂ” выпуклое множество, 7(х) Е С''(Х). Тогда [у(х) — 7'(у) — (У'(у), х — у) [ < Ь [х — у[т/2 (7) при всех х, у Е Х. Доказательство. С помощью формулы (2) имеем ! Г(х) — 7(у) — (Г'(у), х — у) = ((У'(у+ а(х — у)) — Г'(у), х — у)Ю.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
