Ф.П. Васильев - Методы решения экстремальных задач (1125244), страница 16
Текст из файла (страница 16)
Отсюда при а-д.+сю получим равенство (26). Пусть теперь У(и) выпукла на ЕУ. Согласно теореме 3.6 тогда ЕУ, Ф ОУ. Возьмем произвольную точку и, ~ е-=(Уд. Из теоремы 2.1 и условия (20) имеем 0(ил= У(ил) — У(и„) «= (/'(и„), ид — и„'; =- = — 1д(ил) ( —,Уд(йд) =( Ул(йд) (, )о=О, 1, ... (30) Отсюда и из равенства (26) следует, что (ид) — миннмизн- руюгцая последовательность. Согласно теореме 3.6 тогда (ид) слабо сходится к ЕУ,, Докажем оценку (27).
Так как Уд(йл)-о-0 прн й — со, то найдетсЯ номеР й, такой, что 0(Ул= ~ Хд(йл) ~У(Ег(о) ( (! при всех Уо=»)го. Тогда максимальное значение функ- ции а~ lд(йд) / — аоидЕУ2 переменной а при — оо (а< (+оо, которое достигается при а=ум будет совпадать с максимальным значением этой функции на отрезке 0( (и( 1 прп всех Уо) ио. Поэтому, полагая в оценке (28) а=у„ получим ид — ад „= о' (и,) — У (идол) ~ ! о'л (йд) 1дУ(2ЕУ(д), й =- Уго. 8! Отсюда и из неравенств (30) следуст ал — а„,~аЦ2ЙР), сс~Ао. Остается применить лемму 2.3.4 из (4) и убедиться в справедливости оценки (27).
Последнее утверждение теоремы для сильно выпуклых функций следует из оценки (27) и неравенства хссс,— и„:,' — 1(ис) — 1(и„), /с=О, 1,... Заметим, что описание метода условного градиента и теорема 6 сохраняют силу и в том случае, когда У вЂ” выпуклое замкнутое ограниченное множество из рефлексивного банахова пространства. 4. Метод возможных направлений может применяться для прнблси>кенцого решения задачи 1(и)- (п1; ива(1=(иенВ: а,(и)(0, с=1, т), (31) где  — банахово простоанство, 1(и), дс (и), ..., д„, (сс) еи ~С>(В) Для описания этого метода нам понадобятся следующие два понятия.
О п р е д е л е н и е 2. Пусть У вЂ” некоторое множество из В и ияли. Направление е я В, ечиО, называется возможным в точке и, если существует число С,)0 таксе, что и + Се ен (1 и р н всех с, О ( С ( (,. Определение 3. Направление е~В, е~О, называется возможным направлением убывания функции 1 (и) в точке сс на множестве У, если е — возможное направление в точке и и, кроме того, 1(и+(е) <1(сс) при всех с, 0< (<(с, ГдЕ 0<(ск=.йл Метод возможных направлений заключается в следующем. Пусть и, ен У, е, ) 0 — некоторое начальное прибли>кение.
Допустим, что )с-е приближение (иы е„), ив(1, е,)0 прп каком-то сс)0 уже известно. Определим множество номеров 1с = (сй 1 ( с < т, — ес ( дс (и,) ( 0) н в пространстве переменных г=(е, о) ен В>сЕс рассмот- рим вспомогательную задачу о-~)п1; г=(е, о) ~(Г,=>с(е, о): (1'(ис), е)(о, (д,'(и,), е) =.о, с ~1в', 1'е1(1). (32) Множество %'„вьспукло, замкнуто и ограничено, поэтому если В является рефлексивным банзховыч пространством, 82 то согласно теореме 3.6 задача (32) имеет решение. Пусть (е» од) — решение задачи (32), т.
е. (е„од) ы )!Р» и о»=рп(о. Так как г=(0, 0) а=К», то ясно, что п»«0. Имеются две возможности: 1) од « — ед. Тогда направление е» Ф 0 является возможным направлением убывания функнии р'(и) в точке и» на множестве (.Р. Полагаем и»„= и»+а»ем 0 < ссд «р»; еды — — ед, (33) где Р»=зпр(сс: ид+(едеп(р', 0«( =а))0. 2) — ед(од =.О. Тогда полагаем ид„=и», едрр=аед, 0<а<1, где а — параметр метода, и снова переходим к рассмотрению задачи (32) с заменой множества (» на множество )„,,=-(Е 1«. р'«т, — е»„«ир(и») «О).
Величина а» в (ЗЗ) может выбираться из условий: 1) )д(а») = )п( )д(сс) =)»„где )д(а) = )(и»+аед). »(а(ад На практике это условие можно реализовать приближенно в следующем смысле: 1д(а»)«1»,+6», 6»)0, '~~ 6»(со, д=» или )»(ад)«(1 — Лд) )(ид)+Л»7»„, 0<Л«Лд«1. 2) Можно задать а»=!)», проверить условие монотонности: ) (и»»р) ( ) (ид), а затем при необходимости дробить а„до тех пор, пока не выполнится условие монотонности.
3) Если р'(и) ~ С' ' ((р) и константа Липшица Е для ,р" (и) известна, то в (33) можно принять ссд=пп)п(()»', !од! Ц, 4) Возможен выбор а» из условия У (ид) —,1 (и, +а,е») =-- еа»,' о» !, 0 (е (1)2; для определения такого а» сначала можно положить ад= !)д, а затем при необходимости дробить эту величину. 83 Заметим, что задача (32) далеко не всегда просто решается.
Поэтому методом возможных направлений пользуются для решения лишь таких задач (31), в которых решение вспомогательных задач (32) может быть легко найдено. Предлагаем читателю самостоятельно исследовать сходимость этого метода и рассмотреть, в частности, возможность обобщения теоремы 5.5.2 из 14)на случай банаховых пространств. 5. Метод сопряженных направлений применяют для решения задачи / (и) -э(п1; и е= Н, где Н вЂ” гильбертово пространство, ) (и) ен С'(Н). Зтот метод заключается в построении последовательности (и») по правилу и»„=и» вЂ” а»ры Ь=О, 1, ", (34) где ро = Г (ио), р» = .)'(и») — 6»р»-ь й = 1, 2, ..., (35) величина Р» определяется по одной из формул Р = (Г (и ), /' (и ,) — э" (и )) ) Г (и он)>-', или (1»= — ) У'(и„)10~ У'(и»,) 1-0, а а„в (34) находят из условия )» (а») = !п1 )» (а), )» (а) = / (и» вЂ” ар„), а ) О.
(36) а')о Как показывает практика, погрешности, неизбежно появляющиеся при определении а, из условия (36), могут привести к тому, что векторы (р») из (35) перестают указывать направление убывания функции и сходимость метода может нарушиться. Чтобы бороться с этим явлением, метод сопряженных градиентов время от времени обновляют, полагая в (35) (1»=0. В отличие от конечномерных пространств (см.
с 5.6 из 141), в гнльбертовых пространствах нельзя ожидать, что точку минимума сильно выпуклой квадратичной функции ) (и) = - - (Аи, и) — (Ь, и), и ен Н, А ~ Х (Н -+ Н), Ь ен Н, 84 удастся найти за конечное число шагов метода сопряженных градиентов. Предлагаем читателю самостоятельно сформулировать и доказать аналог теоремы 5.6.1 из [41 для гильбертовых пространств, а также рассмотреть возможность при-. менения метода сопряженных градиентов к задаче (1) — (3).
6. Метод Ньютона может быть использован для решения задачи !п(; и и, где У вЂ” выпуклое замкнутое множество пз банахова пространства В, / (и) еи С' (Ц. Зтот метод заключается в построении последовательности (и») по следующему правилу: по известному А-му приближению и» ~ (/ находят вспомогательное приближение й, еи(7 из условия (» (и») = )п! .)» (и), (37) где ,1»(и) =(('(и»), и — и»)+ „— (У" (и,) (и — и»), и — и,), и — и, н затем полагают и»„= и» -(- а» (й» вЂ” и„), О ( а» ( 1.
(38) В частности, если У=В, то в точке минимума функнии ,(»(и) ее производная У;(и) обращается в нуль, т. е. 1» (й,) = 7' (и») + 7" (и,) (и» вЂ” и») = О, Если оператор ("(и») имеет обратный оператор (У" (и»))-', то отсюда имеем и» = и» вЂ” (Х" (и»))-' У' (и,). Подставляя это выражение для и» в (38), получим и,„,=и» вЂ” а»(Г'(и»))-'У'(и»), й=О, 1..., (39) Таким образом, при (/=В метод (37), (38) представляет собой широко известный метод Ньютона для решения операторных уравнений (в данном случае уравнения .У (и) =0).
Существуют различные способы выбора величины а, в (38). Приведем некоторые из них: 1) в (38) часто полагают а»=1, А=О, 1,, В этом случае прн У=В нз (39) имеем и„„=и» вЂ” ()" (и»))-'('(и»), А=О, 1, ..., — это классический вариант метода Ньютона решения уравнения У' (и) =О. 2) В качестве яз в (38) можно принять а,=Л", где (а — минимальный среди номеров 1) О, удовлетворяющих условию 7 (и,) — 7 (их+ Л' (и, — иа)) ) аЛ' / Уз (и,) /, где Л, е — параметры метода, 0<Л; а <1. 3) Возможен выбор а, в (38) из условий )~(сх~) = ппп 1,(а), ~,(а) =У(и„+я(и~ — и,)).
0<а(! 4) Иногда полагают а„= 1, проверяют условие монотонности: l (и„„) < У (и„), а затем при необходимости дробят аа до тех пор, пока не выполнится условие монотонности. Метод Ньютона обычно применяют в тех случаях, когда вычисление производных ('(и), l (и) не представляет особых трудностей и вспомогательная задача (37) решается достаточно просто.
Предлагаем читателю самостоятельно сформулировать и доказать аналоги теорем 5.7.1 — 5.7.3 из 141 о сходи- мости метода Ньютона для задач минимизапии в банаховых пространствах. Достоинством метода Ньютона является высокая скорость сходнмости. Однако этот метод весьма чувствителен к выбору начально приближения иэ — если точка и, далека от искомой точки минимума, то метод может не сходиться. 7. Метод с кубической скоростью сходнмости, изложенный в З 5.8 пз [4) (см. также 12231), может быть применен для решения задачи у (и) -э !п1; и я В, где  — банахово пространство, 7(и) енС'(В).
Для описания этого метода нам понадобится понятие разделенной разности для градиента. О п р е д е л е н и е 4. Пусть ./ (и) ен С' (В). Разделенной разностью градиента 7'(и) называется линейный симметричный оператор Г (и, о), действующий из В в В* и такой, что У' (и, о) (и — о) = Х' (и) — У' (о) (40) при всех и, вен В. Заметим, что равенство МО), вообще говоря, неоднозначно определяет оператор ('(и, о) яЖ(В-~В*).
Мы 86 будем дополнительно к равенству (40) еще требовать, чтобы для функций У(и) ен С'(В) оператор Г (и, о) удовлетворял условию г'(и, о)= /" (и)+е(и, о), и, оенВ, (41) где ~,'е(и, о),",— 0 при ~ и — о,-~О. Пример разделенной разности для градиента функции конечногб числа переменных, удовлетворяющей условиям (40), (41), был приведен в 4 5.8 14]. Предположим, что функция У(и) ен С'(В) такова, что разделенная разность У'(и, о) при всех и, о енВ существует и, кроме того, имеет обратный оператор (Г (и, о))-'. Тогда для минимизации функции l (и) на В можно предложить следующий двухшаговый итерационный процесс: й„=и„— Гмр(и,), и„„=да — Г,У'(ир), й=О, 1, ..., (42) где Г~=(Г(и„, их — 5„Г(и„)))-', ()ь — параметр метода, ()а~О.
Предлагаем читателю самостоятельно сформулировать и доказать аналог теоремы 5.8.1 из 14! для случая, когда В= — Н вЂ” гильбертово пространство, и убедиться, что при достаточно хорошем выооре начального приближения иа для сильно выпуклых функций метод (42) имеет кубиче- скую скорость сходимости. 8. Метод штрафных функций может быть применен для решения задачи У (и) -+.1п(; и ен У, (43) Сl=-(и~(У,: д;(и)(0, (=Ъ, т; д;(и)=0, 1=-т+1, з), (44) где Н,— заданное множество из банахова пространства В, функции у(и), д, (и), ..., д,(и) определены на (l,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
