И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 79
Текст из файла (страница 79)
рейти к шагу ХЧ. ХХП. Положить в<о = О, и перейти к шагу Х1. Теорема 2. Если выполнены предположения 2, то алгоритм 2 реиюет задачу 2 за конечное число итераций, при етом либо полу- чается точка х*, минимизирующая квадратичную функцию 1,(х) (з — (Ск, х) + (<1, х) на множестве Х, либо устанавливается тот факт, что у,(х)— неограничена снизу на множестве Х. Замечание 2. В случае вырожденности матрицы С может воз- никнуть ситуация, когда на шаге ХЧП алгоритма 2 будет выпол- няться (Ч!,> (х'), Ь"+') ~ О, но (Ь"+', Сйь+<) = О, что влечет рь<л = оо.
Тогда, если. р~+> ( оо, то осуществляется переход к шагу ХХ. Если же рь<.> неограничено, т. е. на шаге ХЧП1 бу- дет выполняться (а', Ь'+>)(0 для всех < ЕР„ то это означает, что задача 2 не имеет решения, так как нижняя грань функции 1, (х) на множестве Х равна — <ю, Замечание 2'. Приведенные в пунктах ! и 2 алгоритмы содер- жат, по существу, одну сложную вычислительную операцию: про- ектирование градиента на подпространство, т.
е. вычисление век- тора (1 — Н~<л>) Чу„(х), что требует нахождения обратной матри- цы (Аь<юА~е<„>) Чтобы избежать вычисления обратной матрицы, можно вначале найти решение и' задачи безусловной минимизации: найти агу гп1п — )~ Ч1, (х) + А~~<,>и<>~'.
(з. шв) и (Задачу (5.108) можно решить, например, с помощью метода сопря- женных направлений). Кроме того, решением задачи (5. !08) являет- ся вектор ио = — (Ат<„А~<„>) ' А-,„,Ч1,(х). 430 Зная и„можно найти вектор (У вЂ” Ндпа) Ч1о(х) по фоРМУла (! — Н~,~) Ч)' (х) = Ч1, \х) + А~ы,~и. 3. Метод еопрямеввых градпевтов дяя еадачи квадрятичвого программвровавив е простыми огравичепивмп 3 а д а ч а 3.
Найти агя пип ~ — (Сх, х) + (а1, х)~, Г 1 «Ех 1 2 где ХЬ(х(х,~О, (ЕВ~); а«'~ — некоторое подмножество множества (1, 2, ..., и); Ы Е В". Предположение 3. Матрица С положительно-определенная. Определение 3. Определим множество У (х) и функцию 1е (х) И (х) с~~ (1 ( х; = О, 1 Е ~+); 1е(х)1х — (Сх, х)+(а(, х).
Алгоритм 8 Н а ч а л о. 1. Выбрать начальное приближение хе ~ Х. П. Найти множество Р (х'). Н1. Вычислить градиент Ча ( о)~~ д/о(х') д1а(ха) )т дх, ' '''' дха 1У. Если 1( ) О Ча~у)(~) дха "го перейти к шагу Ч; иначе перейти к шагу ХЧ1. Ч. Если )а( ) , 'аО, Ч1~3!(хе), дха то положить х' = х' и прекратить вычисления (в этом случае находят оптимальное решение ха задачи 3); иначе положить 3!'(хе) = (!) ' ~в О, аЕ У(хе)) и перейти к шагу Ч1.
Примечание. На последующих шагах применяется метод сопряженных градиентов для минимизации функции )а (х), где в качестве переменных берут только хо 1 Я Р'(х'), а все х,, (ЕО'(хо) приравниваются к нулю. Ч1. Положить Ьа = — Ч~ (ха). Ч11. Положить й = 0 и перейти к шагу Х. Основной цикл. Ч1П. Вычислить Ча ( " (~( д1а(х") д!а(ха) т ез! Если ' = О, Чс )С ГС'(хс), то положить хе =х и перейтй дхс к шагу 11; иначе перейти к шагу 1Х. 1Х. Вычислить вектор ее+с Чс ( «) + 1и)а(хе)Р ье 17)е(х~ ')(е Х.
Вычислить р,„,= — (Ч1,("), йе+ лье+с, Сй ). Х1. Определить 9 (х') — множество всех с )сс гс' (хс), для кото- рых Ь;+ < О. Х11. Вычислить е А+! ре+с = ппп ( — хс/)сс ). ссУ(х'с Х!11, Если ре+с ( ре.с с, то положить хс+ =хс+ре+с)с;+, с я "с'(хс); хс'"' = хс = О, с Е О' (х'), и перейти к шагу Х1Ч; иначе положить хс ' = х; + ри;.сйс~', с' (сс й' (хе); хс =хс =О, сспм'(хо), и перейти к шагу ХЧ.
Х1Ч. Положить й = й + 1 и перейти к шагу ЧП1. ХЧ. Положить хе = хе+' и перейти к шагу П. ХЧ1. Положиться (хе) = й (хе) и перейти к шагу Ч1. Для алгоритма 3 имеют место теорема и замечание, аналогичные теореме 2 и замечанию 2. 4. Модвфипаиил метода сопрлжеввыл иапразлевий длл задач пзадратичвого программирозавил большой размерности 3 ада ч а 4. Найти агдппп1е(х), где се(х) = ( — (х, Сх) + (сс, х)), при ограничениях (а:, х)=Ьс, с'=1, ..., пс; (бы ой) исв~хсв" си„с = 1, ..., а, Сб. Мо) где С вЂ” и х п-матрица (С в О); с( — и-мерный вектор; ас, ) = 1, ..., п — и-мерная строка, т.
е. ас = (а„..., ас,); Ьп 1, ..., лс; и„ис„с' 1, ..., и — действительные числа. Приводимая в этом пункте модификация метода сопряженных бэй направлений приспособлена для задач квадратичного программирования с большим числом переменных х„! = 1, ..., п, и относительно малым числом и ограничений вида (5.109). При отсутствии вычислительной погрешности приводимый алгоритм определяет те же точки, что и метод сопряженных направлений.
Отличием приводимой модификации от метода сопряженных направлений является то, что она требует меньшего количества вычислений, меньшего объема машинной памяти и позволяет устранять накапливающуюся погрешность машинных вычислений. Алгоритм 4 Н а ч а л о. 1. Задать начальное приближение х', удовлетворяющее ограничениям-равенствам (5.109) и следующим неравенствам; ос~х~ <%о 1= 1> ° ° ° 1!. Обозначить через А и х п-матрицу, 1-й строкой которой является аг, 1 = 1, ..., т.
111. Положить й = О. Ос нонна й ц и к л. 1Н. Вычислить множества индексов 6+, О по формулам О+ = (1~ х, ~ шь 1= 1, ..., и); О =(1/хс(оо 1=1, ..., и) и положить О = йг~ () а Ч, Вычислить Чг, (х') — градиент функции цели в точке х ~ х ЧД„(х') = Сх" + г(. Ч1. Для произвольной матрицы В с т строками определить матрицу В, которая получается, если в В заменить все строки с номерами / ~ И+ () О нулевыми строками, и определить матрицу В+ (или В ), строками которой являются строки матрицы В с номерами 1' Е И~ (соответственно, / ~ О ). Ч11.
Для произвольного л-мерного вектор-столбца д оцределить операторы 9тй=д — А (АА ) Ад; (5.11!г (6.112г где б+д = (А ) (АА ) Ад — о .; б~д = д — (А ) (АА ) Аа -г (здесь А — матрица, транспонированная к А). 433 ЧП1. Вычислить векторы 9тЧ~«(х"), 6~~Ч, (х") и положить у = Ото~« (х»). 1Х. Если Ят7~«(х') ~ О, то перейти к шагу ХП; иначе перейти к шагу Х. Х. Если при всех 1 = 1, ..., и выполняется д! ~ О, то прекратить вычисления (в этом случае хь является решением задачи 4); иначе перейти к шагу Х1. Х1.
Построить новые множества в!+ и Р путем удаления из них одного из номеров !' таких, что д! ( О и перейти к шагу ХП. Отметим, что при изменении множеств Г!~ и Р меняются также операторы Ят, б~. На шагах ХП вЂ” ХЧП осуществляется минимизация квадратичной функции !» (х) на подпространстве, задаваемом уравнениями х! =во »сгг+; х! =о„»~О; (а', х)=йн 1=1, ..., т, пРичем минимУм 1» (х) на Указанном поДпРостРанстве НахоДЯт не более чем за п — т — х «малых» итераций, определяемых шагами ХП вЂ” ХЧП, где х — число элементов в множестве а~ () й . ХП.
Положить в = О. Х П1. Положить у' = хь, й' = О. Х1Ч. Вычислить вектор й'+ = — !~~Ч~,(у')+ «~а Ч(,(у')И(~ Ч1,(у ХЧ. Вычислить р,+! = — (71«(у'), й«ы)/(й'+', Сй'+'). Если р,+! = О, !то роложнть х»+' = у' и перейти к шагу ХЧ1П! иначе перейти к шагу ХЧ1. ХЧ1. Вычислить величину р,+! по правилу "' у! . у! о! ь ь р,+! = пнп ппп,+, ', ш!п,+! ~ь»+!>ь ь' ь'+!>» ! ХЧП. Если р,+! ( р,ьь то положить =у +р+!й . в=в+1, В.!. ! 5 »-!-! и перейти к шагу Х1Ч; если р,.ь! з р,+ь то положить =у+р»,!й »+! ! »+! и перейти к шагу ХЧ1П.
ХЧП1. Положить й = й + 1 и перейти к шагу 1Ч. Теорел«а4. Пусть итеративный процесс, задаваемый алгоритмом 4, реализован на ЗВМ и пусть у' — точка, построенная на з-й итерации. Тогда выполняются следующие неравенства: у,'.— ш;(с,и; о,— у,'(с,и; )Ау* — Ь))(сти(1+ Л)))А))+))Ауе — Ь)) (здесь см с,— константы; и = 2' ' — единичная ои4ибка округления (т — число значащих разрядов мантисы); Ь = (Ьы ..., Ь„,); Л вЂ” константа, удовлетворяющая неравенствам 4 (сопб С + (сопб С) — 2) ( Л ( — (сопб С + (сопб С) — 2), где С вЂ” матРица сУженин фУнкЦии 1е (х) на гипеРплоскость (5.109); сопб С й )) С)) )) С ' )) — число обусловленности матрицы С).
Замечание 4. Так как погрешность выполнения равенства (5.109) может расти весьма быстро, то в (209) рекомендуется применять на некоторых итерациях по зследующую процедуру корректировки вычислительной погрешности: у = 0Оу + (1 — 9) у', 0ьпз) где 14 — проектор Дя, определяемый по (5.111) при О~ = ΠΠ— максимальное число из отрезка )0, 1! такое, что правая часть в (5,113) удовлетворяет ограничениям задачи.
й. Устойчивый алгоритм решемва вадач ввадратвчвого врограммвровавва Задача 5. Найти агягп(п — ))бх — с "1т при ограничениях г Ах=Ь, х Во, где 6 — 1 х п-матрица, состоящая из столбцов д(, 1 = 1, 2, ..., и. с — ' 1-вектор; А — т х п-матрица, состоящая из столбцов а1, 1 = 1, ..., й Ь вЂ” т-вектор. В приведенном ниже алгоритме на каждой итерации требуется решать систему линейных уравнений. Алгоритм за конечное число итераций приводит к решению задачи 5 либо устанавливает отсут- ствие допустимых решений задачи 5 и что важно, может применять- ся и в (почти) вырожденном случае задачи 5.
Алгоритм б Н а ч а л о. 1. Найти множество индексов О с= (1,2, ..., и) та- кое, что начальная матрица ) ~ ~ (здесь и далее В~ — подматрица матРицы А, состоЯщаЯ из столбцов а~, 1 ~ о, матРицы А; Ят — под- матрица матрицы О, состоящая нз столбцов йп, 1 б О, матрицы 6), имеет полный столбцовый ранг и система линейных уравнений В,у-Ь; В~та + ()~О~у = Я~~с (6.114) имеет решение (у, и), для которого у ) О. 0 с н о в н о й ц и к л. П. Если д ) О, то перейти к шагу П1; иначе перейти к шагу ЧП. 1П.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
