И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 51
Текст из файла (страница 51)
Положить х»+ =х' — р,(х" — у'„). й=й+1 ""'р'"'и к шагу П1. 3 а д а ч а 1. Найти агя ш(п)о (х) для заданной функции ях 1»: В"-о 1(' и заданного множества Х ~ В". Предположение 1. (1) — функция )о выпукла вниз и непрерывно дифференцируема на множестве Х; (11) — Х вЂ” выпуклое замкнутое множество; (Н()— '1Ч1о(х) — Ч7»(У)Ц(У(х — У), 0<У<со, Чх, УРХ.
Алгоритм 1 Н а ч а л о. 1. Выбрать начальное приближение х' Р Х. П. Положить й = О. Оси о в но й пи кл. П1. Вычислить Чго(х»). 1Ч. Выбрать множитель р», удовлетворяющий одному из заранее выбранных условий 0 < р' < р» < р'<+ щ ($. ().
0 < р' < р» (()' < 21у. ($.2) Ч. Вычислить точку у»Е В" по формуле у» = х» — р»Чго (х»). Ч1. Вычислить точку у»х — проекцию точки у" на выпуклое замкнутое множество Х. ЧП. Если р» выбирается в соответствии с неравенствами (5.2), то выбрать множитель р„, удовлетворяющий неравенствам 0<р<р„<1 ($.3) и перейти к шагу ЧП1, если ()» выбирается согласно (5.!), то вычислить множитель р» по одной из формул 1»(х Р»(" Ух)) = ш)п 1о(х — Р(х — У»х)) ($4) очрап Предполагается при этом, что р„на каждой итерации вычисляется по одной и той же формуле.
Теорема 1. Пусть выполняются предположения 1 и ((о) — множество Хай (х!Уе(х) (Ро(хо) хЕ Х) ограничено; (о)— ЗЧ7о(х)((т<+ оо для всех хЕХе. Тогда алгоритм 1 порождает последовательность (х")Г е такую, ) (х") — щ)п1 (х)(а1й, й О, 1, ..., а)О. кех Причем: а) если в алгоритме 1 !)а удовлетворяет неравенствам (5.1), а ре — равенству (5.4), то справедлива оценка 1е(~") — 1о(х'+')>(~ Р— — 'Р)1Х' — У„"(', й-О, 1, ..., е 2 где О( р с ппп11 — —.~; тй (' 5) если в алгоритме 1 ()ь удовлетворяет неравенствам 1'5.1), а рь вычисляется по (5.5), то справедлива оценкаг при ра = 1 Ье(х') — Уо( '+')> 25.! "— Уат!!' Ь=О, 1, " ' при ра — — т,(Ч~,(ха), х" — ухайха — уьх(а уо(х') — уе(х'+') > ° (х" — у,"!! й = О. 1 ": В) если в алгоритме 1 ()а удовлетворяет неравенствам 1'5.2), и ров (5.3), то справедлива оценка Ихь) — 1 (ха+') > р( —.
— — ")1х' — у' !!'. 2. Метод проенпип градиента диа мннимнааиии фгеинпа при ннпеанмн ограиичениаи 3 а д а ч а 2. Найти агя ппп 1о (х) Дла заданной фУнкцин аЯХ 1е: В" -~- В' и заданного множества Х= (х)(а~, х) — Ь;(О, 1=1, ..., т, х~В"), где а!ЕВ"; Ь,ЕВ'. )=1, ..., т. Предположение 2.
Функция 1о выпукла и непрерывно дифференцируема. Обозначения и определения. 1. Произвольное подмножество множества (1, ..., т), содержащее т' элементов, обозначим через й. 270 2. Матрицу размера и х и)', столбцами которой являются векторы а(, / с е(, расположенные в порядке возрастания 7', обозначим через Ау. 3. Матрицу проектирования В" на подпространство 1,у, порожденное вектоРами а), 7' С а, обозначим чеРез Ру.
,4. Если векторы а), 7' Е 5(, определяющие подпространство 1.у, линейно независимы, то матрица, проектирующая В" на подпространство ?.у, вычисляется по формуле Ру —— Ау(АутАу) ' Аут. ($.6) Если векторы а(, ) ~ а линейно зависимы, то необходимо найти подмножество И' такое, что векторы а), 7' Е И' будут линейно независимы и порождают ьу, а проектирующаяматрицаРу — — Ру будет определяться (5.6) при О = а '. 5. Матрицу проектирования В" на ортогональное дополнение к 1.у обозначим через Руе ! Ру где ! — единичная и х п-матрица. 6. Обозначим через й, (х) з-активное множество индексов, опре- деляемое формулой г),(х) = (!((а), х) — ()(+з, )О, 7'=1, ..., и, хЕХ), где а~О. Утверждение 2. Точка х Е Х оптимальна в задаче 2 тогда и только тогда, когда (()?е(х) = Ау(, уе(х), т.
е. Рух д'Р?е(х) = О; уе(х)(О, Ф где уе (х) вычисляется по следующей формуле (при з = О и х = х): т т е' (х) = (Ау (е) Ау (е)) Ау ( ее)(ее (х). (5.7) Заметим, что матрица Ру,, проектирующая В" на подпрое(") стРанство Лу, ) натЯнУтое на вектоРы а), 7' С Уе (х), вычислаегсЯ е(М' по формуле т — т Ру (х) Ауе(е) ('4уе(е)'4у (е)) Ау (е) если выполнено предположение 2'. Предположение 2'. Существует такое число е') О, что для любой точки х с Х и любого числа з Е (О, з') векторы а), ) с г?е (х) линейно независимы.
271 Ч1. Вычислить вектор Ь'l (х) = Р~~Це(х). (8.9) ЧП. Если ) Ь'((х) 1е ) е,, то положить Ь (х) = — Ь'( (х) и перейти к шагу ХЧП; иначе йерейтн к шагу ЧП1. ЧП1. Если е е", то вычислить множество индексов Ое (х) н перейти к шагу 1Х; иначе перейти к шагу ХП. 1Х. Вычислить вектор Ь'(х) = Рф Чге(х), где Ру — матрица, определяемая по (5.8) при О = 5(е. Х. Вычислить вектор у' (х) по (5.7) при е = О. Х1.
Если ) Ь' (х)1е = 0 и уе (х) < О, то положить х' = х н прекратить вычисления; иначе перейти к шагу ХП. ХП. Вычислить вектор у'((х) по формуле (5.7) прн е = е( и положить у = у'7 (х). ХП1. Если у е.. О, то положить е;>~ — — ()ер 1 = 7'+ 1 и перейти к шагу 1Ч; иначе перейти к шагу Х1Ч. Х1Ч. Предполагая, что О = ((м (е, ..., („;) и (, < (е« ...
(„т, пОлОжить ре (х) да~ ех = 1 ° ° г тп ХЧ. Найти наименьшее число 1 среди чисел 1Е 5', для которых вектор Ь (( )ЙРу ~Ч~ (х) (6.!1) удовлетворяет условию '1Ь'7(х)) так((Рф,Ч~е(х))!)1~6, (здесь и далее 77 — (~~ (/(1~9, 1Ф()) Ье. ( ХЧ1. Если 1Ь (х) 1е < е, то положить н перейти к шагу 1Ч; иначе перейти к шагу р~(х) ) О), (вла) и положить Ь (х) = е;+~ = реп! =/+1 ХЧ11.
272 Алгориием 2 Н а ч а л о. 1. Вычислить хе~ Х; выбрать р Р (О, 1) (обычно полагают р = Че), е Е (О, е') н е" ~ (О, е); положить Ь = О. Основной цикл. П. Положить х=хе. Ш. Положить е,= е, 7' = О. 1Ч. Вычислить множество индексов 5(, (х) н положить И =* = 5(, (х). Ч. Вычислить матрицу Рт, проектирующую В" на ортогональное дополнение к Ея, Рх т 1 (АтА,— ~ (8.8) ХЧП.
Вычислить наименьшее из чисел р (х) ) О, удовлетворяющих условию /ь(х+ р(х) й(х)) = ш!и (/ь(х+ рй(х)) )р~ О„х+ рй(х) С Х). (влз1 ХЧП1. Вычислить следуюшее приближение хь+' = х+ р(х) й(х). Х1Х. Положить й = й + 1 и перейти к шагу П. Теорелга 2. Если вьтолнены предположения 2, 2' и множество Х'(х')~(х(),(х)<),(хь), (а/', х) — Ь/~~О, ! = 1, ..., т) компактно, то последовательность хь, й = О, 1, ..., построенная алгоритмом 2, либо конечна и ее последний элемент оптимален для задачи 2, либо бесконечна и каждая ее предельная точка оптималь- на для задачи 2.
Замечание 2. Если шаг Х1Х алгоритма 2 заменить шагом Х!Х' или Х!Х", описанными ниже, то заключения теоремы 2 остаются в силе при условии, что величина р (х) иа каждой итерации однознач- но определена. (Такая замена является рациональной с вычисли- тельной точки зрения). Х1Х'.
Положить е = е, й = й + 1 и перейти к шагу П. Х1Х". Если й//' — целое число (здесь целое число Р ~ 1 введено для управления скоростью уменьшения величины е), то положить е = в/, й — й + 1 и перейти к шагу П; иначе положить й ° й + 1 и перейти к шагу П. Замечание 2'. Чтобы получить реализуемую версию алгоритма 2, можно шаг ХЧП алгоритма заменить на ХЧП'.
Вычислить наимень- шее из целых чисел ! ~ О, для которых 1,(х+ й'рй (х)) — /ь (х) — р/ра (Ць (х), й (х)) ( О; !/(х+йрй(х))(О, 1=1, 2, ..., т; //(г) = — (а', г) — Ь/, и положить р (х) = Р'р, где р ) О; р а (О, 1); а р (О, 1). Алгоритле 2' (ускоренная версия алгоритма 2) Н а ч а л о.
1. Вычислить хь а Х; выбрать р Е (О, 1), еЕ (О, е') н а" р (О, е); положить й = О. Основной цикл. П. Положить х=хь. 1П. Положить е,= е, ! = О. 1Ч. Вычислить множество индексов 0/,, (х) и положить Г/ / = 5', (х), / Ч. Вычислить проектирующую матрицу Рх по (5.8). Ч1. Вычислить вектор й / (х) по (б 9). ЧП. Если ! й'/ (х)1,') е/, то перейти к шагу ЧП1; иначе пе. рейти к шагу ХП. 273 ЧП1.
Вычислить вектор у'! (х) в соответствии с (5.7) и положить у = у'! (х). 1Х. Если у,4 О, то положить й (х) = — Ь'! (х) и перейти к шагу Х1Х; иначе перейти к шагу Х. Х. Предполагая, что Р = (1„1„..., рм ) и 1, < !е« ... 1„, и~~ожить р~„(х) = уо, се — — 1, " ~ ш . Х1. Вычислить й' (х) согласно (5.11) и (5.12), положить Ь (х) = — й'! (х) и перейти к шагу Х1Х. ХП.
Если а! < е", то вычислить векторы йе (х), у' (х) согласно (5.10) и (5.7) и перейти к шагу Х1П; иначе перейти к шагу Х1Ч. ХП1. Если 1йе(х))е = 0 и у' (х) а О, то' положить хе= х н прекратить вычисления; иначе перейти к шагу Х1Ч. Х1Ч. Вычислить вектор у'! (х) согласно (5.?) и положить у =. = уч (х). ХЧ. Если у а О, то положить еоь1 —— (!е,, ! = ! + 1 и перейти к шагу 1Ч; иначе перейти к шагу ХЧ1. ХЧ!.
Предполагая, что О = (!м 1„..., ! ) и 1, < 1, < ... < 1„,, положить р~ (х) = уо, ое = 1, 2, ..., гл'. ХЧП. Вычислить вектор й'! (х) согласно (5.11) и (5.12), положить й (х) = — й'! (х). ХЧП1. Если !5 (х)(е < еп то положить аучл = абер ! = ! + 1 и перейти к шагу !Ч; иначе йерейти к шагу Х1Х. Х!Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
