И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 34
Текст из файла (страница 34)
1Х. Если е = О, то перейти к шагу Х; иначе перейти к шагу Х1. Х. Используя алгоритм 1', определить, принадлежит ли начало координат многограннику Ьо(ха). Если начало координат «69 принадлежит 1„(х»), то положить х'= х" и прекратить вычисления; иначе перейти к шагу Х1. Х1. Используя алгоритм 1", найти точку г„которая является ближайшей к началу координат точкой многогранника Е, (х"). ХП. Вычислить ф, (х») по формуле ф, (х") = — )г, ~. Х!11.
Если выполняется неравенство»(ь (х») ( — е (а»7еь), то перейти к шагу Х1Ч; иначе положить е!+1 — — е,/2~~', ! = ! + 1 и перейти к шагу Ч1. Х1Ч. Вычислить вектор !»~ (е) — направление е-наискорейшего спуска функции шах <р, (х) в точке х» по формуле !» (е) = %.У ° (1! 1 ге 1) гв ХЧ. Вычислить шаговый множитель р из условия шахор,(х" + р п»(е)) = ппп гпах ~р,(х»+ р!»»(в)).
сев Рмь сеу ХЧ1. Вычислить следующее приближение х»+' = х»+ р»й»(е). ХЧП. Положить й = й + 1 и перейти к шагу 1Ч. Теорема 1. Если выполнено предположение 0 и начальное приближение хь в алгоритме ! таково, что множество Х, ~1 (х (шах <р, (х) ( шах ~р, (х'), х 6 В"), мяу 1я ч ограничено, то любая предельная точка бесконечной последовательности (х»)Г ~, порожденной алгоритмом 1, является спюционарной точкой функции шах <р, (х). Ж.т (Точка х'~ 11", для которой выполняется неравенство » де;(х') 1п1 шах ~ дх ' Д),~~ О, Ь=~ сЕЯйк ) называется стационарной точкой функции шах у,.
(х) на Н". Если Жу функция шах у, (х) выпукла,то стационарная точка хь является КЯ точкой минимума). Замечание !. Чтобы на й-й итерации уменьшить количество сравнений ф, (х») с — е (а»!е») в [1271, рекомендуется начинать сравнение не с е = е„а со значения з, полученного на предыдущей (й — 1)-й итерации, т. е. при таком е, которое получается при выходе из цикла, образованного шагами Ч1 — ХП1 на (й — 1)-й итерации. Алгории»м 1' (алгоритм определения принадлежности начала координат многограннику Ь,(м»), который является выпуклой оболочкой множества векторов (Ч~р,(х"), ! Е Я,(х»))).
!70 1. Вычислить величину 1 — количество элементов множества Ж, (х"), П. Вычислить о, — наименьший элемент множества Яо (хо). П1. Положить ! = 1. 1Ч. Положить и = О. Ч, Вычислить индекс ! = !о+ и. 71. Если индекс ! принадлежит множеству Жо (хо), то положить у! = 7 !р, (хо) и перейти к шагу ЧП; иначе положить и = и + 1 и перейти к шагу Ч. ЧП. Если 1(1, то положить 1 =1+ 1 и перейти к шагу 1Ч; иначе перейти к шагу ЧП1.
Ч1П. Решить задачу линейного программирования в (1+ 1)- мерном пространстве векторов (у„у,, ..., у„а): найти ага пипа при условиях ~,у!д'! — а(0, о=1, 2, ..., и; 1=! ! — ~~ у!у!' — а(0, з= 1, 2, ..., и! ! ! ~ у! — — 1; у! В О, 1 = 1, ..., 1; а в О. у=! Обозначить через (у!, уо, ..., уп ао) решение этой задачи. о о о 1Х. Если а' = О, то начало координат принадлежит многограннику Е, (хо), если ао ~ О, то начало координат не принадлежит многограннику 1.,(хо). Алгориим 1" (алгоритм вычисления ближайшей к началу координат точки многогранника Ь,(!х!), который является выпуклой оболочкой множества векторов ог = (Чф! (хо), ! с Жо (х"Ц). 1.
В качестве начального приближения уо выбрать произвольную точку многогранника 1., (хо) (в частности, в качестве у' можно взять вектор Чфч (хо), для которого (7<ро,(х"), Чф!,(хо)) = ш)п (7ор,(хо), Ч<р,(х")), !еяе!" ! или вектор, равный 2", у~у~, где (уо!, у~о, ..., уо!) — вектор, получен!=! ный при решении задачи линейного программирования на шаге ЧП1 алгоритма 1', а вектора у!', 1 = 1, ..., 1, определяются шагами 1 — ЧП алгоритма 1').
П. Положить и = О. П1. Найти точку у множества Я, для которой (у'", у'") = и!п (Чф,(хо) у"). серго(ко! 1Ч. Если (у — у, у") = О, то положить г,= у и прекратить вычисления; иначе перейти к шагу Ч. Ч. Найти параметр т р (О, 11, удовлетворяющий условию $у + т (ум — у )) = пйп) ум+1(у — у )~. оие,п Ч1. Вычислить следующее приближение у+'=у" + (у" — у ). ЧП. Положить т = т + 1 и перейти к шагу 1П. Теорема 1'.
Если выполнены предположения теоремы 1, то бесконечг/ая последовательность (у )7 м порожденная алгоритмом !", сходится к ближайигей к началу координат точке г, многогранника Е, (х»). 2. Модвфпвадпл первого метода поеледовательвыл првблпл»евпя Алгоритм 2 Все шаги алгоритма 1, за исключением шага ХЧ, остаются без изменений. Шаг ХЧ записать в виде: ХЧ. Используя алгоритм 2', вычислить шаговый множитель р„, удовлетворяющий условию (шах ф, (х») — гпах ф, (х» + р,й" (е)))/(шах ф, (х')— сну 1 ау ~з.т — ш(п шахф,(х" + р/т»(е)))~~, (3.
П) о>о го о Где () Е (О, 1) — произвольный параметр, фиксированный для всех значений й. Алгоритм 2' (алгоритм вычисления за конечное число итераций шагового множителя р„, удовлетворяющего условию (3.11)) 1. Выбрать произвольный параметр р Е (О, 1) и константу ба) О. П. Вычислить )» = ()/5 — 1)/2. П1, Определить функцию /»; В' -ь 1Р по правилу /» (1) = гпах ф, (х» + П» (е)).
(ЗА2) ~з.т 1Ч. Вычислить значения /» (6,) и /» (0). Если /» (6») (/» (0), то перейти к шагу Ч; иначе перейти к шагу Х. Ч. Положить з = 1. ., Ч1. Вычислить 6, = 6 |р. ЧП. Если 1» (6,) ~/» (6 1), то перейти к шагу 1Х; иначе перейти к шагу ЧП1; ЧП1. Положить з = з+ 1 и перейти к шагу Ч1. 1Х. Положить 6~»п О, 6~~»~ = 6, ь 6~»и = 6, и перейти к шагу ХЧ. Х.
Положить з = 1. Х1. Вычислить Ь, = Ь, (1(». ХП. Если 1» (6,) (~» (0), то перейти к шагу Х1Ч", иначе перейти к шагу ХП1. ХП1, Положить в = в + 1 и перейти к шагу Х1. Х1Ч. Положить Ьь') = О, бьо) = 6„6~»~> = б ХЧ. Положить 1 = О. ХЧ1.
Найти множество индексов К ~ О Ж ~ (! ~ шах <р, (х» + 6<<2>1>» (а)) — <р, (х» + б~п'1)» (е)) ~ О). ел Вычислить производную справа 1» (6<2) + 0) и производную слева 1» (Ьо!) — 0) функции 1» в точке 6~~<~: 1» (6<2>+ 0) = шах (Ч<р! (х" + 6>(Р)1<» (е)), 12» (з)); <яя 1» (6>р) — О) = ппп (Ч<р, (х» -1- б<('>й» (е)), 6» (в)). <яус ХЧП. Вычислить <»! = шах (>'» (6(гв + 0) (6<<" — 6(г'), 1„(6!'> — 0) (6<<~) — 6(<п), 0).
ХЧП1. Если выполняется неравенство (1» (0) — 1» (6<о>)) ° (1 — (3) ~~ь (3<<<и то положить р» = 6!) и прекратить вычисления; иначе перейти к (2> шагу Х1Х. Х1Х. Вычислить у! — середину отрезка 16';", 6<<~)) у! —— (6,'и + б,'")/2. ХХ. Вычислить точку б,'", симметричную 6>г' относительно точки ур ХХ1. Если 1» (б~~") ~ 1» (6<!"), то положить б>+! = 6;; 6;+! 6! ', Ь;+! 6; (!) (2). (2) (4), (3) (3) и перейти к шагу ХХП; иначе положить 6>+! = б! ', 6>+! = Ь/ ', Ь!+! = 6! <<> Р>.
Р> <г>. <2> <4) н перейти к шагу ХХП. ХХП. Положить 1 = 1+ 1 и перейти к шагу ХЧ1. Теорема 2. Если выполнены условия теоремы 1 и функции !» (1), й = О, 1, ..., выпуклы на множестве 1О, оо), то любая предельная точка бесконечной последовательности (х") ~ ~, порожденной алеоритмом 2, является стационарной пи>якой функции шах <р! (х). <еЯ' 173 В. Второй метод иоеледоелтельвых вриблилвевий Алгоритм 3 применяется для нахождения е-стационарных точек функции шах ф, (х). Если х' — е-стационарная точка и ф, (х), оку 1Е Я, (х') — выпуклые функции, то шах ф, (х*) — приближенное сну значение для минимума функции шах ф, (х) с абсолютной погреш1ау постыл,'не превышающей ю Алгоритм 3' основан на применении алгоритма 3 и дает возможность вычислять стационарные точки функции шах ф,(х).
ост Точка х' ~ В" называется е-стационарной точкой функции шах ф, (х), если Гет l дяи(кв) ппп шах ~ ф'( ), д)~0 оа1 1 ~аяв1км ~ дк (здесь а Е В", Я, (х) определяется по (3.10)). Алгориивм 8 Н а ч а л о. !. Выбрать произвольное начальное приближение хе Е В", константу е ) О. 11. Положить й = О. Основ но й ц и кл. 1П. Найти множество индексов Я, (хе) ~(1'(шах ф, (хе) — ф, (хе) (е, (с и). опт 1Ч.
Найти многогранник 1.в (хе), который является выпуклой оболочкой, натянутой на множество точек ь Чфо (хл) 1 6 Я (хли Ч. Используя алгоритм 1', определить, принадлежит ли начало координат многограннику Ев (хе). Если начало координат принадлежит Ьв (х"), то положить хв = хе и прекратить вычисления; иначе перейти к шагу Ч1.
Ч1. Используя алгоритм 1", найти точку г„которая является ближайшей к началу координат точкой многогранника 1,, (х"). ЧП. Вычислить вектор й' (е) — направление е-наискорейшего спуска функции гпах ф, (х) в точке хе %т й~(е) = — (14гв() гв Ч1П. Вычислить шаговый множитель р„из условия шах ф, (х" + рй' (е)) = пип шах ф, (х" + рй'(е)). ~ау р>о 1НУ 1Х. Вычислить следующее приближение х"+' = х" + рейь(е). 174 Х. Положить я = й + 1 и перейти к шагу Ш.
Теорема 3. Если выполнены условия теоремы 1, то любая предельная точка 'бесконечной последовательности (х»)ь о, порожденной алгоритмом 3, является е-стационарной точкой функции шах <р, (х). СЕ.У Замечание 3. Вычисление шагового множителя р„на шаге Ч1П алгоритма 3 из условия минимума практически йеосуществимо. В П271 рекомендуется использовать алгоритм 2' для вычисления за конечное число итераций шагового множителя р, удовлетворяющего условию (3. !1).
В случае, когда !» (!), й = О, 1, ...,— выпуклые на (О, оо) функции, теорема 3 остается в силе. Алгоритм 3 может быть также использован для нахождения стационарных точек функции 'гпах <р, (х), только на шаге Ч1 алгорит»ат ма 3 необходимо дополнительно вычислять значение фе (х») = — 1ге1. Алгорип»м 3' Н а ч а л о. 1. Выбрать произвольное начальное приближение х" Е В", константы а,) О, р,) О. П.
Положить ! = О, й = О. О с н о в н о й ц и к л. !П. Положить хе = х'"», а = ен р = Р» 1Ч. Используя алгоритм 3, вычислить точку х"ц такую, что »Ь»(х»)~ — р (такая точка получается за конечное число итераций алгоритма 3). Ч. Положить х'+' '+' = х»Ц е»+1 = е,/2, рц1 р,/2 и перейти к шагу П1. Теорема 3'. Если выполнено предположение 0 и хо» анисово, что множество (х / шах <р, (х) ( шах <р, (хе е), х Е В" ) сну ееу ограничено, то любая предельная точка бесконечной последовательности (х~'~') Г-о, порожденной алгоритмом 3', является стационарной точкой функции гпах <р,(х).
!Я~ 4. Модифииедии второго метода иоеледолотельимл ириближеиий Предположение 4. Функции но ! ~ Р— дважды непрерывно дифференцируемы на всем В". Алгоритм 4 Н а ч а л о. !. Выбрать произвольное начальное приближение хе ~ В", константы сс ) О и а ) О. П.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
