И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 84
Текст из файла (страница 84)
Х1. Положить т = 1. ХП. Вычислить и"+' = и" — тЛ. ХП1. Вычислить о»+~ и х"+', соответственно, (6.10). Х1Ч. Если о»+1, О, то положить й = й+ 1, т перейти к шагу ХП; иначе (если о»+1 = 0) положить З-„, и'+', В»++, — — и', й = й+ 1 и перейти к шагу ХЧ. ХЧ. Вычислить (6.9) (ало) +1 и пе— и» по (6.9), =т+1и и»+' = (»)» +»)»+)/2, ХЧ1. Вычислить о», ь х"+', соответственно по (6.9), (6.10). ХЧП. Если о»,1 — — О, то положить и»+1 = и'+', т)»+~.~ »)»~, й = й+ 1 и перейти к шагу ХН; иначе (т. е.
если о»+~ ) ) 0) положить 1)»+~ В», т)»+~ = и'+', й = й+ 1 н перейти к шагу ХЧ. Теорема 1. Если выполнено предположение 1, то алгоритм 1 порождает последоеательность (и»)7», длл которой 1ппи'=и*, ».~ «« причем точка х = агнш)пу(х, и*) «6Е меляется решением задачи 1, т. е. х = агд шах пни ф (х, у). «ях»еу Замечание 1. На практике итерации проводят до тех пор, пока для заданного малого числа е ) 0 не выполнится неравенство т1+ — П-» < е. 460 Тогда за приближенное значение максимина принимают и», а за решение задачи 1 — вектор х» й Я, х» = агдш[пд(х, и»).
«по Бйблиографие«си»а раиаиил. При иаписаиии параграфа испольаовались ра. боты [70, 72, 3721. 6.8. Квааиградиентные методы решении непрерывных минимаксных задач стокастического программирования 3 ада ч а О. Найти агд ппп тах Еф (х, у, в) для заданной «ех ару функции <р: В" х В х»1-~-В' и заданных множеств Х с В", [«сВ.
Предположения О. (») — функция 1(х, у) ~1 Е~р (х, у, в) н ее градиент по х непрерывны по совокупности переменных х, у; (Й)— Х вЂ” выпуклое, замкнутое ограниченное множество; (1И) — 1'— замкнутое ограниченное множество; ([п) — имеется возможность вычислять только значения функции ф (х, у, в) и ее градиента Ч„~р (х, у, в) в каждой точке (х, у, в) ~ Х Х У Х »1. Предлагаемые ниже методы решения задачи 0 основаны на построении специальных множеств У» для определения на й-й итерации направления движения Ь» к (Й + 1)-му приближению х»+'. Вектор [»» определяется как стохастический квазиградиент функции гпах Ев (х, у, в) в точке х". »вг» 1. Стохастичесиий пааамградпеитиый метод Алгоривал» 1 Н а ч а л о. 1.
Выбрать начальное приближение хе ~ Х. П. Выбрать натуральное число У„положить У = У, П1. Выбрать произвольные действительные числа аь 1 ~ ~ 10: У1. [Ч. Построить сетку Ух = (у'[у'Е)', 16[0:У)). Ч. Положить й = О. Ос нови о й ци к л. Ч1. Найти индекс 1» из условия г», = шах г,". '» та[о:и[ ЧП. Вычислить независимую реализацию в» случайного параметра в. ЧП1. Вычислить Ч„в (х» (в), у'», в»). [Х. Вычислить шаговые множители р» и о», удовлетворяющие условиям теоремы 1. Х, Вычислить следующее приближение х»+'(в) пх(х»(в) — р,Ч„»р(х»(в), уа, в»)).
461 Х1. Вычислить значения функции ~р (хе+' (ь»), у', о»е), 1 с Е (О: й/1. ХП. Вычислить величины г,".~' (ь») = г» (о») + аь (ср (хе+' (ь») у' е»е) — г» (с»)), 1 с [О: Е1. Х1П. Положить й й+ 1 и'перейти к шагу Ч1. Теорема 1. Если выполнены предположения 0 и (1) — функция Ею (х, у, с») выпукла по х, х а Х при каждом у ~ У; (»1) — градиент функции / (х, у) Ь Е~р (х, у, с») по х удовлетворяет условию Лапши ца 1Ч ((х, у) — Ч„/(х, у)()(и,~)х — х1, уЕУ, х, хсХ; (111)— Е(~р(х, у, «о))е(оо, Е'1Ч,лр(х, у, о»)1«(со, уЕУ, хсХ; ((о) — шаговые множители р» и о„удовлетворяют условиям Ю ~„ать( со, ~ Р„= оо, Ре/ое-«-0 пРи й — » оо; е-с ь-с ре, ~/р„— » 1 при й -».
со, то почти при каждом «с предельные точки х~е последовательности (хе (о>))Г=», порожденной алгоритмом 1, являются точками минимума функции шах Е~р (х, у', с») на множестве Х. ~И«:«1 Для решения исходной задачи О, необходимо при каждом фиксированном Л/, (л/,-~ оо при г — оо) решать дискретную мичимаксную задачу с помощью алгоритма 1, причем последовательность сеток (Ун )," «должна обладать свойством плотности на множестве У. Каждая предельная точка последовательности (х~ ),=е является решением задачи О.
Последовательность сеток (Ун ), е «обладает свойством плотности» на множестве У, если для любого е ) 0 можно указать такой номер У, что для всех /Ч, ) У расстояние между произвольной точкой у ~ У' и ближайшей к у точкой сетки Ун будет меньше е. 2. Модифидироваиимй стовастичесиий иваеиврадиеитиый метод Алгоритм 2 Н а ч а л о. 1. Выбрать начальное приближение х'е К. 11.
Выбрать натуральное число /1/е и построить сетку Ун. = (у'(у'Е У, (Е(0:/ЧеИ. 1П. Выбрать произвольные действительные числа геи ч (О о/»1 1Ч. Выбрать начальное значение шагового множителя ре) 0 и константы а ) О, р ) О. «62 Ч. Положить й = О. Ос н о в но й ци к л. Ч1. Найти индекс г» из условия ег (в) = гпах гг(в). гав:н г Ч11. Найти независимую реализацию в» случайного параметра в, Ч111. Вычислить 7, (~р (х» (в), у'», в»). 1Х.
Вычислить следующее приближение х»+'(в) = пх(х»(в) — р»Ч„гр(х" (в), уг», в')). Х. Вычислить значения гр (х»+' (в), у', в»), г Е (О: У»). Х1. Найти шаговые множители р»+г и а»ч.г, удовлетворяющие условиям теоремы 2. Х11. Построить сетку )'н»ч, = (уг ! уг с 'г', г е (О: У»+1)) так, чтобы она содержала нсе точки сетки гн с сохранением их нумерации н чтобы выполнялось следующее условие: для произвольного у С У расстояние от у до ближайшей точки сетки ун»+, не превышало значения ир»+вг Х111.
Вычислить величины г»+' (в) = е»г (в) + а»ег (гр (х»+' (в) у' го») — е» (в)) 1е (О: М»1. Х1Ч. Положить г = У»+ 1. ХЧ. Найти точку уй сетки Унм которая принадлежит шару радиусом сгр»+~ с центром в точке у' и имеет наименьший индекс 1г Е(0: Е»). ХЧ[. Положить гг (го) ег. (в). ХЧ11. Если г' ( ЛГ»+г, то положить г =! + 1 и перейти к шагу ХЧ; иначе перейти к шагу ХЧ111. ХЧ111.
Положить А А + 1 и перейти к шагу Ч1. Теорема 2. Если выполнены условия теоремы 1 и (1) — грункция Е~р (х, у, в) для произвольного х ~ Х удовлетворяет условию Липигицп по переяеннай у )ЕР(х, У, в) — ЕгР(х, У, в))~а»1У вЂ” У~, а»(оо; (й) — последовательность (а„)» ь дополнительно удовлетворяет усласию Вгп 2, и оо при т — з-»- оо, (например о» й — », т Е (г/„1)), та почти при каждом в предельные тачки последовательности (х" (со) ) Г=о, порожденной алгоритмом 2, являются точками минимума функции гпах Ж~р (х, у, го) на множестве Х.
гбг Библиографические указания. Параграф написан на основании работ [30, 31, 32, 171, 1131. 6.9. Градиентные методы отыскания седловых точек 3 а д а ч а О. Найти точку (х*, у*) ~ Х х )', удовлетворяющую условию <р(Х, уа)(~р(Х«, уа)(~р(Х«, у), )1ХЕХ, у~)г, (а.11) где ф(х, у) — вогнуто-выпуклая функция; Х и )' — выпуклые замкнутые телесные подмножества эвклидовых пространств В" и В , соответственно.
Определение 1. Множество точек (ха, у'), удовлетворяющих условию (6.11), называют множеством седловых точек Х* и )«а функции <р (х, у) на множестве Х х г. Предположения О. (г) — функция ф (х, у) непрерывно дифференцируема на множестве Х х )', вогнута по х и выпукла по у; (й)— множество седловых точек Х' х )га функции <р непусто и ограничено; ([и) — выполняется условие устойчивости множества седловых точек по х, т. е. для произвольного х ~ (Х'~,Х') выполняется строгое неравенство ~р(х, уа) ( ~р(х*, у«).
Предположения О выполняются для функции Лагранжа задачи вогнутого программирования: найти агн п1ах 1о(х), (6.12) «сх, где Х, (х[1,(х)~О, 1*=1, ..., т, хЕВ"), с дифференцируемыми (и вогнутыми) функциями 1н 1 О, 1..., т, если фУнкциЯ 1о стРого вогнУта и выполнЯЕтсЯ Условие СлейтеРа. Условие (1и) играет существенную роль, так как при его отсут- ствии градиентные методы отыскания седловых точек, в общем, не сходятся.
Примером служит функция <р(х, у) (1 — у)х, Х В', )г = В», являющаяся функцией Лагранжа задачи найти ага п1ах х, «сх, где Х, = [х! — х вО, хЕВ'); В». — поднространство т-мерных векторов с неотрицательными компонентами. 1. О»воевой алгорвтм Алгоритм 1 Н а ч ало. 1. Выбрать начальное приближение (х', у') С Х х ~ У. 1!. Положить й = О Оси о в н о й ци кл. П1.
Выбрать шаговый множитель р», удовлетворяющий условиям теоремы 1. 1Ч. Вычислить векторы Ч„»р (х», у») и Ч„!р (х", у") — градиенты, соответственно, по х и у функции !р (х, у) в точке (х», у»). Ч. Вычислить следующие приближения: х»+' = пх(х»+ р»Ч,!р(х», у»)); у»+' *= пг(у» — р»Ч„»р(х», у»)), где пч — оператор проектирования на множество (г. Ч1. Положить й = й + 1 и перейти к шагу 111. Теорема 1. Пусть выполняются предположения О. Тогда для любого положительного числа 6 существует такое положительное число р (6), ипо при всяком начальном приближении (хе, у') и Я (6), 2(6)с»Их,у)( ш!п (!(х, у) — (хе, уе)((<6, (х, у)ЕХхУ), (вяз) <г,г >Ех хг и любой последовательности (р»)»=е, удовлетворяющей условиям р») О; р»-» О; 1,' р» оо; р»,, р(6), алгоритм 1 порождает последовательность ((х», у») )»" о, которая схо- дится к множеству седловых точек Хе х У'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
