Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 78
Текст из файла (страница 78)
Непрерывный и дискретный варианты методов более высокого порядка см„ например, в [520-521!. 1. Вычислить несколько итераций метода проекции градиента при различных способах вы бора аь в (2) для функции 7(и) = (х — 1) + (у + 1), иЕХ=Е~ч=(и=(х,у)ЕЕ~: хмО, у)нО). Рассмотреть начальные приближения ио — — (О, 0), но = (О, 1), ео =(1,0), ио = (1, 1). 2. Описать одну итерацию метода проекции градиента для функции (1.5), считая, что множество Х представляет собой шар, гиперплоскость, параллелепипед, полупространство или положительный ортант (см.
примеры 4.4.1-4.4.6). Исследовать сходнмость метода. 3. Рассмотреть метод проекции градиента для функции 7(х) = ]Ах -'6], где А — матрица 2 порядка т к и, 6 е Ех, считая, что множество Х имеет вид, описанныи в примерах 4.4.1- 4,4.6. Исследовать сходимость. 9 3. Метод проекции субградиента 1. В рзссыотренных выше градиентном методе и методе проекции градиента требовалась дифференцируемость минимизируемой функции. Однако для выпуклых функций указанные методы более естественно описать на языке субградиентов (см. 6 4.6).
А именна, пусть Х— выпуклое замкнутое множество из Еп, функция 7(х) выпукла на Х и ее субдифференциал дг"(х) непуст при всех х Е Х. Тогда для приближенного решения задачи можно предложить следующий итерационный метод: , ='Р (х — а„с„), ссь>0, сьЕд!(хь), 6=0,1».. где хо — некоторая точка из Х, а субградиент сь выбирается из дУ(хь) произвольным образом. Если при некотором й окажется, что ха+ с —— хс, то процесс (2) прекращается, так как в этом случае хс — решение задачи (1). В самом деле, при хс — — Рх(х — сс„сь) согласно теореме 4А.1 (х„— (х, — аьос), х — хь) = (сь, х — хь) ссс > 0 или (сь, х — хь) > 0 пРи всех х Е Х.
Отсюда нз теоремы 4.6.4 следует, что хь с Х,. Согласно замечанию 1 к теореме 4.6.4 точка х, е Х„ тогда и только тогда, когда х„ = = Р (х, — ас„), а > О, где с, — некоторый элемент субдьфференциала ду(х„). Отсюда ясно, что итерационный процесс (2) представляет собой метод поиска неподвижной точки операто а Рх(х — ), с Е дУ(х). В том случае, когда функция 7(х) дифференцируема во всех точках х е Х, метод (2) превращается в метод проекции грдкнента, а при Х = Е" — в градиентный метод. При выборе длины шага аь в (2) можно руководствоваться теми же соображениями, которые были о са ны выше в $1, 2, Мы здесь ограничимся рассмотрением случая, когда аь в (2) выбирается б, ли опииз условий аь>0, й=О,!,,,ц 2; а„=оо, 2 ~аз<~, (3) ь=о ь=о Как уже отмечалось в 6 1, в качестве ас можно взять ас = С(й+ 1), где С = сола! > О, !/2 < а < 1; например, аь = (й + 1) ~, й = 0,1, н каж.
Метод (2), (3) не гарантирует выполнения условия монотонности 7"(х ) > 7"(х ) на каж. дой итерации и сходится, вообще говоря, медленно, но если проекция точки на множестве Х н субграднент сс е ду(хь) находятся несложно, то этот метод очень прост для реализации на ЭВМ. Докажем его сходимость. Теорема !. Пусть Х вЂ” еьтуклое замкнутое множество иэ Е", функция У(х) определена и выпукла на некотором открытом выпуклом мнозхестве Ис, содержащем Х (например, Ис=Е").
Пусть |, >-оо, множество Х, точек минимума 7(х) на Х непуста и ограничено, и пусть, кроме того, знр зир [с! = А < оо. (4) ь е Х е ду(ь) Тогда последовательность(хь), опредгллемая условиями (2), (3), та „о 1'ш сс(хь) = уы 1ип р(х„, Х,) = О, (5) Доказательство, При сделанных предположениях функция 7"(х) непрерывна на Х субдиф~»еренциалы дг"(х) непусты, выпуклы, замкнуты и ограничены при всех х е Х (см, теоремы .2.15, 4.6.1, 4.6.2). Из ограниченности множества Х„и теоремы 4.2.17 следует, что множество М(С) = (х Е Х: 7(х) < С) ограничено при любом С ) ух Множество Х, выпукло и замкнуто в силу теоремы 4.2.1 и леммы 2.1.1.
Согласно определению 4.4 ! проекции точки на множество и теореме 4.4.2 имеем 2< р (хь, ы Х )=!хь ы Рх (хьщ)! < !хьчс Рх (хь)! =]Рх(хь-стась)-Рх(Рх (хь))! < !хь-аьсь — 'Рх (хь)]]=р~(хь, Х,)-1-аьз]с„[2-2аь(сь, х -'Рх (хь)) 2 ь('ь хь Рх(хь))(аьз[сь[2+рз(хь х ) р2(х ых), й=о,1 .„ Суммируя неРавенства (6) по й от 0 до некоторого з ) 1, с учетом условий (3), (4) „ 2а„(с,*„— р ( )) < А2 та- 2+ 2 ) <А 2.
аз+р (хо,Х)» В<со, э=!,2, (7) ь=о Даяее, по определению субгрвдиента имеем 0 (7(хь) — 7, =У(хь) — 7(Р» (хь)) ( (сь, хь — Р» (хь)), й =О, 1,... (8) Из (7),(8) следует, что числовой ряд Е а„(с„,х„- Рх (х„)) ь=о с неотрицательными членами сходится. Но согласно (3) име т~ — . П ем т~ аь--со, оэтомУ сходив=о ЕР!: 9 3. МЕТОД ПРОЕКЦИИ СУВГРЛДИВНТЛ 260 г . 5. мВтоды минимизлции ФУнкций многих пВРВмВнных 261 масть предыдущего ряда воаможна лишь при 1)ш (сь,хь — 'Р» (хь))=0. Это значит, что суще Ь СО ствуют номера й)<йг«... й„<... такие, что (9) (с„,,-Р (х„))=О «О Р' ° ° Р Тогда из (8) при й = й -Р сю получим !пп /(хь ) = /ю Кроме того, из (8), (9) следует, что г СО Р /(хь ) <</„+зир(сь, хь — Р» (хь )) = С <оо, т.
е. (хь ) ЕМ(С). Но М(С) ограничено, а (хь )— Р Р минимизирующая последовательность, поэтому из теоремы 2.1.2 имеем 1пп р(хь, Х,) = О. ) -РОО Р' Тем самым показано, что для подпоследовательности (хс ), удовлетворяющей условию (9), справедливы равенства (5). Опираясь на это, покажем, что равенства (5) имеют место для всей последовательности (хь). Иэ (3), (4), (6), (8) получаем, что рз(х,, Х ) < р (хь, Х ).~-оь~(сь)~ < р (хь,Х )+ оьл, й =0,1, Это значит, что числовая последовательность аь — — р (хс, Х,), й = О, 1, .. О удовлетворяет усло- 2 виям леммы 2.6.2, из которой следует существование предела 11ш р (хь, Х„).
Так как под- 2 Ь СО последовательность (рз(х„, Х,)) сходится к нулю, то этот предел может равняться лишь нулю. Следовательно, 9ш р(хь, Х,) =О. Покажем, что тогда 1)ш /(хь) =/,, По условию Ь СО Ь СО множество Х, ограничено. Тогда последовательность (х„), сходящаяся к Х„также ограничена. Возьмем любую предельную точну х, этой последовательности, Пусть (хь ) -Р х,, Так кзк Х, — замкнутое множество и йш р(хь, Х,) = р(х„Х„) = О, то х„е Х,. Л тогда 1)ш /(хь ) = /(х ) = / .
Это означает, что числовая последовательность (/(хь)) имеет един- СО ственнусо предельную точку, ревную /„т. е. 1)ш /(хь) =/,. Теорема 1 доказана. П Ь СО 3 а и е ч а н и е 1. В условии теоремы 1 предполагается выполнение условия (4). В том случае, когда Х ограничено, то, как следует из теоремы 4.6.5, условие (4) всегда выполняется. Заметим также, что в теореме 1 вместо (4) можно потребовать сходимость ряда ~„' оь )сь ! . 2 2 ь=о 3 а и е ч а н и е 2. Описанный выше метод проекции субградиента после некоторой модификации можно использовать для решения следующей задачи выпуклого программирования: /(Х) — Р)П11 ХЕХ=(ХЕЕ": ХЕХО, д (Х)<0, С=!,.,ОГП).
(10) Заметим, что система неравенств д((х) < О, с = 1,..От, равносильна одному неравенству д(х) < О, где д(х) = шах д((х), х Е Х. Кроме того, из выпуклости функций д((х), с = 1,... ) < с < ОР ..., Рп, на хо следует выпуклость д(х) на ха (см. теорему 4.2.7). поэтому задачу (10) можно переформулйровать в виде эквивалентной задачи /(х) О)п1; хЕ Х =(хЕХо, д(х) <0) татке являющейся задачей выпуклого программирования. Предположим, что субдифференциалы д/(х), дд(х) непусты при всех х Е Хо. Следуя (766), рассмотрим метод хь „( — — 'Р» (хь — оьсе), й = О, 1, .. ц хо Е Х(„ (12) где (оь) выбирается иэ условий о >О, )с =О, 1,, ~, "оь)+7 =ею, ~; паз <со, 0<'7 <1, (13) ь=о ь=а а субградиенты (сь) таковы, что сь е д/(хь) пРи д(хс) < оьт и сь е дд(хс) пРи д(хь) > оьт.
(14) Таким образом, метод (12)-(14) работает так: если ограничение д(х) < 0 при х = хь не нарушено или нарушено немного, то минимизируем функцию /(х), а если нарушение этого ограничения велико, то минимизируем функцию д(х). Если функции /(х), д(х) дифференцнруемы на Хо, то в (12), (14) вместо с„нужно брать соответствующие градиенты /'(хь) или д'(хс). В качестве последовательности (оь), удовлетворяющей условиям (13), можно взять, например, оь — — С(й+ 1) ", где С = соим > О, а число о таково, что 1/2 < о <(1+ 7) '. В частности, при сг = 3/5, Г = 1/2, С =1 получим о =(й+ 1) З/Э, й =О, 1,...
Теорем а 2. Пусть Хо — еьшухлог замкнутое множество из Е", функции/(х), д(х) определены и выпуклы па некотором открьипом выпуклом множестве Иг, содержагцем Хо (например, ИР= ЕО ). Пусть Д = (и1/(х) > — со, мнохсестео Х„точек минимума задачи (11) непусто, ограничено и, кроме тога, зир ьпр )с)=А <оо с е хс с е гг( ) о гг(,) Тогда для последовательности (хь), определлглсай условиями (12)-(14), справедливы рагепстга (5).
До каза т ел ь с те о. При выполнении условий теоремы функции /(х), д(х) непрерывны на Хе, субдифференциалы д/(х), дд(х) непусты, выпуклы, замкнуты и ограничены при всех х Е Хо (см. теоремы 4.2.15, 4.6.1, 4.6.2), а множество Х, выпукло и замкнуто (см. теорему 4.2.1 и лемму 2.1.1). Покажем, что множество М(С), Сз) = (х Е Хо( /(х) < С(, д(х) < Сз) ограничено при всех С( > )п1/(х), Сз >(п1д(х). В самом деле, М(/„О) = Х, ограничено по Хс с условию. Тогда по теореме 4.2.17 множество М(С), О) = (х: х Е Хо, д(х) < О, /(х) < С() ограничено при всех С) > ш1/(х). Теперь, фиксируя любое С), по той же теореме 4217 получаем »с ограниченность м(с(, сз) при каждом сэ >(п(д(х). Хс Нетрудно видеть, что неравенства (6), (7) сохраняют силу и для метода (12)-(14). Из (7) имеем схь(+ то( 7(сь, хь — Рх (хь)) ( В < со, г = 1, 2, (15) а=о Отсюда следует существование номеров й( < йг «...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
