И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 75
Текст из файла (страница 75)
Пусть функция 1» (х) имеет вид г Ра(х) =,Е, РА (х), 40$ где РсР б. Х Рс = 1, и пусть функции 1с (х), с = 1, ..., г — дважс=! ды непрерывно дифференцируемы. Введем случайную величину т, которая принимает значения 1, 2, ..., г с вероятностями р„р„...,р,.
За вектор стохастического квазиградиента в й-й итерации можно взять 1т»("'+ а»Р ') — 1ч»("")»д где т» — реализация случайной величины т в й-й итерации, вектор р ' и числа з», с»» такие, как и в примере 1. Условное математическое ожидание такого вектора й'(ь'1х») =+ Ч (х») + о"Л где о» вЂ” некоторый случайный вектор, измеримый относительно зз», ~ 0 )) ~~ сопз(. Пример 3. Пусть функция 1» (х) имеет вид 1»(х) = спах1(х, у), »Яг где ! (х, у) — выпуклая вниз по х, дважды непрерывно диффереицируемая по х при каждом у функция; У вЂ” выпуклое компактное множество.
Обобщенным градиентом функции !» в точке х является вектор !тс (.) (д1(х, У) д1(х, У) » дх! ' ' ' дхсс где вектор у (х) такой, что 1(х, у(х)) = псах1(х, у). »ег За вектор стохастического квазиградиента в Ьй итерации можно взять »» ч'с 1(»»+а»р ' У(х»)) — 1(х» У(»»)) а».
а» ! ° в ! где вектор р ' и числа с»», з„определяются как и в примере!. Условное математическое ожидание такого вектора равно й) ($~1х') = + су1, (х') + о"Л», где о» вЂ” некоторый случайный вектор, измеримый относительно дз», ! о» )) ~ сопзй Пример 4. Если !» (х) = КГ (х, ес) и выполнены требования, достаточные для дифференцирования под знаком математического ожидания, то в качестве С» можно брать 7»Р (х', !о), так как Е (Рlх») = Ч~, (х»), или е» Чт е (х»+ а»р и) е(х» о) о4е а» ! ю й! где р" определены в примере 1. 1. Метод ироевтироваиив стовастичесиив аваоитрадиеитов Алгоритм 1 Н а ч а л о.
1. Выбрать произвольную начальную точку хо Я Е й", для которой Е (( хо )(» < оо, задать последовательность шаго- вых множителей (р»)»" о и последовательность нормирующих мно- жителей (у»)Г о. 11. Положить Ь = О. Основной ц и кл. П1.
Вычислить случайный вектор 9» (о!), условное математическое ожидание которого Е(9'Ухе, ..., х») = а„7~,(х»)+ Ь", где ໠— неотрицательная случайная величина и Ь»= (Ь|, ..., Ь,)— случайный вектор, зависящие от последовательности хо, ..., х», или, более точно, измеримые относительно о-подалгебры а)», инду- цированной семейством случайных величин (х', ..., х»); Цо (х')— обобщенный градиент функции (о( ) в точке х». 1Ч. Вычислить вектор х»+! = пх (х' — р»у»9» (о!)), (6.99) где и» вЂ” оператор проектирования на множество Х.
Ч. Положить Ь = Ь + 1 и перейти к шагу П1, Теорема1. Пусть имеют место предположения 0 и пусть, кро- ме того, для любого числа и! ( оо найдется такое число с„( оо, что Е()(9»()»/хе, ..., х»)<т)'(с при ((х'(((и!, ! =О, ..., й, Кроле того, величины р», у» измеримы относительно 3» и та- кие, ипо у»> О, у»(т)»+ т,((х»() (сопз1, где т» = 1 при ~Ь»)(ныл; т» = 0 при ((Ь»~ = 0; р» ~ О, ~~ р»а» — — оо, Ч~~~ Ер»(Ь»(( оо.
» о »-о Тогда найдется подпоследовшпельность х»' последовательности (х»)» !, порожденной алгоритмом 1, для которой 1)ш~о(х"!) = 1»(х*) и. и, !-~ о 407 1пп пи(п1»(х') = 1»(х') и. н. »- !к» Теорема 1'. Пусть в дополнение к условиям теоремы 1 множество Х' ограничено. Тогда !п1 Е~1«" — х»'1»-ч-О при lг-«со.
'ех Для последовательности точек х», х', ..., порожденной алгоритмом 1, в котором на шаге 1Ч процедура (5.96) заменена процедурой х"+' = пх (х" — рД' (а)), имеет место следующая теорема 1", дающая оценку скорости сходимости. Теорема 1". Пусть выполнены предположения О и пусть существуют такие постоянные р и Х, что 1,(х) >1»(х')+ Р'1«* — х'1» при х е Х, и с вероятностью 1 Е(Д»(»Ь, ..., «)<Л. Кроме того, р» детерминированные и а» «а)О, 10»(<г», г»(р„, г»<г<2ра. Тогда существует такое число с,( сопз1, что при р, = с»lя последовательность (х»)~ ь с.
вероятностью 1 сходится к единственному решению х», причем Е(х* — х»!/» = 0(11й). Определение 1. Пусть 6 — некоторое подмножество пространства В". Последовательность г' (в), з = О, 1, ..., случайных векторов называется случайной квазифейеровской последовательностью относительно множества 6, если для произвольной точки у а 6 Е(1у — г'+'(!»Iгь, ..., г')((у — г'"1»+ (у„в=О, 1, ..., где случайные величины В', (ь») ~ О являются измеримыми относительно о-подалгебры Й„индуцированной семейством (г', ..., г*) и такими, что ~ Ейг,< оо, -ь Теорема 1"'.
Пусть имеют место предположения О и пусть т1»вЂ” случайная величина, измеримая относительно о-подалгебры З», индуцированной величинами (х', х', ..., х»), такая, что для любого ш и некоторого числа с„ Е(1$»1»/«4..... х»)(Ч»»(с (8.07) 408 при 1х'~( и!, в = О, 1, ..., й; нормируюи(ий множитель 7» для некоторых чисел у, у удовлетворяет условию О < у < у» (!)» + т» !! х' !! ) < у < оо, где т»= 1, если )! Ь" 1) 0 и т» = О, если !) Ь» ( = 0; величины р», !х», Ь» такие, что р») О, а»,,» О, ~ К(р»'1Ь»(+ р»») < оо; (З 99) начальная точка х» такая, ипо К Ц х' 1)» < оо. Тогда последователь- ность точек х", Ь = О, 1, ..., порожденная алгоритмом 1, является случайной квазифейеровской относительно множества Х».
Если же, кроме того, с вероятностью 1 р»а» — — оо, »=ь то почти для каждого !о последовательность (х» (ь»))»» сходится к некоторому элементу х* (ы) б Х». Замечание 1. Условия теоремы Г" легко проверяются при реп)енин конкретных задач. Заметим, что К(!Р6'Ю») = Х 11Ю1Е»)+»Я1»(х»)Ъ+ + 2~~(Ч~.(х") Ь')+НЬ" 1' отсюда, например, следует, что если сумма дисперсий ~, В ($7/08») /=! компонент вектора ~»1~ ($~!, ..., $,',) ограничена в области Х, а также ограничены а», ( Ч7» (х») ), ) Ь» !1, то !)»= сопз1, т. е.
(5.97) выполняется. Справедливость этого условия в реальных задачах обычно является следствием ограниченности области Х. Замечание 1'. Если "область Х ограничена, то утверждение теоремы 1" остается справедливым при у» = сопз1. Замечание 1". Утверждение теоремы 1"' остается справедливым также и при следующих (иногда полезных) изменениях условий; '1 Ь" ~ удовлетворяет условиям, аналогичным (5.97) т. е.
~ Ь» ~ < с,„ при)х')~ < и!, з = О, 1, ..., й; нормирующий множитель у» удовлетворяет условиям О < у < у»ЧА г»~ у < у» (1 + Н х Н ) П Ь 1$ < б где у — некоторое число; б», 㻠— величины, измеримые относительно Й»; вместо (5.98) справедливы условия р» В 0; а » 0; 1, К (р»б + р'г') < оо, ь=о 409 3. Стодествчесива метод соврет»еиии веси»од и детермииироееивмд еедечед 3 а да ч а 2.
Найти агя ппп ~с(х), где »' = Х П (х(Д~(х) ( О, «ах у'= 1, ..., т), Х~ Š— заданное множество, а Д,: Е"-»- Е', 1 = = О, ..., и» вЂ” заданные функции. Предположения 2, (») — функции 1~ ( ), 1 = О, 1, ..., т — непрерывные н выпуклые зннз в области Х; (И) — множество Х выпуклое н замкнутое; (1И) — ограничения задачи 2 удовлетворяют условию Слейтера, поэтому функция Лагранжа ~р(х, и) = ге(х)+ ~, 'иД(х) (з.зз) ! имеет седловую точку (х', и') в области х~ Х, и в О (и = (и,, и, ..., и' )), причем множество (ие) компонент седловых точек )(р = ((хе, ие)) ограничено.
Стокастнческнй метод сокращения невязок является своеобразным стохастическим вариантом градиентного метода Эрроу — Гурвнца. Однако, здесь не делается предположения о точном вычнсленнн функцнй ~г (х), / = О, 1, ..., гп. Стохастнческнй метод сокращения невязок основан на применении функции Лагранжа (5.99), седловые точки которой вычисляются с помощью методов стохастнческнх квазнграднентов. Алгорип»лс 2 Н а ч а л о. 1.
Выбрать начальную точку (хс, и') ~ Е":к Е, для которой Е (~ хс'1» +( ис ~~) ( со 11. Выбрать последовательность щаговых множителей (р,)» с (нзмернмых относительно Ю»). 111. Выбрать последовательность нормнрующнх множителей (у»)"„с (нзмернмых относительно Й»). 1Ч, Положить й = О. О в н о в н о й ц н к л.
Ч. Вычислить реализацию случайного вектора Р, удовлетворяющего равенству Е($»1(хс, и'), ..., (х", и')) =о.»Ч,Ч(х», и»)+ 6», где случайная величина сс») О н случайный вектор 6» измеримы относительно о-подалгебры Й», нндуцнрованной семейством величнн (х', и'), ..., (х", и»); Чд (х», и') — вектор обобщенного граднента функции Лагранжа (5.99) по переменной х прн фиксированном и в точке (х», и'). Ч1, Вычислить реализацию случайного вектора (,», условное математическое ожидание которого Е(ь»1(хе, ие), ..., (х", и»)) = а Ч„~р(х», и»)-+ У, где Ỡ— случайный вектор, нзмернмый относительно о-подалгебры Я»; Ч„~р (х», и») — градиент функции Лагранжа по переменной ао и при фиксированном х в точке (х', и»), который равен вектору (1» (х»), 1» (х), ..., 1 (х")).
Ч11. Найти точку (х"+', и»+') по формулам х"+' = пх (х' — р»уД»); и"+' = пи (и» + р»уД»), где пи — оператор проектирования на выпуклое и замкнутое мно- жество (1, содержащее компоненты и* седловых точек (х*, и*) функ- ции Лагранжа <р (х, у) в области х ~ Х, и > О. ЧП1. Положить й = й + 1 и перейти к шагу Ч, Теорема 2. Пусть имеют место предположения 2 и, кроме того, 1» (х) — строго выпуклая функция. Пусть т1» — случайная величина, измеримая относительно о-подалгебры Й», индуциров нной величи- нами (х', и'), ..., (х», и») такая, что Е(Ца-"Ц'+ЦЫЦ'1(»', й), ....
(х', и»))<ЧХ<с.( при Ц х' Ц + Ц и' Ц ( ш ( оо, з = О, 1, ..., й; нормируюи(ий множи- тель у» для некоторых чисел р, у удовлетворяет условию 0<у(у»(т)»+ т»Цх»Ц+ О»Ци" Ц)(у< оо, где т» = 1 при Ц Ь» Ц ) 0 и т» = 0 при Ц Ь» Ц = 0; О» = 1 при й» Ц ) 0 и О» = 0 при Ц й»Ц = 0; величины р», а» и векторы Ь", й» такие, ипо р»~0, а»~~»0, 2, Е(р»ЦЬ»Ц+р»Цй»Ц+р»)<оо. (а.1оо] » О Тогда последовшпельность точек ((х», и»))Р=о, порождаемая алгоршпмом 2, является случайной квазифейеровской последовательностью относшпельно множества седловых точек В'. Если при етом с вероятностью 1 ~ р»а» = оо, » а то с вероятностью 1 одна из предельных точек последовательности (х»)»» принадлежит Х», т.
е. почти наверное 1пп (ш(п 1»(х»)) = 1»(х*), х'~ Х*. в.ьсо Оч»к» Замечание 2. Утверждение теоремы 2 остается справедливым при условиях р»~0, а»)0, ~, Е(р»б„+р»»г~~)<оо; »=о ЦЬ»Ц+Цй»Ц<с„при Цх'Ц+Ци'Ц(го, з = О, 1, ..., й; нормирующий множитель у» удовлетворяет условиям 0 < у < у»ч» ( г» < оо; 2((1+ Цх»Ц)ЦЬ»Ц+ (1+ Ци»Ц)Цй»Ц:я б», 411 где 7 — некоторое число; величины г„, 6, измеримы относительно Юд. Замечание 2'.
Если предположить, что функции );( ),) = О, 1, ... , т, вычисляются точно и функция Лагранжа имеет по х вторые производные, ограниченные в области х Е Х, и р У, то на шаге Ч алгоритма 2 можно взять вектор ед <р(хд+Ьдрд', ид) — р(хд, ид) д,е 'д, ~1 где р ', з = 1, ..., з, — серия независимых наблюдений вектора (тд„..., р„) с независимыми и равномерно распределенными иа [ — 1, И компонентами в )д-й итерации, причем зд)~ 1, еда~ О; на шаге Ч1 алгоритма 2 в качестве ьд можно взять вектор ~" = 3 (~д( » Тогда Е®®д) = '3' Чхр(х', ид)+ одй где (! од() ( сопз(; Е(ьд!йбд) = 3 7„<р(хд, ид).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
