И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 67
Текст из файла (страница 67)
Замечание 2'. Если выполняется предположение 2 и если последовательность ((х«, у")) «о, порожденная алгоритмом 2, сходится к точке (х, у), таточка (х, и), гдеи = ((у,)', ..., (у )') удовлетворяет условиям Куна — Таккера для задачи 2. Теорема 2". Пусть выполняются условия: (Ы) — существует оптимальное локальное решение х* исходной задачи 2; (и)— (1, ..., 1) =(1(1,(х )=О, 1=1, ..., т), 1<т; (о!) — функции ~ь 1 = О, 1, ..., т — дважды непрерывно дифференцируемы в открьипой окрестности точки х*; (о[«) — суи[ествует всего лишь единственный вектор множителей Лагранжа иа Е Н~ такой, что пара (х*, иа) — есть точка Куна — Таккера, удовлетворяюи[ач доспиипочным условиям оптимальности второго порядка и х* — РегУлЯРноЯ точка длл ~ь 1 Е (1, ..., 1); (ойй) — выполнены условия строгой дополняющей нежесткости в точке (хе, и'), т.
е. и,:" ) О, если ) (х*) = О. Тогда для достаточно большого конечного числа а сущеспиуют окрестности т'(х') и [[7 (у") точек ха и уе такие, чтпо для любой точки у'~ [5'(у*) существует всего лишь единственная точка х' Е 'т' (х*) (где Р (х*) — замыкание множества У (хе)) такая, что Ч„«Р (хе, уе, а) = О и последовательность ((х", у')(«о сходится к точке (х', у') линейно. Более того, если а стремится к бесконечности, то последовательность (у«)«о сходится к у* сверхлинейно. Библио«рафат«асин указании.
При написании пункта 1 использована работа 12331, пункт 2 основан на результатах работы [5321. В работе [5501 исследуются свойства расширенных латранжианов. 359 5.16. Методы нагруженного функционала В приводимых в этом параграфе методах на й-й итерации требуется искать абсолютный минимум по х нагруженного функционала «]!(х, а») Ь()'»(х) — а»]»+ х' (~! (х))', ! ! где числовая последовательность (а»)»~ строится в алгоритмах таким образом, чтобы обеспечить равенство 1пп а» = ппп1»(х). »-~ю «ЯХ 1. Общий елучай 3 а д а ч а 1. Найти аги ппп 1» (х) для заданной функции «ЕХ г,: В" -!. В' и заданного множества Х(,'х(х)1»(х) =О, ! = 1, ..., т, х~В"), где 1! ! В"-~В', т(п.
В алгоритме 1 на й-й итерации вычисляют точку х» = агя ппп !]!(х, а»), «Япл ф(х, а,) Ь(1,(х) — а,]'+ ~ ((!(х))', где а»-~ппп(»(х) при х-«оо. «ЯХ Предельные точки последовательности (х»)»=о являются решениями задачи 1. Кроме того, на каждой итерации вычисляется отрезок (а —, а+], содержащий значение ппп ~, (х), и длина которого «ех при й . оо стремится к нулю. Алгоритм 1 Н а ч а л о 1. Выбрать произвольное начальное приближение хо 6 Х. 11. Положить а» = ]о (х») П1.
Положить й = 1. 1Ч. Определить функцию ф(х, а) В" Х В'-!-В' по правилу ф(х, а) (!»(х) — а)'+ Д', (!!(х))». Ч. Выбрать константу б,) О (б,— достаточно малая величина) и положить 6 = б,. Основной цикл. Ч1.Вычислить а»=а» ! — б. ,ЧП. Вычислить вектор х", удовлетворяющий условию ф(х», яд) = пп'и »р(х, а»). «яп" ЧП1. Если выполняется неравенство [«р(х», я»)) н(ерз (ерз — «машинный ноль»), то положить о = 26, й = й + 1 и перейти к шагу Ч1; иначе положить а+= а» ! и перейти к шагу 1Х.
1Х. Положить а — = а и перейти к шагу Х. Х. Вычислить значенйя од.ь! и т», и соответственно, по формулам о» ь! = ад + (ф (х», а»)) ', ъдь! = а»+ »р(хд, а»)l ф(хд, ад) — ~ (1«(х»))»~ 1=! Х1. Положить й = й + 1. ХП. Положить сс-= од. ХП1. Если т»( я+, тогда положить я» = тд и перейти к шагу Х1Ч; иначе положить я„= а» и перейти к шагу Х1Ч. Х1Н. Вычислить вектор х», удовлетворяющий условию »р(хд, ад) = пппф(х, а»). «сп" ХЧ.
Если [!Р(х», яд))ч* ~ ерз, то перейти к шагу Х; иначе положить а+ = а„и перейти к шагу ХЧ1. ХЧ1. Если а+ — а — ( ерз, тогда прекратить вычисления (в этом случае находят решение х» задачи !); иначе положить яд = = я — и перейти к шагу Х1Ч. Теорема 1. Если (») — функции /! (х), 1 = О, 1, ..., т — непрерывны в любой замкнутой ограниченной области У пространства В"; (й) — задача 1 имеет решение хч; ерз = О; (111) — «Р (х», ад) = = ппп !р (х, ад) может быть найдено алгоритмами безусловной оп- ««Д" тимизации; (1о) — ф (х", я») ) О эквивалентно 1» (х») ( /с (х*), то алгоритм 1 сходится и предельные точки последовательности [х»)»=л являются решеничми задачи 1.
2. Выпуклый случай 3 а д а ч а 2. Найти аги гпах /» (х) для заданной функции »ех 1» ! В" -!- В' и множества Х, задаваемого соотношением Х/.'!(х[~»(х)(О, 1=1, ..., т, хРВ"). Предположения 2. (1) — функция 1 (х) — вогнута, функции 1» (х),1 1, ..., т — выпуклы в В"; (1») — функции 1! (х), 1 = О, 361 1, ..., т — дважды непрерывно дифференцнруемы в И"; (111) — множество Х ограничено и непусто.
Метод нагруженного функционала в выпуклом случае при определенных условиях сходится к решению задачи 2 со сверхлинейной скоростью. На каждой итерации алгоритма требуется решать (точно) задачу безусловной минимизации нагруженного функционала. Для начала работы алгоритма необходимо иметь оценку сверху для величины шах 1» (х). «ох Алгоритм 2 Н а ч а л о. 1. Найти число а„удовлетворяющее условию а» >1о(х ) где х* — решение задачи 2.
11. Определить функцию «р (х, сс) (нагруженный функционал) по правилу ф(х, а) Ь(шах (О, а — го(х)))о+ ~ (шах (О, 1»(х)))'. !»м 1П. Положить й = 1. О с н о в н о й ц и к л. 1Ч. Вычислить вектор х', удовлетворяющий условию ф(х», а») = ппп ф(х, а»). (зйч) «еип Ч. Если ф (х», и») = О, то прекратить вычисления, иначе перейти к шагу Ч1.
. Ч1. Вычислить и»+! = ໠— ф(х», и») (и» вЂ” !о(х»)) '. Ч11. Положить й = й + 1 и перейти к шагу 1Ч. Теорема 2. Пусть выполняются предположения 2 и существует решение хо задачи 2 таксе, что имеет решение и задача: найти агатах(7~о(хо), х — х'), ($.72) «сг У = (х ) (Ч~! (хо), х — хо) ( О, ! Е (/ ) ~! (хо) = О), х Е В"). Тогда для бесконечной последовательности (а»)» !, порожденной алгоритмом 2, существует константа р такая, апо 1пп а» = = го (хо) и при достаточно больших значениях й выполняется неравенство 0(а»+! — 1' (х')(~(໠— ~о(хо)) и. Теорема 2'. Пусть выполняются предположения 2 и (1о) — существует решение хо задачи 2 такое, что векторы Ч!'! (х'), ! р Е (1) !'! (хо) = О, 1 = 1, ..., т) — линейно независимы; (о) — су- З62 ществует число б > О, для которого т ~ Ч~ 1Р .
х ) у) ( где р(р, «) = 1е (х) — 1 рд~ (х) р = (рм, рв)' ~=1 (Ч)(хе)) р*= 7)е(хе), 1(х) = (~,(х), ..., ~ (х)); (р', 1(хе)) = О, р*) О. Тогда для бесконечной последовательности (хь)Г ь порожденной алгоритмом 2, существует константа т( ~ 0 такая, что при достаточно болыиих я выполняется неравенство ))х" — х*)( т((а„— де(хе)) п))хь ' — х*~, т. е.
последовательность (хе)Г 1 сходшпся к х* сверхлинейно. 3. Првбввжеввав евева В приводимом ниже алгоритме при известной оценке сверху значениЯ шах ге (х) за конечное число итеРаций вычислЯетсЯ пРи- «ЕХ ближенное решение х задачи 2 такое, что в К,(х) — )е(х"))е — ~; (шах (О, 1, (х)))'(е„ 1=! где х* — решение задачи 2; е,— наперед заданная константа. При этом на каждой итерации алгоритма задачу безусловной минимизации нагруженного функционала достаточно решать также приближенно. Алгоритм Я Н а ч а л о. 1. Выбрать произвольное начальное приближение хеЕ х1 . П. Выбрать произвольное число а, (обычно а, в ге (х*), где х* — решение задачи 2). 1П.
Задать произвольные константы е, ) 0 и е, ) О, определяющие точности решения вспомогательной задачи и задачи 2 (рекомендуется з, Е (1О ~, 10 ), е,Е ПО, 10 )). 1Ч. Определить нагруженный функционал ф(х, а)~(шах (О, а — ге(х)))е+ ~(шах (О, );(х)))'. 1=! Ч. Полож~ть к 1.
Ос н о в н о й ц и к л. Ч1. Вычислить вектор х", для которого выполняется неравенство ф(х', а„)(ф(«~ ', ае), (б.73) ЗбЗ а также либо неравенства [[ ч,тР (ха, аз) [[ ( е, (аа — 7е (хз)), т[з (хь, ссз) > е„(5.?4) либо зр(х", аз) ~(еа. (5.75) Ч11. Если выполняются неравенства (5.73) и (5.75), то прекратить вычисления; если (5.73) и (5.74), то перейти к шагу ЧП1. ЧП1. Вычислить аз+! = аь — $(хь, аа)(аз — 7е(хл)) (5.?6) 1Х.
Положить й = й + 1 и перейти к шагу Ч[. Теорема 8. Пусть вьгполняются условия (з), (йз) предположен ия 2 и функции 71 (х), 1 = О, 1, ..., т — непрерывно дифференцируемы. Тогда для произвольного начального приближения хе Е 1т" и любых значений а„е, > О, е, > О алгоритм 8 остановится за конечное число шагов, причем точки х" его остановки, полученные при фиксированных хе, а, )з 1з (хе) и различных е„е„будут при е, -«О, е,— -«О сходиться к множеству решений задачи 2.
Теорема 8'. Пусть выполняются предположения теоремы 8 и, кроме того: (з) — функция 1е (х) — дважды непрерывно дифференцируема; (й) — существует константа р такая, что для любы х, у С лт"' выполняется неравенство дкз ' У1 (зи) — производная д7е (хе)1дх не равна нулю; (зо) — в алгорип!ме 8 неравенства ['5.74) заменены следующими: аз>(о(» ) ! ьг 3 '[Ч,тр(хз, аа))(еггп[п~~', (шах (О, 1г(хз))), г 1 гл Тп! ~(шах (О, 11(ха)))з(аз — 1,(хз))~ ); (5.?7) чр(х", сз ) >е,; (о) — фУнкЦиЯ 1е (х) стРого вогнУпи. Тогда при достаточно малых е, > О и любых х', аз„е, > О, удов- летворяющих условиям (5.77), значение аз+„вычисленное на ша- ге У111 алгоритма 8 по (5.76), будет не меньше, чем )е (х*).
библиографические указания. Пункт 1 написан на основании работы [509[, при написании пункта 2 использовались работы [216, 217, 218). пункт 3 основан иа результатах работы [217[. Дополнительные сведения о методах нагруженного зрункнионала и их вариантах, примеры практического использования методов можно найти в работах [302, 322, 508). 5.17. Методы штрафных оценок 3 а д а ч а О. Найти агу ппп !е (х) для заданной функции еех )е ! В"-!-В' и заданного множества ХЕ~(х!~!(х)=О, 1=1, ...,,в, хЕВ"). Метод штрафных оценок является комбинацией методов штрафных функций и множителей Лагранжа и основан на построении модифицированной функции Лагранжа ф! В" х В х В+ — ~ В'! ф (х, У, а) Ь Ге (х) + 'Я УА (х) + — ~ч.", ~! (х), / ! / ! где а,вО, у=(у„..., у )ЕВ . В методе ведутся итерации как по исходным переменным х, так и по двойственным переменным у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
