И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 29
Текст из файла (страница 29)
Алгорит,м 6 Н а ч а л о. 1. Выбрать произвольное начальное приближение хо Е В" и константу т, О < 7 < 2; положить я = О, Ос н о в н о й ц и к л. 11. Вычислить вектор направления движения Й» к следукицему приближению х»+' пв' формуле Ь» = 6 (х»). Ш. Вычислить значение шагового множителя р» = 7(1 (х") — 1»"й)г" Р 1т'. Вычислить следующее приближение х»4' = х» — р»й». Ч. Положить й = й + 1 и перейти к шагу 11. Теорема 6. Пусть выпуклая функция 1, имеет единственную точку минимума х*, причем известно значение 1о функции 1, в точке х*.
Тогда, при О < т < 2 последовательность (х»),~=с, порожденная алгоритмом б, сходится к х' из любого начального приближения хе Е лт". Теорема 6'. Пусть: (1) — 1» (х) — сильновыпуклый функционал, причем 1»(х) — 1»(хо) ~се(х — хе( (И) — функция 1» (х) удовлетворяет условию Липигица на области 1'~( и( — *() а — !~Н. т. е.
для всех х, у ~ У выполняется 1.(х) — 1(у) =Ч вЂ” у!1 Тогда, при О < 7 < 2 последа тельность (х")ь,, порожденная алгоритмом б, сходшпся к точке минимума х* со скоростью геомепы рической прогрессии !! х" — х*!) < д»(х' — х')! со знаменателем д = (1 — 7 (2 — 7) аЧЛ») н < !. т. Помелоустойииаый алгоритм Алгоритм 7 указывает на устойчивость метода обобщенного градиентного спуска к малым ошибкам в вычислении точек х», й =. = О, 1, ... и обобщенных градиентов 6 (х") в этих точках. В й-итерации алгоритма за вектор движения Ь» к следующему приближению х»+' выбирается единичный вектор обобщенного градиента функции 1, в точке у", лежащей в 6„-окрестности точки х'. Последовательность (х')» с, порожденная алгоритмом 7, сходится 142 к точйе хеь Хе, Х' = ( У (х) = С); Я = гп1 »т ( (х).
«ян" Алгорип»м 7 Н а ч а л о.' 1. Выбрать произвольное начальное приближение хе Е г»" и положить И = О. Ос н о в но й ц и кл. П. Вычислить шаговый множитель р» и величину смещения б„удовлетворяющие условиям теоремы 7. П1. Вычислить обобщенный градиент д' (у») функции ге в любой точке у", удовлетворяющей неравенству ((у» — х'(( < 6». 1Ч. Вычислить вектор направления движения И» к следующему приближению х'+' И' = у (у'йу (у') <.
Ч. Вычислить следующее приближение х»+! » И» Ч1. Положить И И+ 1 и перейти к шагу П. Теорема 7. Пусть 1» — выпуклая функция, множество минимумов Хе которой непуспю. Тогда, если числа 6», р», И О, 1, ..., выбирать такими, что р»)0; 6»)0; 1)!и 6» О; » м «« «О О Е 6»Р»<'"' Х р»»<оо .7» Р» = оо то последовательность (х»)» л, порожденная алгоритмом 7, удовлетворяет предельному соотношению 1пп х» хе ~ Х'. 8. Мвогощогоемй метод обобщеввого гродвевгвого гоуова Предположение В.
Функция )е — выпуклая. В приводимом ниже алгоритме направление спуска выбирается с использованием обобщенных градиентов и значений функции 1» на предыдущих итерациях. На каждой итерации требуется решать специальную задачу минимизации, которая соответствующей нормировкой сводится к задаче линейного программирования. Шаговые множители р» удовлетворяют классическим условиям. Алгоритм В Н а ч а л о. !. Выбрать произвольное натуральное число т ь 1.
П. Выбрать произвольный набор точек (х-"+', ..., х'). !43 111. Выбрать константу а, сс ) !о (х'). 1Ч. Положить Ь = О. Основной ни кл. Ч. Вычислить Цо(х») — обобщенный градиент функции !о в точке х'. Ч1. Вычислить шаговый множитель р», удовлетворяющий ус- ловиям теоремы 8, ЧП. Если Ч!о (х») = О, то положить х*= х» и прекратить вы- числения; иначе перейти к шагу ЧП1. ЧП1. Если ~о (х») ) а, то положить в» = (Ь) и перейти к шагу 1Х, если )о (х») (а, то положить О» = (Ь вЂ” т + 1, ..., Ь) и пере- йти к шагу 1Х. 1Х.
Вычислить вектор Ь» из условия гп!п <р»(Ь) = <р»(Ь»), ив<о» где функция ~р»(Ь) Ь так К(х!) + (х» — х!, 7!о(х!)) + (Ь, 7!о(х!))]. !6т» Х. Вычислить следующее приближение х»+' = х» + Ь». Х1. Положить Ь = Ь + 1 и перейти к шагу Ч. Теорема 8. Пусть выявляя~ется условия: (1) — функция !о выпукла; (Й) — множество Х'Ь(х]]о(х) = !п1 !о(х)) тяп" непусто и оераничено; (!11) — итоговые множители р», Ь = О, 1, ..., удовлетворяют условиям р»-»-+ О при Ь-». оо, ~ р» — — оо.
»-о Тогда бесконечная последовательность (х»]» о, порожденная алгоритмом 8, такова, что ш!п]х — х»!)-э О при Ь-». оо; тех* !о(х»)- 1п1 !о(х) при Ь- клав Замечание 8. Если множество Х* содержит внутренние точки, то последовательность (х»)Г о, порожденная алгоритмом 8, конечна. 9. е-еубтаадвовтвый метод 3 а да ч а 9. Найти агй ппп!о (х) длЯ заданной фУнкции ,ен" !о ° м»л ° !44 Предроложения 9. (1) — функция г,— выпуклая полунепрерывная снизу; (И) — )п1 Гь (х) ) — оо; (й() — по крайней мере в одной точке х у «ян Е В выполняется условие г„(х) - оо. Определение 9. Для произвольного е) О вектор у,(х) ~В" называется е-субградиентом функции ), в точке х, если ), (г) ~ ~ г,(х) — е+ (г — х, д» (х)) при всех г~ В". Множество е-субградиентов в точке х обозначается через 6, (х).
Алгоритм 9 Н а ч а л о. 1. Выбрать вектор х' Е В" такой, что 1, (хь) ( оо. П. Выбрать константы е, ) О и О ( а ( 1. 1П. Положить (г = О. Основной цикл. 1Ч. Вычислить е»+1 = ае„, где 1 — наименьшее неотрицательное целое число, при котором О Я О,+,(х'). (Если хь не является точкой минимума функции Г„то всегда существует неотрицательное целое число 1, при котором выполняется включение О (С 6,», (х')). Ч. Найти вектор й", для которого выполняется неравенство гцр (й', д)(О. гИ»ь+б» > Ч1. Положить хьь' = х~ + рыл", где р„) О такое, что выполняется неравенство 1, (х") — 1„(хь+') ) еь+ь ЧП. Положить й = й + 1 и перейти к шагу 1Ч. Теорема 9.
Пусть выполняются предположения 9. Тогда либо бесконечная последовательность (хь)ь" ь удовлетворяет предельному соотношению ((о)— либо 1 (х ) = ппп )', (х) при некотором т ) О. Если, кроме того, »ен" множеспию Х«й (х*~ 1„(х*) = ппп 1,(х)) «ьн не пусто и ограничено, то: (о) — каждая сходящаяся подпоследовательность последовательности (х')" ь имеет предел в Х«и хотя бы одна такая подпоследовшпельность существуетг (о() — при каждом а ) О существует и ь О такое, что хь Е Х'+ ег' при всех й» т, где )' ~ (х ( ) х (1 ( Ц; (пВ) — если минимУм фУ кЦии ге достигается в единственной точке х«, то (ха)а с стрем я к хе. Библиографические указания.
Прн написании параграфа нспфзоналнсь ра* боты [395, 396, 397, 401, 404, 391, 392, 406, 290, 126, 160, 277, 4 , 491, 4811. 3.2. Методы градиентного типа с растяжением пространства 3 ада ч а О. Найти агя ппп ге (х) для заданной почти диффе- «67« ренцируемой функции 7»: В" -~ В'. Сущность методов градиентного типа с растяжением простран- ства заключается в построении в процессе последовательных при- ближений линейных операторов, изменяющих метрику простран- ства, и выбора направления спуска, соответствующего антнгради- енту в пространстве с новой метрикой.
Определение О. Оператором растяжения пространства В" в на- правлении $~ В" ((($( = 1) с коэффициентом а (а,,.'а О), назы- вается оператор Оа ($), действующий на вектор х, представленный в форме х 1~(х)3+д«(х); ($, й1(х)) = О, (здесь у4 (х) = (х, $); йа (х) = х — (х, 9) $) следующим образом: Оа (ь) х = иу4 (х) ь + йг (х) = х + (㻠— 1) (х, ь) $~ где 6 (9) — линейный симметричный оператор.
Оператор Ор (9) = 67а ($) называется оператором «сжатия». Ниже приводятся алгоритмы с растяжением пространства в -направлениях: сначала почти градиента, а затем разности двух по- следовательных почти градиентов (2 3.3). В алгоритме 1 в Ьй итерации следующее приближение х"+' на- ходят по формуле + = ' - В„р„Р, где $» — единичный вектор почти градиента функции гра (у) Ьр ~17е (В„У), котоРаЯ полУчаетсЯ из 1е (х) пРи использовании линей- ного преобразования пространства у = А,х; В, — оператор, об- ратный результирующему оператору А, преобразования простран- ства (А, получается в результате последовательного применения операторов растяжения пространства в направлении нормирован- ных почти гРадиентов яе, ят, ..., 9» ' с коэффициентами ат, ...
..., аа: А„= б (9' ')Аа 1); р» — шаговый множитель, Операторы Ва+~ для отображения преобразованного в основ- ное пространство В" определяются рекуррентными соотношечиями В+ =В,бр,~,Р); где (1»+~ гз 1/с«а+1 — коэффициенты «сжатия» пространства. 146 Алерритл«1 'Н а ча л о. 1. Выбрать начальное приближение х» ч В" и не- особую мйтрицу В, (можно выбрать В, = /, где / — единичная и Х и-матрица); положить й = О.
Ос н о вн о й ц и к л. П. Вычислить почти градиент у(х») функции Ц» в точке х». П1. Если у (х») = О, то положить х» = х» и закончить вычисления; иначе перейти к шагу !Ч. 1Ч. Вычислить оператор В», сопряженный оператору В». Ч. Вычислить почти градиент у (у») функции ч!» (У) Й /о (В»у) в точке у»= В» 'х» д (у") = В»у(х»).
Ч1. Вычислить направление растяжения пространства Р = у(у'Иу(у'6 ЧП. Вычислить значения шагового множителя р». ЧП1. Вычислить следуя»щее приближение х'+'= ' — р В»Р. 1Х. Найти коэффициент растяжения пространства а»»!. Х. Вычислить коэффициент «сжатия» пространства ~»+! = 1/««ь+!. Х1. Вычислить оператор В».ь!, обратный результирующему опе- ратору Аь~.! преобразования пространства, в,+, = в,а„,„, у), где оператор «сжатия» Ов» »! (а») вычисляется согласно определе- ния О. ХП. Положить /г = й + 1 и перейти к шагу П. Теорема 1. Пусть/» (х) — почти дифференцируемая функция и х» — точка ее локального минимума.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
