И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 72
Текст из файла (страница 72)
Замечание 1. Алгоритм внутренней аппроксимации может быть использован для решения задач нелинейного программирования а невыпуклой целевой функцией )е. Для этого целевую функцию 1е заменяют новой переменной х„ь1 (выпуклой функцией), а ограничение [е (х) — х„+1 < О добавляют к ограничениям еадачи. Для решения новой задачи в пространстве Й"+' применяют алгоритм 1. Библиографические указания. Параграф написан на основаннн работы [5[51. В работе [5331 используются аппрокснмнрующне касательнме плоскости в Пеленой функции для свсдення исходной задачи нелинейного программирования к решенню последовательности более простых задач оптнмнзапнн.
6.23. Методы покоордннатного спуска 3 а д а ч а О. Найти агй ппп 1з (х) для заданной функции еех 1» ! В"-~. 1[' и параллелепипеда Х= (х(а,(х,(йь 1=1, ..., и, хЕВ"), где с«„ро 1 1, ..., и — заданные действительные числа. Предположения О. (з) — функция 1е (х) — непрерывно дифференцнруема и для любых х, у Е Х выполняется $7~,(х) — 7~ (у)(<у((х — у(, О<у<со. 1. Детерминированный иеиеердиватвый еауси В методе детерминированного покоордннатного спуска за направление движения последовательно выбираются орты. Параметры метода р и 6 вычисляются в процессе работы алгоритма. Алгоритм включает «большие» итерации по гндексу к и «малые» вЂ” по индексу 1, причем при каждом я «малые» итерации ааканчиваются при конечном значении индекса 1.
Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение ке Р Х и вычислить 1е (х'). П. Выбрать произвольные константы р„б„п>, удовлетворяющие неравенствам р,'>О; бо>О; ш> !. П1. Задать векторы е', ..., е" (здесь е', < = 1, ..., а — вектор, <-я координата которого равна единице, а остальные равны нулю). 1Ч.
Положить й = О. Основной цикл. Ч. Положить)=0. Ч1. Вычислить индекс >» (<» с (1: и)) по правилу >» = й — пЕп!(Ып) + 1, где Еп! (1) — целая часть числа (. ЧП. Положить Ь»= е». ЧП1. Вычислить векторы х»<+' = х»+ (р»/2')й»; х"< — > = х» — (р !2>)!>». 1Х. Если х»<+>с Х и х"<-'р Х, то перейти к шагу Х; если х'<+> Е Х и х" — > Я Х, то вычислить 1,(хм+>) н перейти к ша- гу ХЧ; если х»<+> (с Х и х»< — > Р Х, то вычислить 1, (х»<->) и перейти к шагу ХЧ1; если х»<+> >с Х и х»< — > (с Х, то положить ! = 1 -<- 1 и перейти к шагу ЧП1.
Х. Вычислить ! (х"<+>). Х1. Если выполняется неравенство 1о (х~+') — 1о (х») ~ ~— Р»6»12' (5.85) то положить х"+' = х»<+>; рь< > = р; 6»+> = б„; 1, (х»+') = 1,(х»<+>) и перейти к шагу ХУП1; иначе перейти к шагу ХП. ХП. Вычислить 1» (х»< — >). ХП1.
Если выполняется неравенство 1» (х" ') — 1» (х') < — р»6»12~* (5.88) то положить х»+' х»< >; р»+> = р»' 6»+> < 6»' 1»(х»+') = 1»(х»< >) и перейти к шагу ХЧП1; иначе перейти к шагу Х!Ч. Х!Ч. Если выполняется неравенство ! 1о (х»<+>) — 1о (х»< — ') ~ < 2р»п>б»/2~, то перейти к шагу ХЧП; иначе положить 1 = 1+ 1 и перейти к шагу ЧП1. ХЧ. Если выполняется неравенство (5.85), то положить +'= +>; 1 ( +)=! ( "+>), р»+ =р».
б+ =б„ и перейти к шагу ХЧП!; иначе перейти к шагу ХЧП. ХЧ1. Если выполняется неравенство (5.86), то положить х»+ = х" " 1о(х'+') = 1»(х'< — >); р»+> = р„; бь,.> = 6» и перейти к шагу ХЧП1; иначе перейти к шагу ХЧП. 389 ХЧП. Если выполняются равенства /а оо и; х" = х" — "+', то положить х"+' = ха; /е(х'+') = /е(хь); рь+1 = рь/2; бе+1 Ь«/2 и перейти к шагу ХЧШ; если 1,~ п или х'~ х"-"+', то поло- жить х'+'= ' /о(х"+')=/о('); р+ =р«.
б.+ / йа и перейти к шагу ХЧП1. ХЧП1. Положить й = й + 1 и перейти к шагу Ч. Уеорема 1. Если выполнены предположения О, функция /е (х) выпукла на Х и множеспию Х,= (х)/е(х)~(/е(хо), »ЕХ) ограничено (здесь хо — напальное приблилсение в алгоритме 1), то алгоритм 1 порождает последовательность (х")~ о, для которой 1пп !п1 1»" — хо(= О, ь м «*их" Х*= (хо(/о(хо) ш!и/о(х), х«~Х). «ех 2. Слуоайвый покоордпватвмй епуеп — ш!и (~~ — се~, дх 1« (х )/7~, д дх /о(х ) ~О д дх~ ш1" (~'„»1 ° ~ дх /о(х ) ~/У~ если дх /о(» ) ~~ д ь! д В методе случайного покоординатного спуска за направление движения в й-й итерации случайно выбирается /ь-й орт. Для вычисления шатовых множителей р, приводятся три различные правила, легко реализуемые на практике.
Алгоритм 2 Н а ч а л о. 1. Выбрать произвольное начальное приближение хоч Х. П. Задать векторы е', ..., е" (здесь е', 1 = 1, ..., п — 1-й координатный вектор). И1. Положить й = О. Оон овнов ци кл. 1Ч. Найти независимую реализацию 1« случайной величины 1, которая принимает значения из множества (1, ..., и), соответственно, с вероятностями рх = !/п,, р„— 1/и. Ч. Вычислить частную производную — /о(ха). д дх~ о Ч1. Вычислить шаговый множитель Здесь предполагается, что известна константа Липшица у в условии (1) предположения О. Если константа у неизвестна, то рь вычисляется по формулам, приведенным в замечании 2.
ЧИ. Вычислить следующее приближение хь+' = х" — р,е ь. ЧП1. Положить й = й + ! и перейти к шагу 1Ч. Теорема 2. Если выполняется предположение 0 и множество Х,= (х(!з(х)((1о(хе), хсХ) ограничено (здесь хе — начальное приближение в алгоритме 2), то алгоритм 2 порождает последовательность (хь)~ з, для которой с вероятностью 1 1пп !п1 '1хь — хе((=0, г «««'ях где Х*Я,, (Хе ((71е(Х«), Х вЂ” Хь) ~ 0 дЛя ВСЕХ Х Ь Х ) — множество стационарных точек функции 1е (х).
Если, кроме того, функция !е (х) выпукла на Х, то с вероятностью 1 1пп 1е (х") = ппп 1е(х). ь-« «ах Замечание 2. Шаговый множитель р„на шаге Ч1 алгоритма 2 можно выбирать из условия 1е (» рье ") < Л«1о (х ) + (1 — !"ь) и'м где 0<Л((Ль<1; шь = !п(1о(хь — Ре'); хь — Ре~ьСХ. Р В качестве р, также может быть выбрано любое число Р ~ ~б!зм где 6 Е (О, 1); р„— наибольшее из чисел, удовлетворяющих неравенству (з(хь — рье') — 1е(хь)< — —,р ~ д„, Ге(х')~. Для вычисления рь могут быть использованы следующие неравенства: Иг В ш!п ~хг — сггь, д„1е(хь)1у( при д 1е(х ) ь 0; / » д д д„е 'ь р,> — пп ~0,„— х,',, ~ —,„' ~,('фу~ щ —,„' 1,(")<О.
Библиограгричгасиг у«озвнил. Пункт 1 оеновзн нз результатах работы 11611, в пункт 2 — нв результатах работы 11311. 891 б.24. Релансационные методы длл общих задач нелинейного программирования 3 а д а ч а О. Найти аги ш)п /е (х) для заданной функции »е» 1е. В"-+ В' и заданного множества Х= (х(б,(х) =О, 1=1, ..., и;, д,(х)(0, (=тт+ +1, ..., и; х,)0, 1=1, ..., и; хЕВ) Предположения О, (1) — функции /е (х), л; (х), 1 = 1, ..., и— непрерывно дифференцируемые. Определение О. Точки х Е Хе, где Хе= (х(д,(х) =О, 1= 1, ..., т;, д;(х)(0, 1= т, + +1, ..., т; х,)0, 1=1, ..., л; хЕВ"), называют внутренними точками множества Х, а точки х Е Х'~,Хе— граничными.
В приводимых ниже методах решение задачи 0 сводится к на- хождению предельных точек (при 1 — ~. оо) решения х (хе, 1) задачи Коши для системы — = — М(х)Ч/е(х), х(0) =хе~Хе, где М (х) — матрица размера и Х л, определяемая функциями ограничений задачи О. 1. Непрерываыа вариант Алгоритм 1 1. Выбрать произвольное начальное приближение х = хе ~ Х'.
11. Определить на полупрямой ш) 0 непрерывную функцию $ (ш) скалярного аргумента такую, что $(ш)) О при ш) О и $(0) = О (обычно принимают $ (и) = и). 111. Вычислить и Х т-матрицу д, (х) (у которой (1, 1)-й элемент есть дд; (х)/дх,). 1Ч. Вычислить диагональную и х и-матрицу д) (э" (х)) (у которой /-е, 1 = 1, ..., л, диагональные элементы есть $ (х~)). Если ограничения х;) О, 1 = 1, ..., п, в задаче 0 отсутствуют, то следует положить х) ($" (х)) = 1„, где 1„— единичная и х лматрица. Ч.
Вычислить диагональную и Х и-матрицу Я ($ ( — н (х))) (у которой 1-е, 1 = 1, ..., и, диагональные элементы есть $ ( — и; (х))). Ч1. Вычислить л Х 1-матрицу Ч„/е (х). Ч11. Вычислить л х л-матрицу М (х) = х) ($" (х))(1„— ((д, (х)) 3 $" (х)) д„(х) + + Я) Я ( д(х)))) (д»(х)) ЙЯ (х)))ю (5 87) где I„— единичная и 'х и-матрица; индекс «Т» обозначает транспонирование.
ЧП1. Найти решение х (х„г) задачи Коши для системы х= — М(х) Ч„/е(х), х(0) = хе. (з.зз) Теорема 1. Пусть: («) — на компактном множестве Х функции /, (х,) й, (х), 1 = 1, ..., т — непрерывно дифференцируемы; (й)— на множестве Х выполнены условия регулярности ограничений д;(х)<0, 1=1, ..., т; х~)0, 1=1, ..., п; (ограничения д, (х) < О, 1 = 1, ..., т, и х! в О, / = 1, ..., и, удовлетворяют условию регулярности в точке х, если а, (х), / С 1, т— непрерывно дифференцируемы, а векторы ег, 1 Е ( /! к~ —— О, / Е 1, и) и Чу, (х), 1 Е (1)д; (х) = О, 1 Е 1,т) — линейно-независимы); (й() — все стационарные точки из множества Х изолированы; (йо) — для каждого хе Е Х система (5.88) определяет единственное решение к (х', г).
Тогда для любых нестационарных точек хе Е Хе решение х (хе, Г) системы (5.88) сходится (при Г -э оо) к допустимой стационарной точке, в которой выполнены необкодимые (в случае задач выпуклого программирования — и достаточные) условия минимума задачи О. Теорема 1'. Пусть: (1) — /, (х) — выпуклая, непрерывно дифференцируемал функция; (й) — и, (х), ! = 1, ..., т — линейные функции; (й/) — всюду на компактном множестве Х выполнены условия регулярности ограничений д;(х)<0, 1=1, ..., т; к~~О, /=1, ..., и. Тогда решения системы (5.88) (при г - оо) скодятся к множеству решений задачи О при любык хе Е Х'.
2. Двсвретвмв вврвавт Алгоритм 2 Н а ч а л о. 1. Выбрать произвольное начальное приближение х' Е Х'. 11. Положить я = 0 О с н о в н о й ци к л. П1. Вычислить Ч/„(х"). 1Ч. Вычислить по (5.87) и х и-матрицу М (х"). Ч. Вычислить значение шагового множителя р», удовлетворяющее условиям теоремы 2. Ч1. Вычислить следующее приближение х'+' х' — р,М (х') Ч/е (х'). ЧП, Положить я = й + 1 и перейти к шагу П1. Теорема 2. Пусть выполнены условия теоремы 1 и условия (1)— 6Ч/е(х) — Ч/е(у)Ц<у)х — у), 0<у<со, Чх, уЕХр («1) функции д; (х), ! = 1, ..., т — линейные; (Ш) — шаговые множители р» таковы, что 0<р„<пнп(1/р, !/т, 2/Ху), 393 где Л = шах п]ах «™() У ( оо; «ех м«1« 1 ееВ р = п]ах шах — '; и =п]ах [пахи,(х); дН (х, о) и[па] «ех дх[ нные] «сх Н(х, о) = 1'е(х)+ ~ о,(х)у[(х); вектор о (х) ьз (о, (х), ..., о (х)) является решением системы линейных уравнений (все матрицы определяются в алгоритме 1) [(д,(х)) л)($" (х))д,(х)+Я($ ( — д«(х))))о(х)+ + (й,(х)) Я(ь" (х))Ч[е(х) = О; (зо) — скалярная функция $ (го) выбрана в виде $ (гс) = го.
Тогда при любых нестационарных начальных точках х'~ Х' последовательность (хз)ь=е, порожденная алгоритмом 2, сходится к допустимой стационарной точке, в которой выполнены необходимые (в случае задач выпуклого программирования и даст точные) условия минимума задачи О, причем хьс Х', (о (хз+') ~(е (х") .для й = О, 1, .... Если, кроме того, []х])г~'(г Н (х, о(х))г(Ц~г[з при всех х Е Х, г Е В"~ где (т + и — т,) Х (т + и — тт)-матрица Н (х, о (х)), определяется по формуле д'Н(х, о(х)) Н««(х~ о (х)) = о х) (о (х)) о (х) = (о +' (х), ..., о" (х)), Я (о (х)) — диагональная матрица, элементы которой являются соответствуюи(ими координатами вектора о (х), то для любой начальной точки ха ~ Хз справедливо дх ~ +3й)(( — у(хз))'о(х')1з( (Ц '"'",„"'"'" ~+ 1 й) (( — у(хе))нз о(хзц'~ [1 — М, + М" и последовательность (хз)з е сходится к единственной точке минимума х* задачи О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
