Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 79
Текст из файла (страница 79)
й <... таних, что (сь, х) — Р» (хь )) (от, р=!,2, (16) В самом деле, допустим, что (16) не имеет места. Тогда (сс, хь — Р» (хь)) > оьт при всех й = О, 1,... Отсюда и из (15) имеем в в ос < г оь(сь,хь — 'Рх(хь))<В<оа, г=!,2,..п ь=о а=о что противоречит расходимости ~; оь+7, ь=о Тем самым показано существование подпоследовательности (хь ), удовлетворяющей уело вию (16). Докажем, что 1!ш /(хь ) = /, )пп р(хь, Х„) = О.
(17) Сначала убедимся в том, что сь Е д/(хь ), р = 1, 2,... (18) Для этого достаточна показать, что д(хь ) ( о)";, р = 1, 2, .. О и вспомнить условия (14). ДопУстим, что д(хь ) > оь пРи некотоРом Р > 1. УчитываЯ, что тогда сь е дд(хь ) и, кРоме того, 7 Р Р» (х„) с Хс с Х, т. е, д(Р» (хь )) < О, из (16) имеем оьт < д(хь ) < д(хь ) — д(Р» (хь )) ~ <(сс, хь — 'Р» (хь )) ~ (оьт. Получили противоречивое неравенство. Включения (18) доказаны, и попутно установлено, что д(хь)(оьт, р=!,2,... (19) ; ! э' р'.
262 Гл. 5. МЕТОДЪ| МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЪ|Х 8 4. МЕТОД УСЛОВНОГО ГРАДИЕНТА 263 Множество номеров (й ), удовлетворяющих условиям (16), представимо в виде объединер ния непересекагощихся множеств Х! — — (йр. 'Х(хь ) >л Х,) и 1т = (йр! Х(хь ) < Х,). Сначала рассмотрим случаи, когда множество 1! бесконечно, Иэ (16), (18) имеем О ( Х(хь ) 1 Х(хь ) Х(Рх (хь )) ( (сь > хь Рх (хь )) ( пьт йр Е 1! Отсюда следует, что Х(хь ) ч Д при р ч со, йр е 1!. Тогда Х(хь ) < С! < со, и, кроме того, согласно (13), (19) имеем д(ха ) < оь~ < эцр оьт — Сз <со, т. е.
(хь ) е М(С|, Сз), й е 1|, Так ь>а как М(С!, Сз) ограничено, то (хь, й е 1!) имеет хотя бы одну предельную точку. Не умаляя общности, мажем считать, что (хь ) -ч х„й е 1!. Из замкнутости Ха, неравенства (19) и г ' р непрерывности д(х) следует, что х, е Х. Но 1(хь ) т Х(х„) = ?„при й„-ч оа, йр е 1|, так что х, Е Х,. Отсюда и ив непрерывности р(х, Х,) имеем р(хь, Х„) ч р(эры Х„) = 0 при й ч со, й„с 1т Теперь рассмотрим случай, когда множество Хз бесконечно. Если йр е Хз, то Х(хь ) < Д, а д(хь ) < оьт ( эцр оь — — Сз в силу (19), Это значит, что (хь ) е М(Х„, Сз), й„Е 1э.
Поскольку ь>а множества М(Х„Сз) ограничено, то (хь, й е 1з) имеет предельную точку. Не умаляя абщр ности, можем считать, что (хь ) ч х„, йр е 1з. Иэ (19) и замкнутости Ха следует, что х, е Х. Поэтому Х(х„)>Х„. Сдругой стороны, Х(хь )<~'„, й е1з, так что 8ш 1(хь )=Х(х,)(1„. р ь ег,р Ор г а Следовательно, Х(х,) = Х„т. е, х„е Х,, Отсюда и из непрерывности р(х, Х„) получаем р(хь, х„) ч р(х„, х,) =0 при й ч со, йр е1з. Объединяя оба рассмотренных случая, заключаем, что для подпаследовательнасти (хь ), удовлетворяющей условию (16), справедливы равенства (17), Отсюда, повторив заключительные рассуждения из донаэательства теоремы 1, убеждаемся в справедливости равенств (5) и для метода (!2)-(14).
Замечание 1 сохраняет силу и здесь. На этом закончим рассмотрение методов минимизации негладких выпуклых функций. Отметим, что негладкие задачи в последние годы интенсивно исследуются, продолжается разоаботка различных методов их решения (73; 226; 251; 256; 263-266; 302; 314; 318; 361; 386; 396; 426; 434; 495; 502; 542, 5?2; 586; 6!3; 718; 720; 769; 777; 7951. Упражнения 1. Рассмотреть возможность применения метода проекции субградиента к задачам иэ упраж. пений 4.6.1 и 4.6.3. 2.
Описать метод (12)-(14) применительно к задаче Х(и) = !х Ч- у/ 4 |х — у| — э !п|, и Е Х = (и = (х, у) Е Е: и Е Х, д(и) = и — 1 Е <О), Ха — — (и=(х,у); х>0, у<0). 3. Проверить условия теоремы 2 для задачи 1(и) = |(с, и) | -э !п|; и Е Х = (и ЕЕ": и >О, д(и) =|(а, и)| — 1 <О), где а, с е Еч. Описать метод (12)-(! 4) применительно к этой задаче. 4.
Пользуясь формулой (4.6.!0), модифицировать метод (12)-(14) так, чтобы его можно было применять к задаче (10) непосредственно, не сводя ее к задаче (11), 5. Пусть Иг — открытое выпуклое множества, 1(х) — выпуклая функция на Иг. Показать, что вектор с„удовлетворяющии условиям (с„| = !п1 |с| > О, с, е д?(х), е э?!р! является направлением убывания функции 1(х) в точке х. $4. Метод условного градиента 1. Этот метод приспособлен для решения задачи 1(х) — > !П1; х е Х, (1) где Х вЂ” выпуклое замкнутое ограниченное множество из Е", функция ?(х) е С!(Х).
Опишем его. Пусть х е Х вЂ” некоторое начальное приближение. Если известно й-е приближение хь е Х, й >О, то приращение функции 1(х) в точке х„можем представить в виде 7(х) — Х(хь) = (1'(хь), х — х,) + о(!х — хь!), Возьмем главную линейную часть этого приращения ?ь(х) = (7'(хь), х — х„), (2) и определим вспомогательное приближение хь из условий х Е Х, |п(,?' (х) =Хь(х ) = (?'(хь), х„— х„). (3) Так как множество Х замкнуто и ограничено, а линейная функция Х (х) непрерывна, то точка х, из (3) всегда существует.
Если функция Хйь(х) достигает своей нижней грани на Х более чем в одной точке, то в,качестве точки х„возьмем любую из них. Заметим, что если Х=(хЕЕ™: х>О, (о,,х)<Ь', з=1,...>гп; (ог,х)=Ь', з'=т+1,...,а), то задача (3) превратится в задачу линейного программирования, которая может быть решена известными методами (например, описанным в гл. 3 симплекс-методом). Укажем случаи, когда решение задачи (3) будет выписываться в явном виде.
Если Х =(х=(х',..., х"): ой < х! < 1)г, э =1,..., п1 — ть-меРный паРаллелепипеД, то фУнкциЯ Хь(х) = 2 „Уы(хь)(х' — х„*) или ч 2, ')ы(хь)х', очевидно, достигает своей нижней грани на Х в точке хь = з=! = (х',...,х„), где сто Хы(хь) > О, ?эз, Хы(х„) < О; ы в случае Хы (хь) =О здесь возникает неопределенность и в качестве х', можно взять любое число из отрезка [гхг, )У,.) (обычно берут х'„= сх,р или х, = Д, или х'„= (ст! + Д)/2). Еслй Х =(х ЕЕ'! !х — ио! < т) — шар радиуса т с центром в точке ош то с помощью неравенства Коши — БУнЯковского (Х'(хь), х) = (1'(хь), х — оо) + (1'(хь), и ) > — ~1('(хь)<т + + (('(хь), ио), х е Х, получаем, что х, = иа — т1'(хь)(?'(хь)! '. 264 Гл. З.
МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ 265 4 4. МЕТОД УСЛОВНОГО ГРАДИЕНТА (9) или пип(1; р„! /ь ( х, ) И хь — х„! '), аь О, Г„(х„) <О, /„(х„) > О, (10) где (12) *о (7) Разумеется, так просто получить вспомогательное приближение хь удается далеко не всегда, и вместо точного решения задачи (3) часто приходится довольствоваться определением какого-либо приближенного решения. А именно, будем предполагать, что оно определяется из следующих условий: хь е Х, Гг(хь) < пип/,(х)+ г„, г„> О, !ип г„=О. (4) Допустим, что точка х„, удовлетворяющая условиям (4) (или (3)), уже найдена. Тогда следующее (к + 1)-е приближение будем искать в виде х, „, = хь + а„(х„— х,), 0 < а, < 1.
(5) В силу выпуклости множества Х всегда х , е Х. Заметим, что при х„= х„(это может случиться, например, когда /'(х,) = =0) имеем х„„, = х, йезависимо от способа выбора аь в (5). Если прн этом х, было определено точно из условий (3), то имеем 7ь(хь) =Гь(хь) = 0 = ш!и 74(х) н (г (хг) х хь) > 0 при всех х 6 Х. Согласно теореме 4.2.3 это означает, что точка х, удовлетворяет необходимому условию минимума в задаче (1). В этом случае итерации прекращаются, и для выяснения того, будет ли х„ Е Х„, при необходимости проводится дополнительное исследование поведения функции /(х) в окрестности точки х„. В частности, если /(х) выпукла, то согласно теореме 4.2.3 имеем х, е Х„ т. е.
задача (1) решена. Если случай х„ = х„ реализовался при определении х„ из условия (4), то будем иметь -г, < ш!и Д,(х) < / (х„) = /ь(хь) = О, и при г„> 0 здесь теорему 4.2.3 прил менять нельзя. В этом случае согласно (5) полагаем х„э, = х и переходим к проверке условия (4) для номера й + 1 и т. д. В зависимости от способа выбора величины аь в (5) можно получить различные варианты описанного метода, часто именуемого в литературе ме>подом условного градиента. Укажем некоторые наиболее употребительные способы выбора а„в (5).
1) Величина а„может выбираться из условий 0< а„~ (1, дь(а„) = пип д„(а) =д„„дь(а) =/(хь+ а(хь — хь)). (6) Ока4! Для некоторых классов задач можно получить из (6) явное выражение для а„. Пример 1. Пусть /( ) = 2 (А' *) - (б ') где А — симметричная положительно определенная матрица размера и х и, б е Е". Тогда /'(х ) = Ахь — б.
Пользуясь формулой (4.2.10), имеем д (а) =/(х,)+ а(/ (х„), хь — х ) +(а'/2)(А(х, — х ), х, — х ). Если (А(х„— х„), х, — х„) =О, то хг = х, и, как было указано выше, тогда х„е Х,. Поэтому пусть (А(х, — х,), х„— х„) > О. Тогда функция (7) представляет собой квадратный трехчлен, достигающий своего наименьшего значения на числовой оси -оо < а < +оо при а„* = — (/'(х„), х„— х„)((А(х„— х„), х„— х )) '. г ! . !::>', 1 ю Рассматривая возможные случаи а,*<0, 0< а,*<1, а„*>1, из условий (6) тогда получаем О, а,*,<0, (8) Кстати, если точка хь в (7) найдена из условий (3), то /„(х„) < /г(х„) = 0 и, следовательно, а", > 0 — в этом случае формула (8) для а, запишется в виде а„= ш!п(1; аД.
Однако точное определение а„из условия (6) возможно далеко не всегда. Поэтому вместо (6) можно ограничиться определением величины а„из условий 0<с!а<1, д„(а„)<д„+б„бь>0, ~; б„=б<со ь=о 0< а„< 1, д (а )<(1 — Л„)д„(0)+Льды, 0<Л < (Ль(1 Здесь могут быть использованы известные методы минимизации функций одной переменной (например, методы из гл. 1). 2) Если /(х) е С'!(Х) и константа Липшица Ь для /'(х) известна, то возможен выбор а„в (5) из условий 0 « .„ р„ ( 2(! — г)/Ь, г, г — параметры метода, 0 < г < 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
