И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 65
Текст из файла (страница 65)
Ч. Вычислить следующее приближение х»+' = х» — р»ВД». Ч1. Вычислить п Х и-матрицу В» ~! (обратную результирующей матрице растяжения пространства после (/г+ 1)-го шага с коэффициентом растяжения а = 1/р) В»+! = В»ба (К»), где 68 ($») — оператор растяжения пространства в направлении $» с коэффициентом р. ЧП. Вычислить значение шагового множителя р»+! р» В— .1 Ул~ — ! ' ЧП1.
Положить й = й+ 1 и перейти к шагу П. 348 Теорема 3'. Пусть выполнено предположение 3' и точка хе лежит на рассглоянии, не превыигающем у от оптимальной точки х*. Тогда при п - 1 последовапмльность ]х»)» о, порожденная алгоритмом 3', удовлетворяет неравенствам ~]А»(х» — х*)[(р»(я+ 1), А»= В» ', /« =О, 1, Теорема 3' дает оценки сходимости алгоритма 3', выраженные в терминах уменьшения объема области локализации минимума. Приведенная ниже теорема 3" характеризует скорость сходи- мости алгоритма 3' по функционалу.
Теорема 3". Если функция /е выпукла в В' и в процессе применения алгоритма 3' выполняются следующие условия: (')— [] хе — х*[( у; (11)— ][у(х»)])(о, /«=О, 1, ..., здесь у (х») — обобщенный градиент функции /о в точке х», то для последовательности (х»)»" о, порожденной алгорит- мом 3', справедливы неравенства ппп (/е (х') — /е (х*)) ( О<в<» ( уо» )Г/г (аа — 1) д„"т/)/1 — рт»г", я = 1, 2, ..., о„= гпах )]у(х')]), сс = 1/и; о«» Замечание 3".
Так как для достаточно больших и г/„г= 1 — —, ! то теорема 3' гарантирует скорость сходимости «рекордов откло- нения» функционалов от оптимального значения, соответствующую скорости сходимости геометрической прогрессии со знаменателем 0~1 — —, 1 2яз ' Библиографические указания. Пункт ! написан на основании работ [320, 330], пункт 2 основан на реэультатак работы [222], пункт 3 написан на основании [402, 403, 404, 462, 4П1, В работе [443] предлагается вариант метода отсечения лля решения задачи вогнутого программирования с линейными ограничениями. 349 6.14. Методы, использующие функцию Лагранжа 1.
Градаеитиыа метод дяя аадач е ограиичеииями типа иерааеиета 3 а д а ч а !. Найти агп шах )е (х) для заданной функции «ах Де: В"-» В' и множества ХЬ(х(~~(х)~О, 1= 1, ..., т, Х~В"). Предположения 1. (1) — функции 1~ (х), 1 = О, 1, ..., т,— вогнуты и непрерывно дифференцируемы в В" Де (х), кроме того, строго вогнута); (В) — выполняется условие Слейтера, т. е. существует такая точка х, что ~! (х) ) О, 1 = 1, ..., т; ((В) — существует стационарная точка х' задачи 1 такая, что ~»(Х ) О, > ~р(х ) О ~р+~(Х ) «'О, ~ ~м(Х ))О! (1п) — функции )! (х), 1 = О, 1, ..., т, имеют в точке х' вторую производную. Введем функцию Р ср (х, у) Ь Ро (т) + Х уА (х), у = (у„..., уе) Е В+, которая является ограничением функции Лагранжа р(х, у)й1»(х)+ ~ уА(х), у=(у„..., у„)бВ+, Окав) » ! на множество В" Х Ваь.
Поскольку х' — стационарная точка задачи 1, то существует вектор уе = (ур, ..., у*) ~Во «такой, что Ч„<р(х*, у*) = О. Ниже приводится метод множителей Лагранжа с постоянным шаговым множителем, который при определенных условиях сходится глобально к седловой точке функции Лагранжа со скоростью геометрической прогрессии. Алгоритм 1 Н а ч а л о. 1.
Выбрать произвольное начальное приближение (х уе) Е В" Х В+. 11. Выбрать постоянный шаговый множитель р ) О. 1П. Положить А = О. !Ч. Определить функцию Лагранжа <р (х, у) по (5.66). О с н о в н о й ц и к л. Ч. Вычислить вектор Ч,~р (х», у"). Ч1. Положить И' = Д, (х"), ..., Г (х»)).
Ч11. Вычислить следующие прйближения х»+' и у»+' по формулам х»+' = х»+ рЧ„~р(х», у"); у'+' = гпах (О, у' — ОИ»). ЧП1. Положить И = И + 1 и перейти к шагу Ч. Збо Теорема 1. Пусть выполняются предположения 1 и пусть: (о)— задача 1 строго регулярна, т. е. 1) не существует ненулевого вектора и С 11» такого, что 2 — ~ч„„ф (х'", уе) и = О, Ч-ср (х*, уе) и = О; 2) не существует ненулевого вектора о Е В» такого, что , (Ч„-„ср(х*, у*)) о =О (т. е., векторы 71т (хе), ..., 71» (хе) — линейно независимы); 3) выполняется условие строгой дополняющей нежесткости уеб1п1 Вс', т.
е. у,')О, с = 1, ..., р; (о1) — не существует числа Л ~ О и ненулевого вектора и ~ И псаких, что — Чааф (х у ) и = О; 2 (Ч„-,ср(хе, уе)) Ч„-,ср(хе, у*) и = Л'и. Тогда для любого 6 ~ О найдется число р (6) ) О такое, что алгоритм 1 при всяком начальном приближении (хе, уе), удовлетворяющем условию 1(хе, у') — (х*, уе)1(6, и произвольном постоянном шаговом множителе р ( р (6), порождает последовательность ((хе, уе)Д „которая линейно 1т.
е. со скоростью геометрической прогрессии) сходится к седлоеой точке (х', уе) задачи 1. Замечание 1. Условие (ос) теоремы 1 является не только достаточным, но и в некотором смысле необходимым для сходимости алгоритма 1 в строго регулярной задаче. 2. Градиентный метод даа аадач е отреввчевиаин тина рааенета 3 а д а ч а 2. Найти агд ппп се (х) для заданной функции тех (е . Па -с- Вс и множества ~Й(х!1с(х) =О, с'=1, ..., т, хЕВ"). Предположения 2. (с) — задача 2 имеет решение хе; (11) — функции сс (х), 1 = О, 1, ..., т, непрерывно дифференцируемы в окрестности точки х*; (йХ) — функции 1с (х), 1 = О, 1, ..., т — дважды дифференцируемы в точке хе; (1о) — векторы Ч1с (х*), с = 1, ..
..., т — линейно независимы. Предположения 2 гарантируют существование и единственность множителей Лагранжа у*= (ус, ..., у ) задачи 2, т. е. Ч,ф(х', у*) = О, 7„ср(х', у*) = О, 351 где и Ч(х, у)ЬД„(х)+ ~„'уА(х) — функция Лагранжа задачи 2. Введем обозначения А ~~Ч„',»р(х», у'), СЬЧ»',<р(хч, у*), Сг— матрица, транспонированиая к С. Приведенный ниже алгоритм порождает последовательность ((х», у»))» ь, которая локально (т. е. при начальном приближении (х', у') из окрестности точки (х', у»)) сходится со скоростью геометрической прогрессии к точке (х», у*). На й-й итерации алгоритма движение к следующему приближению х»+' осуществляется е направлении аитиградиента по х функции Лагранжа, а движение к у»+' — в направлении градиента по у этой же функции.
Алгоритм 2 Н а ч а л о. 1. Выбрать начальное приближение (х', у') из окрестности точки (х', у'). П. Выбрать постоянный шаговый множитель р ) О. 1П. Определить функцию Лагранжа <р (х, у) для задачи 2, т. е. положить и~ <с(х, у)(~~»(х)+ ~, уА(х), у~В . (6.67) 1Ч. Положить й = О. Основной ци кл. Ч. Вычислить векторы ЧЛ(х~, у ) = Ч1»(х )+ 1 у,'РЧ,( ); Чр(х», у") = Д,(х"), ..., 1„(х»)). Ч1. Вычислить следующие приближения: х»+' = х» — рЧ„~р(х», у»); у " = у + рЧ~Ч( у ) Ч11. Положить й = й+ 1 и перейти к шагу Ч. Теорема 2. Пусть выполняются предположения 2 и пусть: (о)— матрица АС имеет ранг т, т.
е. из АС и = О следует и = О; (о() — мшприца А — неотрицательно определенная, причем Ах чь чь О при Сх = О, х Ф О. Тогда существует число р ) О такое, что при р ( р алгоритм 2 локально сходится к (х*, у») со скоростью геометрической прогрессии (т. е. найдутся числа е ) О, О ( д, ( 1 такие, что при любых 3 х' — х* ) ( е, ) у' — у* 1 ( е будет ~х' — х*1((3, (е) (ц,)»; ~у» — у*~(р,(е) (д»)»).
352 3. Метод квадратичной аппроисимапви дяя задач с ограничениями типа равенств В методе квадратичных аппроксимаций пай-й итерации функция Лагранжа »р (х, у) квадратично аппроксимируется по х в окрестности точки х" и следующее приближение х"+' находят из условия минимума этой квадратичной аппроксимации. Движение по переменной у осуществляется, как и в градиентном методе.
Алеоритм Я Н а ч а л о. 1. Выбрать начальное приближение (х', у') из окрестности точки (х*, уе). П. Выбрать постоянный шаговый множитель р ) О. П1. Определить функцию Лагранжа по (5.67). 1Ч. Положйть lг = О. Ос но зной ци кл. Ч. Вычислить векторы че4р(х», у») = (1,(х»), ..., 1 (х")); Е4 Ч,1р (х', у') Ч1, (х') + ~„'4 у»Ч14 (х"), 1 1 Ч1. Вычислить матрицу Чс.»р(х», у') Ч 1е(х')+ Х д1Ч 14(х») 1 1 ЧП.
Вычислить следующее приближение (х"+', у»+') из системы Ч,4р(х», у")(х"+' — х») = — рЧ,4р(х», у"); д+ =д +рчюУ, д). ЧП1. Положить й = й + 1 и перейти к шагу Ч. Теорема 3. Пусть выполняются предположения 2 и пусть (пЩ— матрица А Е~ Ч~ур (х', уе) — положительно определенная, т. е. (Ах, х) ~ О при х чь О. Тогда существует число р ) О такое, что при р ( р алгоритм 8 локально сходится к (х', у*) со скоростью геометрической прогрессии (т. е. найдутся числа е ) О, О ( оз ( 1 такие,что при любых ( хе — хе ( ( е, ( у' — уе ( ( е будет !! х» — хе (( ()з (е) (уз)»; 1У» — Уе ~! ( Рз (е) (Уз)»).
4. Двойственный метод дая задач с ограничениями типа равенств В двойственном методе на й-й итерации вычисляют (й + 1)-е приближение х»+' путем решения задачи безусловной минимизации по х функции Лагранжа 4р (х, у') (предполагается, что задача 42 3-341 353 безусловной минимизации разрешима).
Движение по переменной у осуществляется, как и в градиентном методе. Алгоривем 4 Н а ч а л о. 1. Выбрать начальное приближение (х', у') из окрестности точки (х", у'). 11. Выбрать постоянный шаговый множитель р ) О. П1. Определить функцию Лагранжа по (5.6?). 1Ч. Положить й = О. Ов н о в но й ц и кл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
