И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 10
Текст из файла (страница 10)
е. В«+! = В«)«!/ао 1, (г"), где Я!!«„+! (г") — матрица растяжения пространства в направлении г" с коэффициентом растяжения и«4 ! (элементы гк; матрицы )«(г") определяются равенствами [404) ((а 1) гег« гу = (К,(г«)еп е!.) = ~ ! Если г имеет овражную структуру, то г" чаще ориентировано «поперек» чем «вдоль» оврага и поэтому данное последовательное растяжение пространства уменьшает овражную структуру функции 1 и тем ускоряет сходимость градиентного метода.
Рассмотренный выше метод эллипсоидов, очевидно, является вариантом метода растяжения пространства со специальным выбором шагового множителя Л„. 3. Мо»оды соврввкеввыв ерадвевтов Векторы р~, р', ..., р" называют сопряженными относительно симметричной, положительно определенной матрицы А, если (Ар', р!) = 0 при !' ~ 1 и (Ар', р') ~ О. Метод сопряженных градиентов состоит в последовательной ! минимизации функции ! (х) = — (Ах, х) + (д, х) по направлениям р', т. е.
начиная с произвольного х' Е В , вычисляем х"+'=х" +Л р" Л„=агдппп1(х" +Лр"). (а 41) Утверждение 14. Метод сопряженных градиентов минимизирует функцию 1 (х) = — (Ах, х) + (д, х) за Ф итераций, т. е. 1 х" = х* = агк ппп 1(х). к Действительно, если ввести новое скалярное произведение (х, у), Е~ (Ах, у), то метод сопряженных градиентов оказывается эк- 1 вивалентным минимизации ) (х) = — (х, х),+ (з, х), по координатным направлениям. Распространение этой идеи на случай нелинейной функции г приводит к расчетным формулам (0.41) при Р+ = Ч1(х ) р +' = ~( Ч) (х + ) )!' р /) Ч~ (х") ~!' — Ч1(х + ) (а 4т1 (или при р' = — Ц(х'), В! =1, р'+' = — В„+!Ч1(х"), 38 <О.оа> д" = 71(хе+') — 7Г(х"), зе = х"+' — х", О" В„О" ее*о" Утверждение 15 (470!. Метод (О 41), (0.42) и метод (0.41), (0.43) обеспечивают квадратичную скорость сходимости к единственной точке минимума х" сильно выпуклой функции Г с липшицевым гес- сианом.
Если 1,„ вычислять приближенно, то р"+' рекомендуется вы. числять по формулам р+~(Ч(»+)Р))~о1(+~))1о(1»+~) 1о11") 1* 1 " )о((. ) р Матрицы В„можно вычислять также по более общим формулам~ В„чаде'В* Рео' В„„ь~ = „—, " + —,„+ Со"о"', д Ве9» Ч о" = з"lд"'з" — В„дед'*В„д", С б В. Данные методы можно интерпретировать как варианты квази- ньютоновских методов. 4. О методах штрафов в задачах е отраннченвямн Задачу минимизации функции Го при дополнительных ограничениях »ЕХАЙ(х~~,(х) = О, (ЕР, ~,(х)(0, (са ) можно провести с помощью метода штрафов к задаче безусловной оптимизации, которую затем можно решать упомянутыми выше методами безусловной оптимизации. Для этого выбираем некоторую вспомогательную функцию 6 (х)(функцию штрафа), которая равна нулю, если х е Х и увеличивается с удалением х от Х (например, й(х) =С( 2' 11(х)+ 2, Ц, (х))'), 'Е.ке ~ау С ) О, в+ (х) = 1;(х), если), (х) ) 0 и ~т (х) = О, если ~, (х) ( 0) и затем, минимизируя вспомогательную функцию ) (х) = 1е (х) + + Ь (х), находим х" (С) = агя ппп 1" (х).
Нетрудно убедится в том, к что при весьма общих предположениях х'(С)- х' = агйпнп~е(х). с ках Если в качествеЬ (х) выбрать недифференцируемую функцию вида й,(х) = С( ~ (~,(х)1+ ~ ~+(х)), ю.т кем 39 то во многих случаях получаем х* (С) = х* при сравнительно небольших значениях С (и это весьма существенно, так как увеличение С обычно увеличивает овражную структуру функции ) и тем уменьшает эффективность ее минимизации упомянутыми градиентными методами). Утверждение 16. Если функции 1е, ~, выпуклые и С ) шах и,, где и; — множители Лагранжа для функции (е (х) + ~ иА (х), то К.7— для й, имеем х'(С) = х' = агн ппп 1'(х). ~ »(к) чо, 1 Ел Действительно, если функции )'„ /„(Е а — выпуклые, то (х*, ие) — седловаЯ точка длЯ фУнкции ЛагРанжа )е (х) + + ~ иА (х), т.
е. имеем неравенства СЯУРе(х*)Ю»(х)+ Х и,'l,(х)Ю»(х)+ Х АР+~(х)(й,(х)+Го(х), '6у г6у которые вместе с равенством й, (х") = О дают х* (С) = х*. Однако функция й,(х) недифференцируема и для ее миними. зации требуются специальные методы (см. минимизация негладких функций). Ряд методов о гладкими штрафами описан в гл. Ч. б. О методан ноеледоаательвыа приближений длл задач уелоевой оптамиаадвн н мавимиааааа веглалкин функнив Как отмечалось выше в методах последовательных приближений вычисляют (й + 1)-е приближение х'+' с помощью решения х"+' для упрощенной задачи оптимизации х'+ = агнии(пР,(х).
кех Если выбрать Х» Х (или Х, (х", Л»)), Р„= Р, (х», ) и положить х'+' = (1 — Л) х" + Лх»+', Л = агн ппп ге ((1 — Л) х» + Лх'+'), то получим вариант метода условного градиента. Если выбрать Х* =* Х» (х», Л„) (или Х, (х', Л»)), Р» — — Р, (х", ) и положить х"+' *= агн ппп ) х — х»г' '1, то получим вариант кгХ метода проекции градиента. Если положить х"+' = х'+', Х" = Х» (х», Л„, е,,) П Х, Р, = г, то получим метод покоординатного спуска (1» = й— — ЕЙТ (йг и)). ЯО Если в случае Х = [х ] г! (х) = О, ! Е l] выбрать (см. с. 22) Х" = [х)г'!(х») +(Чг!(х»), х — х»)(О, ! Е у» Ь» Агй [!'! (х») ~ С» — еЛ,], ! хЕХ,(х», Л»)], С»йгпахг!(х»), Р» = Р,(х», ), х»+' =х'+', !а.в то получим вариант метода линеаризации и метода возможных на- правлений, выбрав а» = з!нп (С» — вЛ»)+ х»+' = х» + Л„[(໠— 1) Ч[» (х") — а» ~; Ч[! (х»)] а,я» получим вариант «вазиерадиентного метода.
При негладкой аппроксимации Р» (х) * Ра (х", х) имеем Р»(х», г) = ~а!(х») шах (с'(х'), г) %~,!»»,е (в'»(х», !)Ьагй шах Р,(х', х»)) !я.т!» м и поэтому можем вычислять направления убывания Г и направления наискорейшего убывания г (х") = агн п»!и Р» (х', г).
Если вычис9м ! ление г(х') затруднительно (как, например, в стохастическомслу. чае 1(х) !'! М„Р (х, а)), то удобнее использовать метод х' — '' = = х' — ЛД»!' ~] $» ]~, $» = $ (Р», х') ~ ~„а! (х') с';и, !»! Е в'! (х', 1) (в стохастическом случае [153] Ц» = Ь» (в»), М„Ь» (е!) -» ь ((, х')), ко. торый для выпуклой задачи обеспечиваетг (х») — ! (х*) при Л, ) О, 2 '„~ Л» = со, Л» — О, [» Л» ( оо, для слабовыпуклой (при лопал»=! »=1 нительном условии Л!,4.!!Л» †» !) имеем !'(х») -» / (х») (в стохасти. ческом случае полагаем х»~-! = х», если [] х»+' (е!)[ > С [272]), а для ), касательных к Р„ обеспечивает [ г (х")~( ( и [32].
В [32] получены условия сходимости для конечных Л„ = Л, поскольку на ЭВМ трудно обеспечивать Л» — О. Методы развязываюи(ей декомпозиции для общей задачи х* = агнш(п1»(х), «ех Х»» [х = (х„х,) [(! (х) = О, (Е l», 1! (х) ( О, !' Е.(„х» Е Х»] (о.441 основаны на следующем утверждении [23]. Утверждение 17. Если для всех х, Е Х, и всех ! из множества в, существенных ограничений О, с=. l, [] л'» ~ [О) вспомогательные функции г!, В,, и и В, удовлетворяют условиям 1! (х) = Д (х,, х„д (х)), Ч!»(х),~Ы(х) — В'(х,, !'у,(х)) =О, Ч! (х) ь» 1! (х) — В! (х», д (х), ) т (х)) — = О, (0.45! 4! то оптимальное значение хо равно агнш[пВо(х„Во(х„О), 0)[В,(х„В'(х,, 0), 0) = О, (ЕОо. (аыа) о ех Задача (О.
46)обычно имеет существенно меньшую размерность, чем задача (0.44). Несколько ббльшую размерность имеет эквива- лентная задача минимизации штрафной функции 1, (х) + С~ [[й (х) — и[+ ~ Сьч1+ (х), ы~о «тз илн функции 1„(х) + Р (х), Р(х)~шах [О, шах [иг — и;(х) [, шах 1,(х)), ! ~Ио~ Я при связях 122, 241 1т,(х„х„и) = О. Функцию В, называют развязывающим оператором для функ- ции 1, по переменной х, на множестве Х,относительно функции 1~. о з Ее аппроксимация Во, обеспечивающая в точке хо нулевые значе- ния всем производнымдо з-го порядка по всем направлениям в про- странстве переменной х, для функции ~ро определяет в точке х" асимптотнчески развязывающий оператор з-го порядка В[(хо) 1х 1, (хг, х,) + В~ (х„ В' (х„ О), 0)— — В1 (хо В (хо 1э; (хм хо)) 1у (хм хо)) обладающий следующим важным свойством [231, Утверждение 18. 1~ (х) = 0=~1,(х) = В[(хо)-[-о(!х — х,[').
3 о Поэтому естественно выбирать в качестве указанных выше Х н Е„соответственно Х, и В*(х,)~(1 — а,)Во(х,) + ~; шах (О, з[йпВ[(хо)) В';(х,) "~в н вычислять хь+' с помощью известных методов недифференци- руемой оптимизации (малая размерность вектора х, позволяет здесь эффективно воспользоваться методами растяжения простран- ства). Приведем общий А,-алгоритм. Начало: выбираем произволь- ные хо Е Х„положительные числа Л„С„С, и С, и полагаем й = !.
Основной цикл: вычисляем хо+ для -о.~-1 Х = [хо Е Х, [ ([ хо — хо~[ В [Ло, СоЛо[1, где˄— максимальноечислоиз последовательности [СоЛо ~ 2 ) -о, удовлетворяющее неравенству 1о(х ) ~~1о(х )+ СРо Утверждение 19. Если Г» (х«) ~ — со и ~, являются функционалами равномерного роста з-го порядка на Х» (например, ограничены все производные г'; до (в + 1)-го порядка по всем допустимым направлениям), то подпоследовательность (х»~) сходится за конечное число итераций я = я (з) к з-экстремальному решению и, з-го порядка (т. е.
производная в,-го порядка функции Г, в точке и, по любому допустимому направлению не меньше — е'ч'4' для всех в,= О, з). Реализуемые В6-адекватные модели. Выше уже отмечалось, что прн решении практических задач функции ~, обычно являются всего лишь некоторыми приближениями к соответствующим либо неизвестным, либо слишком сложным для современных ЭВМ «реальным» функциям ~, (т. е. исходная математическая модель обычно либо неизвестна, либо нереализуема).
Поэтому актуальной является проблема выбора таких приближений 1, (т. е. формулировки такой задачи оптимизации), чтобы, во-первых, ее приближенное решение х~ не слишком отличалось от искомого х- и, во-вторых, существовала бы практическая возможность вычислить х~ в требуемые сроки на имеющейся ЭВМ. Одним из инструментов для выбора и адаптивного уточнения таких функций является следующая теорема. Теорема о реализуемой Вб-адекватной модели. Если неизвестные (или нереализуемые) функц ии ~„7, в реальной задаче антил«ива ции аппроксимированы реализуемыми функциями Г», ~о а развязывающие операторы В, апароксимированы функциями В,, удовлетворяющими на приближении х к решению х~ условиям /~~(хп х«) — ~;(х», х»)(~~ба(Ро х»)йба(7.
х») (В,(х„~о (х„х,)) — В,(х„~я (х,, х»)) !(6и(~, х„), ! 1г; (х) + В, (х„) в (х)) — ~, (х„х,) — В; (х„Г ~ (х„х,)) ! ~ ~(6»ю(Р, х») з и ~ бл (г', х,) ( би то функция В,(х») й~~ (х„х»)+ В~(х» ~х (х„х,)) — В, (х„О) определяет реализуемую Вб-адекватную модель для ~и т, е. удовлетворяет неравенству ф (х) — В, (х») ((6,. Эта теорема указывает пути целесообразного перераспределения вычислительного ресурса ЭВМ как на уточнение х, так и на уточнение г с целью быстрейшего уменьшения и(» (х) и 6, (6~). Для этого 43 очевидно достаточно находить зависимость скорости убывания величин 60 от объемов вычислений при уточнении х, 7" и В и дальше перераспределять ресурсы на уточнение либо х, либо г или В в зависимости от того, где обеспечивается наиболее быстрое убывание ),, 6„ а значит и ~».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
