И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 52
Текст из файла (страница 52)
Вычислить наименьшее из чисел р (х) е (О, ао), удовлетворяющих (5.13). ХХ. Вычислить следующее приближение х"+' хе+ р(х) й(х). ХХ1. Положить А = А +! и перейти к шагу П. Для последовательности хе, й = О, 1, ..., порожденной алгоритмом 2', справедлива теорема 2. 3. тибрвдвый метод проекции градиента дла мввимаеацви фуиаций нри неливейвмн отраввчеваах 3 а д а ч а 3.
Найти агд ш!и ге (х) для заданной функции кех !е: В"-е В' и заданного множества Х= (х)1;(х)(0, ! = 1, ..., гп, хЕВ"). Предположения 3. (!) — функции !?, ! = О, 1, ..., т, непрерывно днфференцируемы и выпуклы; (!е) — существует такое число е') О, что для любой точки хЕ Х и любого числа е Е (О, е'! векторы Чг! (х), ! р О, (х), линейно независимы.
Гибридный метод проекции градиента объединяет идеи метода проекции градиента (алгоритм 2) и метода возможных направлений (алгоритм 1 см. 3 5.7). Приводимый ниже метод получен в (536! добавлением к методу (овнсанному в 15001) е-процедуры, которая сделала этот метод заведомо сходящимся (версия метода, приведенная в 1500), таким свойством не обладает). Алгорилвм Я Н а ч ало. 1. Вычислить хв 5Х; выбрать ~3 Р (О, 1) (обычно полагают 5 Чв), а Е (О, е') и а" Е(0, а); положить й = О. Основной цикл. П. Положить х=хв. Ш. Положить е,= е, 1 О. 1Ч.
Вычислить ерактивное множество индексов О,. (х) по фор! муле амтв (х) =(11),(х)+а~~О, 1=1, ..., лв, хЕХ) (зл4> и положить Р = У,~ (х). Ч. Найти матрицу А~, столбцами которой являются векторы Ч); (х), 1 р й, линейно упорядоченные по 1. Ч1. Вычислить проектирующую матрицу Рф 7 — Ат(А~~Ат) ' А~~. Ч11. Вычислить вектор Ь'! (х) = Рф~,(х).
ХП1. Вычислить вектор т т у' (х) (Ат,елАт,ел) Ат,(в)Чв (х). Х1Ч. Если 1йв(х)1в 0 и у'(х) ~0, то положить прекратить вычисления; иначе перейти к шагу ХЧ. ХЧ. Вычислить вектор у'! (х) согласно (5.7) при е = жить у=у~(х) ХЧ1. Еслиу~О,то положить а~+1 ()ар!=1+1 к шагу 1Ч; иначе перейти к шагу ХЧП. ХЧП. Предполагая, что О (1„1„..., 1 ) н 1в ~ 1„,, положить !вы„(х) = у, а = 1> 2, ..., пв'. е~ и полон перейти ( (в< ". Ч1П. Если ! й'! (х))в ) еп то положить й (х) = — 1в'1 (У) и се рейти к шагу ХХ; иначе перейти к шагу !Х. 1Х.
Если е, ( а', то вычислить множество индексов Ив (х) по (5.14) (при е~ — — 0) и перейти к шагу Х; иначе перейти к шагу ХЧ. ' ' Х. Найти матрицу Ат (как на шаге Ч при 0 = Рв). в Х1. Вычислить проектирующую матрицу (~т ! )-~Ат ХП. Вычислить вектор л (х) Р~ Ч~,(х). ХЧП1. Найти наименьшее из чисел 1 е й, для которых вектор АЧ(х)йР~~ Ч~,(х) удовлетворяет соотношению )й!(х)((=шах(((Р~ Ч(,(х)(((ЕО, р~(х))О), и положить й (х) = — Ь'~ (х). Х1Х. Если ((й (х)Р (еп то положить еьь1 = ~еь 1= /+! н перейти к шагу 1Ч; иначе перейти к шагу ХХ. Примечание. В общем случае луч (х'= х+ рй(х) (р) О) пересекает множество Х только в точке х, т.
е. вектор й (х) не определяет возможное направление. Ниже строится вектор в (х), определяющий возможное направление. ХХ. Если й (х) = — й'! (х), то положить Ж = О и перейти кшагу ХХ1; иначе положить в(: = Р— 1 н перейти к шагу ХХ1. ХХ1. Вычислить вектор о(х) = Х(х) й(х) + Ачс (АрсАус) 'д, где д = — е~ (1, 1, ..., 1) ~ 11" и Х (х) ~ 1 — наименьшее нз чисел на луче П, оо), для которых (Ч~,(х), д(х))( — зп где 1 = О прн Х = о и! = 1 прн Я а — 1. ХХП. Вычислить наименьшее из чисел р(х) = О, удовлетворяющих условию 1ь(х+ Р(х) Ч(х)) = ш(п (1~(х+ ра(х)) (р ~ О, х+ ро(х) ~ Х) ХХП1.
Вычислить следующее приближение х'+' =- х" + р (х) а (х). ХХ1Ч. Положить й = й + 1 и перейти к шагу П. Теорема 3. Пусть выполнены предположения 3 и пусть задача 3 .иакова, что алгоритм 3 корректен для всех хЕ(х(1о(х)~7ь(х'), хЕХ). Тогда последовательность хь, й = О, 1, ..., порожденная алгорит.иом 3, либо конечна и ее конечный элемент оптимален для задачи 3, либо бесконечна и каждая ее предельная точка оптимальна для задачи 3. Замечание 3. Алгоритм 3 можно привести к реализуемой форме тем же способом, что и алгоритм 2 (см. замечание 2').
Можно также получить ускоренную версию алгоритма 3, используя для этого .идею построения алгоритма 2', 4. Метод вроевивв гредвевте ври девичее воевтшеиий За д а ч а 4. Найти ага ппп 7» (х) для заданной функции «ях 7»: 1!" — ~ 1т'и заданного множества Х. Предположения 4. (») — Х вЂ” замкнутое выпуклое множество; (»1) — )»вЂ дифференцируемая на Х функция, В алгоритме 4 предполагается, что имеется возможность вычис- лять на каждой итерации приближенное значение й» градиента функ- ции 1» в точке х». Алгоритм 4 Н а ч а л о. 1.
Выбрать произвольное начальное приближение х»ЕХ. 11. Положить я = О. Ос н о в и о й ц и к л. 1П. Вычислить направление движения и» (приближенно совпадающее с градиентом функции 7» в точке х = х'). 1Ч. Найти шаговый множитель р». Ч. Вычислить следующее приближение х»+' пх (х» — р»7» ), где пх — оператор проектирования на множество Х.
Ч1. Положить й = й + 1 и перейти к шагу 1П. Теорема 4. Пусть выполняются предположения 4 и (»11) — градиент фУнкЦии 7» на множестве Хе=(х)1»(х)((1»(хе)ю хЕХ) удовлетворяет условию Липшица с константой у (здесь х' — начальное приближение в алгоритме 4); (»о) — веюпор Й», вычисляемый на шаге ПI алгоритма 4, удовлетворяет условию 1й» вЂ” Ч1»(х»)1())))х»+1 — х~), й =О, 1, ....
Тогда для последовательности (х»)Г е, порожденной алгоритмом 4, справедливы утверждения: 1) если 0 ( р» ( 2/(у -)- 2й), й = О, 1, ..., то (1» (х»))» е монотонно убываещ 2) если Х, огРаничено, 7» выпУклаЯ фУнкЦип, 0(е,(р„(2/(у+ 2Я вЂ” е„й =О, 1, ..., (в, >0),то 1пп 7»(х») (е ~1п17»(х), 1»(х») — ~; = О~ — 1; »««««Х а 3) если функция 7' дважды дифференцируема и у, ) у !» ~ (Ч,«7' (х) у, у) ( у)) у)~е, у~ ) 0' П~'.Г ( ) — ~«ЬЬ)П('7.)) — ~И: б=шах()1 — ру,), ) 1-ру)), ц= —, ( 1, +рр 277 то при р» = р, я = О, 1,..., последовательность (х»)» е сходится к точке минимума хе, причем !) ха — хе [! = О (!)»).
Библиогри!ричгапм укавзиил. Пункт ! написан на основании работы [1й21, пункт 2 и 3 — на основании работ [235, 5101, пункт 4 — на основании работы [кзб!. Различные модификации метода проекции градиента и различные способы оостроенин проектирующих матриц описаны также в [551, 500, 320, 536, 251.
5.2. Общий метод штраФных Функций и, таким образом, решение задачи 1 сводится к вспомогательным задачам максимизации по х ~ )к функции [е (х) — ф (х, а) при достаточно больших а. Решение последней в силу «простой» структуры множества )к является проще исходной задачи. В общем случае решение задачи 1 находится как предельное решение вспомогательных задач при а-» оо. В некоторых случаях решение исходной задачи можно получить при конечном значении а. Ниже приведены примеры штрафных функций: т)(х, а) = а ~„~ш1п (О, )г(х)) [~, т«0; (5 14) ! ! кр(х, а) =а!ш!п(0, ппп /г(х)) ~', т)0; (злз) М(!»'0 1 О, если пип)г(х)~вО, !Е(пгч тр(х, а) = ае ' в противном случае; 1 (6.16) 3 а д а ч а 1. Найти агй !пах )е (х) для заданной функции »ЕХ Де: )т"-» еет и заданного множества Х = (х[ук(х))0, ! = 1, ..., т„хЕ)к«:Л ).
Предположения 1. (!) — 1' — компактное множество в В" (з))— функции ~р ! = О, 1, ..., т — непрерывны на множестве )~. Определение 1. Семейство функций тр (, а), определенных на множестве )', зависящих от параметра а и обладающих свойствами: (!) — »р(х, а) ~ 0 при всех х Е)'; (11) — ф (х, а) -«0(монотонно убывая) при а -«оо на множестве Х', всюду плотном в Х; (ш)— 1пп тр (х, а) = оо равномерно по х ~ ()к ~, [гь (Х)) для любого а б ) 0 (где $'ь (Х) обозначает б-окрестность множества Х) называют штрафными функциями (или функциями штрафа), а параметр а — иипрафным аэффициентом (или коэффициентом шперафа).
Если тр (, а) — штрафные функции, то справедливо шах(е(х) =!пп зцр(1»(х) — тр(х, а)), кЕХ а кк кЕУ «« та «(«(х, сс) = 1+ ~')ш(п (О, /с(х)) !'~ — 1, т 0; (злт) — ~/с — '(х) при ппп 1с(х))0, ф(х, а)= а с 1 М[сс»Ч -(-оо, в противном случае; ф(х, а) = «~~ ехр( — сс/с(х)). (5.19) ! Штрафные функции (5.14) — (5.17) называют внешними, а (5.15) — (5.19) — внутренними штрафными функциями. Для функции «р(х, сс) вида ф(х, сс)= сс с с — — 1,' 1и/с(х), х~Х»; со, хЯХ» условие (с) в определении 1 штрафных функций в общем случае не выполняется, но теорема 1 остается для нее справедливой. Алгоршпм 1 1.
Выбрать семейство штрафных функций ф (, сс). И. Задать последовательность (сс»)Г р штрафных коэффицнеитов такую, что 1пп 1/а» О. »»» 111. Задать последовательность (з»)~~ такую, что 1!гп з» О, е„ ) О, й = О, 1, .... » 1Ч, Вычислить прн каждом й (/с = О, 1, ...) точку х», удовлетворяющую условию 1 (х») — «р(х», сс») с знр(1»(х) — ф(х, сс»)) — е». «су Здесь также требуется решать задачу условной максимизации. Однако на практике под множеством У обычно подразумевается некоторое «простое» множество (например, параллелепипед в пространстве В") и решение этой задачи стачки зрения наличия ограничений не представляет особых трудностей.
Теорема1. Если выполняются предположения 1, пи любая предельная точка последовательности (хь)» ь, порожденной алгоритмом 1, принадлежит допустимому множеству Х и реализует шах /» (х), и. е. являепсся решением задачи 1. «ях В следующей теореме приводятся оценки скорости сходимости алгоритма 1, на основании которых выбираются штрафные коэффициенты, обеспечивающие заданную точность решения по функционалу. Теорема 1'. Пусть выполняются предположения ! и (ссс) — функция /ь (х) удовлетворяет условию Липшица на компакте г' с 279 константой у; (1о) — существуют постоянные 6, (), о) 0 такие, что при всех хЕ(Уь(Х)' Х) П Г справедливо неравенство ппп ~~ (х) ( — ~ (рг(х, Х)1, кн1«ч где рг — метрика в У'; Ув (Х) — 6-окрестность множества Х; (о) — штрафная функция ф (х, а) имеет вид о~ ф,(х, и) а~„/ш!п(0, 1,(х)) !', т)0.
к-~ Тогда для достаточно болыиих сс при то ) 1 справедливы неравенства 0 ( Ь (а, т) а„' р (у"Ча)' ' рг(х*(и, т), Х) ~ !с(у1а)па где Л(и, т) = снах(1ь(х) — ф,(х, и)) — шах!в(х); эсу эсх !с — величина, не зависяиутя от сс, у; х*(а, т) = агягпах (1,(х) — Ф,(х, а)). эсУ Если то 1, то сущеспмует значение штрафного коэффициента а = а(у, р, т) = 0(у16') такое, что хь (а, т) ь Х и Л (и, т) 0 при всех а ) и (у, (), т). Замечание 1. Условие ((о) теоремы 1' с произвольным 6 ) О, о = 1 и некоторым б ) 0 выполняется в каждом из следующих двух случаев: 1) функции ~,(х), с = 1, ..., т — вогнуты на компакте У и вы- .
полнено условие Слейтера, т. е. существует точка х С У такая, что ~, (х) ) О, 1 = 1, ..., т; 2) У вЂ” выпуклое множество из В", а 1, (х), 1 = 1, ..., т,— линейные функции. Замечание 1'. Условие (!о) теоремы !' с произвольным в ) О, 6 ) 0 и некоторым (достаточно малым) р выполняется, если У— конечное множество. Замечание 1".
Если система неравенств 1;(х) «О, 1=1, ..., т, имеет единственное решение х* р В", причем 1, (х*) = ° = )„+~ (х«) = 0; 1„+э(х') ) О, ..., ! (х'))0 и любые и векторов системы (ф, (х'), ..., )ф+~ (х")) линейно независимы, то пп'п 1,(х) ~~ — р)х — х" (. цчс<а Замечание 1"'. Из теоремы 1' следует, что при то ( 1 возможно точное решение задачи математического программирования методом штрафных функций при конечном значении коэффициента штрафа а.
Обеспечить выполнение условия тп ( 1 можно выбором параметра ч. Однако следует учитывать, что при т ( 1 функция ф, (х, а) вообще не является дифференцируемой по х, даже если функции /, (х), 1 = 1, ..., т дифференцируемы по х, что может усложнить решение задачи шах (/е (х) — Ф (х, а)) кеУ Библиографические увязания. При написании параграфа использовались рзботы [370, 3721. Дополнительные сведения об общем методе штрафов, оценкзх скорости сходнмости, рекомеидзциях по практическому использоввнню метода штрзфов можно найти в работах [! 41, 146, 289, 89, 468, 571, 452, 514, 4301. В работе [5651 доказывается, что при линейных внешних штрафных функциях из существования седловой точки для функции Лагранжа вытекает сходимость решений вспомогательных зздзч безусловной оптимизации к решению исходной задачи при конечном значении козффициентв штрафа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
