И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 31
Текст из файла (страница 31)
( '+ уР'). о=ь.,м 1Ч. Вычислить следующее приближение х»+' = х»+ р$»х' Ч. Положить й = й + 1 и перейти к шагу П. Замечание 4. С увеличением числа пробных шагов направление вектора движения $»" приближается к направлению, обратному градиенту Ч1о (х'), и в пределе при т -» со, у -» О совпадает с ним. Ь, Алгоритм статиствчесиого граииеита Алгоритм б Н а ч а л о. 1. Выбрать произвольную начальную точку хо с Е В", пробный шаговый множитель у ) О, рабочий шаговый множитель р ) О, число пробных шагов и в 1; положить й = О. О с н о в н о й ц и к л.
П. Вычислить т независимых реализаций $~', 1 = 1, ..., и, случайного единичного вектора $, равномерно распределенного по всем направлениям пространства В". П1. Вычислить приращения функции 7» й, = 1е(х»+ тих) — 1е(х»), 1 = 1, ..., л». 1У. Вычислить вектор й» = ~ (6»'Лг). г=! Ч.
Вычислить вектор движения й» к следующему приближению х»+' по формуле [г» = — д»/[[я» [[. Ч1. Вычислить следующее приближение х»+' = х» + рй". НП. Положить А = й + 1 и перейти к шагу П. Замечание 5. Вектор д» является статистической оценкой граДиентного напРавлениЯ фУнкции 1е в точке х» (пРи и -ь оо, У вЂ” ь О л» стремится к направлению градиента Ч(е (х»)), Библиографические ркоаакпа. При написании параграфа нспольаована рабо. та [3261. Лополнительиые сведения о методах локального случайного поиска мож. но найти в раеогах [326 †3, [77, !78[ и в сборнике статей [41. 3.5.
Псевдоградиеитиые методы адаптации и обучения 3 а д а ч а 1. Найти агд ппп 7» (х) для заданной функции кем" [и: В" ~ В'. Псевдоградиентные алгоритмы адаптации и обучения основаны на предположении, что существует некоторая детерминированная гладкая функция 7',: В"- Вх, называемая критерием оптимальности. Этот критерий либо задан априорно (если, например, исходная задача заключается в минимизации функции 1е (х) = 1» (х)), либо может вводиться искусственно. Если минимизируемая функ- циЯ 7» — гладкаЯ, то1, (х) — = )е (х) и в псевдогРадиентном алгоРитме в качестве вектора $», определяющего направление движения к следующему приближению х»+', выбирается псевдоградиент функции 7». Если минимизируемая функция 1» — негладкая, то в качестве вектора Р выбирается псевдоградиент некоторой специально постРоенной вспомогательной гладкой фУнкции 7» точки минимУма которой являются точками минимума функции 7,.
Например, если точка х* является точкой минимума функции 1», то в качестве фУнкции 1» можно выбРать 1, (х) = ) х — х' ,'1 Чтобы этот пример не показался бесполезным и не вызвал недоразумений (ведь нам нейзвестна точка минимума функции )е), следует отметить одно чрезвычайно важное свойство псевдоградиентных алгоритмов — эти алгоритмы не требуют вычисления ни значений 7, (х), ни градиентов Ч1, (х) для функции г„они требуют только вы- чнслениЯ псевдогРадиентов 6» длЯ фУнкции 1» в точках х = х», а псевдоградиент $» часто можно вычислить косвенным путем, не зная точки х*. Оаределглие 1. Вектор в» называется псевдоградиентом функ- !54 ции 1! в точке х = х»,если он является реализацией некоторогослу- чайного вектора $, удовлетворяющего условию (Ч)'! (х»), Е$) ~ О.
Приводимые ниже теоремы о сходимости псевдоградиентного ал- горитма адаптации и обучения позволяют с единой точки зрения обосновать сходимость многих алгоритмов стохастической аппро- ксимации, случайного поиска, обобщенного градиентного поиска н др. Предположения 1. (1) — функция г! ограничена снизу 1! (х) л 1,* ) — оо; (И) — градиент функции 1! удовлетворяет условию Липшица $$%7»(х) — Ч~!(у)Д~~ЧЦх — у(, Ух, у~В", у(оо.
Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение х' б 1)". !1. Положить й = 1. О с н о в и о й ц и к л. 1П. Найти значения р» и Л„удовле- творяющие условиям теоремы 1. 1Н. Вычислить псевдоградиент Р функции 1, в точке х», т. е. вычислить одну реализацию я» случайного вектора $», условноема- тематическое ожидание которого удовлетворяет неравенству (Ч! ( ), Е(Р/в», Р, ..., $ — !))>О, (Предполагается, что Р и 1! удовлетворяют неравенству Е()(Р(»I$», ..., $» !)(Л»+ 6,~»(х»-!)+ + 6»(Ч)! (х"-'), Е(Р!$», ..., $»-!))), У. Вычислить следующее приближение х»+! х" — рД». У1. Положить й = я + 1 и перейти к шагу П1. Теорема 1.
Пусть выполняются предполозсения 1 и (й1)— Ю р»~0 Х Р» = оо Е р~~Л»~оо »-! »-! (1о) — Р и г! удовлетворяют неравенствам Е(!/Р(»IК! К' !) (Л»+ б,~д(х»-!) + + 6»(Чг»(х» — '), Е(Р!'а» ° ° $" ' )) (о)— ~ р'(оо или Л» О, 6,=0, 11шр»(2/уб». » ! 156 Тогда при любом хз последовшпельность (ха)а" и порожденная алгоритмом 1, почти наверное такова, что для нее суи]еспгвует предел последовательности (1з (ха))Г-з и 1пп(Ц,(х"-'), Е$а) ЫО. Теорема 1'. Пусть в дополнение к условиям теоремы 1 (и)— (Ч]".з(ха-'), Е Я/З', ..., $а-')) ~ 6(е) ) 0 пРи 1з(х"-') ~ ~~ + е для всех е ) О. Тогда, почти наверное 1!пт1з(ха) =/;, а»» Теорема 1".
Пусть в дополнение к условиям зпеоремы 1 выполнены условия (о!г) — множества (х ! ~з (х) ( сопз!) ограничены; (ти)— (Ч~ (х" ') Е(Р/зз $а-з)) >б(е))0 при !! Ч/з (х" ') ]! ~ е для всех е ) О. Тогда почти наверное найдутся подпосяедовательностпь (й,)з" з и точка ха такие, что Ч~з (х*) = 0; ]пихтач = х*; 1пп)з (х") = 1з (х').
l а»» Теорема 1"'.. Пусть в дополнение к условиям теоремы 1 множество Ха точек минимУма фУнкции 1з непУстое и (]к)— !п]~з(х))~; при йз(х, Х*)~е; л йз(х, Х*) = !и! !]х — у]!, ыах' (я)— (Чглз(ха з), Е(»кз»1»зз, ..., »з" ')) ~б(е))0 при йз(х, Х*) ив для всех е ) О. Тогда 1пп аз (х", Х') Ы 0; ]пп ~з (х") Я П. а-» «»Ф В частности, если Х* состоит из единственной точки х', то в.в. х" -и' хч при й -~ оо.
Библиографические указания. Параграф написан на основании работы (303]. 3.6. Квазиградиеитвые методы Задач а О. Найти агяппп1в (х) для слабовыпуклой вниз фУнкции 1а:В" †- В'. Определение 1„Функция 1а называется слабовыпуклой вниз, если для любого х из произвольного замкнутого ограниченного множества существует непустое множество 6 (х) векторов Ч)о (х) таких, что для всех г и ЧГо(х) р 6(х) 1о(г) — Г (х) ~(Чго(х), г — х)+ г(г, х) ~з.з> и г (х, у) 1 х — у ~~ ' -1- О равномерно по х при у - х.
Определение 2. Вектор Чго (х), удовлетворяющий неравенству (3.5), называют кгазиградиентом слабовыпуклой функции ~о в точке х. Слабовыпуклыми функциями являются дифференцируемые, а также выпуклые функции (не обязательно дифференцируемые).
Впервомслучаеквазиградиентомявляется обычный градиент, а во втором — обобщенный градиент. Класс слабовыпуклых функций оказывается замкнутым относительно операции взятия максимума, т. е. если г (х, у) — слабовыпуклые при каждом значении у функции, то (о(х) ~шахг(х, у) =1(х, у(х)) тат является слабовыпуклой функцией и Ч~д (х) ЧД (хэ у) (в вгз мах иим.
озу 1. Квззатрздаовтиый мотод мивамиззиав овзбовыиуилой вава Фуиииаа 3 а д а ч а 1. Найти агн пип Го (х) для слабовыпуклой вниз з функции гз: В"-» 11'. Множество решений Х' для этой задачи определим равенством Х*= (х / О Е б (х) ), где 6 (х) — множество квазиградиентов функции Го в точке х.
Сущность данного метода заключается в построении в й-й итерации квазиградиента слабовыпуклой функции в точке хз. Если движение в направлении квазиградиента выводит за пределы специальным образом построенного множества 3, то процесс построения такой последовательности точек прерывается, и алгоритм начинает работать с произвольной точки некоторого подмножества А с= 5. Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение хо, постоянную 6) О, шаговый множитель р,.
П. Построить множество Я по правилу 5 = я(Го(хо)+ 6), где Я (а) Й (х ~ ~о (х) ( а). 111. Задать произвольное компактное подмножество А множества 5. 157 1Ч. Положить й = О. Основной ци кл. Ч. Вычислить квазиградиент Ч1« (х«) фУнкции 1« в точке х".
Ч1. Вычислить вектор х« — р»Ч1«(х"), если х»+ р«Ч(о(х«)сВ, х'+' = у~А, если х'+ р»Ч1«(х») КВ где у — произвольная точка множества А. ЧП. Вычислить шаговый множитель р»+ь Ч1П. Положить я = й + ! и перейти к шагу Ч, Теорема 1. Вели выполнены условия: («) — Х Ь (х ! 0 6 0 (х)) к»мпактног (1«) — »1 (а) ~ (х ! 1« (х) ч а) компактно длЯ любого а; (и») — Функция (о принимает на Хе конечное число значений~ 11о) — шалавые мнсввители удовлетворяют условиям р»)0; р»-»О; р»+~/р«-+1; ~ р» = со. «=о то любая предельная точка последовшпельности (х»)» о, порож денной алгоритмом 1, принадлежит множеопву решений Х" зада- чи 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
