Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 84
Текст из файла (страница 84)
(9) Доказательство. Из неравенства (4) при г = рг(у,а) имеем: -!рг(у, а) — рг(х, и)!' < ~р(рг(у, а), х, а) — ~р(рг(х, а), х, а). Меняя здесь х и у ролями, получим -(рг(х, а) — рг(у, а)!' < ьо(рг(х, а), у, а)— — у(рг(у, а), у, а). Сложим эти два неравенства: !рг(х, а) — рг(у, и)!з < < р(рг(у, а), х, сз)- ср(рг (х, а), х, а)+(о(рг(х, а), у, а) — (о(рг (у, а), у, а). 280 Гл. З. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ В правую часть этого неравенства подставим соответствующие значения функции р(г, х, сс) согласно ее определению (2). После простых преобразований получим !рг(х,а) — рг(у,сс)!><(рг(х,а) — рг(у,о),х — у) >Ух, уеЕ", сс>0. (10) К правой части неравенства (10) применим неравенство Коши — Буняковского: !рг (х, сс) — рг (у, сс)!' < !рг (х, сс) — рг (у, сс)/ !х — у!. Отсюда следует не авенство (9).
!3 следующей теореме приводятся условия, обеспечивающие непрерывность рг (х, о) по совокупности аргументов (х, сс) во всех точках х е Е", сс >О. Т е о р е м а 3. Пусть в дополнение к сделанным выше предположениям функция 7(х) удовлетворяет условию дипшица: 1,>" (х) — Г'(у)~ < Ь !х— — у~ Чх,уЕХ, пустьх„ЕЕ, сс„>0, й=1,2,..., [х„) — >х, (с> ) — ~а>0. Тогда !пп рг(х„, сс„) =рг(х, а). Доказательство. По неравенству треугольника имеем: /рг(хь, а„) — рг(х, сс)~ < /рг(хь, сс„) — рг(х, оь))+ + !рг(х, сс„) — рг(х, сс)~, й = 1, 2,...
(11) Первое слагаемое в правой части неравенства (11) в силу (9): !рг(х, с>„)— — рг(х, ссь)! < !х„— х! — 0 при й — оо. Докажем, что второе слагаемое также стремится к нулю. Из неравенства (4) при сс = сс„, х = рг(х, сс) следует 2!рг(*, сс) — рг(х, аь)!'<( 2!рг(х, ы) — х~ — 2!рг(х, сс„) — х/ + + с>ь(Т(рг(х, сс)) — !'(рг(х, сс„))), й = 1,2, По условию функция 7'(х) удовлетворяет условию Липшица, поэтому !)(рг(х, сс)) — 7(рг(х, сс„))~ < Ь!рг(х, а) — рг(х, сс„)!.
Отсюда и из предыдущего неравенства для величины а, = (рг(х, сс) — рг(х, ссь)! > 0 имеем: а>ь — 2сс„Ьа„— !Рг(х, а) — х!з < О, й = 1,2,... ЗамечаЯ, что леваЯ часть этого неравенства представляет собой квадратный трехчлен относительно переменной а„, получаем оценку для а„: 0 < а„ < а Ь + + !рг(х, сс) — х!~ + сс'Ь' < 25 зцр сс„+)рг (х, сс) — х~, Тогда последователь- >во ность (рг (х, а„)) также ограничена и согласно теореме Больцано — Вейерштрасса имеет хотя бы одну предельную точку ю. Выбирая при необходимости подпоследовательность,можем считать, что (рг (х, сс„))-+ ю.
Тогда множество >с, состоящее из точек рг(х, с>„), й = 1, 2,... и точки ю компактно. В силу компактности субдифференциального отображения (теорема 4.6.5) тогда компактно и множество () д7(у), которое содержит субградиенты ге и с(рг (х, сс„)), входящие в неравенства (7) при сс = аь, й = 1, 2,....
Поэтому можем считать, что (с(рг(х, сс ))) — > с. Из замкнутости субдифференциального отображения (теорема 4.6.5) следует, что с е дг(ю), Теперь мы можем совершить предельный переход при й — оо в вариационных неравенствах (рг (х, сс„) — х+ с>„с(рг (х, сс„)), з — рг (х, аь)) > 0 >>х Е Х, полученных из (7) при с> = сс„. Будем иметь (ю — х+ ссс, з — ю) > 0 Чх Е Х. Здесь с Е д!'(ю) и согласно формуле (6) имеем с, = ю — х+ ас Е д~р(ю, х, сс). Отсюда и из предыдущего неравенства, записанного в виде (со х — ю) > 0 >>а Е Х с помощью $ б, пРОксимАльный метОд 281 теоремы 4.6.4 получим, что ю решение задачи (3), т. е. ю = рг(х, сс). Это значит, что последовательность (рг(х, сс,)) имеет единственную предельную точку рг (х, си), т.
е. !пп рг (х, аь) = рг(х, а). Тем самым мы доказали, что второе слагаемое из правой части неравенства (11) также стремится к нулю. Непрерывность проксимального отображения рг (х, а) по совокупности аргументов (х,а) установлена. П Замечание !. В силу теоремы 4.6.6 выраженное в теореме 3 требование условия Липшица от функции Г(х) можно заменить условием ограниченности множества Х, Проксимальный метод заключается в построении последовательности (х ) по следующему правилу: х„л, = рг (х„, ссь), й = О, 1,..., (12) где начальная точка х и последовательность (оь) > 0 предполагаются заданными.
Итерационный процесс (12) основан на известном из анализа 1393! методе поиска неподвижных точек сжимающих операторов и идейно близок к рассмотренным выше методам проекции градиента и субградиента. В соответствии с определением проксимального оператора на й-м шаге процесса (12) для определения очередного приближения х,л, нужно решить задачу минимизации (3) при х = х„, сс = сс„: У(л1 хю с>ь) = 2!з хь! + оь7(а) — > !и1, а Е Х, й =О, 1,... (13) Если функция У'(х) дифференцируема на Х, то согласно теореме 4.2.3 точка х„л, будет решением задачи (13) тогда и только тогда, когда (ь>,'(х„„„хь,а ),г — х„+,)=(хь,,— х,+с>„>' (х„с,),з — хь+,) > 0 ЧгеХ. Отсюда, используя характеристическое свойство проекции (неравенство (4.4.1)), получаем, что хил, = Рх(хь — а„~'(хь „)), й = О, 1,...
(1,4) Таким образом, для дифференцируемых функций проксимальный метод (12) равносилен методу проекции градиента в так называемой неявной форме, когда х„л, явно не выражено через предыдущее приближение х, и должно определяться как решение уравнения (14). Т е о р е м а 4. Пусть Х вЂ” выпуклое замкнутое множество из Е", функция 7"(х) определена и выпукла на открытом выпуклом множесаве Ис, содержащем множество Х, и полунвпрерывна снизу на Х, Г; = !п1 Г(х) > — оо, Х„= (х С Х: У(х) =- Я ф !2>, пУсть 0 < Уь < сс, < "~,, мсх й = О, 1,...
Товда последовательность (х„~, определяемая методом (12) при любом начальном приближении х е Е ', сходится к некоторой точке о, = с,(хь) Е Х,. Дока з а тельство. Применяя неравенство(4,3.3) кзадаче (13) имеем -!х — х„~,!з < ~р(х, х„, аь) — !с(х „, х,, ссь) = ! 2~!з хь~ 2!хе+1 хь~ +ссь(Пз) Х(хь„,)) ЧЯЕХ, й = О 1,... (15) 282 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Возьмем произвольную точку х, е Х, и в (15) положим л = х„.
С учетом неРавенства У"(х,) — У'(хьчс) < О полУчим [х,— хь „с!~ ( [х„— ха[2 — [хь ! — хе[2 ((хь — хь[ес й =О, 1,..., Сгх„ЕХ,. (16) Отсюда видно, что последовательность ([хь — х,[2) не возрастает, а (хь) ограничена. Тогда существует подпоследовательность (х, ), сходящаяся к некоторой точке и„ причем п,еХ в силу замкнутости Х. Можем считать, что (сгь )- сг, О< у < сх < Тс. Далее, суммируя неравенство (16), имеем [х „— хе[2 ( [х. — х [2 — [х.
— х, „с)2 ( )х, — х )2 !71)7 = 1, 2, (18) это значит, что РЯд Я [хаю с — хь!2 сходитсЯ и, следовательно, !пп [хь ь=о Ь с — х ~ = О. Тогда подпоследовательность (х, г с) также сходитсЯ к ью ПеРехоДЯ в (15) к пРеДелУ пРи й = йг — с оо с Учетом неРавенства!|щ~(хаю с) > Т(п), получим: О < сг (У" (х) — Т(п )) сок Е Х. Это значит, что и, Е Х,, Поскольку последовательность ([хь — х„[~) не возрастает при Чх„Е Х., то в частности пй!ги х„= и, мы также получим невозрастающую последовательность ([хь — и„! ).
Тогда* [!|п [хь — п„[2 = [пп [хь — п„[2 =О. Теорема 4 доказана. (:) Ь ю юю Для сильно выпуклых функций 7"(х) несложно получить оценку скорости сходимости метода(12) при пь-— п)0, й=0,1,... Теорема 5. Пусть выполнены условия теоремы 4 и функция 7"(х) сильно выпукла на множестве Х с постоянной сильной выпуклости х > О. Пусть последовательность (хь) определена методом (12) при пь — — и > О, й =О, 1,...
Тогда' [х — ж[ <[х — ж[ д, й=0,1,,.4 у= 1 (17) Доказательство. Иэ теоремы 4.3.! следует, что при сделанных предположениях задача (1) имеет, притом единственное, решение ж„ и хл[г — х,[ < С'(г) — С'(з,) сг Е Х. Кроме того, функция зс(г, х, п) из (2) сильно выпукла с постоянной сильной выпуклости 1+ах и из (13) имеем 1+ах 2 [г — зь ь с [ < ю(гс зь с и) — Ус(ха+ с, хь с п) с (19) Чг Е Х, й = О, 1,... В неРавенстве (18) положим г = вью с и Умножим его на и > 0 и сложим с (19) пРи г = х,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
