И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 47
Текст из файла (страница 47)
Вычислить величину т! = ) (х, д) — ~,(д) у'(~,(д) !. Если и ) т)~, то положить е = ре и перейти к шагу 1Х; если В (~ т!', то перейти к шагу ХЧ1, ХЧ1. Если 1х — (х, у)е(( ба, то прекратить вычисления (в этом случае точка х принимается за решение вспомогательной 245 Х1. Положить ч = !. Х11. Выбрать алгоритм А для решения следующей задачи квадратичного программирования. найти агп ппп 1х+ ~, у,а')е, !4.42) а-,чд,<а+ муе мяв где норма ! ° (а определяется по правилу (4.41). Х1П. Найти приближенное решение уь ! Е Р„задачи (4.42), применяя ! итераций алгоритма А.
Х1Ч. Вычислить вектор х = х+ ~' у~а'. муз з адачи, а вектор у = (у« " у ) где !ЕО«; ус = а„(Я О„> =!» ... л, принимается за приближенное решение задачи 3); иначе перейти к шагу ХЧП. ХЧП. Вычислить вектор о = (х — (х, д) е)~~~ х — (х, д) е (. ХЧ1П. Вычислить значения «р, = (о, а') — >р, (е, о), 1 = 1, ..., л. Х1Х. Вычислить значение ~ у",— а+, если ф(О, к 1« — (х,х)«1 ~ст ( У~~ — а~-, если ф~)0. ХХ.
Если д ) б«(в этом случае задача (4.42) ие решена с тре- буемой точностью), то положить т = т + 1 и перейти к шагу Х1П, принимая за начальное приближение алгоритма А приближенное решение у~ ' задачи (4.42), полученное на (т — 1)-й «малой» итерации; если «( ( «!«, то перейти к шагу ХХ1 для пересчета век- тора у.
(«Малые» итерации порождаются шагами Х1 — ХХ алгоритма 3. Новый вектор д определяется как «г = у (р) (1 — р (е, о)) у+ ро, где параметр р = ягошах пни (х, у(р)). На шагах ХХ1 — ХХХ » «и« алгоритма методом «деления вилки» вычисляется нужное значение р за конечное число итераций. Величина (х, д) является верхней оценкой для»,«, точной лишь при ) х)о = 0).
ХХ1. Вычислить значение ~.=(, ) — Ь(. ). $ -(, у) ХХП. Положить иР = (1, 0), и>« = (О, 1). ХХП1. Для вектора и> = (п>„п>«) определить функцию (а~-, если н>,ф, + «о«ф,(0, ~ (ш) = ь«+ ~ ф, х [ (а,, в противном случае. ХХ1Ч. Если ~ (и>«) = О, то прекратить вычисления (в этом случае исходная задача 3 не имеет решения), если ь (и>«) ( О, то перейти к шагу ХХЧ. ХХЧ. Положить ! = 1. ХХЧ1.
Вычислить вектор Х» 2 ( + ХХЧП. Если ь(Х») ) О, то положить о»+' = Х», ш»+' = » ! = ! + 1, и перейти к шагу ХХЧ1П, если ь(Х») ( О, то положить ш»+' = и»», и»»+' = Х», ! = ! + 1 и перейти к шагу ХХЧ1П. ХХЧП1. Если ) г⻠— и~) ( го„то перейти к шагу ХХ1Х; иначе перейти к шагу ХХЧ1. ХХ1Х. Вычислить Р (го2 + го2)!(м(+»о()~ где (в',, и4) =ш', (и»ь и»»в) =и»». ХХХ. Вычислить вектор д =(1 — р(е, о))д+ ро. ХХХ1. Положить д = д и перейти к шагу Ч. Теорема Ю. Пусть основной итерационный цикл )» — ХХХ! приводит к переходу от вектора дв к вектору д~+'.
Пусть этот переход совершается в ситуации, когда приближенное решение задачи минимизации ('4.42) дало тоюсу хв !при переходе от шага ХХ к шагу ХХ!), удовлетворяющую условию й ( йе. Тогда !. (у"+') ) !е (и') + з "1 'Ь(1 — й'), где !е (у) определяется по (4.40), а норма ) (о — по (4.4!). Алгоритм 3 за конечное число итераций находит приближенное решение х вспомогательной задачи и отвечающее ему приближенное решение у задачи 3.
Сходимость!~ ⻠— и» '1 к нУлю имеет поРЯдок ('!з)», позтомУ требуемая точность гое достигается за сравнительно небольшое число итераций по !. 4. Алгоритм «Заац» ретеикл вракой и двойетвевкей задач ликекиого крограммировавив 3 ада ч а 4 (прямая задача). Найти агя шах (с, х) для задан«ья ного вектора с б В" и заданного множества Х~й(х(Ах(Ь, х вО, ЬЕВ, хЕЩ. 24Т 3 ад а ч а 4' (двойственная задача). Найти агя ппп (у, Ь) для гав заданного вектора Ь р В и заданного множества У~(у(уА~с, у~О, срВ", урВ ).
Предположения 4. Задачи 4 и 4' — разрешимы. Решение пары двойственных задач 4 и 4' сводится к решению следующей вспомогательной задачи нелинейного программирования: найти агя ппп д (х, у, $, Ч) при ограничениях ылсвф х вО, 5~ох, ~~те"; 14АЗ) у~О, чубу, Ч~~те", где у(х, у, $, и) =(у, Ь)+ (д(у), $) — (с, х) — (р(х), т1); д (у) = гпах ( — уА + с, О); р(х) = шах(Ах — Ь, 0); е" р В", е р  — векторы с единичными компонентами; о, т— константы, удовлетворяющие условиям 1 «о < 3, т ) О.
Если вектор (х*, у', $*, г)') — решение вспомогательной задачи, то х* — решение задачи 4, а у' — решение задачи 4'. Алгорипгм 4 Н а ч а л о. 1. Выбрать произвольные начальные приближения х' Е В+. у' Е В+ 11. Выбрать константы а и т из условий 1<о<3; т)0. 1П. Выбрать векторы вг = ($1, ", $.), т)'= (з~ь... П ), умов- летворяющие ограничениям (4.43) при х = х', у = у'. 1 1Ч. Выбрать константы 1 и р < — (1 ) р), определяющие шаго- вые множители алгоритма. Ч. Выбрать константу е ) О, определяющую точность вычис- ления оптимального значения задач 4 и 4'. Ж1. Положить х = х', у = у', $ = зг, т) = Ч' р~= — оо т~ = = +со, у = у', д = О, й = 1, р = Н .
Ос но в но й пи к л. Н11. Вычислить векторы х (у) = = (х, (у), ..., х„(у)), у (х) = (у, (х), ..., у (х)) по формулам (О, если о,=О, ~(У) ~5Ь если дг)0, (О, если р,=О, где р = шах (Ах — Ь, 0); д = !пах (с — УА, 0). ЧП1. Вычислить следующие приближения х+ и у+ т+! 4+1 х~+! = (1 — р) х~+ рх(у); у«! = (1 — р) у~ + ру (х) и положить х = хь«-«, у = уь«-! 1Х. Если р ) р, то перейти к шагу Х, если р ( р, то перейти к шагу ХП.
Х. Положить Ь = й + 1, «1 = «(+ р и перейти к шагу Х1. Х1. Если «т' в 1, то положить «( = О, р = р/2 и перейти к шагу ЧП, если «1 ( 1, то перейти к шагу ЧП. ХП. Вычислить значение «р (х, т)), где функция «р (х, т)) определяется по правилу «р(х, т)) =(с, х) — (т), р), р = шах (Ах — Ь, О) (4.44! и положить «р = «р (х т)) ХП1.
Если «р ) «р, то перейти к шагу Х1Ч; иначе перейти к шагу ХЧП. Х1Ч. Положить «р,= «р, х = х. ХЧ. Вычислить вектор .9 (х) = шах (ох, те") и положить $ $ (х). ХЧ1. Вычислить значение ф (у, $), где функция тр (у, $) определяется по правилу «Р (у, $) = (у, Ь) — («), $), «) = шах (с — УА, 0) (4.4з) н положить ф, = тр (у, $). ХЧП. Вычислить значение тр (у, $), где функция ф (у, $) задается по (4.45), и положить «Р = «Р (у, $). ХЧШ.
Если тр(тр„то перейти к шагу Х1Х; иначе перейти к шагу ХХП. Х1Х. Положить ф! = ф, у = у. ХХ. Вычислить вектор т)(у) = шах (оу, те") и положить т) = т) (у) ХХ1. Вычислить значение «р (х, т)), где функция «р (х, т)) задается (4.44) и положить «р,= «р (х, т)). ХХП. Вычислить 14 = («р, + ф!)/2. ХХП1.
Вычислить Ь = (ф — «р )/( Уа (+ 1) 249 ХХ1Ч. Если 6 ( е, то положить х» = х, у»= у и прекратить вычисления; иначе перейти к шагу Х. Теорема 4. Если выполняется предположение 4, то точки х", у» и значения 1», порождаемые алгоритмом 4, удовлетворяют соотношениям 1ппх»=хе; 1ппу" =у*; 11ш1»=(с, х*)=(Ь, у*). е О е О е О б. Итерадвоввый метод, вевольаующвй модвфвдвроваввую фуввдвю легравюа длл решеввл даойетвеввей вары задач лввейвого врограммвроваввв 3 а д а ч а 5.
Найти агя гпах ~„с!х! при ограничениях к! !=! л ~, ае!х!(Ье, ! = 1, ..., т: ! ! х!~О, /= 1, ..., и. Двойственной к задаче 5 является следующая. л 3 ад ач а 5', Найти атаги(п~; Ь,у, при ограничениях г. е=! ! ~а!!у! всп !=1, ..., и; ! 1 у!~О, е=1, ..., т. Предположение б. Множества оптимальных решений Х* и )'е, соответственно, задач 5 и 5' непусты и ограничены. В приводимом ниже алгоритме отыскание оптимальных решений Хе и У' задач 5 и 5' сводится к вычислению множества седловых точек модифицированной функции Лагранжа пары двойственных задач 5 и 5': л /л ел л ер„(х, у) = ~, с,х; + ~ Ьеу, — ~~', ~' ае;х;у;— !=! ! 1 ь=! у=! Х[ 2 (( ее(х))+) +ул(ее(х))у!~+ е=! л +Х[ —,(( — ~;(уП+) +ул(~!Ы) !1.
(=! где 6;(у) = Е а!!у! — с!, 1= 1, ..., и; ! ! 250 х=(х„..., х„), у=(у„..., у,„); е, (х) = — ~, "ассхс + Ь„с = 1, ..., лд; с=! О, и(0, ( )+, и)0; О, если 1(0, с/„(1) = аР/2, если 0(1(1/а, 1 — 1/2а, если 1) 1/а; а ) 0 — параметр. При этом множество седловых точек функции ф (х, у) при любом а ) 0 состоит из множества Х* х У*. Седловые точки функции ф~ (х, у) находят градиентным методом. Отметим, что применить градиентный метод для отыскания седловых точек обычной функции Лагранжа ф (х, у) в виде л ИЗ ас й ф (х, у) = ~ с;хс + ~, Ьсус — Е 1 ас;хсус с=! с ! с=! с ! в общем случае невозможно из-за неустойчивости множества седловых точек этой функции (определение устойчивости седловых точек приводится в $6.9 (пункт 3)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
