И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 32
Текст из файла (страница 32)
2. Стовастическвй кваеитрадиевтвмй метод мввимваацвв слабовыиуквой функции Алгоритм 2 Н а ч а л о.м1. Выбрать произвольную константу а Е (О, оо) и произвольное замкнутое множество В, содержащееся в сфере ра- -диуса а, т. е. В ~ 5 Й (х((!х((а), выбрать произвольную на- чальную точку хо Е В . П. Задать правило формирования последовательности щаговых множителей (р«) «-о. П1. Положить я = О, найти ро.
О оно вне й ци кл. 1Ч. Вычислить случайный вектор и«, условное математическое ожидание которого Е(РI»с, ..., х») = Ч~о(х")+ 6», где Ь» вектор, измеримый относительно о-подалгебры Й«, индуци- рованиой случайными величинами (хо, х', ..., х»); Ч1» (х») — квази- гРадиент слабовыпУклой фУикции 1«. Ч. Вычислить вектор х« — р,д», если 1«е((а, х"+' = г'+' Е В, если 1»«() а, где г«+' — произвольная точка множества В.
Ч1. Найти р«ч ь $58 ЧП. Положить й = я + 1 и перейти к шагу 1Ч. Теорема 2. Пусть[» слабовыпуклая вниз функция и, кроме того, выполняются условия (»)— шах 7»(х) ( [п1 )о(х); гав «лана (11)— ~~[+ Ф~. (")[[+ [д" [~(~: (111) — ии7говые множители р», измеримые относительно о-подалгебры 3» и таковы, что р,-. О, р»+1[р» 1, 2,'р»= «=о ~', р»[[Ь»[[( оо и. н, ~„Ер»»( ао.
Тогда почти при каждом «о предельные точки последовательности (х» (ь«) ) ь-о, порожденной алгоритмом 2, принадлежат миожесгпву Хо«» (х [ О Е 6 (хК, и последовательность (7» (х» («а)))» о сходится («г (х) — множество квазиградиентов функции 7» в точке х). Библиографические указании. Параграф написан нн асноннннн работ [267, 268, 269, 272, 153, 2741. ЗЛ.
е-кваанградиентиые методы 1. е-кненвсрнцвевчвмй метод мквкмкннцвв н»«вуклмн функций 3 а д а ч а 1. Найти агд пцп 7» (х), )». И"-» 11« — выпуклая »67« функция. За направление движения к следующему приближению х»+» в данном методе выбирают е;квазиградиент выпуклой функции 7» в точке х». Алга)в«тм 1 Н а ч а л о.
1. Выбрать произвольное начальное приближение х' Е В", шаговый множитель р и число е», удовлетворяющее условиям теоремы 1, и некоторую константу с« ~ 1. П. Положить й = О. Основной цикл. П[. Положить е=е». 1Ч. Вычислить е-квазиградиент дг (х») функции 7» в точке х". Ч. Вычислить нормирующнй множитель 1, 1д,(х»)~[(а, 1д, (х») Г, /[д, (х») [!) а. У1. Вычислить следующее приближение х»~-' = х» — р~у»яг (х»).
Ч11. Вычислить шаговый множитель р»+~ и число е»+ь удовлетворяющие условиям теоремы 1. У1П. Положить й = й + 1 и перейти к шагу 1П. Теорема 1. Пусть функция 1, выпукла и множество Хеь» 1~ (х ) 0 Е О (х, 0)) (здесь О (х, е) (е ~~ 0) — множество е-квазигра3иентов функции 1, в точке х) компактно. Тогда, если числовые по. следовательности (р»)Ге и (е»)» е таковы, что р»-»+ О, е»-»+ 0 при й-» оо и ~ р» = оо, то предел любой сходящейся подпоследовательности последовательноапи (х»)»=е, порожденной алгоритмом 1, принадлежит множеству Х*. Теорема 1'. Пусть функция 1, удовлетворяет условиям теоремы 1 и е» = сопз( ) О, й = О, 1, ....
Тогда, если числовая последовательность (р»)»-е такова, что ее р»-»+ 0 при А-» оо, ~~ р» — — оо, то существует подпоследовательность (х»е) -е последовательности (х»)» е, порожденной алгоритмом 1, сходящаяся к множеству Х; с» (х ) 1, (х) ( пип 1, (х') + е). 2. е-кааеаградиевтвыв метод мвиимкеавии слабееывувлыл фувквий 3 а д а ч а 2. Найти ага гп!п 1, (х) для заданной слабовыпуклой функции 1,: В" -» В'. В данном итеративном методе последующее (й + 1)-е приближение х»+' выбирают в направлении е-квазиградиента у, (х») для функции 1» в точке х» (й-м приближении). Определение 2. Вектор д, (х) называют е-квазиградиентом слабо- выпуклой функции 1, в точке х (е ) 0), если для всех г с В выполняется неравенство 1» (2) 1»(х) еее (ке (х) 2 х) + Г (х 2) е и отношение — ' стремится к нулю равномерно по х при 2-» х г (х,г) )~ г — х1 (в каждом компактном подмножестве нз В ).
Если функция 1, определяется равенством 1»(х) = шах9(х, у), еаг где множество )г компактно, а у (х, у) непрерывна по совокупности переменных и равномерно слабовыпуклая по х для каждого у, 160 то е-квазигРаДиеитом фУнкции го в точке х ЯвлЯетсЯ квазнгРаднент функции ~р (х, у) по х в точке х = х, где у — произвольный вектор из множества У," (х) Е) (уо ) ~р (х, уо) го ор (х, у) — е, Ч у Е 1«). Алгоритм 2 Н а ч а л о. 1.
Выбрать произвольное начальное приближение хо С 11", некотоРУю постоЯннУю б ) О, шаговый множитель Ро и величину е„удовлетворяющие условиям теоремы 2. 11. Положить й = О. Основной цикл. !11. Если го(хо))го(хо)+б, то положить х"+' = хо и перейти к шагу Ч1; иначе перейти к шагу 1Ч. 1Ч. Вычислить и„-квазнградиент д,, (х") функции 7о в точке х". Ч. Вычислить следующее приближение х'+' = ' — Рой.,(х"). Ч1, Вычислить шаговый множитель роь1 и величину ео+ь удовлетворяющие условиям теоремы 2. Ч11. Положить й =. й + 1 и перейти к шагу 111. Теорема 2.
Пусть функо(ия 7о слабсвыпуклая и выполнены условия: (1) — множества ~(х) го (х) (а) компактны при всех а; (й)— множество Хо,(й (х ) О с 6 (х, О)] компактно; («И) — числовые последовательности (ро)Г-о, (ио)о..о таковы, что ро-»+О, ро+~lро-»1, ео-;»+О Ф« О« при я-» со, ~'„ро = оо, ~', е ( со. Тогда предел любой сходящейся о-о о=о псдпсследовательности последовательности (хо) о о, порожденной алгоритмом 2, принадлежит множеству Х*. Замечание 2.
Чтобы избежать вычисления на каждой итерации значения функции 7о (хо), шаг 1П алгоритма заменяют на ПГ. 11Г. Если )~ хо)) ) р, то положить х'+' = хо и перейти к шагу Ч1; иначе перейти к шагу 1Ч (здесь константу р выбирают из услоВия го (х))[о(хл) + б при (х1) р). Боблиооросоиооокое у«агония. При написании параграфа испольоооаим работы 1275, 272, 2041.
3.8. Методы обобщенных почти градиентов дла нщвнмнвштощ фуннций, удовлетворяющих локальному условию Лнпшнцв 2. Дооорнииироииииый скучай 3 а д а ч а 1. Найти агн ппп 1о (х) для функции)о: 11" -» В', «ел удовлетворяющей локальному условию Липшица. 6 о-зо !6! Если существует практически аффективный способ вычисления обобщенного почти градиента у (х) функции г» (х) в любой точке х р В", то за направление движения к следующему приближению х»+' в приводимых ниже алгоритмах выбирается вектор я», равный обобщенному почти градиенту функции 1» в точке х", равномерно распределенной в п-мерном кубе с центром в точке х" со стороной а»> О, т. е.
Р = а(х'). <з.в) В других случаях за направление движения Р выбирается ковечна-разностный аналог обобщенного почти градиента д (х') ! / ( а» »(~ — 7 (х„..., х, — +, ..., хл„))г', (3.7) где е', ! = 1, ..., и — 1-й орт. Алгоритл» 7 Н а ч а л о.
!, Выбрать произвольное начальное приближение х' ~ В", шаговый множитель р, и величину смещения а„удовлетворяющие условиям теоремы 1. 11. Поаожить й = О. 0 с н о в н о й ц и к л. 1Н. Вычислить реализацию х' случайной точки, равномерно распределенной в и-мерном кубе с центром в точке х» со стороной а».
1Ч. Вычислить вектор Р направления движения по формуле (З.б) или (3.7), Ч. Вычислить следующее приближение х'+' = х' — рД» при й-». оо. Тогда, если последовательность (х»)~, о, порожденная алгоритмом 1, принадлежит ограниченному множеству пространства В", Ч1. Вычислить значение шагового множителя р»+~ и величину смещения а»+о удовлетворяющие условиям теоремы !. ЧП. Положить й й+ 1 и перейти к шагу П1. Теорема 1. Пусть функция!» в любой ограниченной области удовлетворяет условию Литиица и, кроме того, выполняются условия р»>0, а»>0, й=О, 1, ...; О 6 ~" р» — — ао; ~ р»»( оо; р»/а»-~0, » 0 ь=ь (໠— и»+~)/р» -» О, ໠— ю- 0 то с вероятностью единица предельные тачки последовательности (х»)» ~ принадлежат множеству Х»Ь (х* ) О е 6 (х*)) и по.следовательность Д (х»))Г» почти наверное сходится.
Здесь и далее б (х) — множество обобщенных почти градиентов функции г» в точке х. 2. Стояаствчесяий случай 3 а д а ч а 2. Найти аги ппп Е )ь (х, а) для заданной функции 1~:И" х а Е1. Предположение 2. Функция г» удовлетворяет локальному условию Липшнца уь(х, ю) — рь(р. а))~у(ь»)!)х — у)! Еу'(") < Если существует достаточно эффективный способ построения об- общенного почти градиента Е (х, ьэ) функции Д» в любой точке (х, в), то в приводимом ниже алгоритме за направление движения $» к следующему приближению х»+' выбирается вектор И=а(х", ю"), (3.3) где х» — реализация случайного вектора, равномерно распреде- ленного в и-мерном кубе с центром в точке х» и стороной а» ) О; ьу» — независимые наблюдения в.
Если же построение д (х, в) за- труднительно, то за направление движения з» выбирается конечно- ,разностный аналог обобщенного почти градиента Е (х», в») в виде и = — Х У» (~„", х,'+ «», ° ., х', ю')— ໠— 1»(х»,, ..., х,' — а„..., х„', а»))е', (3.9) гдето,(=1, ..., и — (-й орт, Алгоритл» 2 Н а ч а л о. 1. Выбрать произвольное начальное приближение х' ~ И", значения шагового множителя р, и смещения а„удовлехворяющие условиям теоремы 2; положить й = О. Ос н о в н о й ц и кл. Н. Вычислить реализации х1, 1 = = 1...,, п, случайных величин, равномерно распределенных на отрезках (х,".— а», х,"+а„1, 1=1, ..., и.
111. Вычислить реализацию в» случайного параметра а. !Ч. Вычислить вектор $» направления движения к следующему приближению х»+' по формуле (3.8) (или (3.9)). (63 Ч. Вычислить следующее приближение х'+' = х" — р»9». Ч1. Вычислить значение шагового множителя р»+~ и смешения а»+т, удовлетворяющие условиям теоремы 2. ЧП. Положить й = й + 1 и перейти к шагу П. Теорема 2. Пусть выполнены предположение 2 и условия р»)0, а»)0 при у=О, 1, ...; «« « Х ~ =, 2", (', -, 2'.((У'.)'~ а»-~0 И (а — а»+1(/р -~-0 Прн й-ьоо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
