Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 86
Текст из файла (страница 86)
е. существует такая точка хе Х, что 7, > — оо, Х, ф!21; числа пю е„в (2),(5) таковьз, что е„>0, ~,,/еь <со, 0< 7,(ск„(а, (7) ь=о где а определяется ниже формулой (22). Тогда множество (3) непусто при всех )с > О, последовательность (х„), определяемая методом (5), сходится к некоторой точке и, е Х,. Доказательство. Согласно теореме 4.2.2 Отсюда следует, что если х е Х, то х е Ию так что Х с Игь. По условию Х ф ю, поэтому И'ь ф «З, !с = О, 1,....
Таким образом, при каждом Ь > О, зь )~ 0 существует точка х„„«, УдовлетвоРвющав Условивм (5)! напРимеР, можно взЯть кь э ! — — оь, где оь — точное Решение задачи (4). Применяя теорему 4 3.! к задаче (4) с учетом (5) имеем )хь „! — еь)~/2 <Фь(хь „«)- — Фь(оь) < еь, так что ~к, „, — яь) < )/2еь. 286 Гл. 5, МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЪ|Х 6 7, МЕТОД ЛИНЕАРИЗАЦИИ 287 Сложим оценки (17)-(20); с помощью (16) получим 0 < — |хй — х,] — — ]ей — х ] — лз]ей — хй] ! 1 — лхЬай — Ь]Л*|уай). Выберем ай из условий 2 1— 0<7а< ай < Ь(1+2]Л ] > = (21) (22) Воаьмем произвольную точку х, ц Х,. При сделанных предположениях по теореме 4.9.2 и лемме 4.9.2 найдутся такие числа Л! ) О, , Л* > О, что (/'(х„)+ д,' Л,'д/(х„), ж — х,) >0 Чх6 ХО, (10) а=! Л;дс(ж)=0, «=1,.,оп!, х,цХ,.
(11) Подчеркнем, что в силу замечания, сделанного после формулировки следствия 2 к теореме 4.9.5, числа Лас, .. о Л' а (!0), (11) могут быть выбраны одни и те же для всех х, ц Х,. Далее, из условия (6) и неравенств (8) следует д,.(хй) + (д,'(ж„), Ж вЂ” х„) < д;(ж) < О, а = 1,..о гл. (12) Это значит, что множество (3) также удовлетворяет условию Слейтера, и к задаче (4) также применима теорема 4.9.2, из которой следует, что функция Лагранжа этой задачи Ь |(х, 5)= =2]х хй]'+ай(/(хй) х хй)+ хт: бс(дс(хй)ь(д!'(хй) — хй>) хбХо 6=(5! 6 )6 с=! б Ло — — Е~~, имеет седловУю точкУ (ей, С й ), ей — Решение задачи (4), 5 й'= (5 ! й, ..
о 5 й) 6 Е«. В сйлу леммы 4.9.2 о (ей — жй + ай/ (хс,)+ х, с!ад! (жй), х — е. ) > 0 Ух 6 Хо, (!3) с=! бсй(дс(хй)+(д (хй),ей — хй))=0, а'=!,.,огл, (14) д.(жй)+ (д.а(Х«), Ей — жй) <О, ! =1, от, Ей 6ХО. (15) Возьмем в (10) х = ей, умножим на ай > 0 и сложим с (13) при х = х,. Получим 0 ( (ей — хй, х — ей) + ай (/ (х,) — / (хй), ей — х ) + +ай ~„Л,*(д/(х,),ей — ж )+ Ь' ,Ясй(дс (хй>,х, — ей).
(16) =! а=! Преобразуем и оценим каждое слагаемое в левой части (16). Для первого слагаемого имеем (ей хй х ей)= ]хй х,] ]ей хй] 2]х ей] 1 2 1 2 1 2 (17) Пользуясь неравенством (4.2.20) при и = хй, ю = ей, е = х„ получаем оценку для второго слагаемого ай(/'(х„) — /'(хй), ей — х„) < а«Ь]хй — ей]2/4. (18) Далее из леммы 2.6.1 при /(ж) = дс(х), х = е«, р = хй с учетом неравенств (15) имеем дс(ей) ( ( д; (хй) Ч- (дс'(хй) а ей — жй) + Ь ]жс — ей]2/2 ( Ь]хй — ей]2/2, а = 1, .. о гп. Отсюда для третьего слагаемого из (16) с помощью равенств (1! ), неравенств (8) при ж = ес и Лй > 0 получаем о х ай Ь,' Л; (дс (х„), ес — х ) = ас Л Л,".(д (х,) + (д! (х„), ей — х )) ( <сай , "Л,'.д,.(ей)(ай]Л"]уЬ]жй — ей]2/2, ]Л']! — — Я ]Лт].
(19) а=! *'= ! Наконец, для четвертого слагаемого из (16) с учетом равенств (14), неравенств (8) при х =ж„, включений ха с Х, 5 й ц Еох имеем Е бсй(дс ( й) * ей>= тс.:(бсй(дс(хй)+(д'( «) ' хй» а=! а=! — Рсй(дс(хй)+ (д '(хг,), ей — хй))] < ~, бсу,дс(х ) < О. (20) а=! где уо, у такие малые полохсительные числа, что уо < 2(1 — у)/(Ь(1+ 2|Л*],)), Из (21), (22) тогда имеем ]ей х ]2+7]е«хй]2 <|х х ]2 й О 1 (23) Из неравенств (7),(9),(23) и леммы 2.6.10 следует существование конечных пределоа |нп ]хй — х,] = 1!ш ]ей — ж,], йгп ]хй — е ] = 0 й оо * й ао й- (24) о о (ей-ха+ай/а(жй), ж-ей) > — х ~1!«(дс~(хй)ах-ей>= х, (ссй( — дс(хй) — (дса(хй),х — хй))-1- 45 й(дс(хй) ь(д а(жй), ей-жй))]) ~, ссй(-дс(х>> > буй ппп |дс(ж)], 2=1, .. оп« !<с< а Отсюда и из неравенств (22), ограниченности (хй) и (ей) получаем 0< 6 й ( .
((ес — хй -1-ай/ (хй),Я вЂ” ейи~(сопя!<со, у'= 1,, т 1 а !< <х Таким образом, последовательность (6~) ограничена. Отсюда и из (22) следует ограничен- ность (бй/ай>. Перепишем (!3), (14) в виде х ( й ~+/'( й)+ 2. а! д/(хй) ' — й)>О Ухцхо аг, г (д,.(хй)+(д! (жй),ей — хй))=О, (25) Выбирая при необходимости подпоследовательности из ограниченных последовательностей (жй), (ес>, (5 /а >, можем считать, что эти последовательности сходятся.
С учетом (24) тогда йгп хй — — йш ей— - е„1!ш а =уа,у)0, а=!,..от. й оо й оо * й оо ай Из замкнутости Хо следует, что е, 6 Хо, а из (15) при й -а со получим д, (е„) < О, а' = 1, .. о т. Следовательно, е, б Х, Далее, из (25) при й — асс с учетом (22) имеем (/'(еа) + х тр,. дд(е„), х — е„) ~ )0 У/х ч Хо, ртдс(е,) = О, а' = 1,,, о ал. (26) с=! Как следует из леммы 4.9.2 и теоремы 4.9.2, соотношения (26) означают, что ра аХ„. Вспомним, что неравенство (23) было получено при любых х, 6 Х,. В' частности, (23) верно и при х, = е,. Но е, — предельная точка паследовательностй (жй>. Согласно лемме 2,6.10 тогда (хй) -ае,, Теорема доказана.
ь! 3 а м е ч а н и е 1. Если в (5) зй — — О, то согласно (9) тогда жй „! †- ей, й = О, 1,..о и неравенство (23) можно записать в виде |хй ! — х]2+ у]х,, — хй]2 < ]хй — х]2, й =О, 1, .. о тх, цХ,. Пользуясь произволом в выборе ж, б Х„, отсюда имеем ]хй — е,])|хй ! — е], р(х«,Х)>р(хй „с,Х„), й='0,1, пРичем Равенство здесь возможно лишь пРи хй т ! — — хй — — е, 6 Х,. Таким обРазом, пРи точной реализации описанного метода линеаризации расстояние от точки хс до множества Х, или до точки е, монотонно убывает. В то же время можно отметить, что хотя и (/(хй)) — а /(е„) = /„ но (/(хй)) не обязательно монотонно убывает и не обязательно жй ц Х. Непрерывные и другие различные варианты метода линеариззции описаны и исследованы, например, в [24; 27; 29; 286; 304; 603; 606; 670; 738; 774].
Это значит, что последовательность (жй>, (ей) ограничены. Покажем ограниченность после- довательности (бй > из (!3)-(15). С помощью (12), (14) из (13) при ж = М имеем 289 Упражнении 1. Рассмотрим задачу д !$; (3) Л* Е Ло. (4) (5) 1О Ф.П. Васильев 288 Гл, 8, МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ 1. Доказать, что если в (4) окажетсЯ оа — — хь пРи некотоРом й > О, то точка хь УдовлетвоРиет необходимым условиям оптимальности. У к а з а н и е: применить теорему 4.8.1 к задаче (4), затем принять хь - -оь. 2.
Доказать, что если выполнены условия теоремы 1, зь —— О, й = О, 1,..., и в (4) оь — — хь при некотором Ь ) О, то хь еХ„. Указание: положить в (28), (!8) о =ха и воспользоваться леммой 4.9.2 и теоремой 4.9.2. 3. Рассмотреть метод линеаризации для задачи (!) при Хо = В+, пт = О. 4. Описать метод линеаризации для задачи (!) с дополнительными линейными ограничениями (о;, х) = Ь', ( = т Ч-1,..., в. 9 8. Квадратичное программирование 7(х) = -(Сх, х) + (с, х) ч 1п1, х Е Х, (1) Х = (х Е Е": (а,,х) ( Ь', з' = 1,...,т; (а,, х) = Ь', з' = т + 1,..., а), (2) где С вЂ” симметричная неотрицательно определенная матрица размера и х х тз, т.
е. С > О; с, а. Е Е", Ь' Е )к, з =1,..., а, (возможности т = О, или а = т, или а = тп =() не исключаются). Задачу (1), (2) принято называть задачей квадратичного программирования: в ней квадратичная выпуклая функция минимизируется на многогранном множестве. Такие задачи возникают в различных приложениях.
Задачи определения расстояния от точки до многогранного множества, проектирования на такое множество также представлятот примеры задачи квадратичного программирования, когда в (1) С = 1 — единичная матрица. Задачи вида (1),(2) часто возникают как вспомогательные при описании различных методов минимизации (см., например, $6). Поэтому важно иметь, достаточно простые методы решения задачи квадратичного программирования. Оказывается, для задачи (1), 2), как и для задачи линейного программирования, существуют конечные конечношаговые) методы их решения. Для построения таких методов сначала нужно выявить некоторые специфические особенности этой задачи, В частности, здесь полезно рассмотреть двойственную к (1), (2) задачу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
