И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 76
Текст из файла (страница 76)
а. Метод еопращенна неаавоп в вадачах етонаетачеепого нрограммарованна 3 ада ч а 3. Найти агя пни )е (х), где «ко Х'дзХ П (х(1 (х)(О, 1= 1, ..., т)1 ~;(х)1~ЕР;(х, Ф), /=О, 1, ..., и; Х с: В" — заданное множество; р;: В" х 11 - В' — заданные функции. Для функций )О 1'= О, 1, ..., т, и множества Х выполняются предположения 2. Алгоритм 8 Н а ч а л о. 1.
Выбрать произвольную начальную точку (хо, ие)ЕВ» Х В~ 11. Задать шаговый множитель р„нормирующий множитель у, и величину смешения Ь„удовлетворяющие условиям теоремы 3. 1П. Положить )е = О. Ос нов н ой ц и к л. 1Ч. Вычислить вектор и $д =Х Ф(хи+ аде~, ид, вдл) — Ф (х", ид, аде) г' ад т -где е»", ч = 0„1, ..., и — серия независимых по й наблюдений «состояния природы 4оо (в частности, можно взять»о»о= ы»л = ... — 4О»,о — Ы»). функция Ф (х, щ о») определяется по правилу а Ф(х, и, о) = с'о(х, о»)+ ~„и~р~(х, о»), !=1 здесь и = (и„..., и ); е-', 1 = 1, ..., и — 1-й орт, Условное математическое ожидание вектора $» равно ЕЯх», и') = 7„<р(х", и»)+ о»1»», где функция »о (х, и) »» ЕФ (х, и, о»); о" — некоторый вектор, для которого ) о») < сопз1, т.
е. вектор в» является стохастическим квазиградиентом функции у (х, и) в точке (х', и'). . Ч. Вычислить вектор х»+' = пх (х» — р»у»ь»). Ч1. Вычислить вектор и»-л по(и»+ р у»Р(х» юко)) где Р = (Р„..., Р ); множество У определено в пункте 2. Ч11. Вычислить шаговый множитель р»4 ы нормирующий множитель у»+1 и величину смещения по координатным осям Л»+ь удовлетворяющие условиям теоремы 3. ЧП1. Положить я = я + 1 и перейти к шагу 1Ч. Теорема 3. Пусть выполнены предположения 2 и, кроме того, функции )о 1 = О, 1, ..., т, имеют ограниченные в области Х вторые производные и 1,— строго выпуклая функция. Пусть: (1) — т)„— случайная величина, измеримая относительно о-подалгебры, индуцированной величинами (х', и'), ..., (х", и»), такая, что Е ( 1 В» '1« + 1 Р (х», о»» о) )3/(хо, ио), (х» и»)) " Чо < Р (Х) < 00 при 1/х /)+1и'!/<Х<оо, в=О, 1, ..., й (здесь р(К) и Х— ограниченные константы); (»1) — нормирующий»тожитель т» для некоторых чисел у'> у' удовлетворяет условию О < у' < у» (В» + т»1 х' ( ) < у" < оо, где т»= 1 при 1сР !! ) О, т»= О при 1 о» '1 = О; (1И) — шаговый множитель р» и величина смещения по координшпным осям Ь» детерминированные и такие, апо Ф Ю р»~вО, ~; р»= оо, ~'„(р»)Ь»)+рД<оо.
~о »=о 413 Тогда с вероятностью 1 одна из предельных точек последовательности (х»)Гс, порожденной алгоритмом 3, принадлежит Хе, т. е. поспи наверное 11ш (ш)п 1» (х»)) = ~, (хе), хе ~ Хе. еию св»<в 4. Гвбрвдвый стевеспсоесввй метод 3 ада ч а 4. Найти агд пип 1» для заданных множеств Х с «ехал ~ В" и А = (х(1(х) (О). Предположения 4. (о) — функция(о ( ) — непрерывна и выпук- ла вниз; (й) — множества Х и А — выпуклые и замкнутые; (йо)— А() ХФ8 Приводимый гибридный стохастический метод поиска экстре- мума функции 1» ( ) сочетает в себе идеи стохастического релакса- ционного метода для решения систем неравенств и стохастического ивазиградиентного метода для решения задач нелинейного про- .граммирования.
Алгоритм 4 Н а ч а л о. 1. Выбрать начальную точку хо ~ 11", для которой а)хо 11» < со. П. Задать последовательности щаговых множителей (б»)Г=»1 (р»)Г о. П1. Задать последовательности нормирующих множителей (()»)Г=»1 (7»)Г о 1Ч. Положить й = О. О с н о в н о й ц и к л. Ч. Вычислить случайный вектор $», условное математическое ожидание которого К (с»1хо, ..., х») = со»Ч1» (х») + 6», (5.10!) где ໠— неотрицательная случайная величина и о» вЂ” случайный вектор, измеримые относительно о-подалгебры Й„ индуцированной семейством случайных величин (хо, ..., х»); Чго (х») — вектор обобщенного градиента функции 1» в точке х". Ч!.
Вычислить случайный вектор Ь», условное математическое ожидание которого Е(г»1хо, ..., х») =),»д(х») + У, (0.102) где 1» — неотрицательная случайная величина и о(» — случайный вектор, измеримые относительно о-подалгебры Й»; я (х») — вектор, для которого полупространство, отвечающее неравенству (а(х), г — «)+1(х)((О> при х = х» содержит множество А, если х»~ А. 414 Ч11.
Найти вектор пх (х» — 6»р»Г (х") Ь» — р»уД»), 1(х») ) 0; ~ (' — р.ус'), 1(х») < О. Ч111. Положить й = й + 1 и перейти к шагу Ч. Теорема 4. Пусть имеют место предположения 4 и пусть з)» слу- чайная величина, измеримая относительно о-подалгебры Й», та- кая, ипо для любого числа со < оо найдется число с, для которого Е(~~»~з+ ~~»)з/»л, ..., х») <»1'- <с„ как только ~ х'1< со, в = О, 1, ..., А; для некоторых чисел, у, у нормирующие множители р» и у» удовлетворяют условиям Р~(1(х')(~ (й))х»~~+1)+ Ч~) = 11 у<у»(та(й)1х'1+»)»)<у, где т» (й) = 1, если!/ й» '1 ) О, т, (й) = О, если ( й» 1 = 0; т, (й) = 1, если ~ Ь" 1) О, т, (й) = О, если ~ Ь» ~ = 0; величины р„б», а», Л„и векторы Ь», й» такие, ело р»~0, 0<6»<2Л» — е», е» вО, а,) О, Л»; »0; Ю ~", Е(р,))Ь»)+ р'+ р»6„+ 6») й»))) с- оо.
Тогда случайная последовательность (х»)» о, порожденная алго- ритмом 4, является случайной квазифейеровской относительно мно- жества Х*. Если же, кроме того, с вероятностью 1 ~, '6,в» = оо; ~„р»а» = оо, »-о о=о то она сходшпся к некоторому злементу х*Е Х' почти наверное. Замечание 4. Если, например, ((х) = шах~,(х) й~им(х), где функции ), (х) — выпуклые вниз и непрерывно дифференци- руемые; 1(х) — индекс, на котором достигается гпах ~, (х) при за- данном х, то всктоР Е(х) = Ч)~ (х) ~; кю УдовлетвоРЯет неРа- венству (5.103).
Замечание 4'. Отметим, что на шаге Ч11 алгоритма 4 использует- ся стохастический релаксационный метод х"+' = пх (х» — 6»р»~ (х») ь») для решения системы неравенств ~;(х)<0, 1=1, ..., т; хсХ, где ~(х) = гпах ~, (х). 1<1<а Библиогрп4»з»еское упования. При написании параграфа использовались работы 1!49, 1531.
41$ 5.29. Комбинированный метод стохастнческих градиентов и штрафных функций 3 а д а ч а 1. Найти агя шах !» (х) для заданной функции гях Д»: В" » В' и заданного множества Х = (х)~,(х) 1»О, 1= 1, ..., т, хЕ!г). Предположения 1. (1) — функции 11 (х), 1 = О, 1, ..., т — непрерывны вместе со своими производными; (й) — функции П (х), 1 = О, 1, ..., т — вогнуты; (111) — У вЂ” выпуклый компакт из В".
В приводимом здесь методе определяются функции д,(х, а) =!»(х) — а ), р»)ппп(О, 1,(х)) )' 1 (здесь т) 1 — константа; а — коэффициенты штрафа, стремящиеся к бесконечности; р,, 1 = 1, ..., т — выбранные вероятности) и для отыскания их максимума применяется метод стохастического градиента. Алгорип»м 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение х'Е 1' П. Задать числа р„ 1 = 1, ..., т (р, ) О, ! = 1, ..., т; ~ р,= 1 = !), которые, соответственно, характеризуют требуемую относительную точность выполнения ограничений-неравенств в задаче 1 (обычно р, = !/т, 1= 1, ..., т). П1.
Выбрать параметр т) 1. 1Ч. Положить й = 1. Ос н о в но й ц и к л. Ч. Найти независимую реализацию 1» случайной величины 1, которая принимает значения из множества 9 = (1, ..., т), соответственно, с вероятностями р„..., р . Ч1. Найти значения шагового множителя р и коэффициента штрафа а», удовлетворяющие условиям теоремы 1.
ЧП. Вычислить стохастический градиент 6» функции у, (х, а») в точке х» й» = Ч), (х») + а»т ) ш)п (О, П (х')) )' ' Ч~,, (х"). ЧП1. Вычислить следующее приближение х"+' = пг (х" + рД»), 1Х. Положить й = й + 1 и перейти к шагу Ч. Теорема 1. Если выполняются предположения 1, множество Х— непусто и числовые последовательности (р»)» ь (а»)» ~ удовлетво- 416 ряют условици р >О, 1ппр„= О, р»+!(р», 2„' р» »-ко »-! кк а >О, 1ппа»= оо, а»+!,'~а», ~ (р»а„)а(со, » о »=! то для любого начального приближения х' последовательность (х»)» и порождаемая алгоритмом 1, с вероятностью 1 сходится к Ага шах ге (х) — множеству решений задачи 1.
ксХ Замечание 1. Алгоритм 1 в (3721 рекомендуется применять для решения задач математического программирования с большим числом ограничений (в особенности для тех задач, ограничения которых могут формироваться по мере надобности в ЭВМ) и для решения задач с блочной структурой. Библиографические указания.
При написании параграфа использовалась работа 1372!. 5.30. Методы усреднения направлений спуска к. Петерввнвровавваа задача 3 а д а ч а 1. Найти агд ш!п)е (х) для заданной функции «ах 7а ! Л"-э-11! и множества Х, заданного соотношением Х=Х, ПХю где Х,= (х~ 1! (х) (О, 1'= 1, ..., т, ХЕВ"); Ха — выпуклое, замкнутое, ограниченное множество.
Предположения 1. (1) — функции 71, 1 = О, 1, ..., т — выпуклы; (И) — множество Х, имеет иепустое пересечение о множеством внут. ренних точек множества Х,. Ниже приводятся два алгоритма усреднения направлений спус- ка, первый из которых требует вычисления субградиентов функ- ций Г„ / = 1, ..., т, а второй — лишь вычисления значений функ- Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение хе Е 1?". П. Выбрать произвольное натуральное число 1. П1.
Положить й = О. Ос но в н о й ц и к л. 1Ч. Вычислить шаговый множитель р», удовлетворяюший условиям теоремы 1. Ч. Если выполняется неравенство шах 7! (х») ( О, !н!<а то положить ч» = О и перейти к шагу ЧП, иначе перейти к шагу Ч!, 14 з.зл! 417 Ч1.
Вычислить индекс 1~ (1 ~ т), удовлетворяющий условию, 1,(х») = шах ~~(х»), ! <уел положить»» =1 и перейти к шагу НП. ЧП. Вычислить субградиент Ц»„(х») функции г» в точке х", ЧП1. Если й ~ 1, то вычислить вектор ь'= Е 71,,( ') н перейти к шагу 1Х; иначе вычислить вектор й" но формуле й» = ~„»1» (х») » о и перейти к шагу 1Х. 1Х. Вычислить следующее приближение х»+' = нх, (х» — р»й»), где пх, (х) — оператор проектирования на множество Х, точки хс В". Х. Положить й = й + 1 н перейти к шагу 1Ч. Теорема 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
