Ф.П. Васильев - Методы оптимизации (1125241), страница 81
Текст из файла (страница 81)
Если, кроме того, /(х), д,(х) выпуклы на Е", и выполнено условие Слейтера (4.9.15), то всякая точка х, е Х, для которой задача (?) определяет величину о, = = !п1 ст = О, является решением задачи (1). Доказательство, Необходимость. Пусть х,ЕХ„, По теореме 2.3.2 или 4.8,1 тогда существуют множители Лагранжа Л*,..., Л;„, неотрицательные и не все равные нулю, такие, что Л'/'(х,)+ 2 Л;д,'(х„) =О, Л;дс(х,) =О, ( = 1,..., т. (8) Для определения такого а„сначала можно положить ол =)7о а затем при необходимости дробить эту величину. 4) В тех случаях, когда трудно оценить величину /тс. из (4), приходится довольствоваться нахождением какого-либо стс, > О, обеспечивающего включение х„+со,е„е Х и условие монотонности /(хо+слое„) </(х ).
Для этого обычно выбйрают какую-либо постоянную ст > О, полагают а, = ст и проверяют условие монотонности и принадлежность точки х„о, множеству Х; при необходимости дробят величину ст, = ст, добиваясь вйполнения упомянутых условий. Один шаг метода возможных направлений для задачи (1) в случае о„< 0 описан. Попутно выяснен смысл вспомогательной задачи (2): минимизируя а, мы добиваемся того, чтобы направление е„было как можно ближе к направлению антиградиента (это обеспечивается условием (/'(х„), ел) < о) и в то же время оставалось возможным направлением для множества Х в точке х (это обеспечивается условиями (д,'(х ), ел) < о, ( е 1„), причем, чем меньше с, тем ярче выражены указанные свойства направлейия е„, Кстати, если 1л = О, т.
е. х„Е !и! Х, то е„= — ст/'(хл), ст = ( шах )1.,(хл)!) ' > 0— направление антиградиента. Теперь рассмотрим случай, когда в решении (е„, ол) задачи (2) координата о„= О. Как видно из (2), это может случиться, например, прн /'(хл) =0 или д,.'(хл) =0 для некоторого номера 4 Е 1,. При о =0 уже нельзя гарантировать, что е, будет возможным направлением убывания, В этом случае итерационный йроцесс (2)-(4) прекращается. Оказывается, при ол =0 в точке х, выполняются необходимые условия минимума, выраженные в теореме 4.8.1. Для выпуклой задачи (1) со свойством (4.9.15) условие о, = 0 гарантирует, что х, е Х,.
А именно справедлива Теорема 1. Пусть функции 1(х), дс(х), ( =1,..., т, определены на Ж", 1(х), д,(х) е С'(Х), где множество Х задано условиями (1), и пусть задача (1) имеет решение, т, е. /„> — оо, Х„~в. Тогда для любой точки х, е Х, задача Если ( сА 1„, то из второго равенства (8) следует Л;. =О, поэтому первое равенство (8) можно переписать в виде ЛоГ(х,) + ~ Л;д,,'(х,) =О. (9) лт Возьмем любую точку (е, о) Е Ит„. Тогда ( 1'(х„), е) < о, (д,'(х„), е) < а, ( е 1,. Умножим первое из этих неравенств на Ло > О, остальные — на соответствующие Л,*.
> 0 и сложим. С учетом равенства (9) получим (Ло/ (х ) + Е Л;.д,.'(х ), е) = 0 < ст(Ло + Л; +... + Л' ). от Следовательно, с > 0 Ч(е, о.) е Ит„, и о, =О. До с тат оч ность. Пусть теперь/(х), д,.(х) выпуклы на Х, выполнено условие Слейтера (4.9.15), и пусть для некоторой точки х„е Х задача (7) определяет величину о, =!и! о=О. Покажем, что тогда х, ЕХ,. С этой целью в пространстве Я"+' введем конус К=(г=(е,а)ЕЕ "~'. (1'(х,),е)+( — 1)ст<0, (д,'(х„),е)+(-1)о<0, (Е1,) и вектор д = ( >), Из (7) с учетом !и! а= о„= 0 имеем 10~ (с(, г) = (О, е) + 1 о.
= ст > о, = 0 (10) для всех г =(е, о) е К, для которых ~!ет'! < 1, о' =1,..., п. Однако условие !ет( < 1, у = 1,..., и здесь можно отбросить, и неравенство (10) на самом деле верно для всех г е К. В самом деле, пусть г = (е, о.) е К и !ет~ > 1 для некоторого номера д', 1 < у' < и. Тогда !!е!! = шах !ет) > 1. Положим 1 от'о д=(е> ст), е = е/!!е(), оТ=о/)!е(!. Ясно, что д б Ис„. Следовательно, (с(, г) = (с(, г)/!)е!! = ст = ст/(!е!! > О, так что (с(, г) = ст > О.
Тем самым показано, что неравенство (10) верно для всех г Е К. По теореме Фаркаша 3.5.8 тогда существу!от неотрицательные числа Л;„..., Л„" такие, что или О= — Л'1'(х,) — 2' ,Л;д,'(х,), 1=Л" + 2,' Л,*.. (11) сот, сот Кроме того, из определения множества 1, следует, что дс(х,) = О, поэтому Л,*.д (х )=О, 1 е 1„. Доопределим Л,". =О при всех с(с Х„. В результате с учетом первого равенства (11) получим Ло/'(х,) + ~, Л;,д,.'(х.) = О, Л;.дс(х„) = О, ( = 1,..., т, (12) -1 а из второго равенства (11) следует, что Л = (Ло, Л*„ ..., Л* ) >- О. Покажем, что Л; >О. Если 1, =И, то из (11) сразу имеем Ло =1, Допустим, что 1, ~ (с), но тем не менее Л" = О.
Тогда среди неотрицательных чисел Л,*., Гогда и, аналогично 274 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ з' е 1„найдется хотя бы одно положительное число. Пусть Л; > О, Р е 1,. По условию существует точка х е Х такая, что д,. (ю) < 0 для всех з = 1,... ..., т. Поскольку 1, ~ О, то х ф х„. В силу выпуклости множества Х тогда гххд+ (1 — ст)х, = ю, + сх(х. — ю,) е Х при всех ст, 0 < сх < 1. Это значит, что направление е = ю — х, ф 0 является возможным для множества Х в точке ю„. Из выпуклости функций д!(х) для всех з е 1, имеем 0 > д,.(х) = = дг(х) — дг(ю„) > (д/(ю,), х — х,) = (д/(ю.), е).
Поэтому 2 Л;(д! (ю,), е) < з=! < Л;(дг'(т„), е) < О. Но с другой стороны, из первого равенства (12) при Ло — — 0 получим 2; Л,",(д/(х.), е) = О. Полученное противоречие показывает, '=! что Л' > О. Разделив первое равенство (12) на Л* > 0 и сделав очевидные о и переобозначения, придем к равенству Х'(х„)+ Х Л,".д,.(ю„)=0. Отсюда и из г=! второго равенства (12) с помощью леммы 4.9.2 и теоремы 4.9.1 получим, что ю, е Х,.
Теорема 1 доказана.(З В невыпуклых задачах условие а, =0 не является достаточным для оптимальности точки ю,. Это показывает следующий Пример 1. Пусть /(и) = х+созу, и е Х =(ы =(х, у) е Е'. д(п) = = — к <0). Возьмем точку и, =(0,0). Тогда /'(и,) =(1,0), д'(и„) =( — 1, 0), Иг„= ((е, а) = (е', ех, гг); е' < сг, — е' < а )е!! < 1, )ех~ < 1). Отсюда (е!( < гг при всех (е, гг) е И/. Это значит, что !п! а = и, = О, причем нижняя грань достигается при с,=(0, 1) или е, =(О, — 1), сг, =О. Но здесь м„=(0,0) не является точкой минимума Х(ы) на Х.
Любойытно заметить, что векторы е, = (О, 1) или (О, — 1) в данном случае являются возможными направлениями убывания. 2. Описанный выше вариант метода возможных направлений (2) — '(4) на практике применяют редко. Дело и том, что когда в решении (е„, пь) задачи (2) координата ае < 0 мала по абсолютной величине, направление е„ теоретически являясь возможным направлением убывания в точке хь, практически может обладать указанными свойствами в весьма слабой форме.
Это означает, что либо (д/(ю ), еь) = аь !ыО при некотором з е 1, и направление е почти «касается» мйожества Х, не ведет «вглубь» Х, а величина !дь из (4) может оказаться очень малой, либо (/'(юь), еь) аг окаг О, т. е. вдоль е,. функция /(ю) в точке юь убывает слишком медленно. В результате длина шага сть в (3) может получиться очень малой даже вдали от стационарной точки, й сходимость метода может оказаться очень медленной. Чтобы избежать таких неприятных явлений, можно попытаться варьировать множество номеров 1, в (2) и осуществлять спуск из точки юь только в том случае, когда получаемое из (2) направление еь обладает достаточно ярко выраженными своиствами возможного направления убывания. Опишем один из таких подходов. Пусть то е Х, к > 0 — некоторое начальное приближение.
Допустим, что й-е приближенйе (хь, к„), юь Е Х, к > О, при каком-то й > 0 уже известно. Определим множество йомеров Х„= (з: 1 < з < тп, — кь < д,. (ха) < О) (! 3) и решим вспомогательную задачу (2) при таком 1„. Задача (2) по-прежнему будет задачей линейного программирования и будет обладать хотя бы одним решением (е, оь) с о„=!п! а < О. Имеготся две возможности: Нь , ("., 3 '" 311; 'ь»/ $5.
МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ 275 б) 1) сг, < -еь. В этом случае считаем, что ел является достаточно хорошим возможным направлением убывания в точке юь и полагаем юь ! ! = хь + сгь его 0 < сть < Д„к»+, — — кь, (14) где,З» определяется из (4), а выбор схь может быть осуществлен одним из описанных выше способов. 2) — к, < аь < О. В этом случае считаем, что направление ел не обладает ясно выраженным свойством возможного направления убывания в точке юь, полагаем хь !! =хе, еьт! = е„/2 (15) и снова переходим к рассмотрению задачи (2) с заменой множества 1» на множество Х,, = (з ! 1 < з < тп, /, — еь, = — к,/2 < д,(хь) < 01, надеясь на то, что на более широком множестве (при сужении Хь множество Игь, вообще говоря, расширяется) удастся нанти лучшее возможное направление убывания и т.
д, Описание одной итерации метода возможных направлений для задачи (1) закончено. В методе (2), (13) — (15) имеются параметры к„е„..., удачным выбором которых, вообще говоря, можно улучшить выбор направлений е„ на каждой итерации, ускорить сходимость метода. Кстати, в (15) вместо деления пополам можно принять иной способ дробления ел например, кь .. =0,9сь 3. Следуя 1374), изучим сходимость метода (2), (3), (б), (13)-(15).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
