И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 85
Текст из файла (страница 85)
2. Градвевтвый метод отыевеввл еедлоеыл точек е воетовввым шаговым мкомвтелем Алгоритм 2 Н а ч а л о. !. Выбрать произвольное начальное приближение (хе у') ~Х х У. 11. Выбрать постоянный шаговый множитель р) О. 111. Положить я О. Основной ци кл. !Ч. Вычислить векторы Ч,!р(х», у') и Ч„»р (х", у»). Ч. Вычислить следующие приближения: х»+1 их (х + рЧ»р (х» у»))! у'+'= '(у" — рЧ»'р(х" у»)) где пч — оператор проектирования на множество Я. Ч1. Положить й й+ 1 и перейти к шагу 1Ч. Теорема 2. Пусть выполняются предположения О. Тогда для любых чисел е и 6, удовлетворяющих неравенству О ( е < 6, существуют такие положительные числа р (е, 6) и яе (е, 6), что алгоритм 2 при всяком (хл, у') ~ 2 (6) и произвольном постоянном шаговом множителе р ( р (е, 6) порождает последовательность ((хь, уь)),=о, для которой при всех й ) й, (е, 6) р-' будет (хь, уь) с 2 (е) (здесь и далее множества Я (6) и 2 (е) определяются по (6.13)).
Теорема 2'. Пусть выполняются предположения О и пусть: ((о) — множество ссдловых точек Хь х Уь функции ф (х, у) состоит из одной точки (х*, уь); (о) — функция р (х, у) имеет в точке (х', у*) вторую производную; (о1) — точка (х', у") является внутренней точкой множества Х х У; (вй) — не существует числа Х и ненулаюго вектора (и, о) ~ В" х В таких, что Ч'„„~р(х*, у") и О, Ч„'„~р(х*, у") о = О; Че„~р(х*, у*) и Хо, (Чв,~р(х', уь)) о г.и. Тогда для любого числа 6 ) О найдется такое число р (6) ) О, что алгоршпм 2 при вс ком начальном прибливкении (х', у') б Я (6) и произвольном поапоянном шаговом множителе р ( р (6) порождает последовательность ((х", уь))~ ы которая линейно (со скоростью геометрической прогрессии) сходится к точке (х', уь).
Теорема 2'. Пусть выполняются предположения теоремы 2', кроме условия (о(), и пусть: (ьх) — Х В, У = В~; (х)— (Ч„р(хь, у'), е') - О, ..., (Ч„~р(хь, уь), ег) = О; (Чг~р(х*, у*), ег+'))О, ..., (Ч„~р(хь, у'), е'") )О, где в', 1 1, ..., т — 1-й орт в пространстве В; (х$) — не существует веюпора и ~ О и такого, ипо Ч,'„~р(хь, уь) и О, и нв сушрствует вектора о чь О и такого, что (Ч„-„<р(х~, у~)) о О, Ч-„"~р(х*, у )о = О, ~здесь у обозначает проекцию точкиу на надпространство В', отвечающее первым р координапшм; ~р — ограничение функции рна множество В" Х Вв+, (Ч- ~р (х*, у')) — матрица, транспонированная к мотет рице Ч-~р (хь, у*)).
Тогда для любого 6) О найдется число р (6) ) О «иисое, чпю алгоритм 2 при всяком начальном приближении (хь, уь) ~ Я (6) и произвольном постоянном шаговом множителе р я' р (6) порождает последовательность ((хь, уь)',„" ~, которая линейно (со скоростью ееометрической прогрессии) сходится к седловой точке (хь, уь). Замечание 2. Если ~р (х, у) — функция Лагранжа задачи вогну- того программирования (6.12), т. е. ~р (х, у) = ре(х) + ~, уД (х), то условия (хр) теоремы 2" означают линейную независимость гра- днЕитОВ ЧГ, (Х*), ..., ЧГ (Хе) аКтИВНЫХ ОГраНИЧЕНИй И СИЛЬНУЮ выпуклость функции — Ч (х, у*) в окрестности точки хе.
3. Обобщенный граднентный метод 3 а д а ч а 3. Найти точку (х*, у*) ~ Х х К, удовлетворяю- щую условию ~р(х, уе)(Ч(хе, у*) =~р(хе, у), ЧхЕХ, уЕУ, где ~р(х, у) — вогнуто-выпуклая функция; Х и У вЂ” выпуклые и замкнутые множества эвклидовых пространств 1»" и И"', соответст- венно. Предположения 3. (1) — функция <р (х, у) при любом фиксиро- ванном у Е У выпукла вверх по х в некоторой окрестности Х мно- жества Х; функция Ч (х, у) при любом фиксированном х ~ Х вы- пукла вниз по у в некоторой окрестности )' множества 1', (Ц)— множество седловых точек Х' с Уе функции ~р (х, у) относительно множеств Х и )' непусто и ограничено; ((и) — выполняется усло- вие устойчивости множества седловых точек Хех Уе функции Ч (х, у), т.
е. для произвольных х* б Х', у* Е Уе выполняется Хе = [х1<р(х, у*) = гпах~р(х', у*), х~Х); у'ех 1'*= (у(~р(хе, у) = гп(п~р(хе, у'), у~У). а'И' В приведенном ниже алгоритме в качестве векторов, определя- ющих направление движения по переменным х и у на й-й итерации, выбирают, соответственно, обобщенные градиенты функции ~р (х, ур, по х и у, вычисленные в точке (х», у"). Шаговые множители удов- летворяют классическим условиям. Алгорин»м Ю Н а ч а л о. 1. Выбрать произвольное начальное приближение (, уе) ~ Х Х у. 11.
Положить й = О. 0 с н о в но й ци к л. Ш. Вычислить обобщенные градиенты Ч, ~р (х', у') и Ч„~р (х", у») функции ~р (х, у) по х и у в точке (х', у"), т. е. такие векторы, что (Ч,<р (х", у"), х' — х») ~ ~р (х', у») — <р (х", у»)„Ч х' б Х; (Чр(х», у'), у' — у»)(у(х», у') — <р(х», у'), Чу'~ут. 1Ч. Вычислить шаговый множитель р„, 'Ч. Вычислить следующее приближение (х»+', у"+') х»+' = пх(х»+ р»!!7,!р(х», у")); у»+' = пу (у» — р»Ч„!р (х», у»)). Ч1. Положить й = й + 1 и перейти к шагу П1. Теорема 8. Пусть выполняются предположения 8 и пусть: (ео)— мнткества обобщенных градиентов функции !р (х, у) по х и у, соответственно, равномерно ограничены, т.
е. существует постоянная се такая, что Цр,<р(х, у)Ц(а, Ц на!р(х, у)Ц(а, 1г (х, у)ЕХ Х 1', (о) — шаговые множители р» в алгоритме 8 удовлетворяют условиям р»)0, й=О, 1, ...; [ппр»=0; !пп ~;р!=со. »-~ю » г-е Тогда последовательность ((х, у ))~е, порожденная алгоритмом 3, такова, что ппп Ц(х», у») — (хе, уе)Ц~-0 при й-!-оо.
18.Ы) (а',е*!ех'ху' Теорема 8'. Пусть выполняются все предположения теоремы 3 аа исключением условия (Ь). Тогда существует число р ) 0 такое, чгпо при выполнении дополнительного условия р„<р, й=О, 1, ..., последовательность ((х", у ))» о, порожденная алгоритмом 3, удовлеппюряет предельному соотношению (6.14). Бпблиогра4нческпеукаягнка.
Пункты 1 и 2 написаны на основании работ [231, 1671, пункт 3 — на основании работы 182[. Дополнительные сведения о градиентных методах отыскания седловых точек можно найти в работах [373, 183, 334[. 6.10. Метод эксионенциальных штрафов отыскания седловык точек 3 а д а ч а 1. Найти точкУ (хе, У*) Е Хе Х Уе такУю, что длЯ каждой точки (х, у) из Х, х 1"е выполняется !р(х*, у)~!р(хе, уе)~„!р(х, у*), где Х, (х ( шах у! (х) ( О, х 6 В"); !<а<а Уе= (у( шах 7!(у)(0, уЕВ ); !е !<а !р:В" х В -ьВ»; д!:В" — В', !' 1, ..., р; Р,: В В, 1 = 1, ...7 4бв Пргдположгния 1.
(!) — функция (р (х, у) выпукла по х при каждом у и вогнута по у при каждом х; (11) — д! (х), ! = 1, ..., р и ~/, / = 1, ..., и — выпуклые функции; (!21) — Х, и У(( — непустые ограниченные множества. В методе экспонеициальных штрафов решение задачи 1 сводится к решению последовательности задач отыскания безусловных седловых точек (хг, уг) функций О3 «Рг(х, У) = «Р(х, У) + — ~ 2~ ехР(Цд((х)) — ~~ ехР(~Д (У)), а !-! (=! где и„и р(, — вещественные параметры, удовлетворяющие условиям ()„-» оо при й — оо, р ~ а ) 1, /« ~ 1.
При определенных условйях предельные точки последовательности ((х", у'))Г ! являются решениями задачи 1. При более сильных условиях, налагаемых на функцию «/((х, у), приводятся оценки скорости сходимости последовательности ((х', у'))4"=!крешенню (х*, у*) задачи 1. Удачный выбор параметров а„и получается, если (аг)д ь фг)Г=!, (()г/аг)д ! стремятся к бесконечности. Алгоритм 1 Н а ч а л о. 1. Задать числовые последовательности (аг)ь.! и фг)Г !, удовлетворяющие условиям ~„-» оо прн /« -» оо; ~„эа» э1 при й 1,2,.... (а. щ (например, можно принять' а„=~ь=(а)", й 1, 2, ..., либо Цг=/«, аь=.1, й 1, 2, ..., либо ~г=(1()", аг =(а)ь, й ° 1, 2, ..., 1<а<Р).
П. Положить й = 1. О с нови о й ци к л. П1. Определить функцию (рг(х, у) = (р (х, у) + (1!аг) х р (« 6$ х [Е "«(!,«(*(( — Е Р(!,! о((] ° ! / 1 1Ч. Вычислить седловую точку (х", у") функции «рг(х, у) в В" х В, т. е. точку, для которой выполняется (рг(х, у) <(р (х у ) «ч,(рг(х у ) Ч(х у) бЛ Х г» ° Ч. Положить й = й + 1 и перейти к шагу П1. 469 Если выполняются предположения 1 и существуют точки х' ~ ч В" и у'е В такие, что 1пп (р(х', у)(+ оо; 1(гп (р(х, у') — оо, (влв) ю (м1-~-(-- то при каждом А ) 1 существует, по крайней мере, одна безусловная седловая точка функции (р (х, у). Если же неравенства (6.16) не выполняются, то при выполнении условия 1пп (р»/а») = + оо функция ф» (х, у) для достаточно больших й имеет хотя бы одну седловую точку в В" х В, причем все безусловные седловые точки функции ф» (для достаточно больших й) находятся в множестве Хь х Ув, где Хь= (х) гпаху((х)(6, хеВ"); 1<(в<я 1'ь = (у ( гпах // (х) ( 6, у Е В ); 1</ка 6 — некоторое положительное число.
Теорема 1. Пусть выполняются предположения 1 и пусть для каждого /г ~ 1 (х», у») — безусловная седловин точка функции (р» (х, у) в В" Х В . Если последовательности (а»)» ( и (р»)»=( удовлетворяют условиям (6.1б) и условию 1пп(р»/а») = оо, (в.гт) » в то каждая предельная точка (такова обямипельно существует) по-следовательности ((х», у»))» ( принадлежит множеству Х, х )'ы Кроме того, если а» с(пре,иится к бесконечности или если множества Хью Уь онепусты где Хо=(х(д((х)(0, (=1, ..., р, хЕВ"); (влв) ! а= (у!/;(у)(0, 1= 1, ..., т, усВ ), (влв) то все предельные точки последовательности ((х», у»))», являются седловыми точками функции (р (х, у) относительно Х, Х )'„т.
е. являются решением задачи 1. Теорема 1'. Пусть выполняются предположения 1 и условия (б.1б) и !'В.Щ. Тогда если множества Хь и Уь, определяемые соотношениями (б.16) и 1б.19), непусты, то для достаточно больших й безусловные седловые точки (х", у») функции (р» (х, у) принадлежат множеству Х, х Уь и справедлива следующая оценка скорости сходимости по функционалу: ~ф(х», у") — (р(х*, у*) ~((р+т)/а». Теорема 1". Пусть выполняются все условия теоремы 1' и пусть: (1о) — функция (р (х, у) имеет единственную седловую точку (х*, у») 470 относипмльно Х, х Уз; (о) — функция ~р (, у») — равномерно вы- пукла (с функцией рп (1)), а функция р (х', ) — равномерно вогну- та (с функцией р, (1)). Тогда для достаточно больших й справедли- вы оценки 0 ( рд ( [ х* — х» [! ) ( (р + т)/а»1 0~([»»([[у'.— у»[[)((р+ туа».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
