И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 71
Текст из файла (страница 71)
е. монотонно убывающую последовательность неотрицательных чисел, имеющую своим пределом нуль. Ч. Положить й = О, 1(0) = О. О с н о в н о й ц и к л. И. Если выполняется неравенство )) (хь, бим) ) биль то положить х"+' = Схь, 1 (й + 1) = 1 (я) и перейти к шагу Ч1П; если 0 ( р (х', б,оз) ( бкаь то положить хе+' = Схь, 1(й + 1) = 1(й) + ! и перейти к шагу ЧП1, а если р (х", бит) = О, то вычислить р (х", 0) и перейти к шагу И1. ЧП. Если р (х", 0) = О, то положить х*= хь и прекратить вычисления (в этом случае решение задачи 0 находят за конечное число итераций); иначе положить хе+' = Сх", 1(я+ 1) =1(й) + 1 и перейти к шагу ЧП1.
И П. Положить й = й + 1 и перейти к шагу Ч1. Теорема 1. Если выполняются предположения О, а последовательность (хе!» о, порожденная алгоритмом 1, такова, что последовательность (ге (ха))ь о ограничена снизу, то любая сходящаяся подпоследовсипельность (х~~), о имеет пределом хе; если допол- 382 нительно выполняется условие ~е(Сх)(~е(х), то !ппге(х') =Де(хе), и если, кроме того, точка хе единственная, то 1ппхе = х'.
Ниже приводятся примеры определения операторов С и функций р (х, 6). Пример 1 р(х, 6) = — ппп ((Ч~е(х), $)1(Ч1;(х), $) ( — 6, 1ЕИ(х, 6); (Ц((1, 1= 1, ..., н) = — (Ц~(х), $(х)), где И(х, 6) = (1) — 6(~;(х)~0, 1ЕУ); Сх=х+4(х) (!)О). Пример 2 р(х, 6)=)( ~ о~(х)Ч~8(х)!)= ! /яя'иье) =пи(пД ~ о;Ч7~(х)/!( ~„'о~ — — 1, о;)0,)ЕР'(х, 6)~, ( (!ну мхо ( (!яхчле! где О (х, 6) = О (х, 6) () (0) Сх = х+ 4(х), $(х) = ~ ог(х) Ч~;(х). /яячое) Если в алгоритме 1 функцию р и оператор С определять, как в примере 1, то алгоритм 1 превращается в одну из версий метода возможных направлений; если р и С определять, как в примере 2, то придем к варианту метода одновременного решения пары двойственных задач выпуклого программирования. 2.
Метод унревллюотнл ноеледоветельноетей Ниже приводится алгоритм, синтезирующий методы условной и безусловной оптимизации: в начальной стадии алгоритма используется оператор С, а начиная с некоторого момента вместо оператора С используется оператор релаксации Т. Определение 2. Оператором релаксации Т: У (х', 6) -э (Р (х*, 6) называется такой оператор, для которого выполняется "!Тх — хе(((х — хе (!.
Методы безусловной оптимизации порождают операторы релаксации, обладающие следующими свойствами: 1Т"х — хе!)(а,д", д(1; 383 '(Тьх — »*[< П д„д!-+ 0; Е=! "1 Пах — х' [( азд', д < 1. (8.83) (8.84) Приведем примеры модифицированных операторов релаксации на многообразие активных ограничений, сохраняющих свойства (5.82) и (5.84). Пример 3 Модифицированный оператор градиентной релаксации Тх = (г — (6(г, Р( у), Р(у — ()'(г, Р(у) 6(г, Р(у)), где х=(г, у)ЕВ", ХАЕВ"', УЕВ', и!+г= в; 1 (х) = ( (г, у) = ((! (х), ..., (, (х)); — — !/(Х)[ =~ д ! (Х), д ! (Х))' д1(к) ! д Р(у=у — ~ — ((г, у)~ )'(г, у); 1' (х) = 1' (г у) = - ~ — д„ Р (» у)1 — дг Р (г.
У): 6(х) = — ~,(х)+ — )'4(х)"г'(х), С)О. где 6, Рр г определены, как в примере 3, и матрица Н (х) вычисляется по формуле ! ! где у (г) = (у, (г), ..., у, (г)) — вектор-функция, определяемая неявной системой 1(х) = Цг, у) = О, 384 Модифицированный оператор градиентной релаксации сохраняет свойство (5.82). Пример 4 Модифицированный оператор Ньютона Тх = (г — [Н (г, Р(у)) 6 (г, Р(у), Р(у — )'(г, Р(у) Х х [Н (г, Р)у)) ' 6 (г, Р)у)), а матрица ду (г)/дг вычисляется по формуле — = — ( — ) (х)) — ! (х). дг ( ду I дг Модифицированный оператор Ньютона сохраняет свойство (5.84). Алгорипглг 2 Н а ч а л о. 1. Выбрать оператор С, удовлетворяющий условию (5.82); оператор релаксации Т; функцию р (х, 6), определенную на шаге 1 алгоритма 1.
П. Выбрать произвольную управляющую последовательность (6,)а=а и согласованную с оператором Т управляющую последо- вательность (Л„)Г а. (Управляющая последовательность (Л„)Г=а согласована с опе- ратором Т, если !ппч(Тгх)Л~ = 0 Чхр(р(х*, 6), Ь~п где функция ч (х), характеризующая меру неоптимальности векто- ра х, принадлежащего многообразию активных ограничений, оп- ределяется по правилам т(х) = шах (10(х)$, о(х), ф(х)), здесь 0 (х) определяется в примере 3; ф(х) =шах (1~(х) !1рГг); д о(х) =шах ( — и~ (х))!ЕЮ(х')), (и,(х), 1ЕИ(х*)) = — — „~а(х) х Х(д !( )) Примером последовательностей, согласованных с оператором Т, обладающего свойствами (5.82) — (5.84), являются следующие: ((1+А) )г а, (о )ь а, о<1; ((й+ 1) )г — а).
П1. Выбрать о Р (О, 1). ' 1Ч. Выбрать произвольное начальное приближение ха ~ Х. 'Ч. Положить й = О, 1 (О) = О. 0 с н о в н о й ц и к л. Ч1. Если выполняется неравенство 1г (х", блм) ) блея то перейти к шагу ЧП, если 0 < р (ха, бчм) < бам, то перейти к шагу ЧП1, если )г (х1, бям) = О, то перейти к шагу ХИ11.
И1. Положить ха+' = Сх", ! (й+ 1) = ! (й) и перейти к ша- гу Х1Х. ЧП1. Вычислить значение (г(х", бям), где функция р(х, 6) определяется по формуле р (х, 6) = — ппп ((Ч!а(х), $)((Ч1';(х), $)< Ь, !ЕЮ(х, 6); ! Ес! < 1, ю' = 1э ... э и) э !3 г.гп 333 где множество И(х, б) (/[ — б(Р!(х) 4'.О, /св(]. 1Х. Вычислить и — а(п е, = [(((х», б((»>)] Х. Найти множество индексов б((х», е») = (![ — е»(!((х»)(0, /'ей). Х1.
Положить !(х) =(!! (х), ЯО(х», е»)). д/ (х»/ ХП. Вычислить величину ~([е1 ~ и положить ду Ь (х ) = ~ бе(— д/ (х») ду если Ь (х") ( бндь то перейти к шагу Х1П; если Л (х») ) бпаь то перейти к шагу Х]Ч. Х111. Положить х»+' = Сх", ! (й + 1) = ! (й) + 1 н перейти к шагу Х1Х. Х 1Ч. Положить ха = х». ХЧ. Положить ! = О. ХЧ1. Если ч (х') (/(„то положить х'+' = Тх' и перейти н шагу ХЧ11, если т (х') ) /(„то положить х'+' агипи'и [!а(х) [хЕ (х', ..., х Ц; / (к + 1) = ! (/г) + / + 1 и перейти к шагу Х1Х.
ХЧП. Положить 1 /+ 1 и перейти к шагу ХЧ1. ХЧ111. Если р (х», 0) О, то положить х'= х» и прекратить вычисления; иначе перейти к шагу Ч111. Х1Х. Положить й = й + 1 н перейти к шагу Ч1. Теорема 2. Если выполнены предположения О и (/п) — одна иа функций !! (х), / ~ б(+ (х*), сильно выпукла; (и) — функции !( (х), / Е О Ц (0), достаточно гладки, то в алгоритме 2 последовательность приближений, начиная с некоторого момента, порождается лишь опера(пором Т.
Здесь О+ (ха) = (/ [и( ) О, /Е О (ха)) [] (0), где и! — множители в соотношении Куна — Таккера Ч!а(х*)+ Я и'Ч!((х') О, и,. ~0, /ЕО(х'). %у(х'! Библиографические укаапнпе. При а»писании параграфа пспольэовавы работы 1304, 305, 306]. 5.22. Методы внутренней аппропенмацнн 3 а д а ч а 1. Найти агя ппп уг (х) для заданной функции кех ~>. В"-~В' и заданного множества Х=(х)уу(х)~(0, у 1...., ги, хЕВ"). ПРедположениа У. (!) — фУнкции уп ! = О, 1, ..., ! — диффеРенциРУемые и выпУклые; (й) — фУнкции уп У = ! -1.
1, ! + 2,, ги— дифференцируемые; (11!) — множество Х компактное. Метод внутренней аппроксимации сводится к решению последовательности аппроксимирующих задач выпуклого программирования. В й-й аппроксимирующей задаче каждое невыпуклое ограничение У! (х) а О, у = ! + 1, ..., т, заменяется специально построенным выпуклым ограничением. Алгоритм внутренней аппроксимации прекращает вычисления, когда условия Куна — Таккера, связанные с аппроксимирующей выпуклой задачей, соответствуют условиям Куна — Таккера задачи 1.
Алгоритм 1 Н а ч а л о. 1. Выбрать начальное приближение х' Е Х. П. Положить о,=' 1, (х'). 1П. Найти множество Я,=(х~а~= у,(х), хЕХ). 1Ч. Положить й = 1 Основной цикл. Ч. Выбрать точку х'ЕД ~ и построить функции у, (х, хг), у = ! + 1, ..., т, обладающие следующими свойствами: а) у! (х, х'), у = ! + 1, ..., и — дифференцируемые выпуклые функции; б) у! (х) ( (! (х, х") для всех точек х ~ Х„, где Хь = (х~уу(х)(0, у = 1, ..., у; ~! (х хь) ~ ~О у — у+ 1, ии «ЕВ в) уу(х') =у!(х', х~), !*= у+ 1, ..., т; г) ну!(х~)!охи = Ф~(х', хь)удхо ! = 1, ..., п, ! = 1+ у, ..., лг; д) множество Х» удовлетворяет условию регулярности Слейтера для задач выпуклого программирования.
Ч1. Решить аппроксимирующую задачу выпуклого программирования: найти агд ппп у,(х) для заданной выпуклой функции !а: В" ~ В' кеха и заданного выпуклого множества Хь= (х~уу(х)~(0, 1=1, ..., у; у,(х, х") О, у=у+1, ..., т, хЕВ") и положить о„= т!и у, (х). «ЕХИ 13~ 387 'ЧП. Если а = и«-ь то прекратить вычисления (в этом случае хь — решение для исходной задачи 1 в смысле Куна — Таккера); иначе найти множество г,=( (а,=их).
~Х,) и перейти к шагу ЧП[. ЧП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}
