И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 69
Текст из файла (страница 69)
венств используется модифицированная функция Лагранжа и алгоритм типа штрафных оценок. 5.18. Методы проектирования обобщенного градиента 1. Основной алгоритм 3 а д а ч а 1. Найти агн ппп !э (х) для заданной функции хех 7э: И"-ь Н' и заданного множества Х ~ Л". Предпааожения 1. (э) — функция 7е — выпукла вниз; (э[) — мно- жество Х выпукло и замкнуто. Этот метод напоминает метод проекции градиентов, если вместо, градиента использовать обобщенный градиент Ч7э функции 7э.' Алгоритм 1 Н а ч а л о. 1. Выбрать начальное приближение хэ ~ Л" и по- ложить й = О. О с н о в н о й ц и к л.
11. Вычислить обобщеннь!й градиент Ч!э (хэ) фУнкции [э в точке х". 1!1. Вычислить значения шагового множителя р„и нормирую- щего множителя уэ, удовлетворяющие условиям теоремы 1. 1Ч. Вычислить следующее приближение ха+! = пх (х" — рауаЧ!э (ха)). Ч. Положить я = !г -[- 1 и перейти к шагу П. Теорема1. Пусть выполнены предположения ! и условия: (э)— существует точка х*, принадлежащая множеству минимумов Х" функции [э в области Х, для которой [~ х* ([ ( сопз1; (11) — для лю- бого числа а ( оо найдется такое число Р (а) ( оо, что 1 Ч[з (х) ~! ( Р (а) пРи ~! х [! ( а; ([и) — ноРмиРУюЩие множители Ую [г = О, 1, ..., пинсоны, что Уа> О и Уэ[) Ч(э (х') ([(сопз[, й = = О, 1, где (хэ)а=з — последовательность, порожденная алгоритмом 1; (Ь) — шагавьге множители рш [э = О, 1, ..., удовлетворяют усло- виям р„ > О, р„ О, Е р, = 37$ Тогда найдется такая подпоследовательность ()'о (х )),=о последовательности (1» (х»))»=о, что 1!ш1о(х") = 1о(х*), т.
е. 1пп пп'пго(х') = 1о(х') »-~ гб» Теорема 1'. Если в дополнение к условиям теоремы 1 мнозсество минимумов Хе функции 1о в области Х ограничено, то последовательность (1» (х»))~~, порожденная алгоритмом 1, сходится к ~,(х') и 1п1 (!хе — х"!1-».0 при й-» оо. к'ЯХ' Замечание 1. Если в теореме 1 потребовать, чтобы вместо ((а) выполнялись условия 00 р») О, 2„р» — оо, »-о то последовательность (х")»=о, порожденная алгоритмом 1, будет сходиться к решению х' С Х' без предположения об ограниченности множества Хе.
В. Мвогошегооый метод обобщенного гредвевтвого евгева 3 а д а ч а 2. Найти агя ш!п 1о (х) для заданной функции кох 1»: В"-» В' и заданного множества Х 1.'» (х !1, (х) ( О, х~ В"). Предположения 2. (1) — функции 1» и 1» — выпуклые на В"; (й) — существует точка х Е В" такая, что 1» (х) (О; (й() — множество Х вЂ” ограничено. В приводимом ниже алгоритме направление спуска выбирается с использованием обобщенных градиентов и значений функций 1» и 1» на пРедыДУЩих итеРациЯх.
Шаговые множители Р„Удовлетворяют классическим условиям. Алгоритм 2 Н а ч а л о. 1. Выбрать произвольное натуральное число т ~~» 1. П. Выбрать произвольный набор точек (х — +', ..., х'). П1. Выбрать константу и, удовлетворяющую условию а ) ) 1о (х*), где хе — Решение задачи 2. 1Ч. Выбрать константы 6, )О, 6,)О, причем 6, выбрать из условия 6, ( — 1» (х) (точка х определяется в условии (й) предположения 2). Ч. Положить й = О. 372 Ос но в н о й ц и к л. Ч1. Вычислить шаговый множитель р», удовлетворяющий условиям теоремы 2. ЧП, Если 1, (х») ) а, то положить о«» = (й) и перейти к шагу ЧШ; если 1 (х") со, то положить О» = (й — т + 1, ..., Ь) и перейти к шагу ЧП1.
ЧШ. Вычислить Ч1, (х') и Ч1, (х') — обобщенные градиенты функций 1, и 1, в точке х'. 1Х. Вычислить вектор й» из условия ш!п «р»(й) = ф»(й»), !!»ров» где функция ф„определяется по правилу ф»(й) «» шах фм(й), И.т» 1о(х') — 1» (х') + (х' — х'. Ч1»(х')) + (й, Ч1»(х9). 1, (хг) ( — 6«о «пах (1» (хг) — 1о (х») + (х" — х«, Ч1» (х«)) + (й. Ч1» (х!)), 1, (х«) + (х» — х/, Ч1, (х!)) + (Ь, Ч1, (х!)) ), б, «1»(х«) ~ — б„ 1,(х!) + (х» — х«, Ч1«(х«)) + (й, Ч1,(х')), 1 (х') ) б,. Х. Вычислить следующее приближение х»+' =. х» + Ь». Х1. Положить й = й + 1 и перейти к шагу Ч1.
Теорема 2. Пусть вмполня«отся предположения 2 и шаговые множители р», Ь = О, 1, ..., удовлетворя«от условиям р»-»+ О при й — »ос, 2т» р» —— со. »-о Тогда бесконечная последовательность (х»)»=о, порожденная алгоритмом 2, такова, что гп!п()х» — х))~-О при й-»со; квх* 1о(х») — »ш!п1»(х) при й-» со. »ЯХ где Х'= (х!1,(х) =ппп1,(у), хрХ). »ах 3.
Методы проектвроааввл обобщеввото традвевта длл решеввл предел»выл экстремальвыл аадач 3 а д а ч а 3. Найти агд ш!п 1, (х), где 1» (х) й!пп «р» (х); »ех »-юа «р»: В" -о В', й = О, 1, ... — заданные функции; Х с В". 373 Предположения 3. (») — функции <р«(х), й = О, 1, ...— выпук- лые; (й) — Х вЂ” выпуклый компакт. Алгоритм 3 Н а ч а л о. 1. Выбрать произвольное начальное приближение хо е Х.
11. Положить й = О. О с н о в н о й ц и к л. 111. Вычислить вектор Ч%» (х»)— обобщенный градиент функции ~р (х) в точке х». 1Ч. Найти шаговый множитель рю удовлетворяющий условиям теоремы 3. Ч. Вычислить следующее приближение х"+' = пх (х" — р«Ч«р» (х»)). Ч!. Положить й = й + 1 и перейти к шагу П1. Теорема 3.
Пусть выполняются предположения 3 и (!«о) — по- следовательность (ор«(х))»=о сходшпся на Х равномерно к функции 1о (х) (!") О р»)0, й=О, 1, ...; р«-~0 при й-~оо; ~ р =оо, «=о Тогда для любой сходящейся подпоследовательности (х ",~ 1 последовательности (х«(«. р, порожденной алгоритмом 3, справед- ливо предельное соотношение 1 пи х« ' = хо ~ Х*, о ~О где Х* — множество решений задачи 3.
Ниже приводится стохастический аналог алгоритма 3. Алгоритм 3' Н а ч а л о. 1. Выбрать произвольное начальное приближение хо Е рр 11. Положить й = — О. Ос но в н о й ци кл. 1П. Вычислить реализацию $» случай- ного вектора $", условное математическое ожидание которого удов- летворяет соотношению Е ($»/хе, х', ..., х») = Чор» (х«). 1Ч. Найти шаговый множитель р», удовлетворяющий условиям теоремы 3'. Ч.
Вычислить следующее приближение х'+' = пх(х" — р»з»). .Ч!. Положить й = й + 1 и перейти к шагу 1П. Теорема 3'. Пусть выполняются все предположения теоремы 3 и условие Е (р«)'< 374 Тогда с вероятностью 1 предельные точки последовательности (х»)»=о, порожденной алгоритмом 3, принадлежат множеству решений Х' задачи 3. Библиографические указания, Пункт 1 написан на основании работ [148, !53, 2881, пункт 2 — на основании [126, !291, пункт 8 основан на результатах рабопо [1591. 5.19.
Методы условного градиента 1. Реалвауемыа метод условного традвевта 3 а д а ч а 1. Найти агд ппп [о (х) для заданной функции гкх 1о: 11"- 1[' и заданного выпуклого компактного множества Х. Предположение 1. Функция 1о — непрерывно дифференцируема. Метод условного градиента может применяться для решения задачи минимизации нелинейной функции в области, в которой задача минимизации линейной функции решается без особого труда.
В данном методе на й-й итерации за направлениедвижения к следующему приближению х»+' выбирается вектор й" — г" .— х», где г» ~ Х удовлетворяет условию (Ч!о(х»), г») ш!п(Ч1о(хо), г). гяя Алгоритм 1 Н а ч а л о. 1. Выбрать начальное приближение хо Е Х. 11. Выбрать константу р ~ (О, 1) (рекомендуется [1 * х/о). 1П. Положить й = О. О сна в н о й ци к л. 1Ч. Вычислить Чуя (х»). Ч. Найти точку г» ~ Х, удовлетворяющую условию (Ч1о(х»), г') = ш[п(Ч~о(х»), г). гех У!. Вычислить вектор й»- 㻠— х". Ч11. Вычислить 6„= (Чуо (х»), Ь~).
Ч1П. Если б„= О, то положить х* = х» и прекратить вычисления; иначе перейти к шагу 1Х. 1Х. Положить 1 = О. Х. Вычислить р, = р!. Х1. Если выполняется неравенство 1о(х»+ р»[т») ~()о(х») + р»(1 са) б» то перейти к шагу ХП; иначе положить 1 = ! + 1 и перейти к шагу Х. ХП. Вычислить следующее приближение х»+' = х» + р,й». ХП1. Положить й й + 1 и перейти к шагу [Ч. Теорема 1. Если выполнено предположение 1 и (1) — множество Х выпукло и компактно; (й) — градиент функции /ь в области Х удовлетворяет условию Липшица )Ч7»(х) — Ч/ь(у))(у)х — у1, у<со, Чх, усХ, то любая предельная точка х' бесконечной последовательности (х»)» — ь, порожденной алгоритмом 1, удовлетворяет необходимому условию минимума функции 1» на множестве Х (Ч/ь(х*), х*)((Ч/ (х*), х), Чх~Х.
Условие 6» = О также является необходимым условием мини- мума функции /ь на множестве Х. Теорема 1'. Если выполнены условия теоремы 1 и функция /ь выпукла, то бесконечная последовательность (х»)» ь, порожденная алгоритмом 1, такова, что 1)т/ь(х») = т!п/ь(х), »~ «ЯХ причем справедлива следующая оценка скорости сходимости 1, (х») — т т /ь (х) ( т,/Я, «ьх где ч, ) Π— некоторая константа.
Теорема 1". Если выполнены условия теоремы 1' и (1) — область Х сильно выпукла, т. е. существует число ()ь ) О такое, апо для всех х, у ~ Х точки г = (х + у)/2 + э принадлежат Х для всех ш, удовлетворяющих условию 1ш)! = р (х — у)', (й) — существует константа е, ) О такая, что (! Ч/, (х) !) в е, для всех х Е Х, то бесконечная последовательность (х»)» ь, порожденная алгоршпмом 1, сходится к точке минимума х* функции /ь на множестве Х со скоростью геометрической прогрессии (х» — х*~(<т,д», оь(1, где т =- фь(х') — / (х*))/2рье») ~*, д = (1 — рьеь/4у) /'. 2.
Алгорлтм Франка — Вулфа Предположения 2. (1) — функция /, (х) — выпукла и непрерывно дифференцируема„(й) — Х вЂ” выпуклое множество. Алгоритм 2 Н а ч а л о. 1. Выбрать произвольное начальное приближение хь с Х. П. Положить я = О. Основной ци кл. 111. Найти точку у»~Х такую, что для всех х Е Х выполняется неравенство (Ч/ь (х ) у ) ~ ~(Ч1» (х ) х) 1Ч.
Найти число р» с [О, 1] такое, что 1 ((1 — р„) х" -[- р»у») ( ~, ((! — р) х' + ру") для всех р р [О, 1]. Ч. Положить х'+' = (1 — р,) х» + р„у'. Ч1. Если 1» (х»+') ( го (х»), то положить й = й + 1 и перейти к шагу 111; если го (х»+') = 1о (х»), то положить х* = х»+' и прекратить вычисления (в этом случае находят решение х' задачи 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
