Ф.П. Васильев - Методы оптимизации (1125241), страница 95
Текст из файла (страница 95)
В тех случаях, когда задача минимизации функции (х, Л) по переменной х Е Хо при каждом фиксированном Л Е А решается достаточно просто, можно предложить следующий итерационныи метод: 5(х„„Л)= !и! 5(х, Ль), Ль,=Рл (Л„+алд(х,,)), й =О, 1...
«Х« 4 | 4. МЕТОД МОДИФИЦИРОВАННЫХ ФУНКЦИЙ ЛАГРАНЖА 319 Анализ перечисленных методов показывает, что причина их расходимости заключается в том, что функция Лагранжа (2) по переменной Л не очень хорошо «устроена«. Чтобы преодолеть возникающие здесь трудности, можно попытаться видоизменить функцию Лагранжа, строить так называемые модифицированные функции Лагранжа, которые имеют то же множество седловых точек, что и функция (2), и которые обладают лучшими свойствами, чем функция (2).
Такие функции, оказывается, существуют и могут быть использованы для поиска седловой точки функции (2) и для решения задачи (1). Следуя [24], мы рассмотрим один из возможных здесь подходов, 2. Будем рассматривать задачу ,г(х) — «!п1, хЕХ=(хЕ.Е'. хЕХФ д(х)<0), (6) где 7(х), д(х) = (д,(х),..., д (х)) — заданные функции из С'(Х ). Как и в гл, 3, векторное неравенство д = (д„..., д„) > 0 [д < 0] здесь и ниже означает, что д, > 0 [д,.
< 0] при всех Г = 1,...,т, а неравенство а > Ь для а, Ь Е Е" эквивалентно неравенству а — Ь > О. Наряду с классической функцией Лагранжа задачи (6) Х(х, Л)=Г(х)+(д(х), Л), хЕХю Л ЕЛ =(Л ЕЕ: Л >О) =Е (7) еще рассмотрим следующую модифицированную функцию Лагранжа; М(*, Л) =У(х)+ 2. [(Л+ Ад(х))+]' — 44]Л]' (8) переменных х Е Хм Л Е ЛФ где А — произвольная фиксированная поло>КИ. тельная константа; в (8) принято обозначение а+ =Р (а) =(а+,,..., а"„), а«> =шах(а„'О), « =1,..., т, (9) — проекция точки а Е Е" на положительный ортант Е,"'. Нетрудно видеть, что функция «Р(г) = (шах(лц| 0))' = (х+)' одной перемен-' ной непрерывно дифференцируема на всей числовой оси Е', причем «л«'(г) = 2 шах(г; 0) = 2х+.
Отсюда следует, что при Г" (х), д(х) Е С«(Хо) функция (8) непрерывно дифференцируема по х и Л, причем — = М„(х, Л) = Г'(х) + (д'(х))т(Л + Ад(х))+, эл =Мл(х, Л) = уНЛ+ Ад(х)) — 'Л], хЕ Ха«Л ЕЕ™ где д'(х) — матрица порядка т х и, у которой в «-й строке, у'-м столбце д,(х)= ', Г =1,..., т, у'=1,..., и, а матрица (д«(х))т получена трансдд«(х) понированием д'(х). Далее, пользуясь теоремами 4.2.7, 4.2.8 и следствиями из них, нетрудно показать, что если Х, — выпуклое множество и функции Г(х), д«(х) выпуклы на Х„ то функция М(х, Л) выпукла по переменной х на множестве Х, при любом фиксированном Л Е Е".
Отметим также, хотя это ниже явно йе будет использовано, что М(х, Л) является вогнутой по переменной Л на множестве Л, при любом фиксированном х е Х, — в этом проще всего убедиться, доказав неравенство (Мл(х, Л) — Мл(х,,и), Л вЂ” !л) < 0 для всех Л, |л Е Л и затем обратившись к теореме 4.2.4. ,ес> ! ! сР.П. Ввсввьев 320 Гл.
5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ М1-!ОГИХ ПЕРЕМЕННЫХ Перейдем к описанию метода решения задачи (6), использусощего фунсс цию М(х, Л). В качестве начального приближения возьмем любые точки хо Е Хо, Л Е Л,. ПУсть !с-е пРиближение хь Е Хо, Ль Е Ло Уже известно. Составим ц>ункцию (ср.
с Э б) Фь(х) = 2!х — хь~ + с™(х, Ль) х ю Ло, (11) где сс — некоторое положительное число, являющееся параметром метода. Предположим, что существует точка еьх удовлетворяющая условиям еь Е Хо, Ф„(е„) = 1п1Ф„(х). (12) Ло В качестве следующего ()с + 1)-го приближения возьмем точку х„, такую, что х„, Е Хо, Ф,(хае,) < !п(Фь(х)+бьз/2, )д(хь,) — д(е„)) < бь, (13) ха где бь ) О, !пп бь ж О. В частности, если точка е„из (12) известна, то можно принять х„, = е; в общем случае для определения ть, из условий (13) нужно решать задачу (12) с помощью какого-либо сходящегося метода минимизации.
Дальнейшее изложение не зависит от того, каким методом решается задача (12), поэтому здесь мы можем ограничиться предположением, что имеется какой-либо достаточно эффективный метод решения задачи (12), позволяющий за конечное число итераций найти точку хь которая удовлетворяет условиям (13), После определения х„ , точка Л„„, находится по формуле Ль, = (Л„+ Ад(х„„,))+.
(14) Правила получения ()5+1)-го приближения х„,, ЕХ, Л„, ЕЛ изложены. Описанный метод кратко будем называть методом (13), (14). Для исследования сходимости метода (13),(14) нам понадобятся некоторые свойства функции а', определенной равенствами (9). Из теоремы 4.4.2 следует, что )а+ — Ь" ( <)а — Ь) уа, Ь Ех'". Далее, система соотношений д<0< Л>0, Лсд;=О, >=1,...,т, (16) эквивалентна авенств Р у Л =(Л+ Ад)+ (Гу) при любых постоянных А > 0 В самом деле, если выполняются соотношения (16), то либо д. =О, Л >О, либо Л.
=О, д, <О. В каждом из этих случаев, очевидно, равенство (17) верно. Таким образом, из (16) следует (17). Докажем обратное. Пусть имеет место равенство (17). Распишем это равенство в координатной форме Л; =(Л,. + Ад)е= шах(Лс фАд,;0), > = 1,,т, (17') Отсюда ясно, что Лс > 0 при всех с' = 1,, т, т. е. Л, > О. Если Лс =О, то Лсд; = О и, кроме того, из (17 ) получим 0= (О ь Ад )+ = Л,, ч-Ад>, т. е. д,.
< О. Если же Лс > О, то из (17 ) следует 0 < Л. =(Лс+Ад )+ = Лс+Адс, что возмо>кно лишь при дс =Он Л;дс =О. Эквивалеьстность (16) и (17) доказана. Далее, пользуясь определением (9) функции а+, нетрудно получить, что (а+,а) = (а+, а+), (а+, Ь) < (а+, Ь ") >>а, Ь с Ж". Отсюда имеем (ао Ь+, а — Ь) = (а+, а) + (Ь, Ь) — (а+, Ь) — (Ь+, а) > > (а+, ас ) + (Ь~, Ь+) — (аь, Ь ") — (Ьс, аь) = (а+ — Ь+, а+ — Ь+), т,е, (а — Ь~, а — Ь) > (а+ — Ь+, а+ — Ь+) (13) $ 14.
МЕТОД МОДИФИЦИРОВАННЫХ ФУНКЦИЙ ЛАГРАНЛКА 321 Теорема 1. Пусть Хо — зьтукяое замкнутоемножество изх~ (нааример, Х =Е ), о— функции У(х)> д> х),, д (х) зьспукгьс на Хо и принадлежат классу С'(Хо), й > -оо, Х„ф мЯ, функция ЛагранжаЯ7) имеет хотя бы одну седгоау>о точку(х„, Л") и ХохЛо г смысле неравенств (3). Пусть, кроме того, последовательность (бс) из (!3) яеотрицатеяьна и Ьс < сю. Тогда последовательность ((хь, Ль)), удогяетгорлющая условиям (13), (14), !=о ари г>одом выборе начальных (во, Ло) еХо хЛо и любых фиксированных параметрах а >О, А > 0 суьцестгует и сходится к некоторой седловой точке функции Лагранжа (7).
Доказательство. При сделанных предположениях функция ЛГ(х, Л) выпукла по переменной хе Хо при всех Л е Ло, А > О, поэтому при любых хс е Х, Лс 6 Ло, а > О, А > 0 функция Фь(х), определяемая формулой (11), сильно выпухла на Хо с константой сильной выпуклости х = 1. Отсюда и из теоремы 4.3.1 следует, что точка ес, удовлетворяющая условиям (12), существует и определяется однозначно. Тогда существует и точка хь „>, удовлетворяющая условиям (13): например, в (13) можно взять х е > — — еь. Здесь важно заметить, что многие из описанных выше методов минимизации для задачи (12) сходятся и при любом бь > 0 позволя>от получить точку хь+ > из (13) за конечное число итераций.
Таким образом, прй выполнении условий теоремы последовательность ((хь, Лс)) существует и имеются достаточно эф ективные способы реализации каждой итерации метода (13), (14). аряду с точкой Лье>, определяемой по формуле (14), введем еще точку Рь — (Ль + Ад( ь))-", Ь = О, 1,...
(!9) Покажем, что для любой седловой точки (х„, Л') фуьпсции Лагран>ка (7) справедливо неравен. ство )хь — х,! +А )Ль — Л') В )!еь-х ! +г(рь-Л'( ч.!еь — х>А ч-А с!рь — Ль>!~> у =0,1 .. (20) Согласно лемме 4.9.2 существование седловой точки (х„Л*) в задаче (6) эквивалентно соот. ношениям (>"(х„) -!- (д'(х„)) Л*, х — х,) > 0 Лгх е Хо, (2!) (22) В силу эквивалентности соотношений (16), (17) условия (22) можно переписать в следующей равносильной форме: Л* = (Л'+ Ад(х„))+.
(23) Из (21) с учетом равенства (23) имеем (у'(х„) -!- (д'(х,)) (Л* -!- Ад(х„))+, х — х„) ) О, >ссх е Х . (24) Далее, из условия (12) и теоремы 4.2.3 следует (Фь'(ес), х — е>,) > О, >Ух Е Хо. Отсюда с учетом формулы (10) получим ("ь хь+ а>~(еь)+ а(д (еь)) (Ль+ Ад(еь))ь х ес) ) 0 >ух еХо (25) Примем в (24) х = еьн умнохсим это неравенство на а > 0 и сложим с неравенством (25) при х = х,.
Получим , (с~( ) Г>( ))+ „( >( ))т(Л „1 ( ))е Отсюда имеем — а(д'(х,)) (Л* -1- Ад(х„))", х, — ев) В )О, Ь = О, 1,... (еь — хь, х, — еь) > а(7>(еь) — 7>(х), еь — х ) ч- а ((Ль -ь Ад(еь))+, д (еь )(еь — х ))— — а((Л* т Ад(х,))", д'(х„)(е„— х )), Ь =О, 1,...
(26) Так как функции 7" (х), д,(х) выпуклы, то согласно теореме 4.2.4 (>"(еь) — >"(х,), еь — х,) ) О, д'(еь)(еь — х„) ) д(ес) — д(х„) > д'(х,)(еь — х,). Отсюда и из (26) следует (ес — хь, х„— еь) > а((ЛЬ + Ад(еь))+ — (Л'.1-Ад(х ))+, д(еь) — д(х )) = = А((Ль ЬАд(еь))ь (Л +Ад(хь))~ [(Лс > Ад(ег)) Л>1 (Л +Ад(х)) Л 1) (34) 9 15. Метод штрафных функций 1 1* /(ш) — «1П[; х Е Х (29) жем (30) (зц Ь' = (Ь" + Ад(а,))+ (33) 322 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ К правой части этой оценки применим неравенство (18), С учетом формулы (19), определяю- щей точку Рь, и равенства (23) получим (и«, — х«, х, — и«, ) > Я-((Ль -$- Ад(иь))+ — (Л' -$- Ад(х„))+, [(Ль э А«(и«))+ — Ль[ — [(Л" + Ад(х,))" — Л*[) = ~~(рь — Л*, рь — Ль), ( „—, х, — „) 4 — ($«ь — Л„, Л вЂ” $«ь) > О, й = О, 1,...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
