И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 26
Текст из файла (страница 26)
е. принадлежат также ограниченной области. 4. Столествчеснвй традвентвый метод с ностолвным меловым множителем 3 а д а ч а 4. Найти агя ппп Ее !е (х, а) для заданной функции 1~;Е" х а Е1. градиента функции Ч", (х), вычисляемой о помощью вспомогательного вектора у», приближающего значение Е„»Р (х", ь»).
Алгорип»м 5 Н а ч а л о. 1. Выбрать произвольные начальные приближения х' Е Е", у' Е Е"' . Н. Положить й = О. Основ ной ц и кл. 1!!. Вычислить независимую реализацию ь»» случайного вектора ь». !Ч. Вычислить векторы ЧД (х», у»), Ч,!» (х», у»), ~р (х", ь»»! и матрицу Ч,е(х», ь»»). Ч. Вычислить шаговые множители р» и р», удовлетворяющие условиям теоремы 5.
Ч1. Вычислить следующее приближение х»+' для вектора х» х"+' = х» — р» (Ч,!» (»», у») + (Ч„»р (х», ь»»)) г Ч !» (х», у»)). Ч11. Вычислить приближение у"+' для вектора г (х»+') у»+~ у» р !у»,Р(х»' ы»)) .Ч111. Положить й = й + 1 и перейти к шагу Ш. Теорема 5. Пусть выполняются предположения 5 и (»и) — функция Ч', (х) локально сильно выпукла в окрестности х*, т. е. (ЧЧ',(х), х — х*) ~ ч)х — х* 1», ч ) О, для х близких к х»г (1о) — в окрестности точки х» помехи имеют ограниченную дисперсию: Е )<Р(х, ьэ) — г(х)/!»((о»)', Е 1Ч,<р(х, ь») — Ч,г(х)1»((о»)». Тогда если в алгоритме 5 начальное приближение (х», у») удовлетворяет условию 1х» — х*1»+ ~У» — г»1'(6, а шаговые множители р» и р» такие, что ЮО Ю Х р»=, Е (р„')»(5,(., р',!Р,>()~О, »-ь»м> то для достаточно большого (3 последовательность (х»)» л, порожденная алгоритмаи 5, удовлетворяет соотношениям Р (х»-» х») ~ 1 — т, т = с,б+ с»(о»)»()д»+ с»(о»)»д„ где со ! = 1, 2, 3 — некоторые константы.
Если шаговые множители р» и р» выбирать по правилам Р . Р Р»= »+1' Р'= »+1 ° 127 то для любых чисел т ) О, с4) 0 можно выбирать параметры б, р, р', ! так, епо Р ~~хе — хелп- —" я се й~~ 1 — т. Замечание б. Из теоремы следует, что можно гарантировать сходимость алгоритма б с вероятностью 1 — т, где т тем меньше, чем точнее начальное приближение (х', уе), чем меньше уровень помех н длина шаговых множителей. Сходимости в среднем квадратическом или о вероятностью единица в невыпуклом случае несуществует, так как при наличии помех имеется ненулевая вероятность выхода последовательности (х")ь о из окрестности решения, вне которой сходимость отсутствует.
Библиографические указания. При написании параграфа использовались рвботы !149, 153, 29, !71, 2991. Стохвстнческие кввзигредиентные иетоды решения задач безусловной оптимизации исследовались также в работах 1148, 150, 151, 156, !57!. 2.10. Метод локальных вариаций 3 а да ч а 1. Найти агд ппп !е(х)для заданной непрерывно дифкнне ференцируемой функции !е: 1!"-» Нх.
Метод локальных вариаций не требует вычисления производных минимизируемой функции и не является очевидной модификацией алгоритма, требующего таких вычислений. Алгоритм 1 Н а ч а л о. 1. Выбрать начальное приближение хе ~ В", удов- летворяющее условиям теоремы 1; константур,) 0 (рекомендует- ся р,= 1). 11. Вычислить и-мерные векторы !г', ! = 1, 2, ..., 2п, !гз1-1=с/, 1=1, 2, ..., и; йз! — е!, 1=1, 2, ..., и, где е1, ! = 1, ..., и — !цй столбец единичной п Х п-матрицы. П 1.
Положить й = О, х =* хе. 1Ч. Вычислить 7е (х). Основной цикл. Ч. Положитьр=р„. Ч1. Положить ! = 1. ЧП. Вычислить !е (х+ рй'). Ч П1. Если 7е (х + рй') ( 7е (х), то положить х = х + рй' и пе- рейти к шагу Ч1; иначе перейти к шагу !Х. !Х. Если ! ( 2п, то положить ! = ! + 1 и перейти к шагу ЧП; иначе перейти к шагу Х. Х. Положить хв+' = х, рк+1 — — р/2, й = й + 1 и перейти к шагу Ч. Теорема 1. Если функция(е непрерывно дифференцируема и на- 128 чальное приближение хе в алгоритме 1 таково, что множество Хе~(х)1е(х)(13(хе), хЕВ") ограничено, то каждая предельная точка х' последоеапельности (ха) а е, порожденной алгоритмом 1, удовлетворяет условию Ч13 (х') = О.
Если, кроме того, множество Хе ~ (х( Ч1о (х) = О, х Е В") состоит из конечного числа точек и каждая его точка доспавляет либо локальный минимум, либо локальный максимум, то последовательность (х~)ь.о сходится к такой точке х, что 713 (х) О. Метод локальных вариаций особенно эффективен, когда минимизируемая функция 1, имеет вид 1, (х) = ч~~~ 1, (х,), х = (х„хв, ..., х„). 4 ! Библиографические указании. Параграф основан на работах [286, 16]. Дополнительные сведения о методе локальных вариаций можно найти в работах [386, 388, 449, 260, 261, 339!. 2.11. Методы самонастраивающихся программ Задача 1.
Найти ага ппп1,(х) для заданной функции «ей" 13 ° В -ьВ ° Предположение 1. Функция 13 — непрерывно дифференцируема в В". В алгоритме 1 с помощью принципа самонастраивающихся программ производится соединение следующих методов: градиентного спуска, покоординатного спуска, сопряженных градиентов. На каждой итерации алгоритма определенное число раз производится градиентный спуск в подпространстве быстрых переменных и градиентный спуск в подпространстве медленных переменных.
Алгоритм применим к решению задач овражного типа. Алгорипам 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение хе сВ". П. Выбрать произвольные константы в ) О, б ) О (причем г (( (( б) и четное натуральное число 1. П1. Положить т' = та = 112. [Ч. Положить й'= О. Основной цикл. Ч. Положить х'=х". Ч1.
Положить 1 = 1. б 3-аи 129 ЧП. Вычислить. вектор Ь~= (Ь)ь ..., Ь1), 1-я координата като' ' рого при ~ д( ) ~<з; — — в противном случае д/ (х)) дх; здесь 1 = 1, ..., а. ИП. Вычислить значение рп удовлетворяющее условию ш!и Г' (х~ + рй)) = 1„(х) + р)й)). о~о 1Х. Положить х'+ = х' + р(й). Х. Если 1(тхп то положить 1 = 1+ 1 и перейти к шагу ЧП; иначе положить л~~~ = х'+~ и перейти к шагу Х1. Х1.
Положить х'= хь" . ХП. Положить 1 = !. ХП1. Вычислить вектор Ь) = (Ь)ь ..., Ь)), (-я координата которого О при ~ — )~~6; Ь;= ( — + О;Ь~~ в противном случае, дх~ где Е, = О; В, = (Ч~,Я вЂ” Ч1,(х '), Ч1,(Р)ДЦ,()-')~ при 1 ~ 1.
Х1Ч. Вычислить значение рп удовлетворяющее условию ппп 1,(х) + рй!) ~,(х) + р;Ь!). р~О ХЧ. Положить х'+ = х' + р)й'. ХИ. Если 1( тх, то положить 1 = 1+ 1 и перейти к шагу ХП1; иначе положить х~' = х'~' и перейти к шагу ХЧП.
ХИ1. Вычислить веса Ф Ь(»') — 10(»+') . х 2 10(»+') — 10(» ) р' 2; р,= ХЧП1. Вычислить тх+' = р" Р", +Р2 Х1Х. Вычислить та+, ! 3 х рх+ А ХХ. Положить й = й + 1 и перейти к шагу Ч. Теорема 1. Если градиент функции /о удовлетворяет условшо Липшица, т. е. 6~Чо(х) — Ч/о(У)Ц(Уфх — У(, Чх у~лк и множество Х= (к[го( ) -./ ( о) конечная последовательность (х")а=о, порожденная алгоритмом 1, такова, что ['пп ) Ч/о (х") $ = О. о «о Если, кроме того, /о — дважды непрерывно дифференцируема функция, причем ее матрица вторых частных производных Чв,/о (х) удоаоапворяет условию р[[у$ ~((Ч««/о(х)у, у)(7[[у) (2.18) при всех х Е Хо и любых у е В", то х~ .~. хо, 7о (ха) -ь /о (хо), где хо — тачка минимума (единственная) функции /о.
Для скорости сходимости справедливы следующие оценки: /о (ХЛ) — /о (Х') ~ (а,у', ~ Х" — Хо [(( аву П, (2.19) аг = /о(хо) — /о(х'), ав = (2аг/!))"; у = 1 — (р/2у)'. Замечание 1. Шаги ЧП1 и Х!Ч алгоритма 1 требуют точного вычисления минимума одномерной функции, что на практике не всегда выполнимо, Можно построить модификацию алгоритма 1, требующую приближенного вычисления минимума одномерной функции. Для этого необходимо константу е выбирать из условия О ( ( е( г/„ашаги 'ЧП1 и Х1Ч алгоритма 1 заменить, соответственно, на шаги ЧПГ и Х1Ч'.
ЧПГ, Вычислить значение рп удовлетворяющее условию (1 — е)(Ч/,(х'), Ь~)((Ч/о(х'+ рЯ, й/) .«,;е(Цо(х/), й'). Х1Ч'. Вычислить значение рп удовлетворяющее условию (1 — е)(Ч/,(хг), й') ((Ч~,(х/+ рг/г'), /г/) а е(Ч~,(х/), 6/). При выполнении условия (2.18) для скорости сходимости модифицированного таким образом алгоритма 1 справедливы оценки (2.19) при о = ! — 2е (1 — е)(р/у)(1 + ~/у). Бпблнгмлофкческие укаюкил. Параграф написан иа основании работы [384!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
