Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 90
Текст из файла (страница 90)
Получим (Фй(ий), а(о — ий)))0 или (Фй (и ), и — ий) > О. Таким образом, показано, что при каждом й ) й, ие равенство (48) выполняется при всех и ел с[о. Подставим в (48) явное выра жение для производной Фй (ий); пояучим оси и ([, (49) ГДЕ Р[й = РАй! Е[+ (ий) !Р 1)0 (С =1, ..., И), Рсй РАй! е+(ий)!Р 1 И Х е[йпл[(ий) ([ = и+ 1, ..., г). Рааделим керавеиство (49) иа с о 11[1 1+ ~ р~й ! 1; будем иметь 1 1 < а )село (ий) + 2ьой (ий ио) + ~~ ) [йес (и ), и — и„>0 чси си Уе, й > й, (50) а 1 — 1/з / с 1-1[з ГЛЕК = 1+ ~~~~~ Рсй) >О, )ч =р,„[1+ ~~~~ [сВ„~[ 1=1 с=1 мнтОд штРАФных Функций з Л й)0, ..., Л ))О, й~)й).
Ясно, что ~~~ Лз,=1, так что последова т=о тельность (Ль = (Лчй..., Лы)) ограничепа. Пользуясь теоремой Больцано — Вейерштрасса и выбирая при необхо! й! димости сходящуюся подпоследовательностгч можем считать, что )Л 1»-т -ьЛг =(Ло, ..., Л,), причем Л» >О (! =-О, 1, ..., тп), ~Л»в~ =1, так что не все числа Л, Л, ..., Л, равны нулю. Так как У'(и), у,. (и) непрерывны, Лину-~-ие, то из (50) при й- со придем к неравенству (45). Далее, если у» (иа) = О, то равенства (46) для таких», очевидно, выполняются. Если же у» (и„) (0 при некотором 1, 1 <» < пг, то у»(иь) < 0 при всех й) ~) йь а тогда рлй = О, Лы = О, й ) )с», и, следовательно, Л; = О. Равенства (46) также доказаны.
Замечание 1. Предположим, что наряду с условиями теоремы 8 для задачи (1), (7) справедливо неравенство (21) с параметром «Ъ1, Тогда уое ш16 (и) ( ~ ((и) + ~~~~ с (у+ (и)1(« ~ у (и)+ и!! с (у+ (и)(1« и' »-1 »-1 (и ез По' так что задача (47) также имеет сильно согласованную постановку с теми же параметрами с,, «. Пользуясь оценкой (22) при еь О, р ) «) 1, по лучим »)(р. = р4 (у+ (и ))Р-1( ).)»Р-1)(»Р-«)А-»«-1)(»Р-«) Ц ~р)с)»Р 1РДР «)(со, 1=1,...,з, й=О, 1,, ° ° (51) Выбирая при необходимости подпоследовательпостгч можем считать, что (р»17-ьЛ» (» = 1, ..., г).
Отсюда и из (49) при й-ьос получим неравенство (45) с Ло = 1. Таким образом, гладкие задачи (1), (7) с сильно согла саванной постановкой с параметром «) 1, являются регулярными. Если «) 1, то, как видно пз (51), 1!ш р»а = Л» =0 (» =1, ..., г), и в качест й 1й в * а ве множителей Лагранжа в (45), (46) можно взять Лв — — 1, Л = ... =Л,= О. Это значит, что необходимые условия оптимальности в аадаче (1), (7) совпадают с яеобходимым условием в задаче: ((и) -+1п1, и»м Ус, и ограни чения у»(и) < О, д»(и) = 0 в (1), (7) не играют существенной роли.
Отсюда следует, что класс гладких задач, удовлетворяющих неравенству (21) с параметром «) 1, хотя и не пуст (см. пример 6), но не является слишком содержательным. 9. Отдельно остановимся на случае « = 1. Окааывается, класс выпук. лых задач (1), (7), которые удовлетворяют неравенству (21) с параметром « = 1, является подмножеством задач, у которых функция Лагранжа имеет седловую точку.
Теорем а 9, Пусть Ит — открытое выпуклое множество из Кч, функции У(и), у!(и), ..., у (и) еьтуклы на Ь, у»(и) (а», ир — Ь! (» = т+ 1, ..., г), Уе — выпуклое подмножество ив Ит, пусть в задаче (1), (7) «'е) — со, Речь Ф. Тогда для того, чтобь! в задаче (1), (7) функция Лагранжа имела седловую точку, необходимо и достаточно, чтобы неравенство (21) вььполнялось с показателем « = 1. 332 метпды минжиивлции Функции мнОГих Переменных [Гл, а Доказательство. Необходимость доказана в лемме 1. Докажем достаточность, Пусть выпуклая задача (1), (7) удовлетворяет неравенству (21) с т = 1, пусть ие»и [7е.
Согласно теореме 4.6.1 субдифференциалы дУ(и), дд»(и) непусты при всех и ш Н'. Штрафная функция Ф(и, А)=з (и) + + А ~ч~~ д»+ (и) (А>0) выпукла на И'. Пользуясь правилами 7), 9) суб. » 1 дифференцирования из 3 4.6 и представлением д,+. (и) = ( д» (и) ( шах ((а», и) — Ь'[ 0~ + шах ( — (а[, и) + Ь; 0), [=ш+1, ..., з, имеем дФ (и, А) = дс (и) + ~~~~ Ар дд» (и) + ~~~~~ Ар,.а», (52) »=1 »=»з+1 где 0<р»<1 при [=1, ..., т, причем р»=0 при д»(и) <О, р» 1 при д»(и) >0; — 1<к»<1 при 1= в»+1, ..., з, причем р» = = юлп((а», и) — Ь') при (а», и> — Ь» чь О. Применяя теорему 6 при р = т = 1, А > )с), ааключаем, что Ф(ис, А) = Фе = [п1 Ф(и, А). Тогда по пе теореме 4.6.4 найдется такой субграднент се ш дФ (и, А), что (с„, и — и,»»0 Уи»п Уо (53) Согласно (52) для с справедливо представление с = се !.
~ Арусе, где 1-1 се»н д»(и) с»»н дд» (ие) 0 < р» < 1 прн [ 1, ..., с», причем р» О при д»(ие) <О; с,. =ар — 1<р» ~<1 при [=с»+1, ..., с. Положим Лв =(Х1 ° ° Л,)1 Х» = Ар» (1=1 ..., с), где А фиксировано из условия А > (с(. Далее, заметим, что при сделанных предположениях функция Х(и, Х) =У(и)+ ~ Хге»(и) выпукла по переменной и»=-уу при каждом » 1 Хшйс=(Х = (Х», ..., Х,): Х» >О, ..., Х >0),н, следовательно, дб(и, 3~ А» чь й[ при всех иеи Я', Х»нйс. Нетрудно видеть, что Лс»нйс, сс =се + + ~ Х;с»»н дб (и*, Ле). Тогда из (53) и теоремы 4,6.4 получаем неравен » 1 ство б (ие, Ле) ~ ~Х (и, Хз) для всех и»м [7».
Кроме того, из определения Х» следует, что Л»д»(ие) =0 (1=1, ...,с). Согласно лемме 493 (ие, Ле)— е е седловая точка функции Лагранжа задачи (1), (7). Докааанная теорема 9 дополняет теоремы Куна — Таккера иа 4 4.9. В частности, опираясь на лемму 5 при и = 7 = 1 и теорему 9, можно получить существование седловой точки для некоторых классов выпуклых задач (1), (7) с нерегулярным множеством в смысле определения 4.9.2 (см.
упражнение 9). 10. Рассмотренный выше метод штрафных функций дает простую и универсальную схему решения задач минимизации на множествах, не совпадающих со всем пространством, и часто применяется на практике. Поскольку имеется достаточно богатый выбор штрафных функций, то при составлении функции Ф»(и) можно постараться обеспечить нужную гладкость этой функции, выпуклость, подумать об удобствах вычисления значений функции и требуемых ее производных п т. п. Кроме того, имеется определенная свобода в выборе множества [7» для задачи (2): в аадании мно мктод штулюных Функций жества (7) всегда можно отнести ко множеству Уа наиболее простые ограничения (например, У, может быть шаром или параллелепипедом в Е", совпадать с полупространсгвом или со всем пространством Е" и т. д.), а остальные ограничения оформить в виде у~(и) (О или 83(и) = 0 и учесть их с помощью штрафной функции.
Поэтому можно надеяться на то, что вспомогательные задачи (2), (3) удастся сформировать более простыми, более удобными для применения известных и несложных методов минимивации, чем исходная задача (1). Следует заметить, что хотя сама схема метода штрафных функций довольно проста,но прн практическом использовании этого метода для решения конкретных задач минимизации могут встретиться серьевные трудности.
Дело в том, что для получения хорошего приближения решения эадачи (1) номер й в (2), (3) (или штрафной коэффициент Аь в (8)) приходится брать достаточно большим. А с увеличением номера й свойства функции Фь(и) 1(и) +Рь(и) (и ей У,), оказывается, во многих случаях начинают ухудшаться: эта ~уккция может стать более саранской, некоторые координаты градиента Фь (и) могут быть слипгком большими, могут появиться дополнительные локальные минимумы и т. п. Это все может привести к тому, что прп больших й методы минимизация, вспольэуемые для решения аадачи (2), будут плохо сходиться и определение точки им удовлетворяющей условиям (6), с возрастанием й может потребовать все большего и большего объема вычислительной работы. Поэтому при практическом применении метода штрафных функций вспомогательные аадачи (2) обычно решают лишь для таких номеров й (возможно больших), для которых удается обеспечить достаточно быстрое убывание функции 1(и) и достаточную блиэость получаемых точек ко множеству У при небольшом объеме вычислительной работы.
Если полученное на этом пути приближение к решению эадачи (1) недостаточно хорошее, то привлекают более тонкие и, вообще говоря, более трудоемкие методы минимиэации, стараясь при этом получше испольэовать ту информацию, которая получена с помощью метода пгтрафных функций. Заметим, что если выполнены условия теоремы 6 и в качестве штрафной функции множества (7) берется функция (8) прп р = ч, то нет необходимости неограниченно увеличивать штрафной коэффициент Ам и в атом случае упомянутый недостаток метода штрафных функций, вообще говоря, не будет проявляться.
Правда, штрафная функция (8) при р = т не всегда будет обладать достаточной гладкостью, но появившиеся в последнее время методы минимизации, не требующие гладкости минимизируемой функции (см., например, 4 З.И, 12, 17), поаволяют надеяться, что числепное решение эадачи (2) в рассматриваемом случае не будет слишком трудным. Отметим, что прп описании и исследовании метода штрафных функций выше мы предполагали, что функция 1(и) и множество (7) иэвестны точно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
