И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 81
Текст из файла (страница 81)
$3.12), определить, принадлежит ли начало координат многограннику 1,.а (хе), который является выпуклой оболочкой, натянутой на множество векторов н.я Если начало кооРдинат пРинадлежит многогРанникУ Ь,а (хе), то положить х,„= »" и прекратить вычисления; иначе перейти к шагу ЧП. ЧП. Используя алгоритм 1" (см. 5 3.12), вычислить точку г~а— ближайшую к началу координат точку многогранника Ьсв (»е). Положить бсв ( гса 1 ЧП1. Вычислить вектор й,в (хе) — направление (е, н)-наискорейшего спуска функции шах ф, (х) в точке хе по формуле ~6У пса (» ) — (1Яеа) гса.
1Х. Вычислить шаговый множитель р», удовлетворяющий уоловиям шах ф, (х" + рй,„(х')) = ппп шах ф, (х'+ рй,„(х»)); (ат' Рдс ~ау х»+ р»йсл(х») Е Х. Х. Вычислить следующее приближение х"+' = х» + р»1»с„(х»). Х1. Положить й = й + 1 и перейти к шагу 1Ч. Теорема Я. Если выполнены все условия теоремы 2, то любая предельная точка бесконечной последовательности (х")».=о, порожденной алгоритмом д, является (е, р)-квазистационарной точкой функции шах ф, (х) на множестве Х.
е~ (Точка х,а р Х называется (е, р)-квазистационарной точкой функции гпах ф, (х) на множестве Х, если О Е Еед (хсд)). ~ея 4. Модпфппеппл второго метода последовательных прпблпжеапа Алгоритм 3 для нахождения (е, р)-квазистационарных точек используется в приводимом ниже алгоритме для отыскания стационарных точек функции гпах ф, (х) на множестве Х. ест Алгоритм 4 Н а ч а л о. 1. Выбрать начальное приближение хе Р Х. П.
Выбрать константы е, > О, р, > О, а, > О. П1. Положить в = О. О с н о в н о й ц и к л. 1Ч. Найти множества индексов чье (х') = (!! п1ах фс (х*) = фс (х') 1 Е о ); 'Е.т Яе(х') = Ц)/,(х*) = О, )ЕИ,). Ч. Вычислить множество векторов Н (х') = Н (х') () Нс(х'), где множества Не (х') = ( Чф, (х'), ! р 'в1 е (х')); Но(х*) = (%7!(х'), )ЕЯ»(х')). Ч1. Используя алгоритм 1' (см. 5 3.12), определить, принадлежит ли начало координат многограннику Еее (х'), который является выпуклой оболочкой, натянутой на множество векторов Йее (х'). Если начало координат принадлежит многограннику 443 ьое (х'), то положить хе= х' и прекратить вычисления; иначе перейти к шагу ЧП. Ч11. Используя алгоритм 3, в котором положить 3 и = 1ь„е = е„хо = х, найти первый индекс й, при котором выполняется неравенство 6„"„( а, и положить х'+' = х".
ЧП1. Положить в,», = е,/2, р,» ~ —— 14,12, а,»1 = а,/2. 1Х. Положить в = е+ 1 и перейти к шагу 1Ч. Теорема 4. Если выполнены все условия теоремы 2, то любая предельная точка бесконечной последовательности (х')„о, порожденной алгоритмом 4, являетея стационарной точкой функции шах и, (х) на множестве Х. гаУ Библиографические у«о«авил. При написание параграфе пспольеоввлпсь рабаты 1254, 127, 428, 480, 481, 5291. 6.2.
Обобшенный беснараметрнческий метод внешней точки решения дискретных минимаксных задач 3 ада ч а О. Найти агбгпш гпах); (х), где «ех 021ь 1 х~(х!йг(х)(0, )Е21, 11,(х) =О, 1ЕЕ, хЕВ"); йг . 'В" -«- В', 1 Е Р, Ь1 . В" -«11', 1Е ~; Р и Ь вЂ” конечные множества индексов. Предположения О. (1) — функции ~, (х), 1 = 1, ...„т, дг (х), 1 Е ЕГ«, Ь, (х), 1ŠŠ— непрерывно дифференцируемые в Н"; (11)— еуществует решение х' минимаксной задачи О. Обозначим 1е(х) шах 11(х); У(х) - (11й,(х) )О, ! ЕП). еенео1 1. Ооковвоа алгоритм На и-й итерации алгоритма вычисляется точка х" безусловного минимума некоторой вспомогательной функции и оценка снизу а, для значения Ге (х') такие, что 1 (х') 1.( ') аь -«1о (хе) пРи й -«оо; аь+~ ~аь, й = О, 1, ...; Цо(х*) «а„й = О, 1, ....
Для начала работы алгоритма необходима нижняя оценка ао значения 1о (х'). 444 Алгоритм 1 Н а чало. 1. Выбрать константу а»(~ь(х*) (т. е. нижнюю оценку а, оптимального значения 1» (х*) задачи О). И. Задать произвольные веса шп 1 ~ О и оь 1Е Е. 111. Для фиксированного числа а определить функцию ф(х, а) = ~„"[~,(х) — а]'+ ~ иь(у~(х))»+ ~ о,(Ь,(х))', !Яя (и !ау(о се» где Я(х) = [1[[,(х))а, 1=1, ..., т). 1Ч. Положить й = О. О с н о в н о й ц н к л. Ч. Найти точку х», удовлетворяющую условию ф(х», а») пип ф(х, а„), *ел" т.
е, решить задачу безусловной минимизации дифференцируемой по х функции ф (х, а»). Ч1. Вычислить а»чл = а» + [ф (х», а„)1т] ~'. (6.1) Ч11. Положить я = й + 1 н перейти к шагу Ч. Творе а 1. Пусть выполняются предположения О и пусть: (111)— 1» (х (и)) — непрерывная функция аргумента и в точке и = О, где х (и) является решением следующей задачи: найти агнппп шах ~,(х) т ~кима при ограничениях д~(х) < ир Ь, (х) = и,, 1Е 1., здесь ир 1' Е Р, иь 1 Е 1.
— компоненты вектоРа и. Тогда алгоритм 1 порождает последовательности (х»]ь.~, [а»)Г ~ такие, что а, ~, (х') при й 1 (х»)-».1 (хч) при й-» оо; ф(х», а»)-ч-0 при й-».оо. 2. Уекорьвимй варваит алгоритма В ускоренном варианте алгоритма на некоторых итерациях вычисление величины а»+~ проводится не по (6.1), а по формуле а„', = а' + ф(х", а„)1 ~ Ц,(х») — а'), <ЯЯ(х») при этом справедливо неравенство а»+, ~ а»+,, что обеспечивает ускорение сходимости (а»)» ~ к 1» (хч) по крайней мере прл а» близких к 1» (х'). 44~5 Алгоритм 2 Н а ч а л о.
1 — Ш. Шаги 1 — П1 такие, как н в алгоритме 1. 1Ч. Выбрать верхнюю оценку аа оптимального значения 1а (х') задачи О. Ч. Выбрать константу е~ ) О, характеризующую точность вычнслення га (х*), константу е, характеризующую близость значеннй функции ат (х, а) к нулю.
Ч1. Положить т, = а,. ЧП. Положить й = 1. Основ но й цн кл. Ч1П. Найти точку х', удовлетворяющую условию <р(ха, т,) = пп[п <р(х, т„). «аи" !Х. Вычислить значения 1, н 1„соответственно гг = та + [ф (ха, таУ т) 0; 1« = та+ (Р(ха, та)l ~; ((е(ха) — т,). ее рс олч Х. Если 1,( а„то положить та»1 = 1« н перейти к шагу Х1; иначе положйть та»~ = гт н перейти к шагу Х1. Х1. Положить т, = та»1 — та; аа = 1,; з = <р (ха, т„). ХП.
Положить й = й + 1 н перейти к шагу ХП1. ХП1. Найти точку ха, удовлетворяющую условию <р(ха, та) = пи!в <р(х, т„). «яи Х[Ч. Если а, — аа( егнлн т,( еь то прекратить вычисления (в этом случае находят прнблнженное значение для [а(х*), которое можно вычислить, например, по правилу /а (х«) ы (а,+ аа)/2); иначе перейти к шагу ХЧ. ХЧ. Если «Р (ха, та) ) О, то пеРейти к шагУ 1Х; если е( еа, то прекратить вычисления (в этом случае также находят прнблнженное значение для 1а (х«)); иначе положить а„= тан е = О, т„= = а, н перейти к шагу ХП1.
Замечание 2. Алгоритм 2 основан на том, что неравенство т ~ ~ 1а (х«) справедлива тогда н только тогда, когда [п1 ~р (х, т) = 0 «ран Библиографические ркоаинин. Параграф основан на рабате [4601. 6.3. Метод второго порядка решении задач дискретного минимакса 3 а д а ч а 1.
Найти агд пип шах ерс (х) для заданных функцнй «ех чая грс: 11" — ~ Ит, 1 Е Я н заданного множества Х = (х[1;(х)(0, [сй, хе«1"), где Я, й — конечные множества индексов. 440 Предположение /. (1) — функции <р, (х), 1 с '/1 и /, (х), / с Р— дважды непрерывно дифференцируемые в В". В приводимом методе используется квадратичная аппроксимация ~р; (х), /; (х) соответственно, функций ~р, (х), // (х) в точке х = = х", что приводит к сверхлинейной скорости сходимости с показателем, равным '/,. На каждой итерации алгоритма требуется решать (точно) некоторую вспомогательную минимаксную задачу. Алгоригем 1 Н а ч а л о.
1. Выбрать начальное приближение хг, принадлежащее достаточно малой окрестности множества Х. П. Выбрать произвольные константы 0 ( е ( 1, 6 ) О, р ) С (обычно е = гlм 6 Е 110 ~, 10 '1, Р Е 1!0-', 10 '1). П1. Выбрать достаточно большую константу а ) О. 1Ч. Положить lг = О. О с н о в н о й ц и к л. Ч. Вычислитыр, (х").
/; (х"), ЧЧ, (ха), Ч~~ (х"), Ч„„~р, (х~), Ч~,/, (х~) при всех 1Е К, / Е г/. Ч1. Вычислить множества индексов Х, - (1) ~р, (х"),в шах ч4 (х') — 6, 1~ Ж); ~зя О„= Ц)),(х")~шах/,(х") — р, /ЕО). %~ ЧП. Определить функции ~р~ (х),/у (х), (с Ж, / ~ О, соответственно <р,'(х) = <р,(х") + (Чй (х"), х — х') + — Ч,„ф,(х')(х — х')', /,".(Х) /',(х") + (Ч/,(х'), х — х') + ~ Ч',д/у(х')(х — х')'. Ч1П. Найти решение х" следующей вспомогательной задачи выпуклого программирования: найти агиш1п шах ~р",(х), «ах~, ~ея~ где множество Х, = (х(/,'(х)(0, /~О„, хЕН"). 1Х. Положить й" = х" — хь.
Если 1/г" ! = О, то прекратить вычисления (в атом случае х" — решение задачи 1); иначе перейти к шагу Х. Х. Положить р = 1. Х!. Определить функции ф(х) = гпах~р,(х); д(х) = шах (О, шах//(х)). 'ея КЯ ХП. Если выполняется неравенство »[г (х» + рй ) + ад (х' + р(г») ( $ (х») + си) (х») + + ер [шах гр," (х») — »]г (х») — ад (х»)], 8УГ, ' то положитьр, = р и перейти к шагу Х1Ч; иначе перейти к шагу Х П1.
Х1П. Положить р = р/2 и перейти к шагу ХП. Х!Ч. Вычислить следующее приближение х»+' = х» + р»й», положить й = й + 1 и перейти к шагу Н. Теорема 1. Пусть выполняется предположение 1 и, кроме того: (и) — для любых х, у Р Л", 1 Р Х, 1 Е сг, справедливо у,)х)]»((Ч„'„~р,(у)х, х)(у,)[х]', уг][хЦ'~(Ч'4(у)х, х)(у»йхИ', у,>у,)О; 1111) — для задачи 1 и вспомогательных задач (б.2] вьаюлняется условие Слейтера; (Ь) — множители Лагранжа ]Зг (х»), 1 Е О», вспомогательньгх задач (б.2), соотвегпствуюгцие ограничениям 1; (х) ( О, равномерно ограничены: рг (х») ( оц»ух» Е У,„~ (х] гпах ~р, (х) + ге.т» геЯ + а гпах (О, шах 1; (х) ) ( шах ег, (х') + !а.т гнус +ашах(О, шах1 (х»)), хСВ").
!6Я Тогда для последовательности (х»)» о, порожденной алгорит- мом 1, справедливы утверждения: 1) !пп х» = х"; » са 2) если матрица Ч'„гр, (х), Ч~„1, (х) при 1ЕЖ*Ь(г]гр,(х*) =шах~рг(х'), 1ЕЯ], гаХ 1'Еог'1»(1[Гг(х ) =шах1 (х»), 1ЕО] lср непрерывны в окрестности точки х", то начиная с некоторой ите- рации р» 1; ]пи ! 6» ] I ! Ь»-г ]] = О; »-~а 3) если, кроме пюго, матрицы Ч„гй (х), Ч„)г (х) при 1Е Я~, 1~ О*, удовлетворяют условию Липшица, то при я-» ао )]й» ([~ ( ч ][1»» г []Н где чг) Π— постоянная величина. Замечание 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
