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