Ф.П. Васильев - Методы оптимизации (1125241), страница 100
Текст из файла (страница 100)
Таким образом, о ГЕ) Г. д(Л, 1) > 0 при всех Л и Л,. Функция д(Л,Е) палунепрерывна снизу на Л . В самом деле, ь пусть Л Е ЛГ, (Л ) -1 Л, Л ' б ЛГ, й = 1, 2, .. » пусть Го б 1 и д(Л, 1) = (а. Е; Л а.), Тогда Г Г' ЕГ д(Л ',1) =шах(а„Я Л.а ) > (аг, Г; Льа.). Отсюда при й »со получим 1)ш д(ЛЕ,1) > л' ю > (а., Е Л.а.) = д(Л, 1) ЛГЛ бЛГ. Согласно теореме 2.1.1 полунепрерывная снизу функция Г' Е Г д(Л, 1) на компактном множестве ЛГ достигает своей нилкней грани в некоторой точке Л„б Л, причем ГГ»(1) = 1п( д(Л, 1) = д(Л*, 1) >О. Поскольку множество [Е) различных подмножеств Г Лая, 1 множестве (1,..., т), лля которых векторы [аг, ! б 1) линейно независимы, конечно, то д, =)п! д,(1) >0 Отсюда и из (3?), (38) имеем шах д,+(х) > р(х» Х)д(Л, 1(х)) > р(х, Х)д, РП ' 1ЕГ<х или р(х, Х) ((1/д,) гпах д,"(х), хб Е".
Таким образоы, керавенство (Зб) справедливо с 1 «' » г = 1, М = 1/ди Лемма 3 доказана. Г) Л е м м а 4. Пусть множестго Х=(х б Е"! УГ(х)=(аг, х)-Ьг <О, 1=1,...,т; УГ(х)=(а„х)-61=0, !=из-)-1, »г), (40) где а; б Е", 61 б )й непусто. Тогда р(х Х) < М шах д+(х) Чх б Е" М = сант. (41) 1<гя» Доказательство. Каждое ограничение д (х)=(аг, х)-Ь1=0 замеиим равносильными ограничениями Ь),(х) = у(х) (О, Ьзг(х) = — дг(х) < 0 и воспользуемся леммой 3. Получим р(г„Х) < М! шах[д11 (х), .. » д+(х); Ь1~ „1(х),, 511;(х), Ьз+ „1(х),, Ьз~(х)).
ЗЗ7 6 15. МЕТОД ШТРАФНЫХ ФУНКЦИЙ 336 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Заметим, что в общем случае из выполнения условий леммы 5 не следует существование седловой точки функции Лагранжа задачи (1), (8) и, наоборот, существование седловой точки не гарантирует выполнение условий леммы 5.
Это означает, что выделенные в леммах 1, 5 два класса задач (1), (8), имеющих сильно согласованную постановку, взаимно дополняют друг друга. Отметим также, что этими двумя классами не исчерпываются задачи (1), (В) с сильно согласованной постановкой. Поясним это на примере, П р им е р 8. Рассмотрим задачу у(х) = -х" 1и1, х Е Х = (х > О: д(х) = хд < О), (43) где о >О )у >О, Хо=(хеЖ'. х)~0)=Ее.
Ясно, что Х=Х,=(0), 7,=0. Далее, имеем 5=0=- ч-(хд) )д=у(х)-ь(д+(х)) 1д У ехо, так что неравенство (21) выполняется при з = пь = 1, с, = 1, и = а/Д. Следовательно, задача (43) имеет сильно согласованную постановку и к ней применимы теоремы 5, 6. Отметим, что здесь р(х, х)=!х-0(=!х1=(де(х))чд, хех, т.е. условие(36) выполняется с )ьг=1, т=1/Д, далее, при 0< а < 1 функция 7(х) = — х" удовлетворяет условию Гельдера: !хч -д" ( < !х — у1'", х, де Хо, так что в этом случае применима лемма 5. При а > 1 условие Гельдера на Хо — — Еь не выполняется и лемма 5 неприменима.
далее, функция Лагранжа Л (х, Л) = — хо + Л ха, х > О, Л > О, задачи (43) при и = Д имеет седловую тачку (х„= О, Л" =!). Кстати, седловая точка здесь не единственная: любая точка (О, Л'), Л* > 1, также является седловой. Заметим также, что функция г(х)= — х~, х > О, выпукла лишь при 0< а <1, а д(х) = ха, х> О, выпукла лишь при )у >!. Если а ф д, то функция Лагранвга не имеет седловой точки, Таким образом, при а > 1, Д > О, а ~ Д задача (43) не охватывается леммами 1, 5. 7.
Рассмотренный выше метод штрафных функций дает простую и универсальную схему решения задач минимизации на множествах, не совпадающих со всем пространством, и часто применяется на п)тактике. Поскольку имеется достаточно богатый выбор штрафных функции, то при составлении функции Фь(х) можно постараться обеспечить нужную гладкость этой функции, выпуклость, подумать об удобствах вычисления значений функции и требуемых ее производных и т.
п. Кроме того, имеется определенная свобода в выборе множества Х, для задачи (2): в задании множества (8) всегда можно отнести ко множеству Хо наиболее простые ограничения (например, Х, может быть шаром или параллелепипедом в Е*', совпадать с полупространством или со всем пространством Е" и т. д.), а остальные ограничения оформить в виде д,. (х) < 0 или ду(ю) = 0 и учесть их с помощью штрафной функции. Поэтому можно надеяться на то, что вспомогательные задачи (2), (3) удастся сформировать более простыми, более удобными для применения известных и сложных методов минимизации, чем исходная задача (1).
Следует заметить, что хотя сама схема метода штрафных функций довольно проста, но при практическом использовании этого метода для решения конкретных задач минимизации могут встретиться серьезные трудности. Дело в том, что для получения хоуошего приближения решения задачи (1) номер й в (2), (3) (или штрафнои коэффициент Аь в (9)) приходится брать достаточно большим.
А с увеличением номера й свойства функции уэь(х) = у(х)+Р (х), х е Х„оказывается, во многих случаях начинают ухудшаться: эта !~унькция может стать более овражной, некоторые координаты градиента Ф, (х) могут быть слишком большими, могут появиться дополнительные локальные минимумы и т. п. Это все может привести к тому, что при больших й методы минимизации, используемые для решения задачи (2), будут плохо сходиться и определение точки хь удовлетворяющей условиям (6), с возрастанием й может потребовать все большего и большего объема вычислительной работы.
Поэтому при практическом применении метода штрафных функций вспомогательные задачи (2) обычно решают лишь для таких номеров й (возможно больших), для которых удается обеспечить достаточно быстрое убывание функции 7(х) и достаточную близость получаемых точек ко множеству Х при небольшом объеме вычислительной работы. Если полученное на этом пути приближение к решению задачи (1) недостаточно хорошее, то привлекают более тонкие и, вообще говоря, более трудоемкие методы минимизации, стараясь при этом получше использовать ту информацию, которая получена с помощью метода штрафных функций. Заметим, что если выполнены условия теоремы 6, то штрафная функция (9) множества (8) при р = и будет точной и нет необходимости неограниченно увеличивать штрафной коэффициент А„и в этом случае упомянутый недостаток метода штрафных функций, вообще говоря, не будет проявляться.
Правда, штрафная функция (9) при р =- и не всегда будет обладать достаточной гладкостью, но появившиеся в последнее время методы минимизации, не требующие гладкости минимизируемой функции (см., например, 1264; 265; 361; 386; 396; 426; 572; 586; 718; 769; 7771), позволяют надеяться, что численное решение задачи (2) в рассматриваемом случае не будет слишком трудным.
Отметим, что при описании и исследовании метода штрафных функций выше мы предполагали, что функция 7(х) и множество (8) известны точно. Если же указанные исходные данные известны лишь приближенно, то метод штрафных функций полезно регуляризовать — об этом подробнее см. гл. 9, Различные прикладные и теоретические аспекты метода штрафных функций исследованы в 118-20; 84; 85; 151; 218; 222; 250; 266; 286; 294; 295; 302; 319; 343; 374; 377; 379; 471; 562; 603; 613; 670; 720; 721; 738; 759; 774; 785; 7861 Упражнения 1. Применить метод штрафных функций к задачам а) у(и) = х ч-д 1п1; не Х =(и=(х, д) еЕ~; д(и) =-х — в+1 <0) или ие Х =(и= = (х, д) Е Ез; д(и) = — х — д+ 1 = О); б) 1(и)=зу-т1п(; иех=(и=(ху)еь': ха+уз<25) или иех=(и=(хд)ее~: хз 4 дз = 25); в) 7(и) = в~.г у + х~-ч1п1; ив Х =(в= (яд, в) Е о~: в+ д+ в+ 1 <0).
2. Применить метод штрафных функций к задачам из примеров $2.3. 3. Пусть у(х) = е з*, а множество Х = (х е Ь"'. 0 < х <!) задано либо ограничениями д!(х) = -х ~< О, дз(х) = х — ! ~< О, либо д(х) =1х1+(х — Ц вЂ” 1 =0, либо д(х) = е *(!х1+ !ив — Ц вЂ” !) = О. Выяснить, в каких случаях задача 7(х) -~1п1, х е Х, имеет согласованную или сильно согласованную постановку на Ь'', 4.
пусть (Р.(х)) — штрафная функция некоторого множества х. пусть функция ьг(т) определена при т > О, ьэ(0) = О, причем 1о(т) -~0 при 1 -ч О, ьэ(!) ч со при 1 -ч со. Показать, что тогда (ьг(Рь(х))) является штрафной функциеи множества Х, 5. Применить метод (3), (6), (9) к задаче У(х) = хз — х ч 'ш( и х и Х = (х е Ж'. д(х = = х < О), взяв в качестве штрафной функции Р(х) = (шах(0;х))з. Получить точную оценку погрешности, сравнить ее с оценками из теоремы 5.
6. Пусть множество Х задано либо ограничениями д!(х) = х — 1 < О, дз(х) = -х — ! < О, либо д(х) = е * (хз — 1) < О, либо д(х) = хз — 1 < О. Выяснить, какие из этик ограничений явлаатся корректными на 8 или Хо — — (х е Ж ', — 1 < х < 1). 6 15.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
