И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 68
Текст из файла (страница 68)
В детерминированном случае на каждой итерации решается вспомогательная задача на безусловный минимум. Метод штрафных оценок в детерминированном случае локально сходится со скоростью геометрической прогрессии, знаменатель которой тем меньше, чем больше козфф»)диент штрафа а.
При наличии случайных помех метод штрафных оценок сходится к локальному решению с вероятностью 1 — 6 (ибо без предположения выпуклости функций ~! сходимости с вероятностью ! не существует). 1. Детчрввввровеввый случай .4лгоритм 1 Н а ч а л о. 1. Выбрать начальное приближение у' ~ В двойственной переменной. 11. Положить А = О. О с н о в н о й ц и к л. П1.
Выбрать коэффициент штрафа а». 1Ч. Вычислить следующее приближение х»+' как точку безусловного минимума функции»у (х, у», а») (где ф (х, 'у, а) определяется по (5,78)), т. е. ф(х»+!, у", а ) = ш!пф(х, у", а,). е у»+' двойственной Ч. Вычислить следующее приближени переменной по формуле у»+' = у'+ а»Г(х»+'), где Г(х»+!) = (Г»(х»+'), ..., Г (х"+')). Ч!. Г!оложить й = й + 1 и перейти к шагу 1П. Теорема 1. Пусть выполняются условия: (!) — существует локальная точна минимума хе, т. е. 1!(хе) =О, /= 1, ..., т, и ге(хе)~<~»(х) при ~~(х) =О, 1=1, ..., т, )х — х*)(е, е)0; (11) — в е-окрестности точки х' суи(еапвуют первые и вторые производные функций )~ (х), 1 = О, 1, ..., т, причем Ч ~~ (х), 1 = О, 1, ..., т, удовлетворяют условиям Липшица (7„'„~~(х) — 7„'„~~(х))(у,)х — х), у,(ьь; (11!) — градиенты Ч~~ (х»), 1 = 1, ..., т — линейно независимы; (1о) — выполняется достаточное условие минимума (Ч ~р(х*, у*)х, х)) 6,'!ха, 6,)0 при (Ч„'ц(х", у'))х = О.
Тогда для всякого р ) 0 найдется число р = р (р) такое, юпо при а» ~ р, й = О, 1, ..., алгоритм 1 (в котором под х»+' понимается точка локального минимума функции»р (х, у", а») из окрестности х*) сходится при любом начальном приближении у» ~ Зр, где Зьа (у!)у — у Мр, у~11 ), причем для всех й ~ 1 справедливы оценки 1х» — х»'1((0»)») у» — у»Да,а» ... а» ~); '1у» — у»1((0 )" 1у» — у*11(а»а, ... а» ~), где О, ) 0 — некоторая константа. При условиях (») — ((и) применимо правило множителей Лагранжа, т.
е. найдется уч~ В" такой, что Ч„р (х», у*) = О, где Ч,<р (х*, у*) — производная функции Лагранжа ср(х, у)1~1»(х)+ ~; ~,(х) у, Условия теоремы (условия минимума) выражают условия невырожденностн локального минимума н являются минимально ограничительными. Замечание 1. Из теоремы 1 следует, что при а„= а для достаточно больших а алгоритм 1 сходится не медленнее геометрической прогрессии со знаменателем ц = 0,/а. Причем за счет увеличения и этот знаменатель может быть сделан сколько угодно малым.
Замечание 1'. Алгоритм 1 можно модифицировать таким образом, чтобы на шаге 17 лишь приближенно минимизировать функцию »р (х, у", а»). Именно в качестве х»+' выбирать любую точку из окрестностй х*, в которой 17„ф(х»+', у", а»)(!(р!)/(х»+')~, где р ~ 0 — наперед заданная константа. В условиях теоремы 1 для модифицированного алгоритма справедливы оценки х 1~ (О, (! + р))»1у.' — уе 1У(аеа ° " - )' (у» уе)((Ое(1+Р))»(У' — У»~У(аеа, ." а~-ю) (коистаита О, та же, что и в теореме 1).
Замечание 1". Если известно приближение хе для хе, то начальное приближение у' в алгоритме 1 можно найти из условия минимума квадратичного функционала уе(у) Ы тЧ»(хе) + (Ч',. р(х', О))'И. Чем ближе х' к х*, тем ближе будет найденное у' к у'. Замечание 1". Наиболее существенной трудностью в применении алгоритма 1 является проблема локальных минимумов функции ф (х, у», а»): неясно, как выбрать из них тот, который находится в окрестности х*. 2. Саоааетачееааа еаучаа Алгоритм 2 Н а ч а л о. 1. Выбрать произвольные начальные приближения х' Е Е" и у" ~ Е", основной и двойственной переменных.
П. Выбрать коэффициент штрафа а»~ О. 1П. Положить л = О. Ос н о в но й ци к л. 1Ч. Найти шаговый множитель р», удовлетворяющий условиям теоремы 2. Ч. Вычислить реализацию $» случайного вектора $~, удовлетворяющего условию Е(Р1хе, у', "., х", у») Ч1»( ) Ч1, Вычислить реализацию ~" случайного вектора ~», удовлетворяющего условию Е(ь/хе, уе, ..., х», у») =1(х»), где !' (х») — вектор-столбец с компонентами 1 (х»), )» (х"), (х»). Ч11. Вычислить матрицу А„размера т х л, строками которой являются реализации (~;) случайных векторов (ч~), 1 1, ... »т -» т ..., т, удовлетворяющих условиям Е(т:/хе, уе, ..., х", у») = 7~,(х"), ! 1...,, т. Ч1П.
Вычислить следующее приближение х»+' для основной переменной по формуле х»+' = х' — р»(ф'+ (А»)ту'-1- а,(А») ~»). 1Х. Вычислить следующее приближение у»+' для двойственной переменной по формуле у»+~ «» ! р ~» Х. Положить й = А + 1 и перейти к шагу 1Ч. ' Теорема 2. Пусть выполняются условия (») — (»о) теоремы 1 и (о) — случайные вектора 6», ~", т~, 1 = 1, ..., т — взаимно независимы при различных й; (о!) — случайные вектора Ь» и т;, = 1, ..., т — взаимно независимы; (Ю) — сумма дисперсий компонент каждого из векторов $, Ь, т», 1 = 1, ..., т — ограничена -» -» -» числом о»; (ой») — июговые множители р» таковы, что Р 9 р»~О, й=О, 1, ...; ~~ р» — — оо; ~ р»(оо; (1м)— В(! 'Г+1у'Г)( Тогда найдется такое число а ~ О, что при ае~ а последовательность ((х», у»))» о, порожденная алгоритмом 2, удовлетворяет условию Р(х»-»-х', у»~-уе) ~1 — Ь, б=ЬВ(5 ' — х'Р+Ье — у*(')+у»о' Х Ф у„у, — константы, зависшцие от детерминиров иной части задачи 1. При этом, если йр»- р, йр» — монотонно возрастает, то для всех й при у, ) О выполняется Р (»х хе» + !у у Г(7»р») РВ 1 д !/74 В частности, по всякому бе) О можно выбрать р, р, р, у» так, что при р»= р/(й+ 1»), Е(ц!хе — хе'1»+ !у» — уе!»)(д для алгоритиа 2 справедливо Р (1х» — х*(» +!у» — у*( ( у»1(Й + р)) > 1 — бе.
3. Метод штрефвмв одевов двв »едет еьшувлого врогре»»веро»евое Зада ч а 3. Найти зги ш!п1»(х) длЯ заданной фУнкции »ел 1» ~ В" -»-В' и множества Х~(х(~~(х) О, 1= 1, ..., т, х~5, где (г — множество в В"; ~~. В" — » В', 1 = 1, ..., т — заданные функции. 368 Предположения 3. (1) — множество»г — выпукло н замкнуто; (Й) — функции 1; (х), / = О, 1, ..., т — выпуклые и непрерывные. В выпуклом случае прн естественных предположениях метод штрафных оценок сходится к множеству решений прямой и двойственной задач.
Прн выполнении условий регулярности решения задачи 3 метод локально сходится со скоростью геометрической прогресснн, причем за счет увеличения штрафного коэффициента знаменатель геометрической прогрессии может быть сделан сколь угодно малым. Алгоритм 3 Н а ч а л о. 1. Выбрать пронзвольное начальное приближение двойственной переменной у' Е В+. П. Определить модифицированную функцию Лагранжа ф (х, у, а):В" хВ» ХВ» В', ф(х, У, а) ~11о(х) + — ~, ((У, + аГ';(х))» )' — — ~ (У;)'. 1 1 (Здесь и далее (11» Г~ шах (О, 1)).
1П. Положить й = О. О с н о в н о й ц н к л. 1'ч'. Найти штрафной коэффициент а„) О, удовлетворяющий условнюаь ) а > О, где а ) 0 — пронзвольная константа. Ч. Вычислить точку хо ~ Я, удовлетворяющую условию ф(хь, уь, а„) = пппф(х, уь, аь). «са 'ч'1. Положить й~ = (1, (хь), ..., 1 (хь)). И1. Вычислить точку уь»' = (уь + а»по)+. УП1. Положить й = й + 1 и перейти к шагу 1Ч.
Теорема К Пусть выполняются предположения 3 и пусть (В()— множество решений Х" задачи 3 непусто и ограничено; ((ь) — множество решений У*, двойственной к задаче 3, непусто, Тогда алгоритм 3 при любом у' ~ 0 (и любом а ) 0) порождает огРаниченные последовательности (хо)ь о, (У")ь о такие, что гп)п (х" — х*(-»-0 при й-> оо; «сх ппп(уь — у«)->0 при й-> оо; г Ег' ф(х', уь, аь)(~о(х'), х'ЕХ*. Двойственной к задаче 3 является следующая задача: найти агйгпахдо(у), д>о где 8» (у) Ып1 ~р (х, д), а ~р (х, у) — функция Лагранжа задачи 3, = «че т.
е. »р(х, д)Й|ь(х)+ л«уА(х), у=(у„..., у )ЕВ+, хЕ»г. Множество Хь х уь является -множеством седловых точек функции»ь (х, у). Теорема 8'. Пусть выполнены предположения 3 и пусть: (»о)— в задаче 3 множество Я = В"; (о) — задача 8 имеет решение х*; (о1) — в некоторой окрестности х' функции )~ (х), / = О, 1, ..., т— дважды непрерывно дифференцируемы; (ьй) — векторы Ч), (хь) при ( Е Иь«"«(( ( ~» (х») = О, ю' ~ П: тц — линейно независимы; (о»И)— если (Ч1» (х*), х) = 0 для всех» Е г« *, то (Ч'„~р(х*, у*)х, х) в(),((х((», (1, О, где Ч««»р (х», у*) — мшприца вторых частных производных функции ~р (х, д") в точке х', ф (х, у) — функция Лагранжа задачи 8; у* — множители Лагранжа задачи 8; ((к) — выполнены условия строгой дополняющей нежесткости, т. е.
у» ) 0 при ( Е й*. Тогда для любого. и ) О найдется 6 ) 0 такое, что при ((у'— — у*) ( б последовательности (х»)Г ь, (у»)Г ь, порожденные алгоритмом 3, удовлетворяют при всех я ~ 0 неравенствам ((х' — х'(((у„((у» — у*), у,)0; (5.79) ((д+ — д*((~у,((д — д ), О<у,<1, т. е. последовательности (х»,'» ь и (у»)» ь сходятся со скоростью геометрической прогрессии, соответственно, к хь и у*. С л е д с т в и е. При условиях теоремы 3' для любых а - О, у' ~ 0 найдется такое я„что при я ) й, последовательности (х»)»=ь, (у»)»=ь, порожденные алгоритмом 3, удовлетворяют неравенствам (5.79), Теорема 8'.
Пусть выполняются все предположения теоремы 3' и, кроме того, (к) — матрицы Ч««1» (х) и Ч««1 (х), ( Е Иь, удовлетворяют условию Липшица в некоторой окрестности точки х*. Тогда для любого у' ~ 0 найдется столь большое число а = = а ((( Уь — Уь (() ) О, что пРи сс» ~ а последовшпельности (х')» ь, (у»)» ь, порожденные алгоритмом 3, для всех я ~ 0 удовлетворяют неравенствам 1х» — х'((( — '» 1У» — У*'1; Ь»+' — у*((( ф ((д' — у* В где постоянная т, ) 0 не зависит от а». зто Библиографические указания.
Пункт ! написан на основании работы [3021, пункт 2 основан на результатах работы [3001, пункт 3 — на результатах работы [357!. Рекомендации и подбору начальных значений уэ и аэ в алгоритме 1 можно найти в работах [293, 487, 493, 5411, частные варианты алгоритма 2 приведены в [4111, В [330! для невыпуклой экстремальной задачи с ограничениями в форме неравенств доказана лоиальная сходимость метода штрафных оценок со скоростью геометрической прогрессии, В [302! изучался метод штрафных оценок для невыпуклых задач с ограничениями в форме равенств, в [3011 — для задач линейного прог аммярованин. работе[432! для решения задачи оптимизации с ограничениями типа ра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
