И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 61
Текст из файла (страница 61)
О с и о н и о й ц и к л. 1П. Вычислить матрицу А» — приближение для Ч'„/» (х»). 1Ч. Вычиолить вектор Ь» — приближение для Ч/» (х'). Ч. Вычивлить точку х»+ с Х, для которой выполняется неравенство с »+! (х» — »1 / для всех х Е Х. Вычисление точки х"+ сводится к нахождению приближенного минимума квадратичного функционала (5.56) на множестве Х. Ч1. Положить й = й + 1 и перейти к шагу Ш. Теорема 2. Пусть выполняются предположения 2 и (дй) — лииприца спорых производных Ч /» (х) удовлетворяет условию Липшица с «онстантой у в области Х»= (хЙх — х»)(р, хЕХ); ((о)— (Ч,»/» (х) у, у) ~ т, ( у /(д, т, ~ О.
Тогда: 1) если выполняются условия (о)— то существует точка минимума х* ~ Х, и последовательность (Х)«=е, порожденная алгоритмом 2, такова, что )х« — хе ( ~~ (1х! — хе /!/д) ф (о), где 3. Каааввьютовоаевве методы 3 а д а ч а 3. Найти аги гп!и 1е (х) для заданной функции «ЯХ ге: Н"- Н' и множества ХЙ(х)Ус(х)((0, !'= 1, ..., т, хсН"), где 1!: Н" -«Н', ! = 1, ..., т — заданные функции, Предположения 8. Функции г) (х), ) = О, 1, ..., т — дважды дифференцируемые в Н". На й-й итерации алгоритма требуется вычислять матрицу, близ- кую к матрице вторых производных по х, функции Лагранжа за- дачи 3 (в частности, можно использовать конечно-разностную ап- проксимацию гессиана по х функции Лагранжа). Следующее (/г + + 1)-е приближение (х+', и+') по основным и двойственным переменным задачи 3 находится как решение некоторой вспомога- тельной задачи квадратичного программирования.
Алгоритм 8 Н а ч а л о. 1. Выбрать произвольное начальное приближение (хе и') с В" х Н"' 11. Положить Ф = О. О с н о в н о й ц и к л. 111. Вычислить матрицу 6 (хе, и"), удовлетворяющую условиям теоремы 3. 1ч', Найти точку Куна — Таккера (хь+~, й+), решая сле- дующую задачу квадратичного программирования! найти агдш(п~(Це(х'), х — х")+ — (х — ха, б(х», и")(х — х"))1 « (з.зт) при ограничениях 1!(х")+(7(!(хе), х — хе)(0, !=1, ..., т. Если оешение задачи (5.57) не единственное, то в качестве а.~;1 е-д (х, и + ) выбрать точку, ближайшую к (х", и"). Ч, Положить й = й + 1 и перейти к шагу 111. Теорема8.
Пусть (1) — (х, и) — точка Куна — Танкера, удовлетворяющая достаточным условиям второго порядка для задачи 8 (точка (х, и) из В" х Н удовлетворяет достаточным условиям 325 <р (х, и) = ~,(х) + ~ иА (х), и = (и„ ..., и ), ю-з вычисленная в точке (х, й)), а также условию строгой дополняющей нежесткости и условию ли- нейной независимости градиентов активных ограничений (точка (х, и) удовлетворяет условию строгой дополняющей нежесткости, если и) ) 0 или () (х) ( 0 для) = 1, ..., т); (И) — 1! (х), 1 = О, 1,...
..., т, имеют вторые производные, непрерывные по Липшицу в от- крытой окрестности точки х; (Й1) — матрицы 0 (хо, и') на шаге ((! алгоритма 3 удовлетворяют одному из условий: а) 7"'7(х ио)" ~ 195 ° где 2 7(о(х)+73(х) и ((х) =(11(х), ..., ~ (х)), и,~, (х) г=(х, и), )о(г) = и ~„(х) г'=(хо, ио); б) $0(хо, и') — 7;,ср(хо, ио)!)( —, (6 (хо, ио) — Ч~х5 (х", ио)) (хо+' — хо) ) ~-~ 0 при А — ~ оо 1'+' — У'1 в) (5.58) 0(х», и') = Ч~„ор(х', и'). (5.59) Тогда существуют положительные числа б, и б, такие, что если начальное приближение (х', ио) выбрать из условий 1(хо, ио) — (х, и)1(б; '10(хо ио) Чо, ( о ио))~б 325 второго порядка, если она удовлетворяет условиям Куна — Таккера первого порядка и если Ч'„7 (х, и) у ) 0 для каждого ненулевого у ~ В", удовлетворяющего условиям Ц~(х) у = О, 1 Е (1 ~ и) ) О, 1 = 1, ..., т); 76(х)у(0 ! Е(1! й) — — О, ~)(х) = О, ) Е(1:т)), где Чхх <р (х, и) — матрица вторых производных по х функции Ла- гранжа то последовательность [(х», и"))» з существует и сходится к точке (х, и)1 1) с линейной скоростью сходимости, т.
е. существуют числа г[ Е (О, 1), а ) О, [г,3: 0 такие, ипо ~[(х', и») — (х, и)[)(ар» для всех /г~ й; 2) со сверхлинейной скоростью сходимости, т. е. для каждого сколь угодного малого д 5 (О, 1) существуют а ) 0 и А гз 0 такие, что [[(х», и') — (х, и) ~ (ад» для всех [г в й, при условии, что матрицы 6 (х», и»), й = О, 1, ..., удовлетворяют (5.58); 3) с квадратичной скоростью сходимости, т.
е. существуют числа д Е(0, 1), сг ) О, й э 0 такие, что ~[(х», и») — (х, и)[(ауа» для всех lг ай при условии, что матрицы О (х", и»), й = О, 1, ..., удовлетворяют (5.59). Библиографические уаиания. Пункт 1 написан на основании работ [105, 106, 320, 222[, пункт 2 — на основании работи [2951, а пункта — на основании рабо. ты [4761. Метод Ньютона изучался также в работах [440, 479, 16, 435, 556, 426!. 5.11. Методы линеаривации Методы линеаризации применяются для отыскания решения х' задачи минимизации нелинейной функции 7» (х) при довольно общих ограничениях в виде равенств 71 (х) = О, 1 = 1, ..., т, и неравенств г; (х) ~ ~0,1 = т + 1, ..., т + 1. Решениех* определяется как предел строящейся последовательности хе, х', ..., х», х+, ....
улуч»+! щенное (й + 1)-е приближение х ь' к решению х* определяется с помощью решения значительно более простой вспомогательной аадачи минимизации функции 7е(х)(',Х(Ч1«(х'), х)+ — [[х — х»[~а (5.60) при линейных ограничениях л 1;(х)~~1(х»)+(Ч~г(х")> х — х)~(з»> [~Рь„. (5.61) Вспомогательным множеством йгд, выделяют только те из исходных ограничений, которые желательно удовлетворить на ([г-[-.!)-м приближении х+ (например, те из ограничений, которые «пан»+! более нарушаются» на Ьм приближении х»). Квадратичная добавка 2 [~ х — х [ гарантирует существование решения г (г, 5») » а 327 вспомогательной задачи на непустом допустимом множестве. Улучшенное (й + 1)-е приближение х»+~ вычисляют по формуле х»+' = х" + р, (з (з, 6„) — х"). Различные способы определения шаговых множителей р„и констант з, 6» определяют разные варианты методов линеаризации.
1. Отравив»ива типа иерааевета 3 а д а ч а 1. Найти агд ппп 1, (х) лля заданной функции «ЯХ 1»» УУ -ю- В» и множества Х = (х)1у(х)(0, 1ЕО, хай"), опРеделенного заданными фУнкциЯми 1у ~ Уу" -~ 11', У Е ГУ, Предположения 1. (») — функции 1у, 1Е (0) В гу — непрерыв- но диффереицируемы; (И) — градиенты функций 1н у Е (О) Ц гу удовлетворяют условию Липшица 1Ч1у(х) — Ч1у(у)1(уух — у/!, 1Е(0] () О, у Алгорив»ле 1 Н а ч а л о. 1. Выбрать произвольное приближение х' Е У)а. П.
Выбрать достаточно большую константу а > 0 и констан- ту 6 ) О, удовлетворяющие условиям теоремы 1. П1. Выбрать константу 0 ( з (1. 1Ч. Положить й = О. Овновной цикл. Ч. Положить х=х'. Ч1. Найти множество индексов йе (х) ее (1) 1у (х) ~ шах 1~ (х) — 6, 1Е 6). /еУ ЧП. Найти решение й — й (х) задачи квадратичного программирования~ найти агйппп ((Ч1»(х), й) + — (й)т) при ограничениях (Ч1,(х), й)+1у(х)< О, 1ЕИ»(х). ЧП1. Если й(х) О, то положить х'= х и прекратить вычисления; иначе перейти к шагу 1Х.
1Х. Положить У О. Х. Положить р„= (»1»)'. Х1. Если выполняется неравенство 1, (х + р,й (х)) + а шах (О, 1, (х + р,й (х)К е уе.т ~(1»(х) + а шах (О 1у(х)) — р»з~й(х)1», уев то перейти к шагу Х П; иначе положить 1 = 1+ ! и перейти к ша. гу Х. ХП. Вычислить следующее приближение х~+! * х+ р,й (х). ХП1. Положить й = й + 1 и перейти к шагу Ч. Теорема 1. Если выполнены предположения 1 и существуют кон- станты а ) 0 и 6 ) 0 такие, что ((о) — множество Х = (х(Д„(х) -(-ошах),(х) (1,(х')+ ашахг!(х'), хЕВ"), /ея /е.т ограниченог (о) — задача квадратичного программирования — найти агу ш!и ((~Чю (х), й) + — (й, Ь)) при ограничениях ! (ЧГ!(х), и)+1!(х)кчО, /~Ив(х), разрааима относительно й Е В" при любом х ~ Хч и существу- ют такие множители Лагранжа Х! (х), ! ~ Ог (х), что Х! (х) ~ (а; (о1) — существует такой индекс 1' ~ И, что фуню генг(~! ция Г! (х) ~ О, то бесконечная последовательность (хл)ь ы по- рожденная алгоритмом 1, обладает следующими свойствами: шах(, (х")-~-0 при й-~ оо; (еэ' любая предельная точка х' последовательности (х")ь с принад- лежит множеству Х и в этой точке выполняются необходимые ус- ловия минимума функции гь на множестве Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
