И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 30
Текст из файла (страница 30)
Тогда, если в процессе реали- зации алгоритма 1 выполняются условия; (')— 1х» — х«)(о, о>0, й = 1, 2, ...; (и)— 1+6(сс»<а, 6>0, то существует такая подпоследовотельность (х"»), ! и число у>0, что ! г»» )у(у ~))<у~ П и/) ", э= 1, 2, !=! Теорема 1'.
Пусть Д» (х) — почти дифференцируемая функция, определенная в некоторой сферической окрестности 5«точки хч !«т локального минимума, и в тех точках, где функция дифферрй цируелш, ее производная )оги«> (х) по направлению р (х) = х — хо удовлетворяет неравенству 1огч«> Рб (Х', Х')Х>0, хчьхо. Тогда, если в алгоритме 1 принять (')— хо ЕЗо! 1« (" ) — 1о (» ) . + (у(е«Н! л+х ад+~по«а = 1, то найдутся константа у' и подпоследавательность индексов (й,) -ь й, ( А ~ь такие, что 1о(х ') — 1о(хо)(у'а У ° з 1 2 Замечание 1. Описанный в теореме 1' способ выбора коэффициен- та растяжения а„, й = 1, 2, ..., и шагового множителя рм й = О, 1, 2, ..., находит непосредственное применение при решении систем нелинейных уравнений ~,(х)=0, 1=1, ..., и, путем сведения к задаче ш!и !пах ! ), (х) !.
«ьо но « При этом, как показано в (148), в регулярном случае при до- статочно хорошем начальном приближении хо константы Х и Х' можно выбирать близкими к единице, что обеспечивает быструю схо- димость. При решении выпуклых задач, в общем случае (о (х*) неизвест- но, поэтому представляет интерес вопрос о подборе 1о (х') в процес- се счета. Справедлива следующая теорема. Теорема 1". Пусть выпуклая функция 1« (х) обладает следующими свойствами: (1) — суи(ествует постоянная у ° 1 такая, опо если функция <р(т), ~р(т)~~ ((1 — т)х«+тх'), 0(т:«1, строго убывает по т, то выполняется неравенство ~охи «ч (х') ~ (7 (1о (х') — 1о (хо)) где ~ол««ч (х') — производная функции 1о (х) по направлению (х~ — х') в точке х', (И)— 1пп ~, (х) = + оо.
Рл Тогда, если в алгоритме 1 принять а+~ = (у+ 1)/(у — 1); 148 р» = 2'ч'(!о (х») Р)/(у + 1) ((й (у») $ где ! выбрано большим или равным !« ~ ппп !о (х), то последователь«ен" ность (р»)Я.о является ограниченной и для произвольного е ) О найдется й такое, что 1» (х») ( ! +е (счет прекращается, если на некотором шаге /о (х») (7). Если ! выбрано меньшим 1», то последовательность (р»)ь.е является неогран иченной. Замечание 1'.
Теорема !" позволяет строить алгоритм минимизации функции !о(х), удовлетворяющей условиям теоремы, при неизвестном /а. Этот алгоритм связан с подбором 1* с использованием следующих признаков: если при некотором 1 шаговый множитель р» превосходит наперед выбранное достаточно большое число, то /увеличивается; при приближении !о (х») к 1 — значение 1 уменьшается. Теорема 1"'.
Пусть функция !о выпукла в В и в процессе применения алгоритма 1 выполняются следующие условия: (г)— ((д (х») ~ ( о, й = О, 1, ...; (й)— 1 ( а — а», '(!» —— 1/а». Тогда для последовательности (х»)» о, порожденной алгоритмом 1, справедливы неравенства ш!и (й(у')(~о)I/г(໠— 1)/у'аз»/о — 1, й = 1, 2, .... ~<«ч» Библиографические у«оголил. Прв вапвсаппв параграфа использовались работы 1398, 401, 403, 407, 400, 408, 409, 405, 340).
3.3. Методы градиентного типа е растяжением пространства в направлении равности двух последовательных по пн градиентов (г (сг)-алгоритм) Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение хо б В, коэффициент растяжения пространства а ~ 1 и положить до = О (Π— и-мерный нуль-вектор), Во = 1 (1 — единичная матрица), й=О. Основ но й ци кл. 11. Вычислить почти градиент й(х») функции /о в точке х»; если он определен неоднозначно, то взять такой почти градиент, что (В»д», й (х»)) = О.
149 П1. Вычислить вектор а'=в,'а( ). Примечание: вектор а» является почти градиентом функции ~р» (у) 4»/» (В»у) в точке у = А„х', где А» ~ В»' — оператор растяжения пространства после й-й итерации. 1Ч. Вычислить разность двух почти градиентов от функции <р» (у), вычисленных в точках у' = А,х', у"= А»х»-', по формуле = а — а" Ч. Вычислить направление растяжения пространства $» = г»/!!г»(!. Ч1. Вычислить оператор Вььь обратный результирующему оператору А»+1 преобразования пространства после /» + 1-й итерации, в,+, — в,в,у), где р = 1/а — коэффициент «сжатия» пространства. ЧП. Вычислить почти градиент а"+' функции ~р»+~(у) ~ с» /» (В»+~у) в точке у = В»+~х»: а»'1=6аУ)Р=вг аЮ ЧП1.
Вычислить значение шагового множителя р» из условия р„ага ппп /» (х» — рв».!.1а»+') (3.4) р>О (операция ш1п означает определение ближайшего к нулю локального минимума). 1Х. Вычислить следующее приближение х'+' = х» — р»В»+1а»+'.
Примечание: шаг 1Х фактически реализует шаг наискорейшего спуска для функции ~р»+1 (у) ~/» (В»+|у): у+'= у' — р»+'. Х. Положить й = й + 1 и перейти к шагу П. Теорема 1. Если выполнены условия: (») — функция /» — непрерывна и кусочно-гладкая; (й) — !!ш /» (х) = +ьь; (И1) — функция /» В!- обладает следуюсцим свойством: в любой ограниченной области Х для любого б ~ О найдется такое е ) О, что если х, у б Х, /» (х)— — /«(у) ( г и на отрезке меявду х и у функция /» убывает, то ~ х — у ) ( 6 (для выпуклых функций зто свойство является аналогом сильной выпуклости), то предельной точкой последовательности 150 (х")»-е, порожденной алгоритмом 1 при любом а ) 1, является некоторая точка х, множество локти градиентов которой образует линейно-мвисимое семейство векторов.
При етом, в силу монотонности процесса спуска (1» (хе) > 1» (х') ~ >." > 1» (х») > ...) последовательность (1» (х»))» е сходится к 1, (х). Теорема 1'. Если выполняются все условия теоремы 1 и х' — изолированная точка локального минимума, хе — такая точка, чпю связная компонента множества (х) 1, (х*) ~( 1» (х) ~( 1» (х')) годер жащая точки х', ха, не имеет кроме х' других точек г, у которых семейство почти градиентов 0 (г) линейно-зависимо, то последовательность (х»)~ е, порожденная алгоритмом1 с начальной точкой хе, удовлетворяющей условиям теоремы, сходится к ха. Замечание 2. В отличие от других градиентных методов минимизации негладких функций (обобщенного градиентного спуска, обобщенного градиентного спуска с растяжением пространства в направлении почти градиента) г (сс)-алгоритм обеспечивает монотонность спуска благодаря определенному по формуле (3.4) способу выбора шага спуска: 1, (х') ~ 1, (х') ~ ... л 1, (х").
Одйако он существенно отличается от обычных релаксациоиных методов следующим: если р» = О, то зто не значит, что процесс спуска прекращается. При выполнении серии итераций с нулевым шагом точка х» стоит на месте, но изменяются В» и й». В зто время как бы в скрытой форме осуществляется поиск подходящего направления спуска. Библиаграфкческие еказакпл. При иаписаиии параграфа использовались работы !398, 401, 403, 407; 400, 408, 409, 405, 3401. 3.4. Методы локального случайного номена 3 а дача О.
Найти агйппп1,(х) для заданной непрерывной «еи" функции 1,: В" -ь В'. 1. Алгерптк лекальпаге елучайкеге пепека е парией пробой Алгоритм 1 Н а ч а л о. 1. Выбрать: произвольное начальное приближение ха ~ В", пробный шаговый множитель у ~ О и рабочий шаговый множитель р ) О; положить й = О. О с н о в н о й ц и к л. П. Вычислить независимую реализацию 9» случайного единичного вектора 9, равномерно распределенного по всем направлениям пространства параметров х. П1.
Вычислить вектор движения й» к следующему приближению х»+! "' = $' 31 яп (1» (х — 7$") — 1» (х» + 7$'П. !31 1Ч. Вычислить следуюшее приближение х'+' х'+ рйа. Ч. Положить и = л т ! и перейти к шагу П. Замеаиие 1. Характерной особенностью данного алгоритма является его повышенная тенденция к «блужданию», даже в том случае, если решение задачи 0 найдено. Однако алгоритм 1 приводит с большой вероятностью в е-окрестность точек локального минимума, зависящую от шага р, размерности пространства В" н вида функции )с.
(Например, в центральном поле, т. е. когда гс (х) = х — хе, для того чтобы попасть в е-окрестность точки х" с большой вероятностью, необходимо шаговый множитель р выбирать из условия р ( (а/а,, где при и = 2 а„' = 0,7; при п = 3 а„= 0,9; при и = 4 а„= 1,0). 2. Алгорвтм локальвого случайвого воисва с аоаиратом врв веулачвом шаге Алгоривьм 2 Н а ч а л о. 1.
Выбрать произвольное начальное приближение хс ~ В", шаговый множитель р ) 0; положить й = О. О с н о в н о й ц и к л. П. Вычислить независимую реализацию Р случайного единичного вектора $, равномерно распределенного по всем направлениям пространства В". П1. Вычислить вектор г по формуле г = ха+ рвь. !Ч. Если ге (г) < (с (х'), то положить х"+' = г и перейти к шагу Ч; иначе положить хе+' = х" и перейти к шагу Ч. Ч. Положить й = й + 1 и перейти к шагу П.
Замечание 2. Алгоритм 2 (как и алгоритм 1) может быть рекомендован для оптимизации объектов, функция качества которых изменяется во времени со сравнительно большой скоростью. 3. Алгоритм локальвого случайвого вовеки с лввейвой окстраволавией Смысл такого алгоритма поиска сводится к следующему. После неудачного случайного шага делается двойной шаг в противоположном направлении, но функция цели Гс в этом состоянии не вычисляется, а экстраполируется в предположении о линейном характере фУнкции цели ге.
Алгорииьм 3 Н а ч а л о. 1. Выбрать произвольное начальное приближение хе с В", шаговый множитель р ) 0; вычислить 7е (х'); положить й = О. О с н о в н о й ц и к л. П. Вычислить независимую реализацию вь случайного единичного вектора $, равномерно распределенного по всем направлениям пространства В . 162 П1. Вычислить вектор г = х'+ рв» 1Ч. Вычислить 1, (г) — значение функции 1» в точке г, если 1« (г) ( 1» (х»), то положить х»+' = г, 1, (х»+') = 1» (г) и перейти к шагу ЧП; иначе перейти к шагу Ч. Ч. Вычислить вектор х»+' = х" — рв». Ч1. Вычислить «значение» функции 1« в точке х»+' 1«(х»+ ) = 21»(ха) 1о(г). ЧП.
Положить й = й + 1 и перейти к шагу П. Замечание 3. Алгоритм 3 обладает повышенным быстродействием по сравнению с алгоритмами 1 н 2, ибо он использует неблагоприятные шаги. Однако он плохо работает в нелинейной задаче. 4. Алгоритм случаявого волова во иаилучшей врезе с иаиоилевием Сущность алгоритма заключается в следующем. В й-й итерации из точки х' делается т (т в 1) пробных шагов по независимым случайным направлениям в»~, 1 = 1, ..., т, и определяется наилучшее направление в»л'. Рабочий шаг делается именно в этом направлении. Алгоритм 4 Н а ч а л о.
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}
