И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 25
Текст из файла (страница 25)
В теореме 2" утверждается, что прн наличии аддитивной помехи для сходимости в среднем достаточно условий ~~ р» оо; р» -» О при й -» оо. Скорость сходимости Ег, (х') зависит от скорости убывания р», причем оценка для Ег» (х») не лучше, чем О (1/й). Замечание 2. Если функция г, (х) имеет единственную точку минимума х*, причем выполняется условие г,(х)~»Чх — хь~', Л)0 '119 (например, если г, (х) сильновыпукла), то из сходимости Ег, (х») -а -» О следует средняя квадратическая сходимость х» к х', т.
е. Е(~!х» — хв(»)-аО при /в-~-оо. 3. Схояпмость алгорптма почта пааеопое Теорема 8. Если выполняется условие (в) теоремы 2 и 60 Х )в»т»( оо то последовательность (х )» в, порожденная алгоритмом 1, тако- ва, что п.в. г,(х»)-аО (т. е. Р(г,(х»)-в О) = 1). При этом для всех ее ) О, /ге ~В О, Р(г»(х»)~(ев, А~У») ~1 — Ег»(х»)+ Х )»»т» /ев. »=»в Если, кроме того, 1пп р»~ у ) 1, то для всякого 1» = О найдет» м ся 1, 1» (1„Е«» (хе)) такое, что » †! Р г, (х») ((1, + 1») П (1 — т,) для всех /» ~ 1 — 1,/1„ »т о а если у»~ у ) 1 для всех /в, то »-1 Р г, (х») ( (1» + Ег, (хв) + р,/(у — 1)) П (1 — т,) для всех /» в ~ 1 — Егд (хв)/1» — р»П» (у — 1).
Теорема о'. Если выполняются условие (1) теоремы 2', условие 60 (1)теоремы 2"' и ов = О, либо ~; рт» ( оо, то «» (х») -1 О. Если, »-о кроме того, йр» монотонно убывает и /гр» -в- р < О-', то для всякого 1» ) О найдется такое 1, = 1, (1,, Ег, (х')), что »! -а~в~ Р г,(х")<(1,+1,)е '-' для всех я ~~»1 — 1»/1».
Е частности, если р» = р/я, я ~ 1, рО < 1, то для всякого 1, ) О Р (г,(х») < 1»/Аоа для всех У~» 1),:» ~в 1 — Е«, (х')П» — Хо'р'О/(1» (2 — Хрт) (1 — рО)). Замечание 8. Если функция г, (х) имеет единственную точку минимума хв и г» (х*) = О, 1п1 «,'(х) ) О при некотором е О, 1»-в*1 ьв то из сходимости г, ~х») -а О следует, что х» -а хв. »20 4 Модвфвваивв алгоритма Если условие 2 в алгоритме 1 заменить на 2' (Чг,(х), Е$~)~ — Ц, Ць эО, [)ь-ьО, то при Рь = оо 2л Рата ( ос~ лл Рз чь ( оо Х вЂ”, Х чч !+! ь-о з-о а-о последовательность (х") ь о, порожденная модифицированным алгоритмом, такова, что г, (х') сходится почти наверное к пределу, а !пп ()7гт (хь), Е$з) Ы О.
Если на шаге Ч1 алгоритма 1 следующее приближение х'+' вычислять по формуле хе+' = пх (х" — рдь), где пх — оператор проектирования на некоторое множество Х, то для такого алгоритма все предыдущие теоремы остаются справедливыми. БиблиограФические рхавгиия. Параграф написан на основании работы [296). Результаты типа теоремы 2"' о сходимости алгоритма 1 [но с менее полными опенками скорости сходнмостн) приведены в [3, 263).
Утверждения о сходимости почти наверное в условиях теоремы 3' приведены в [3, 2631, [ч36). Вопросы локаль. ной сходимости рассматривались в [213, 6131. В [2971 для линейного случая приведены более точные опенки сходимостн алгоритма !. 2.9. Стохастическке кваанградиентные методы 1. Обвгвй стохаетвчесввй вваавградвентвый метод дла детерминированных задач 3 а д а ч а 1. Найти агя ппп го (х) для заданной функции к 1о Предположения 1.
(з) Функция 1о непрерывно дифференцируема; (Й) градиент функции [о удовлетворяет условию Липшица, т. е. для любых точек х, у [ Ц, (х) — 7~о (у) $ < у [[ х — у ~, О < у < оо. В стохастических квазиградиентных методах последующие приближения к искомому решению находят в направлении стохастического квазиградиента — случайного вектора йа, условное математическое ожидание которого в некотором смысле близко к градиенту (или обобщенному градиенту) рассматриваемой функции, т. е.
Е(йз/хе, ..., х") = аат[о(х ) + [з~, [за-ьО, аа-ч-соп51) О. 121 Алгоритм 1 Н а ч а л о. 1. Выбрать произвольную начальную точку х» ~ »»" и числа Ро 7». 11. Положить й = О. О с н о в н о й ц и к л. 1П. Вычислить реализацию я» случай- ного вектора $, условное математическое ожидание которого удов- летворяет равенству Е($1х», ..., х") = а»71»(х»)+ Ь", где ໠— неотрицательная случайная величина и Ь» — случайный вектор, измеримые относительно о-подалгебры З», индуцированной семейством случайных величин (х', ..., х»); ч)» (х») — градиент функции 1» в точке х». 1Ч. Вычислить вектор х»+' = х» — р»уД». Ч.
Вычислить шаговый р»» ~ и нормирую»ций у»» ~ множители. 1Ч. Положить й = й+ 1 и перейти к шагу Ш. Теорема 1. Пусть: выполнены предположения 1 и, кроме того, для каждого числа 6 ( оо существует число Сь( оо такое, что ) И» (х) ) (С» при 1» (х) < 6; Ч (ю) — случайная величина, изме- римая относительно о-подалгебры Й», индуцированной величи- нами (х', ..., х»), такая, юпо для любого 6 ( оо и некоторого чис- ла сь Е (1$» )ч1хо, ..., х») ( тЯ ( с при 1» (х') ( 6, з = О, 1, ..., я; нормирующий множитель у» удовлетворяет условию О ( у ( у»»1» ( г» ( оо; кроме того, величины р», ем измеримые относительно о-подалгебры Л», такие„что р» ) О, сс»» О, »Ь»1!а»-» О равномерно с вероятностью 1 и Х Е (р» Ф ~+ р»г») ( »=о \» Х Р»а»Ы оо.
Тогда последовательность (х» (ю))»=л, порожденная алгоритмом 1, такова, опо почти для каждого ь» последовательность Д (х» (ь»)))»=о сходится, и ~!Ц»(х (ю))1-»О почти наверное при з- оо для некоторой подпоследовательн ости (х (ьэ)):-ю Теорема 1'. Пусть выполнены предположения 1 и, кроме того, для каждого числа 6 ( оо существует число Сь ( оо такое, ипо ~~ 71» (х) 1 ( Сь при ~» (х) ( 6; а» а»» 1; й, (о») — случайная величина, измеримая относительно о-подалгебры Й», индуцированной величинами (х», ..., х») такая, что для любого 6 и некоторого числа сь ( оо » Х П(~,Ь, .... ")(~(с» 122 при (е (х') < б, з = О, 1, ..., й; нормируюи(ий множитель уа удовлетворяет условию О < у < узда < ге < оо; кроме того, величина ре, кю измеримые относительно о-подалгебры Зе, и такие, что р„в ,> О, ре-» О, ! Ье)-» О равномерно с вероятностью 1 и 2„й) (р„((о» ~~ + р'„г'„) < с вероятностью 1.
Тогда последовательность точек (ха(ю))» е, порожденная алгоритмом 1, такова, что почти для каждого ю последовательность (Де (хе (и))),",=с сходится, причем 1Ч1е (х" (ю))1-» -» О почти наверное при в-~- со. С л е д с т в и е. Велите (х) унимодальна, т. е. имееттолько глобальный экстремум, и(( Ч1е(х) ! ~ О во всех точках х, за исключением оптимальных, то из теорем 1 и 1' следует, что последовательность (1е (х" (ю)))а с почти наверное сходится к глобальному экстремуму. 2. Общий стохасткческий кказитрадиеитиый метод длл стохастических задач 3 а д а ч а 2. Найти ага ппп Кфе (х, ю) для заданной функции ~ре: Л" Х а-» И'. Предположение 2. Функция (е (х) ~ Е~ре (х, ю) дважды непрерывно дифференцируема.
Алгоритм 2 Н а ч а л о. 1. Выбрать: произвольное начальное приближение хе ~ В"; начальные значения нормирующего и шагового множителей р„и у„, начальное значение величины смещения Ле (числа р„ у, и Ле выбираем в соответствии с условиями теоремы 2). 11. Положить й = О. 0 с н о в н о й ц и к л. 1П. Выбрать натуральное число в, ~ 1.
!Ч. Найти (вд')'е, — серию независимых наблюдений вектора $ = ($ы ..., $„) с независимыми и равномерно распределенными на ! — 1, 11 компонентами в я-й итерации. Ч. Найти (юе')',е, — серию независимых по й = О, 1, ..., наблюдений состояний природы в. Ч1. Вычислить вектор Ые а+1 е ч %е(х -)-аа! и ') те(х~, и ') ь в=! ЧП. Вычислить шаговый множитель ре+ь нормирующий множитель ус+1 и смещение Ле+ь удовлетворяющие условиям теоремы 2. Ч111. Положить я = я +! и перейти к шагу 1П. Теорема 2.
Пусть выполнено предположение2 и условия: (1)— (»» (е») — случайная величина, измеримая относительно о-подалгебры 2)», индуцированной величинами (хе, ..., х»), такая, что для любого а и некоторого числа т (а) < ео е тр(».»*'»-»»". '» — ».»", ье»»к.,„,) „,П,»„» »=» ~» при 1» (х') < а, з = О, 1, ..., й; (й) — нормируюи(ий множитель у» удовлетворяет условию 0 < у < у»(»» < г» < оо; (Ш) — величины р», г», Л», измеримые относшпельно о-подалгебры З», и такие, что р» р О, р» -»- О, Л» -» 0 равномерно с вероятностью 1 и Е Е (р»А + р»г») < Е р» = ° » 0 »-е с вероятностью 1.
Тогда последовательность точек (х" (е»))» е, порождаемая алгоритмом 2, такова, что почти для каждого е» последовательность (~е (х»))»-е сходится, причем ( Чге (х» ) )) -~ 0 почти наверное при з-е оь для некоторой подпоследовательности й,. 3. Стехаетвчееквй каааиградиеитвмй метод е процедурой прерыкавия Зада ч а 3. Найти агяппп1»(х) для непрерывно дифферене цируемой функции 1»: В" -»- Е'. Стохастический квазиградиентный метод с процедурой прерывания основан на построении в й-й итерации вектора стохастического квазиградиента $», условное математическое ожидание которого ЕЯ1хе, ..., х") Ч~ (х») -(-6», где Ь» — вектор, измеримый относительно о-подалгебры Й», индуцированной случайными величинами (х', ..., х").
Если в какой-то итерации движение по стохастическому квазиградиенту выходит за пределы сферы определенного радиуса, то происходит прерывание, и алгоритм начинает работать с произвольной точки, принадлежащей наперед заданному ограниченному замкнутому множеству. Алгоритмы такого рода отражают те часто встречающиеся на практике ситуации, когда в процессе вычислений приходится менять либо параметры алгоритма, либо сам алгоритм. Алгоригпм Я Н а чало. 1. Выбрать произвольнуюконстанту а(О<а <ее) и задать произвольное замкнутое множество В, содержащееся в сфере радиуса а, т. е. В с 5 Ь (х((х)) <а).
Выбрать произвольную начальную точку хе с В. 11. Задать правило формирования последовательности щаговых множителей (р»)»-ы 124 П1. Положить А = 0; найти р,. Основной ци кл. 1Ч. Вычислить случайный вектор $», удовлетворяющий условию Е(Р!хе, ..., х») = Ч~е(х»)+ Ь», где Ь» — вектор, измеримый относительно о-подалгебры Ьг», инду- цироваиной (хе, ..., х»).
Ч. Вычислить вектор х» — рД», если ( х» (а) (( а; х»+' = г'+' Е В, если ( х'(а)( ) а, где г»+' — произвольная точка множества В. Ч!. Найти р»с.ь ЧП. Положить й = й+ 1 и перейти к шагу 1Ч. Теорема 8. Пусть !с непрерывно дифференцируема функция и выполнены условия: (1) — существует такая постоянная 6, что 1Ц»'1+ ЦЧДе(х»)1+(Ь»((6; (й)— гпахДе(х) ( !п( !е(х); лов 3ье>а (еы) — величины р», измеримые относительно а-подолгебры Й», удовлетворяют условиям р» в О, ~; р» = со„~ р»(Ь»~( оо п.
н.; »-с »-с ~, Ер»( со. Тогда последовательность (х» (аЦ„с, порожденная алгоритмом 3, такова, что почти для каждого а последовательность (!е (х» (а)))» е сходится и любая предельная точка последовательности (х» (а))» с пРинадлежит Хе а (х ~ фе (х) = О) почгпи пРи каждом а. Замечание 3. В данной теореме, в отличие от теоремы 1, не требуется глобального условия Липшица. Имеющиеся в теореме 3 условия равномерной по й ограниченности (условие (1)) легко ослабить, используя нормирующий множитель у», Эти условия ограниченности, однако, выполнимы, если только точки х» изменяются вограниченной области, а случайные помехи имеют усеченные законы распределения, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
