И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 28
Текст из файла (страница 28)
Основ ной цикл. П. Вычислить обобщенный градиент д(х») фУнкции !е в точке х». Если д (х") = О, то х» Р Хе; иначе перейти к шагу П1. П1. Вычислить вектор й" (определяющий направление движения к следующему приближению х»+') й = у(х )11у (х )1. 1Ч. Вычислить следующее приближение х"+' х" — рй'. Ч. Положить й = й + 1 и перейти к шагу П.
ТеоРема 1. Если 1»вмпУклан фУнкЦиЯ, то длЯ пРоигвольного 6 ) О можно найти такое р (6), что для последовательности х', х', ..., х», ..., порожденной лгоритмом 1, при р = р (6) найдется такое й = ле, что х»" Е Х*, либо такая подпоследовательность 1пп Де (х") — ш! и 1е (х) ( 6. С «« «8 Ел 136 Теорема 1'. Если выпуклаяфункция Дв имеет область минимумов Х*, содержащую сферу радиуса г ) р/2, то для последовательности хв, х», ..., х", ..., порожденной алгоритмом 1, найдется такое й = й', что х' р Х*.
2. Основной алгоритм В алгоритме 2 в Ьй итерации за вектор, определяющий направ* ление движения к следующему приближению х»+', выбирается единичный вектор обобщенного градиента функции )с в точке х". Шаговый множитель р» удовлетворяет классическим условиям ос р» в О; ~ р» = оо, !пп р» = О. (3.!) » 0 » со Алгоритм 2 Н а ч а л о. 1.
Выбрать произвольное начальное приближение х' Е В" и положить й = О. Основной ц и кл. П. Вычислить обобщенный градиент 2 (х») функции !с в точке х». Если 2 (х») = О, то положить хв= х» и прекратить вйчисления; иначе перейти к шагу П1. П1. Вычислить вектор й» = 2(х»)/~д(х»)~. 1Ч. Вычислить значение шагового множителя р», удовлетворя. ющее условиям теоремы 2. Ч. Вычислить следующее приближение х»+' = х» — р»й». Ч1.
Положить й = я + 1 и перейти к шагу 11. Теорема 2. Пусть )с (х) — выпуклая функция, область минимумов Хо которой ограничена. Тогда, если шаговые множители р, й = О, 1, ..., таковы, что р»~О; !ппр» = О; ~, 'р» — — оо, » ссо »-0 то бесконечная последовательность (х»)~ с, порожденная алгоритмом 2, удовлетворяет предельным соотношениям !пп ш!и!!х» — х(=О; » «зх !пп ~,(х') = ш!п1»(х). » осо Но «Я Теорема 2'.
Пусть множество минимумов Хв Ь (х ! 1с(х) = !п! ~с(х)) «яи с выпуклой функции Д» непусто и шаговые множители р, й = О, 1, ..., удовлетворяют условиям р»~О, в=О, 1, ...; !пир» — О; ~ р» — оо. Тогда, если выполнено одно из следующих пяти условий: (!о) — множество Ха ограничено; , (о)— ~ р»~» оо; (о») — 1п1Х*~Я; (оИ) — множество Ха является линейным многообразием в Вк'; (оИ() — п = 2, то предельные точки бесконечной последовательности (х»)» ~, порожденной алгоритмом 2, принадлежат множеству Х*. При етом условия (о) и (и»») обеспечившот сходимость последовательности (х»)»-..е к точке х Е Х*, а условие (гй) обеспечивает конечность алгоритма 2. В.
Мадифииапив аеиааиого алгоритма В алгоритме 3 в я-й итерации за вектор направления движения к следующему приближению х»+' выбирается вектор, обратный к обобщенному градиенту функции 1» в точке х». Шаговый множитель р, удовлетворяет классическим условиям (3.1). Алгоритм 3 Н а ч а л о. 1. Выбрать произвольную начальную точку х» ч Е В" и положить й = О. Основ ной ци кл.
11. Вычислить обобщенный градиент д (х») функции 1» в точке х». П1. Найти значение шагового множителя р», удовлетворяющее -условиям теоремы 3. 1Ч. Вычислить следующее приближение х»+' = х» — р»у (х"). Ч. Положить й = й+ 1 и перейти к шагу П. Теорема 3. Пусть !е (х) — выпуклая функция, область минимумов которой Х* ограничена. Тогда, если (й) — шаговые мнозсители р», й = О, 1, ..., таковы, что р»~~»О; !ппр»=О; ~~ ~р»= оо; ».~ ок ь-о (И) — последовательность обобщенных градиентов (д (х»))»-е, порожденная алгориплюм 3, ограничена, то бесконечная последовательность (х»)»=о удовлетворяет предельным соотношениям !!ш пп!и ~ х» — х(( =* О; *ах 1пп ~» (х') = пип 1» (х).
»-ккк И» ко 4. Первый алгорвг55 со спсавалавым выбором шага Алгоритм 4 может быть применен для минимизации функции /о (х), удовлетворяющей предположению 4. Предположение 4. Пусть |е (х) — выпуклая функция такая, что при некотором О(р( —, для всех «ЕВ" выполняется нера- венство (я(х), х — х*(х))~сов5р)(д(х)))х — х'(х)1, (Вв) где х* (х) — точка, принадлежащая множеству минимумов функции /о (х) и лежащая на кратчайшем расстоянии от х.
В алгоритме 4 в /5-й итерации ва вектор направления движения й' к следующему приближению х"+' выбирается единичный вектор обобщенного градиента функции /о в точке х'. Шаговые множители ры /5 = О, 1, ..., вычисляются в соответствии с рекуррентной формулой р«+1 = рФ(р) ро = ре(х', р), где в)п 5р, ~ < 5р < 2, ~()= — О< р< —. (З.в) ) хе (хо) — хо(сов 5р, —" (5р ( — ", Ро~ 1«е( ) «01 < 2005 ф О<ор< —, где хе (хо) — точка, принадлежащая множеству минимумов функции /о (х) и лежащая на кратчайшем расстоянии от точки хе.
Ч. Положить /5 = О. О с н о в н о й ц и к л. Ч1. Вычислить вектор направления движения /5" к следующему приближению «5+' /5а = д (х")/) д (х") !). !39 Последовательность (хе) ~=о, порожденная алгоритмом 4, сходится к множеству минимумов со скоростью геометрической прогрессии и знаменателем 5/ = р (25). 4лгориием 4 Н а ч а л о. 1. Выбрать произвольную начальную точку хе ~ ЕВ П. Найти угол О ( 5р < —, удовлетворяющий иеравенетву (3.2) для всех х Е В". 1П. Вычислить значение р (~р) по формуле (3.3). 1Ч. Вычислить начальное значение шагового множителя ре, удовлетворяющее неравенству 'ЧП.
Вычислить следующее приближение х»+' = х" — р 1»». ЧП1. Вычислить значение шагового множителя Р+ =М(Р), где Р (~р) определяется по формуле (3.3). 1Х. Положить й = й + 1 и перейти к шагу Ч1. Теорема 4. Пусть имеет место предположение 4. Тогда последовательность х", я = О, 1, ..., порожденная алгоршпмом 4, такова, что либо при некотором и — д (х») = О и х" принадлежит области минимумов, либо при всех й = О, 1, ...
будет выполняться неравенство Р»асов Ч 4 ~( Р ( '1 х» — ха (хс) 1а' Р( О1~(~р ~ 4 Замечание 4. В неравенстве (3.2) соз гр показывает степень вытянУтости повеРхностей УРовнЯ фУнкции 1«. Если в некотоРой окРестности минимума функции 1» не существует угла ~р ( Ы2, удовлетворяющего неравенству (3.2), то такая функция называется существенно овражной и для ее минимизации алгоритм 4 неприменим. В этом случае следует использовать универсальный метод выбора шатовых множителей, как в алгоритме 3. 6. Второй алгоритм со сисииальиым выбором шага Алгоритм 5 может быть применен для минимизации функции г„удовлетворяющей предположениям 5. Предположения б. (1) — функция ~с выпукла в П"; (»1) — функ- ция 1» имеет единственную точку минимума х', (Й1) — для любого числа а ) О существует конечное число т ) О такое, что для любой пары точек х, г Р У', У ~ (у ! '1 у — х* ~ ( а), такОй, что гс (х) = ~с (г) чь )с (х*), выполнЯетси Условие (~х — х*'1/'1г — х*'1) (т.
В алгоритме 5 в я-й итерации за вектор направления движения й» к следующему приближению х»+' выбирается единичный век- тор обобщенного градиента функции 1« в точке х". Шаговые множи- тели Р„, я = О, 1, ..., вычисляются по рекуррентным формулам 1' о' — ! Р»+1= Р» '. Рс = Рс(хс о), где а» )~2 — характеризует степень «вытянутости» поверхностей УРовнЯ фУнкции 1«. 440 Последовательность (х")в=о, порожденная алгоритмом 5, схо- дится к точке минимума функции (о со скоростью геометрической прогрессии и знаменателем д Уов — 1/о.
АлгориМм Б Н а ч а л'о. 1. Выбрать произвольное начальное приближение хв Е 11". П. Найти число о,;в )~2 и значение шагового множителя р,) О, удовлетворяющие условиям теоремы 5. 111. Положить й = О. Ос нов но й ц и кл. 1Ч. Вычислить вектор направления дви- жения йа к следующему приближению х"+' Иа=у( "у~!д( ")(. Ч. Вычислить следующее приближение х'+' = х" — р„пв. Ч1. Вычислить значение шагового множителя ра+~ = р,)~ а' — 11а. ЧП. Положить й = и + 1 н перейти к шагу 1Ч. Теорема б. Пусть имеют место предположения б и пусть чис- лаоир,удовлетворяют условиям: (1) — о ~ у'2; (11) — р, ~ (1хв— — хв '()/о; (111) — для любой пары точек х, г принадлежащих мно- жеству У а (х ) ( х — х* ( ~~ арв) и таких, что 1в (х) = 1в (г) Ф Ф (в (х') вьтолняется условие (( х — хв1)1(1г — хв () ( о. Тогда последовательность (хв)в о, порожденна алгоритмом б, сходшпся к точке хв со скоростью геометрической прогрессии '!ха — хо(( р„о, й = О, 1, ..., знаменатель которой о Уо' — 1/о, за исключением случая, когда для некоторого й = й, а (х") =* О, т.
е. х" = хв. 6. Алгоритм, ивпольауюалай априориоо ававвв минвмума фунвнва Алгоритм б основан на априорном знании значения го минимизируемой функции в точке минимума. В й-й итерации за вектор движения й' к следующему приближению х'+' выбирается обобщенный градиент функции (о в точке х". Шаговые множители р, й = = О, 1, ..., вычисляются по формуле ра = у Уо ( ") — С)l (у ( ') Г. где у — константа, удовлетворяющая неравенствам О < у < 2. Последовательность (ха)~ о, порожденная алгоритмом б, сходится 141 к точке минимума хе со скоростью геометрической прогресси)4 со знаменателем о = (1 — т (2 — 7) аЧЛ»)ги < 1, где Л и а — кокоторые константы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
