И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 66
Текст из файла (страница 66)
Ч. Вычислить вектор Чг!р(ха, уе) = (),(хе), ..., ? (х")). Ч1. Вычислить следующее приближение (х"+', у'+') по правилам <р(хя+', уя) = ппп яр(х, у"); «ЯЯ« у"+' = УЯ+ рЧ„<р(х", УЯ). ЧП. Положить й й+ 1 и перейти к шагу Ч. Для алгоритма 4 имеет место теорема, аналогичная теореме 3. Ь. Метод Ньоиова дда еадач с отраввчеввввв тапа рааевств Предположения 5.
Выполняются все условия предположения 2 и, кроме того, (1х) — функции Р~ (х), 1= О, 1, ..., гд — дважды дифференцируемы в окрестности точки х*, причем вторые производные удовлетворяют условию Липшица. Алгоривьм б Н а ч а л о. 1. Выбрать начальное приближение (х', у') из окрестности точки (хе, уе). П. Определить функцию Лагранжа по (5.6?). 111. Положить й = О. Основной ци кл. 1Ч. Вычислить векторы Ч,ярУ', у') = Ч1,( ')+ ~«УЧЛА' Чг!р(ха, уе) (11(х ), ..., 1 (х")). Ч. Вычиелить а Х н-матрицу Ч <р (х', у") и л х т-матрицу Ч',„<р (х', у") по формулам т Ч',,яР (х", Уа) Ч««?о (ха) + ~; УЯЧ««Г! (х» Ч„я!р (х", уа) = (Ч?т (х"), ..., Ч? (х )).
Ч1. Найти решение (хе+', у'+') следующей системы линейных уравнений. Ч'-Ч(х', у')(х"+'- ")+ Ч', р(хе, у')(у'+' — у') = — Ч.рФ. у')' (Чу«яр(ха, уе))" (Хе+! — хе) = — Чеяр(х«, у«), Ч!1. Положить й = я + 1 н перейти к шагу !'1г, Теорема й. Пусть выполняются предположения б и пусть (ш)— магприг[а А,~ р~„~р (хо, уо) удовлетворяет условию (Ах, х) чь О при 7'„„(хо, уо)х = О, х чя* О. Тогда алгоритм б локально сходится к (хо, уо) с квадратичной скоростью, т.
е. ! ' — *![<[) ()И.)' ° Ь' — у'!<Р.()(О.)', у <1 !хо — хо[[< а, 1уо — у 1< 3. при 1о(х) + Хл 2 ио((г(х)) С=1 по х на всем пространстве В" при достаточно больших значениях ао. Тогда вектор (аагт (хо), ..., ого[ (х')) будет хорошим приближением для уо. Библиографические укааакия. Пункт 1 написан на основании работы [23[1 пункты 2, 3, 4, 5 основаны на результатах работ [293, 296, 298, ЗОО, 45[, 5[]. В работе [5581 исследуется алгоритм Куна — Таккера решения вадачи нелинейного программирования с линейными ограничениями.
5.15. Методы, использутощие модифицированные функции Лагранжа 1. Градиентный метод 3 а д а ч а 1. Найти агя !пах )о (х) для заданной функции лех [о: В" о- В' и заданного множества Х, Х ~Ъ (х [~!(х) ) О, 1 = 1, ..., т[, 355 !2* Замечание б. Наиболее простым для реализации является градиентный метод, однако сходимость в алгоритме 2 носит немонотонный характер, поэтому на практике трудно определить — имеет ли место сходимость при выбранном р, или нет. Алгоритмы квадратичной аппроксимации и двойственный, как правило, сходятся быстрее градиентного метода, однако они более трудоемки с точки зрения вычислений.
Метод Ньютона по трудности вычислений сравним с методами пункта 3 и 4, однако он сходится с квадратичной скоростью и не требует находить шаговый множитель р, обеспечивающий сходимость. Замечание б'. Для начала работы алгоритмов, приведенных в пунктах 2 — 5, необходимо иметь начальное приближение из окрестности точки (х*, уо). В [293) для получения хорошего начального приближения предполагается использовать метод штрафных функций. В начале необходимо найти хорошее приближение х" для х*, минимизируя функцию Предположения '1.
(»1 — функции 1п ! = О, 1, ..., т — дифференцируемые, выпуклые и их производные на любом компакте удовлетворяют условию Липшица; (И) — множество седловых точек 2' = ((х», и')) функции Лагранжа ~р(х, и)»»1,(х)+ $ 1,(х) и, (5.68) /=! — непустое. Приводимый метод основан на построении модифицированного лагранжиана ф (х, и) задачи 1, т. е. функции »р(х, и) Й1»(х) Е (((и! у1((х))+) и»), 7 >О, (6.66) 7 )-1 где Ы+ (и + ( и !)/2, множество седловых точек которого сов- падает а множеством седловых точек классического лагранжиана ~р (х, и). Алгоритм 1 Н а ч а л о. 1.
Выбрать произвольное начальное приближение (х', и»)ЕЛ" ХЛ ° П. Выбрать константу у ~ О. 1П. Положить й = О. 1Ч. Найти произвольное положительное число р„удовлетво. ряюшее неравенству р»(ппп(у, 2 'ЦЧф(х', и»)Гл), где Ч ф (х', й) = (Ч, ф (х', и'), Ч„»р (х', й)), а функция»р. В" )с )( В" -»- И' определяется по (5.69). Оа но в н ой ц и кл.
Ч. Вычислить вектор х'+' к'+ р»Ч„тр(х', и'). Ч1. Вычислить вектор и»+' = и" — р»Ч»»р (х», и»). ЧП. Вычислить градиент Ч»р (х»+', и"+') функции»р в точке (х'+', и'+'). ЧП1. Вычислить значение шагового множителя р»+~ ппп (р„(1 — р»Ц Ч»р (х», и") Ц'), 2 ' Ц Чф (х»+', и»+') Га) (случай аходимости за конечное число итераций, когда ~! Ч»р (х»+', и"+') Ц = О здесь не рассматривается).
1Х. Положить й = л+ 1 и перейти к шагу Ч. Теорема 1, Если выполнены предположения 1, то для алгоритма 1 справедливы следующие утверждения: (И() — существует такой но- мер й что р»+~ = р (1 — р Ц Чф (х», и») ~~), й ~ й;, ((о) — 1пп р» ) О; (о) — последовательность (х», и»)» ь сходится » ао к некоторой точке (хэ, ио) множества седловых точек функции Лагранжа ('б.бд). Теорема 1'. Если выполнены предположения 1 и (о() — г*= (х«, иэ) — некоторая седловая точка функции Лагранжа,' (ой) — функции ~п 1' = О, 1, ..., т, в точке хэ трижды дифференцируемы; (о(й) — в точке (х*, ио) выполняются даст точные условия максимума второго порядка и условия строгой регулярности, то последовательность (х', иь)ь" э, порожденная алгоритмом 1, сходится к точке (хэ, ио) со скоростью геометрической прогрессии.
Условия (ой1) обозначают следующее: 1) оператор Чг цр (хэ, и*) имеет ранг 1, где ~' (х, и) 1з ~, (х) + 1 + 2,' иА (х), а 1 — число такое, что ограничения 7'; (х) ~ О при к=з 1 = 1, ..., 1, активны в точке хо, а при 1 = 1+ 1, ..., т,— пассивны; '2) и1 ) О при 1' = 1, 2, ..., 1; 3) не существует ненулевого вектора й, удовлетворяющего условиям Ч„„~рэ (хэ, иэ)п = О, Ч„,4' (хо, ио) й = О (отметим, что при этих условиях (х*, ио) — единственная седловая точка функции «р на В» х В"). 2. Метод, венольэующвй щтрэфныо фунвцнн эвоновевцвэльного твнэ 3 ада ч а 2. Найти агдппп 7о (х), где «ех Хй(х(~~(х)(О, 1=1, ..., т, х~В"); 1,: В"-» В', 1= О, 1, ..., т,— непрерывные функции. Предположение 2.
(1) — функции 1п 1 = О, 1, ..., т — непрерывно дифференцируемы на В". В методе штрафных функций экспоненциального типа строится последовательность ((х', у')[, которая сходится при соответствующих предположениях линейно к точке (хэ, у'), где х* — решение задачи 2, а и'= ((у~)э, ..., (у )') — множители Лагранжа задачи 2. Алгоритм 2 Н а ч а л о. 1. Выбрать начальное приближение хо С В", числа у; ) 0,1 = 1, ..., т, и коэффициент штрафа а- О такие, чтобы о Ч«ф(хо, у', а) =О (у'=(уп ..., ун)), где экспоненциальная штрафная функция ф ~ В" х В+ Х В~+-» -» В' определяется по формуле н ф(х, у, а) ~7«(х) + (11а) ~, (у,)' [ехр(а~~(х)) — 1); 1 (у=(у ", у )) 357 П.
Положить й = О. Ос н о в н о й ц и к л. 111. Вычислить вектор х"+' так, чтобы Ч,ф(хь+', у', и) = О. (0.70) Если точка хь+', удовлетворяющая (6.70), не единственная, то выбрать из них точку х'+', ближайшую к точке х' по некоторой норме в В". 1Ч. Вычислить вектор у + = (у1+', ..., у~~~) по формуле уь+' = уьехр(а~;(хе+')/2), 1 = 1... т. Ч. Положить й = й+ 1 и перейти к шагу П1. Теорема 2. Пусть выполняется предположение 2 и (11) — функции ~;, 1 = О, 1, ..., т — выпуклые; (!11) — для любых 6,„2',с: (1, ... ..., т), У, Ф О„подзадачи: найти агЯ ппп )ь (х), «ех, Х, Е~ (х) ~~ (х) ( О, 1 Е О„х Е В"), и найти агй ппп 1ь (х), «ел, Х,сь(х)г';(х)(0, )бд„хЕЛ"), имеют оптимальные решения х'* и х'', соответственно, причем ~~ (х") -ь ) (х~ ).
Тогда любая предельная точка (х', у*) последовательности ((хь, у"))ь=ь, порожденной алгоршпмом 2, является парой, состояи!ей из оптимального решения х«задачи 2 и множителей Куна— Таккера (у«)«для задачи 2. Замечание 2. Теорема 2 остается справедливой в том случае, если заменить условие ()и) одним из следующих условий: (111')— последовательность ((хь, у'))ь~ сходится к точке (х«, у*); (ш")— предельная точка х' последовательности (х')~ ь является допустимой точкой для задачи 2, т. е.
7,(х*) ( О, 1 = 1, ..., т. Теорема 2'. Пусть выполняется предположение 2. Тогда для по- следовательности ((х", уь)), „порожденной алгоритмом 2, справедливы следуюи(ие утверждения: 1) для всех 1 Е Я выполняется неравенство В ш 1п1 Р, (х ) ( О, ь где Я ~ (1)!пп !п1 у", = О, 1 = 1, ..., т); ь м 2) если последовательность (Уь)ь ь сходитсн к точке У, то любая предельная точка (х, у) последовательности ((хь, уь))ь ь такова, что Ч,тр(х, и) = О, уД(х) = О, 1 = 1„..., т, где и=((у,)', ..., (у )'), тр(х, и)т'.з[е(х) [- ~; иД(х), и~В+, /=1 3) если последовательность (х«)«о сходится к точке х, то любая предельная точка (х, у) последовательности ((х«, у«Ц «-о, такова, что Ча~р(х, и) =О (и=((у,)', ..., (у )')); уД(х) = О, ~;(х)(О, ) = 1, ..., т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
