И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 70
Текст из файла (страница 70)
Теорема 2. Пусть выполняются предположения 2. Тогда предельные точки бесконечной последовательности [х')» о, порожденной алгоритмом 2, являются решением задачи 1. 3. уеаореллма алгоритм Фралаа — ВулФа Алгоритм Я Н а ч а л о. 1. Выбрать произвольное начальное приближение х' Е Х и целое число т ~ О. П. Положить уо = ха, ро| — — 1, й = 1.
Основной цикл. П1. Найти точку у»РХ такую, что (Ц,(х»), у»)((Ч~,(х»), х) для всех хЕХ. 1Ч. Найти число р»Р [О, 1] такое, что 1о((1 — р»)х»+ р»у»)()'о((1 — р) х" + руо) для всех р~[0, 1]. Ч. Положить 1 = О. Ч1. Вычислить числа 3»»л=(1 — р»)!»» для 1=0, 1, ..., Й вЂ” 1; Л»',, = р,. ЧП. Положить г»д (1 — р„) х'+ р„у'. ЧП1. Если 1 л т, то перейти к 'шагу Х1Ч; если!(т, то перейти к шагу 1Х. 1Х. Вычислить множество индексов 3»л1' .(1)( т]о(г»п) у' — г»!) ( О, 1Е (О, 1.. ., Й)).
Х. Вычислить число ф»! и вектор о»4 по формулам ф»у=1/ ~~ )'»,; о»м=ф»л ~ Ъ,'» у'. зв»з 'ку»з Х1. Вычислить число Х»з Р [О, 1] такое, что 1о((1 — Х»з) гав+ Х»лак)(1о((1 — Х) г + Ул»»л) для всех Х~[0, 1]. ХП. Вычислить числа )»»гьь 1= О, 1, ..., я, по формулам 1 Ъ к; 1 = (1 — Х»й + ф~;Хь») Х»л для 1ч Я»,, ),»,у+1 = (1 — Х»п) )»з для 1 Я Р»з. ХП1. Положить г"!+' = (1 — Хь1) гь1-(- Ка,;оа1, !' =)'+1 и перейти к шагу ЧП1. Х!Ч. Положить хе+' = гал и рь4! = )ьа,„!= О, 1, ..., й. ХУ. Если 1о (ха+!) - га (хг), то положить й = й + 1 и пеРейти к шагу П1; иначе положить х* = хьь! и прекратить вычисления (т.
е. в этом случае находят решение х* задачи 1). Для алгоритма 3 имеет место теорема, аналогичная теореме 2. Бибгиографииеекие уиавзния. При написании пункта 1 использовались работы 1320, 130, 222, 4441, пункты 2 и 3 написаны на основании работ !521, 420!.
В работе !424! можно найти дополнительные сведения об алгоритмах Франяа — Вулфа. 5.20. Методы сопрявиенных градиентов 1. Метод сонин!иенвыи градиентов 3 а д а ч а 1. Найти аги ш!п уе (х) для заданной функции хех уе ! В"-» В' и заданного множества Х~(х(11(х) =О, ! = 1, ..., т, хРВ"). Предположения 1. (а) — функции 1! (х), ! = О, 1, ..., т — дважды непрерывно дифференцируемы в окрестности некоторой точки х*, в которой выполняются достаточные условия локального минимума 1 ;(хе) = О, ! = 1, ..., т; Чуе(хе)+ 2, к,Чу;(хе) = О; ! ! ы (Ч~х( (хе)+ ~; )ь;Ч~1!(хе))й, й )а(~й((а, сс)О; 1 ! Я1(хе), й) = О. Для применения метода сопряженных градиентов к задачам условной минимизации необходимо иметь хорошее начальное приближение точки локального минимума х*.
По сути, приводимый здесь метод является методом сопряженных градиентов, примененным для безусловной минимизации некоторой вспомогательной функции. На каждой итерации алгоритма требуется лишь вычислять градиенты функций ) (х), ! = О, 1, ..., и решать задачу минимизации одномерной функции. Алгоритм 1 строит последовательность (хь)а=о, локально сходящуюся к х* с квадратичной скоростью, Алгоритм 1 Н а ч а л о.
1. Выбрать произвольное начальное приближение ха из окрестности точки локального минимума х'. 11. Положить й = О. 378 О с н о в н о й ц и к л. 111. Вычислить векторы Чго (хо), Ч1! (х'), ..., Ч1„(хо). 1Ч. Положить !' = 1. Ч. Положить е<п = Чсс (хо), 1 = 1, ..., т. Ч1. Вычислить векторы е<с>, 1 = 1, ..., т по правилам с с! о-! е<с> = (е<с>, е<с>) е<о ., ЧП. Если 1 = т, то положить ес = е«с>, 1 = 1, ..., сп, и перейти к шагу Ч!11; иначе (если !'(т) положить с' = 1+ 1 и перейти к шагу Ч1. ЧП1.
Вычислить числа с<с — — — (Ч(о(хо), ес), 1= 1, ..., т. 1Х. Определить функцию <Р (х) = 1о(х) + ,'> 7<<1<(х). с=! Х. Положить з = О. Х!. Вычислить и-мерные векторы и' = хо — ~1<(х") е<; ! уо=Ч<р(ио) — ~,(Чр(ио) е<)Ч1<(хо); с ! йо о Х11. Если з = и — т, то перейти к шагу ХЧ1; иначе (если з < ~ и — т) перейти к шагу ХШ. ХШ. Найти число р,) О из условия Ч>(и'+ р,й') = ппп «>(и'+ рй'). рво Х1Ч. Вычислить векторы и'+', ус+<, й'~~! и'~ = й+р,и'! у'"! = Ч<р(и'+!) — ~;(Ч<р(и'+'), ес)Ч1<(хо); с=! й' ' = — а'+'+ ()у~'!Ла*!!)'й'. ХЧ. Положить з = з + 1 и перейти к шагу ХП.
ХЧ1. Положить х'+' = и" — '", й = й + 1 и перейти к шагу 1П. Теорема 1. Пусть выполняются предположения ! и (с!) — ел>орые производные функций ): (х), 1! (х), ..., 7 (х) удовлетворяют в 379 окрестности точки х" условию Липшица; (111) — градиенты Ч1, (хе), ..., Ч1 (х*) — линейно-независимы. Тогда последовательность (х»)» с, порожденная алгоритмом 1, локально сходится к точке х" с квадратичной скоростью, т. е.
1х» хе~)~()-'(()1; х«1)с", й О, 1, ..., где р ) 0 — некоторая константа. 2. Стола«тите«сии адалет метода соври«веввмл тредиевтов 3 а д а ч а 2. Найти агд ш1п 1« (х). ««Х Предположения 2. (1) — функция го ~ В" ~- В' — непрерывно дифференцируема и выпукла вниз; (В) — Х вЂ” выпуклое, ограниченное и замкнутое множество. Стохастический аналог метода сопряженных градиентов может быть применен и в том случае, когда функция (или ее градиент) точно не вычисляются.
На каждой итерации строится вектор стохастического квазиградиента 5 и направление г»+' движения к следующему приближению х»+' выбирается с помощью определенного осреднения векторов $", $ ', $ .... Осреднение реализуется таким образом, чтобы обеспечить (с ростом й) приближение значения г» к градиенту минимизируемой функции в точке х". Алгоритм 2 Н а ч а л о. 1. Выбраты произвольное начальное приближение хе ~ В"; шаговые множители р, (0) и р, (0), удовлетворяющие условиям теоремы 2; произвольный вектор ге ~ В" и произвольное число 6 ~ ) г' (. П. Положить й = О. Оси о в но й ци к л.
111. Вычислить реализацию 5" случайного вектора $, условное математическое ожидание которого Е($»l(хе, ге), ..., (х», г»)) =аЧ1»(х»)+ Ь», (а.во) где сс — некоторое неотрицательное число; Ь вЂ” вектор «ошибки», измеримый относительно о-подалгебры Ж», индуцированной величинами (х', ге), ..., (х", г").
1Ч. Вычислить вектор '+' = г" + р,(й)(Р— г"). 7. Вычислить вектор 6г'+'1'1 г»+' 1, если 1г"+'1) 6. Ч1. Вычислить следующее приближение х"+' = пх (х' — р, (/г) г"+'). Ч11. Вычислить значения шаговых множителей р, (й + 1) и р, (я + 1), удовлетворяющие условиям теоремы 2. ИП. Положить й = й + 1 и перейти к шагу П1. Теорема 2. Пусть выполнены предположения 2 и условия: (1)— градиенты функции уо удовлетворяют условию Липшица $ ~Чо (х) Чо (у)!1 ~~ Рт!1 х у! Рх ( оо (й)— Е(УР1(хо, '), ..., (х", г')) =Ра(оо, и= О, 1, ...; (1»1) — рз (й), р, (й), Ь вЂ” измеримьо относительно о-подалгебры Й» и такие, что 2о ЕР (Я)( Х ЕР»(Я)ЪЬ 1 со~ »-о » — о ~ Ерт(й)(оо, ~р,(й) = оо п.
н, (1о) — для некоторых чисел )ь» выполняются условия р, (й) + ра (к) (1 Ь» 1 — "ь»ра (к) ( О п. н; )." ЕЛ,(р,(й)+ р,(йи(Ь1): Тогда последовательность (ха)»=о, порожденная алгоритмом 2, почти наверное сходится к решению задачи 2 (а если решение не единственно, то (х»)» о сходится к одному из решений). Замечание 2, В случае ( Ь (! — 0 условия теоремы 2 ((и) и (1о) выполняются, если только выбрать йт+ (й) йо.
2 1 т где числа т и е определяются неравенствами — 1 ( е С вЂ” т/а; — (1+ е)(т( — (1+ е)/2. Библиографиоеасио указания. Пункт 1 написан на основании работы [2321, пункт 2 основан на результатах работы 1981. 5.21. Методы управляющих последовательностей 3 а д а ч а О. Найти аги ппп уо (х) для заданной функции них 1»: В"-ь В' и заданного множества Х~~ (х!~у(х)~~0 1ЕО хЕВ ) О = (1 ... т) ° Рредположения О. (1) — функции До и ~;, 1 ŠΠ— выпуклые; (Й) — существует точка хо = агн гп!п 1, (х) й градиенты Ч~; (х*), хех 381 1 с О (х*) — линейно независимы, где Э (х*) = (1 ! 1, (хе) = О, ! Е ~ в') (в дальнейшем предполагается, что У (х*) = (1, ..., г)); (ш)— дифференциальное преобразование ~ — 1 (х)), ! = 1, ..., г, непре) д рывно в области (т (х*, 6) = (х ( ( х — х' (( 6), где б ) 0— достаточно малое число.
В методе управляющих последовательностей на основе методов безусловной оптимизации строят операторы релаксации на нелинейном многообразии в окрестности решения х*, которые порождают последовательности приближений (хе)а=о, локально сходящиеся к решению х* с быстротой соответствующих процессов безусловной оптимизации. В начальной фазе различные конкретизацйи общего метода управляющих последовательностей совпадают с процессами оптимизации при наличии ограничений, а в заключительной фазе — с процессами безусловной оптимизации.
1. Оатий метод мииимиеации ири наличии отраиичеиий Различные методы оптимизации при наличии ограничений являются конкретизациями общего алгоритма. Алгоритм 1 Н а ч а л о. 1. Определить на Х к Вч~ неотрицательную полу- непрерывную снизу в точках (х, 0), х б Х, функцию р (х, 6) такую, что из р (х, 0) = 0 следует х = хе (здесь 6 — достаточно малое число). П. Определить оператор С: Х е- Х, удовлетворяющий условию ге(х) — 1е(Сх)~~о(6))0, Чх~(х!~а(х, а) . 6, 0(е(6). (8.80 1П. Найти начальное приближение хе Е Х. 1Ч. Выбрать управляющую последовательность (6,); о, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
