Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 81
Текст из файла (страница 81)
9 Б. Метод возможных направлений 1. Продолжим рассмотрение задачи минимизации гладкой функции /(х) на заданном, множестве Х С Е". Напомним, что направление е ~О назы- ваетсЯ возможным в точке х Е Х, если х+ 1е Е Х пРи всех Ь, О < Ь < го, где хо — положительное число, зависящее от точки х, направления е и от структуры множества Х (см. определение 4.2.3).
Определение 1. Направление е фО назовем возможным направлением убывания функции /(х) точке х на множестве Х, если е — возможное направление в точке х и /(х+ схе) < /(х) при всех сг, О < сх < !8, где О < !3 < Ьо. Метод возможных направлений основан на следующей естественной и прозрачной идее: на каждой итерации этого метода определяется возможное направление убывания функции, и по атому направлению осуществляется спуск с некоторым положительным шагом.
Собственно говоря, зта идея для нас уже не новая — именно на ней были основаны многие варианты изложенных в $1, 2, 4 методов. В самом деле, если Х = Е",,/'(х) фО, 2?О Гл. 3. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ то возможное направление убывания функции легко находится — это направление антиградиента е = — /'(х). Более трудным был выбор возможного направления убывания в методах З 2, 4: в методе проекция градиента (см. формулы (2.2) и (2.2')) для этого нужно было проектировать точку на исходное множество Х, а в методе условного градиента — решать задачу минимизации линейной функции на множестве Х (см. задачу (4.3)).
Понятно, что если задача выбора возможного направления убывания на каждой итерации слишком сложна и требует решения вспомогательных задач минимизации, сравнимых по трудности, быть может, с исходной задачей, то такой метод минимизации будет малоэффективным. Возникает вопрос: нельзя ли указать простые и достаточно удобные для реализации на ЭВМ способы выбора возможных направлений убывания? Оказывается, для достаточно широких классов гладких задач такие способы существуют. Покажем это на примере следующей задачи: 1(х) — «ш1; хЕХ=(хЕЕ":д;(х)(~0«1=1,...,т)«(1) где функции 1(х), д|(х), 1 = 1,, т, определены на всем пространстве Е" и 1(х), д,(х) Е С'(Х).
Чтобы проще было пояснить суть метода возможных направлений для задачи (1), сначала опишем более простой вариант этого метода. Пусть х е Х вЂ” некоторое начальное приближение. Пусть известно й-е приближение х„е Х, й > О. Введем множество номеров 1 =(в': 1(1<т, д(х,)=0) Возможно, что 1„= |2|, — это будет означать, что д|(хь) < 0 при всех 1 = = 1,..., т, т. е, хь е 1п! Х вЂ” такая возможность ниже не исключается.
В пространстве переменных х = (е, а) = (е',..., е", а) Е.Е"+' рассмотрим вспомогательную задачу «г — «!п1, з =(е,а) Е И"„=((е, о); (1'(х„), е) < а; (д,.'(х„), е) ( о; г Е 1; |е'! ( 1, !' = 1,..., и«г. (2) Заметим, что задача (2) является задачей линейного программирования, причем минимизируемая функция (с, з) = (О, е) +1»г, с =(0,1) е Е"+', явно не зависит от переменных е = (е',..., е").
Далее, ясно, что точка з =(е =О, а =О) = (0,0) е И', так что И»„~ 0 и !п1»г = о < 0 при всех я» Ъ = О, 1,... Очевидно, множество И' замкнуто. Наконец, условия !ет! < 1, !' = 1,..., и, называемые условиями нормировки, гарантируют ограниченность множества И'. Тогда из теоремы 2.1.1 следует, что задача (2) имеет хотя бы одно решение. Для получения решения задачи (2) могут быть использованы известные конечные методы линейного программирования (например, симплекс-метод, описанный в гл. 3). Предположим, что задача (2) решена и найдены (е„, оь) е И'„такие, что и, = !п1 о.
Выше было замечено, что а,, < О. и'« Сначала рассмотрим случай о„(0. Оказывается, в этом случае направление е„, полученное из задачи (2), является возможным направлением $ З. МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ Для минимизации функции д„(а) могут быть использованы известные методы (см., например, гл. 1). Точное решение задачи (5) удается найти лишь в редких случаях; возможно также, что на некоторых направлениях е„величина !1, = со и нижняя грань функции д„(а) при а > 0 не достигается.
Поэтому вместо (5) на практике целесообразно употреблять такой спосо выбора а„: 0<а,<|3„д„(а„)(д.+бю б„>0, 2 6» б<со (5) или /(х, +а е„)((1 — Л,)/(х.)+ Лад„„О< Л < Л <1. 2) Если функция /(х) е С" (Х) и константа Липшица 1 для градиента /'(х) известна, то в (3) в качестве а„можно принять а =ш|пЯ; !с«„|1 ').
2?1 убывания функции /(х) в точке х„. В самом деле, из условия (е„,о„) е И', следует, что (/'(х„), е„) «т. <О, (д,.'(х.), е ) <а <О, 1 е1. Отсюда ясно, что е„~ О. Кроме того, для любого номера г е 1„имеем 'ф::„д (х„+ ае,) = д(х„+ ае ) — д(х„) =(д?(х„) е„)а+ о(а) < < а(о„+о(а)/а) <О при всех а, 0< а < а,, а| >О. Если 1 (1 1„т. е. д|(х„) < О, то в силу непрерывности функции д|(х) неравенство д|(х + ае„) < 0 сохранится при всех а,,О < а < а,, где а| > .,~ а достаточно малое число. Положим а =пип(а„..., а„) >О.
Тогда д«(хь+ае„)<0, 1=1,...«т; 0<а<а, т. е. е„ вЂ” возможное направление множества Х в точке х„. Далее, взяв при необходимости число а, > 0 еще меньшим, можно добиться выполнения неравенства /(х„+ ае ) — /(х ) =(/'(х,), еь)а+ о(а) < < а(«г„+о(а)/а!<0 при всех а, 0<а (ах Тем самым показано, что если (е„, »г„) — решение задачи (2), причем о < < 0 то е, — возможное направленйе убывания функции /(х) в точке х„ на множестве Х. е (х 1)-е Используя найденное таким образом направление е„, следующее ( + )-е приближение определим так: хь ~ | —— х~ + аь ею 0 < аь ( Рь « ;3 = зир(а; х„+ $е„Е Х, 0 < ! < а? > О. у риа Выбирая а, в (3) различными способами, будем получать различные варианты метода возможных направлений.
Перечислим некоторые способы выбора а,. 1) Величина а„может выбираться из условий 0 < а < !у„, д (аь)= !п1 д„(а)=д„,; д„(а)=1(х,+ае„). (5) 272 Гл. З. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ $ З. МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ сог ог чо П Ло, или (О) Л* (Е (~г)) у~ Л (гч (~г)) г=! 3) Возможен выбор величин а из следующих условий /(х„) — /(х„+а е„) ) га„/о !г 0< а, (дьг 0(г <1/2 Для определения такого а„сначала можно положить а„=,д„а затем при необходимости дробить эту величину. 4) В тех случаях, когда трудно оценить величину д„ из (4), приходится довольствоваться нахождением какого-либо а > О, обеспечивающего включение х„+аье, Е Х и условие монотонности Г(х +а„е„) </(хо).
Для этого обычно выбйрают какую-либо постоянную а > О, полагают аь = а и проверяют условие монотонности и принадлежность точки х„+, множеству Х; при необходимости дробят величину а, = а, добиваясь вйполнення упомянутых условий. Один шаг метода возможных направлений для задачи (1) в случае сг < 0 описан. Попутно выяснен смысл вспомогательной задачи (2): минимизйруя о, мы добиваемся того, чтобы направление е„было как можно ближе к направлению антиградиента (это обеспечивается условием (/'(х,), е„) < сг) и в то же время оставалось возможным направлением для множества Х в точке х (это обеспечивается условиями (д,.'(х ), е„) < сг, 4 Е 1„), причем, чем меньше о, тем ярче выражены указанные свойства иаправлейия е .
Кстати, если 1„= !сг, т. е. х„Е !п1 Х, то е„=-а/'(х„), а = ( шах (~'„г(х„)~) ' > 0— направление антиградиента. Теперь рассмотрим случай, когда в решении (е„ сг„) задачи (2) координата сгь = О. Как видно из (2), это может случиться, например, при /'(х„) =0 или д,.'(х,) = 0 для некоторого номера 1 Е 1,. При сг =0 уже нельзя гарантировать, что е„ будет возможным направлением убывания. В этом случае итерационный йроцесс (2) †(4) прекращается. Оказывается, при гг = 0 в точке х выполняются необходимые условия минимума, выраженные в теореме 4 8.1.
Для выпуклой задачи (1) со свойством (4.9.15) условие о„=О гарантирует, что х„ Е Х„. А именно справедлива Теорема 1, Пусть функции /(х), дс(х), 1=1,..., ги, определены на Е", /(х), дс(х) е Сг(Х), гдв множество Х задано условиями (1), и пусть задача (1) имеет решение, т. г.
/„> — оо, Х. ф Я. Тогда для любой точки х. е Х, задача сг-+!П1; г=(е, о) е Иг, =((е, сг): (Е'(х,), е) < а, (д,.'(х,), е) < <сг, 4 Е 1„)е'! < 1, З' = 1,..., п)г (7) гдв 1„=(!«1 < о < ги, дс(х,) =0), необходимо имеет решение (е„о,) с сг„= ш1псг =О. Если, кроме того, 1(х), дс(х) выпуклы на .Е", и ввтолнено условие Слгйтгра (4.9.15), то всякая точка х„е Х, для которой задача (7) определяет величину о, = =1п1 т = О, является решением задачи (1). Доказательство. Необходимость. Пусть х, ЕХ,.
По теореме 2.3.2 или 4.8.1 тогда существуют множители Лагранжа Л*,..., Л„*, неотрицательные и не все равные нулю, такие, что Ло/'(х,)+ 2, Л,"д,'(х,) =О, Л,'.д,(х„) =О, с =1,..., ги. (8) Если ! гА 1„, то из второго равенства (8) следует Л;. = О, поэтому первое равенство (8) можно переписать в виде Л'Е'(х,) + 2, 'Л,"д,'(х,) =О. (9) Возьмем любую точку (е, сг) е Иг„. Тогда ( р(х,), г) < сг, (д,'(х„), е) < сг, 1 е 1;, Умножим первое из этих неравенств на Л' > О, остальные — на соответствующие Л,* > 0 и сложим. С учетом равенства (9) получим (Ло/'(х„) + ~ , 'Л;д,'(х„), е) = 0 < гг(Ло+ Л! +...
+ Л;„), Следовательно, о > 0 Ч(е, сг) Е Иг„, и ог = О. До с т а т о ч н о с т ь. Пусть теперь /(х), д,(х) выпуклы на Х, выполнено условие Слейтера (4.9.15), и пусть для некоторой точки х, е Х задача (7) определяет величину с, = 1п1 а =О. Покажем, что тогда х„Е Х,. С этой целью в пространстве Е"+! введем конус К=(г=(е,сг)ЕЕ"'гг! (/г(х„),е)+( — 1)с<0, (д,.'(х.),е)+( — 1)сг<О, 1ЕЕ„) и вектор с( = ~ ). Из (7) с учетом 1п1 а = о, = 0 имеем гол (с1, г) = (О, е) + 1 ° сг = сг ) о; = 0 (10) для всех г = (е, сг) Е К, для которых ~е'~ < 1, у = 1,...,и. Однако условие )е'( < 1, о' = 1,...,и здесь можно отбросить, и неравенство (10) на самом деле верно для всех гЕ К. В самом деле, пусть г=(е сг) Е К и ~е'~) 1 для некоторого номера З', 1 < о' < и. Тогда 8е)( = шах (е'~ > 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
