И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 57
Текст из файла (страница 57)
(Если хе — оптимальное решение задачи 1, то ае (хе) = 0). 2. Методы аоаможвыв вавраавевва решении аадач миввмваанив с ограничеиивмв смешанного твва 3 а д а ч а 2. Найти аги ппп ге (х) для заданной функции «ях )о: В" — ». В' и множества Х, заданного функциями ~~. В"-»- В', 1 = 1, ..., т, матрицей А размера 1 х и и 1-мерным вектором Ь, Х('.1 (х) 7г(х)(0, 1р!1: т], Ах — Ь = О, хб В"). Предположения 2. (1) — функции ~п 1 = О, 1, ..., т — выпуклы и непрерывно дифференцируемы; (И) — множество Х вЂ” компактно; (ги) — существует такая точка хр В", что Ах — Ь = О, ~~(х)(0, 1Е [1,т].
Алгоритм 2 Н а ч а л о. !. Вычислить начальное приближение хе ~ Х. П. Выбрать константы е, ) 0 и 6; ) О, 1 = 0,1, ..., т. 1П. Положить й = О. Основной ци кл. ]Ч. Вычислить множество индексов й ее (х ) Й (0) [] (1 ( ~у (х ) ) )— зм 1 Е [1: т]) . Ч. Найти решение а = а„, й = й", задачи линейного программирования в (и + 1)-мерном пространстве векторов (а, й): пип а (о,е» прн ограничениях (Ч~г(хе), й)(б;а, 1~6, (х'); Ай=О; (й((1, 1=1, ..., и. 30! Ч1. Если а» = О, то перейти к шагу ЧП; иначе перейти и шагу Х. ЧП. Вычислить множество индексов ~е (х») Й (0) Б ()! Г! (х«) > О, / Е 11: т1,'. Ч1П. Вычислить число у„= — шах ~~ (х"). !ФУи «) 1Х.
Если е»(у», то положить х«= х«и прекратитьвычислениц; иначе перейти к шагу Х. Х. Если и» ~ — е«, то перейти к шагу Х1; иначе перейти к шау ХЧП. 'Х1. Положить г = О. ХП. Положить р, (»/»)'. ХП1. Если выполняются неравенства й(х + Р»1«") ~ й (" ) + з 8 Р» «! ! ~!(х»+р»Ы~(0, )=1,... т, то перейти к шагу ХЧ; иначе перейти к шагу Х1Ч. Х)Ч. Положить в = г + 1 и перейти к шагу ХП. ХЧ. Вычислить следующее приближение х»+' = х'+ р»й«. ХЧ1. Положить з«+~ е», й = й + 1 и перейти к шагу 1Ч.
ХЧП. Положить х"+' х», е»+~ = е»/2, й = й + 1, и перейти к шагу 1Ч. Теорема 2. Если выполнены предположения 2 и, кроме того, градиенты функций ~п !' = 1, ..., т, удовлетворяют условшо Лшииица 1711(х) — 7~,(у))«.::у)х — у), у<ос, х, у~В", то бесконечная последовательность (х»)«. », порозсденная алгоритмом 2, обладает тем аюйством, что (1«(х»))Г» монотонно не возрастая, стремится к значеншо 1«(х"), где х~ — точка минимума фун кции !«(х) в области Х. Если х« — единспменная точка мин и- мума, то х«-«- х«при я-«оо. Ниже приводятся рекомендуемые в 128И два метода возможных направлений, удобные для реализации их на ЭВМ.
Алгоритм 2' Н а ч а л о. 1. Выбрать константы е' ) О, е' ~ (О, е'), Х ~ О, Р'6 (О 1). Р'6 (0,5; 0,8) и целое число я, удовлетворяющее условию 5 ( с ~~ 10. зоз П. Если имеется вектор х', удовлетворяющий условиям 1;(х')~(0, [с[1'ги[; Ах' = Ь, то положить х' х' и перейти к шагу ЧП; иначе перейти к ша- гу П1, П1. Вычислить вектор х', удовлетворяющий условию Ах' Ь. [Ч.
Вычислить а =шахф(ха), )е[1'т)). Ч. Использовать шаги ЧП вЂ” ХХ1 алгоритма 2' для решения задачи минимизации в (и+ 1)-мерном пространатве векторов (а, х):ш[п а при ограничениях (а,к) ~~ (х) ( а, 1 Е [ 1: т[; Ах = Ь о начальным приближением (а„ ха) до тех пор, пока при некотором й = й, не окажется, что ~~(х ')(О, 1Е[1:т), Ах'= О. Ч1. Положить ха = ха' и перейти к шагу Ч[1.
О о н о в н о й ц и к л. ЧП. Положить й = О. ЧП1. Положить е = е'. 1Х. Положить х = х'. Х. Найти множества индексов й,', Я„определяемые соотношениями О.' [) Ф.- [О) [) [ЦУх)+а~О, И[1:ш[); Ие [) йе Ы[ обй 1 Е И„только если функция ~~ аффиниа. Х1. Решить задачу линейного программирования в (и + 1)-мерном пространстве векторов (а, Ь): пцп а при ограничениях счм (Ц~ (х), 6) е а, 1' Е й~; (7~((х), Ь)~0, )ЕУв, [Ь,[~1, 1=1, ..., п[ АЬ 0 н обозначить ее решение через (а„й6).
о ь Х11. Если а,'( — Хе, то положить ль = й, "и перейти к шагу ХЧ1; иначе перейти к шагу ХП1. Х1!1. Если е ( е", то перейти к шагу Х!Ч; иначе положить з = ()'з и перейти к шагу Х. Х1Ч. Положить з = з. ХЧ. Положить з = 0 и использовать шаги Х, Х1 алгоритма 2' для вычисления вектора (с4, Ь~~). Если с4 = О, то положить х"'= х и прекратить вычисления; иначе положить а = р'е и перейти к шагу Х. ХЧ1. Положить з = О. ХЧ!1. Положить р„= (р")'. ХЧП1. Если выполняются неравенства !0(х+ риЬ) — !0(х) рД~10(х) Ь )(0 1~ (х + р,Ь ) ( О, ! Е(1: ш), то перейти к шагу Х1Х; иначе положить з = з + 1 и перейти к шагу ХЧ11.
Х1Х. Вычислить следующее приближение х~+' = х + р„Ь". ХХ. Положить Ь = Ь + 1. ХХ1. Если число Ь кратно т, то перейти к шагу ЧШ; иначе перейти к шагу 1Х. Алгоритм 2" (алгоритм2' можно применять для решения задачи 2 лишь при выполнении условий регулярности Куна — Таккера) Н а ч а л о.
1. Выбрать константы е' ) О, е" ~ (О, з'), Л' ) О, Л" ) ) О, (!' Е (О, 1), р' Е (0,5; 0,8) и целое число т, удовлетворяющее условию 5 ( т ~ 10. П. Вычислить начальное приближение х', удовлетворяющее условиям (шаги П вЂ” Ч! алгоритма 2') гу(хч) < О, /Р(1: ш); Ахз = Ь. Ш. Положить Ь = О. Основной цикл. 1Ч. Положить е=е'. Ч. Положить х = х~. Ч1. Найти множества индексов О,' и й!'„как на шаге Х алгоритма 2'. ЧП.
Решить задачу линейного программирования в п-мерном пространстве векторов Ь: минимизировать (Ч 1, (х), Ь) при ограничениях (Ч7!(х), Ь)+Л'в~~О, !ФО, !Ей (7!у (х), Ь) ~ О, ! Е Ие~ ~Ь,~(1, 1=1, ..., и; АЬ= 0 и обозначить ее решение через Ь,. 304 Ч1П. Вычислить ае = (Ч1» (х)~ йе). 1Х. Если а, ( — Х"з, то положить й» = Ь» и перейти к шагу ХЧ; иначе перейти к шагу Х.
Х. Если з ( е", то перейти к шагу Х1; иначе положить е = р'а и перейти к шагу Ч1. Х1. Положить а = е. ХП. Положить е = О и использовать шаги Ч1, ЧП алгоритма 2" для вычисления вектора Лом Х1П. Вычислить ао = (Ч1о (х), Ло). Х 1Ч. Если а, = О, то положить х'= х и прекратить вычисления; иначе положить з = ])'е и перейти к шагу Ч1. ХЧ. Положить з = О. ХЧ1. Положить р» = (р ) ° ХЧП. Если выполняются неравенства 1»(х+ р,й») — 1,(х) — — р,(71о(х), й») (О; 1»(х+ р»й»)~(О, 1Е(1:т], то перейти к шагу ХЧШ; иначе положить з = з+ 1 и перейти к шагу ХЧ1. ХЧП1.
Вычислить следующее приближение х»+' = х+ р»1»». Х1Х. Положить й *= й + 1. ХХ. Если число й кратное т, то перейти к шагу 1Ч; иначе перейти к шагу Ч. 3. Метод воомомвыл иаправлевия с ивадратвчвым ловеком В методе возможных направлений с квадратичным поиском для вычисления вектора движения й» к улучшенному (й + 1)-му приближению к искомому решению используются члены, содержащие вторые производные минимизируемой функции. Очевидно, эти алгоритмы имеют большую скорость сходимости, чем алгоритмы с линейным поиском, однако на каждой итерации требуется решать задачу квадратичного программирования. Предложенный в ]285] алгоритм 3 можно применять для решения задачи 2 в том случае, когда собственные значения матрицы Гессе Н (х) Д д»1, (х)!дхо далеко разнесены, когда выполнены условия регулярности Куна— Таккера и матрица вторых производных Н (х) ~ д»1»(х)!дх» положительно полуопределена на множестве ХоЬ(х]1о(х)~(1»(х'), 1~(х)е;О, 1Е(1:т], Ах= Ь), где х' — начальное приближение.
303 Алгоритм Я Н а ч а л о. 1. Выбрать константы е'~ О, е Е (О, е'), Л' ) О, Л" ) О, р' Р (О, 1), Р" Е (0,5; 0,8) и целое число т, удовлетворяющее условию 5 ( т ( 10. 11. Вычйслить начальное приближение х', удовлетворяющее условиям (о методе вычисления х' см. шаги 11 — Ч1 алгоритма 2'). 111. Положить Ь = О. Основной цикл. 1Ч. Положитьа=е'.
Ч. Положить х х». Ч1. Найти множества индексов й,', И'„как на шаге Х алгоритма 2'. Ч11. Найти решение Ь = Ь", задачи квадратичного программирования в л-мерном пространстве: найти агяш(п~ — ( ~'„г ) Ь, Ь)+(Ч~г(х), Ь)) при ограничениях (Ч$~(х), Ь)+Л'е(0, 1чьО, 1ЕФг; (ЧР!(х), Ь)(0, 1ЕУв' ~Ь,~(1, 1=1, ..., и; Ч1П. Вычислить ~, = — ~ — ф~ — Ь~~, Ьг) + (Ч~~ (х), ф. 1Х.
Если а,( — Л'е, то положить Ьг = Ь', и перейти к шагу Х1Ч; иначе перейти к шагу Х. Х. Если е(з", то перейти к шагу Х1; иначе положить а *= р'е и перейти к шагу Ч1. Х1. Положить з = е. ХП. Положить е'= 0 и использовать шаги Ч1 — Ч1П алгоритма 8 для вычисления значения з ~ ~~3 ЬО~ ЬО~ + (Ц~(х) ЬО)' Х111. Если и, = О, то положитьх*= х и прекратить вычисления; иначе положить е = р'е и перейти к шагу Ч1.
Х(Ч. Положить з = О. ХЧ. Положить р = (р")' ХЧ1. Еали выполняются неравенства Уе(х+ Рай") 1е(х) з Ре(ЧУе(х) й") ~<0~ 1 уу (х + реу1) д-. О, у Е [1: т], то перейти к шагу ХЧП; иначе положить з = з + 1 и перейти к шв- у ХЧ. ХЧ11. Вычислить следующее приближение хе+1 «+ р„ь». ХЧ1П. Положить й = й + 1. Х1Х. Если число й кратное т, то перейти к шагу 1Ч; иначе перейти к шагу Ч. 4. Модвфвдвроеаввый метод аоемомвыа вавраваеввй Зойтевдейва Задача 4. Найти агйшупУе(х) для заданной непрерывной «ЯХ функции уе . 'В" -~. В' н множества Х~(х~Уу(х)=0, у 1, ..., У; уу(х)~0, у у+1, ..., т; хЕВ"), где У~ .
В" -~ В', у = 1, ..., т — заданные непрерывные функции. УУредположения 4. (У) — функции уу (х), у О, 1, ..., т непрерывно дифференцируемы в В"; (И) — 1 ( и. Решение задачи 4 сводитая к решению следующей вспомогательной задачи: найти агйшуп(уе(х)+а ~уу(х) при ограничениях е / 1 — уу (х) е=; О, у ° 1, ..., т, где а ~ 0 — некоторый параметр. Любой минимум вспомогательной задачи, локальный илн глобальный, достигаемый в точке х с уу (х) = О, у 1, ..., У, является также локальным нли глобальным минимумом задачи 4. Дпя решения вспомогательной задачи используется метод возможных направлений Зойтендейка, дополненный процедурой вычисления подходящего значения параметра а.
Алгоритм 4 Н ачало. 1. Найти начальное приближение хе~ Х+, где Х+= (х~уу(х)~ЗО, у 1, ..., т, хЕВ"). (8.88) 11. Выбрать константы р > О, ее оО, а'> 0(з'(( зо) 1) с(0.1) 9 ~ (О, 1), сс ь ) О, б ) О. 807 П1. Для заданных чисел а) О, е) О определить функции с[л,: В"-» В' и Ол: В"-л. (1, ..., и) по правилам с Ф„(х) ~1 гл (х) + а 2, ~~ (х); с 1 Осл(х) ~ (1! — ~~(х) ~в — е, 1Е [1:лс)). 1Ч. Определить функцию ил,: В" -~ В' по правилу д„(х) = ш!яшах ((Чф„(х), Ь), — (Ч)с(х), Ь), !'ЕР,(х)) !з.за) лЕз где 3=(Ь)(йс[(1, с=1, ..., п, ЬЕВ") Ч. Положить Ь = О, а = ал.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
