Ф.П. Васильев - Методы решения экстремальных задач (1125244), страница 51
Текст из файла (страница 51)
Предположим, что функции /(и), рй(и) ен С'(Н) и существует (Т;,(и))-' при каждом и ен Н, й=О, 1, ... Тогда итерационный процесс 166! р~ ! — — и» вЂ” (Т~ (о„))-' Т~ (и,), й = О, 1, ..., (5) 38! В ') !.4 (см. также Я 5.7, 5.8 из 14!), были рассмотрены метод Ньютона и метод с кубической скоростью сходимос|и, причем их сходимость была установлена для сильно выпуклых функций. Было также замечено, что эти методы, хотя и имеют высокий порядок сходимости, но сходятся, вообще говоря, лишь при выборе лостаточно хорошего начального приближения. Покажем, ч|о можно провести такую итеративную регуляризапию метода Ньютона (см. 4 1.4, п. 6) и метода с кубической скоростью сходимости (см.
~ 1.4, п. 7), которая для выпуклых задач при обычных ограничениях гарантирует сходимость этих методов при любом выборе начального приближения. Будем рассматривать задачу минимизации функции у(и) на множестве У=(и: ие— : Н, д;(и)(0, 1=1, т! д;(и)=0, (=си+1, з(, (1) 2) функция Лагранзса У (и, Л) = ((и)+ У', Л,у, (и) на г= ! множсспгве НхЛ«,Л«=(Л=(Л„..., Л ): Л,= О,..., Л„, =О) имееп! седловую точку (о„, Л*) ~ Н х Л„в следуюя("м слгысле! Е.
(о„, Л) = ?. (о„Л«): Е, (и, Л'), и ен Н, Л ~ Л«; 3) для нормального решения и задачи минимизации ,l(гг) на У (т. е. и я(l„, и„!!=-(п(!и~) ичесстнааприори, ная оценк а ( и, ,'! == г(; 4) шсловые пос.гедовательногти (а»), (А„) таковы, что Игп А, = Ип! Игп а»=0, » э а»А'г-' = +ос, (8) г)= оИо — 1) ', — =-. 2, А,== А! А» А», — А» 1 (9) а»м б« 1- — — "(2, 1 и»,, — .!) А» ! ! (л» ! — л») л»,! г (10) а'„! зг«гл ' а', ' зг.г.„~ (! -1- Я) ' где )гг = Гам+ 2 ( Л* ,'«г)-гР!-«виР а»'А! — «1ггг ! Л* «вЂ” » (Л,".,«, а 1 — ар!излагал'е ф:гксирогганног час!о, гиииь =! бы (ра96 (например, можно !зять (=96); 5) начальное приближение о, для последовательности (о»), определяемой (5), и числа А„, а, таковы, что А«?.11 Т„'(о,) ( ( а,'. (1!) Тогда Игп !!о» вЂ” и«(=0 с некоторым начальным приближением г« ~ Н представляет собой итеративную регуляризапию метода Ньютона (ср. с пропессом (1.4.39)).
Справедлива Теорем а 1. Пусть !) функцгггг .?(и), дг(и), г =1, в, принадл жат С' (Н), функции ) (и), у! (и), ! = 1, т, !д! (и) !, ! =т-1 1, з, выпуклы на Н, выполняготся условия (2) и, кро.ие того, ) Р'(и) !== 1. (1+(и!), и е= Н, Е.« — — сапа(=-0, (6) пик ( .)" (и) †.I" (о) г, !,Р" (и) — Р" (о)!!) ~Ь! и — о!', и, о в=Н, б==сопа1зьО; (?) Доказательство. При сделанных предположениях функция Т,(и) ~С»(Н), сильно выпукла на Н и (Т»(о)и, и)~и»[и!», и, о ~Н, А=О, 1,, (12) Покажем, что тогда существует обратный оператор (Т„'(о))-', причем !(Т»(о))»!(с»»', о~Н, й=О, 1, ...
(13) С этой целью возьмем произвольную точку»о»вЂ” : Н и рассмотрим функцию 6»(и) = 2 '(Т»(о) и, и) — (»о, и), и»= Н. Так как 6„"(и)=Т»(о), то из (12) и теоремы 1.2.2 следует сильная выпуклость 6, (и) на Н. В силу теоремы 1.3.8 тогда 6»(и) достигает на Н своей нижней грани в единственной точке гм причем по теореме 1.2.5 для этого необходимо и достаточно, чтобы 6»(г») = Т,"(о) г»вЂ” — »о = О.
Это значит, что уравнение Т„"(о) и =щ при каждом и» ен Н имеет, и притом единственное, решение и = г», что равносильно существованию о ратного оператора (Т» (о))'. Подставим в (!2) и=(Т" (о))-'»о. Получим и» (Т»(о))»»о,» --(ш, (Т»(о))»»о):--'»о °, (Т»(о)) ' »ой»о ~Н. Отсюда имеем ЦТ;(о))-'»о)~и»1!»о при всех щя Н, что равносильно опенке (!3). Таким образом, последовательность [о,), определяемая условиями (5), существует. )-!аряду с (о,) введем последовательновть (и„), которая однозначно определяется условием Т,(и») = 1п1 Т,(и) или Т» (и,) = О, й = О, 1, ... и Из теоремы 8.2 при б,=т»=е»=О, Н» — — Н вытекает )пп ! и» вЂ” и„.
'! = О, где и „вЂ” нормальное решение задачи минимизации /(и) на У; существование и единственность и, показаны при доказательстве теоремы 9.1. Из неравенства ' о„— и„!, = ! о, — и» )+ ! и„— и, ! тогда следует, что нам осталось установить равенство 1(гп !о» вЂ” и»[ = О. Введем числовую последовательность а» = ,'! Т;(о,)1, lг=О, 1, ... Из определения (4) функции Т,(и) с учетом условия (6) имеем а»,, =,',Т».»» (о»»») 1---.)Т»(о»,») ,'+ ~ Т»+ ~ (о»„) — Т»(о»»») !»-. (;!Т»(о»„) +(и» вЂ” а„„) о»„'!+(А»„— А») 1!Р'(о»»»),.'!== «',Т»(о» ), +[с»» — с»»ы+Е»(А»+ — А»)[ (о»»[+ + йо(А»»» А») (14) Из сильной выпуклости Т» (и) следует, что и„! ,— и» !' ( :.
(Т» (о»»») — Т; (и,), — и,, '= (Т, '(о„„), о»» — и„). 288 Отсюда имеем (о„,— и»!()Т»(о»,»))/а». Кроме того, из оценки (8.28) при е» = 8» = ъ» = В» = р» = О, 1» (и) =!и !»?2 имеем )и,((Р. Тогда )о»»» ~~~ и»~+" о„,— и»1(Я+1Т»(о»»,) 1!а». Подставим эту оценку в (14) и с учетом неравенства 2໠— а»м-)-Т,„(А»,,» — А») ( 4а„„вытекающего из условий (9), получим а»м ( 4а»»»а»',, Т» (о»»») !+ + 1»(໠— а»+»)+Т о (1+ Я) (А»»» — А») (15) Далее Т» (о»„,) = Т( (о») + Т» (о»+ В» (о»,» — о»)) (о»,» — о»)= =!Т» (о») — Т»(о»+ В»(о»»» — о»)) !(Т»(о»))-'Т»(о»), 0<В»~1.
Из условия (?) и оценки (!3) тогда имеем ! Т» (о»»»),, < 1. (1+ А„))о»»» — о,)а„'а» (2ЕА»а»а„'. Подставив это неравенство в (15), с учетом условий (!0) получим следующее рекуррентное соотношение для последовательности (и»): а»»» ~ 8ЕА»а»а»»»а»»+ (2?3) Щ-'а»»»А».'„й = О, 1, ... Для последовательности с» = а»а»', й = О, 1, ..., тогда имеем с»»» ( 8(А»с»а,'+(2!3) (?1)-»а»»»Аь„'„'и = О, 1,, (16) Докажем по индукции, что с»(а»А» (ЕО-», й=О, 1, ... (17) При й=О справедливость оценки (!7) следует из условия (1!).
Пусть (17) верно для некоторого й~О. Тогда из (16) имеем с»», ( 81 А»а»»А»» (1,»)-»а»'+ (2?3) (?,()-»а»„А»-'„, = = а»»»А»'» (И) '18 (а»!а»»») (А»»»(А») (-»+ 2)3! ~ ~ а»„А».', (Б)-» (32»'-»+ 2(3) ~ а„„А„-,', (?.О-» Оленка (17) доказана. Наконец, из а»!о — и„,,'-(Т;(о»), о» вЂ” и») ~ а»)о» вЂ” и» ( имеем (о» вЂ” и„(= а,а,' = с, = а»А,' х х(Ы)-»- 0 при й-~с», что и требовалось. Теперь обсудим вопрос о возможности выбора (а»), (А»), о„удовлетворяющих условиям теоремы 1.
Если вначале выбрать (а»), »А») из условии (8) — (1Ь), то для выполнения условия (1!) нужно взять такую точку о„ для которой величина )Т»(о»)1 мала. Это значит, что для 284 выбора начального приближения нужно поточнее решить задачу минимизапии Т4(и) на Н как задачу первого типа. Такой подход к выбору начального приближения вполне может быть использовав на практике. Однако в рассматриваемом методе, оказывается, иа самом деле можно взять в качестве начальной любую точку свен Н, а затем, зная о,, задать последовательности (а4), (А,) так, чтобы удовлетворить всем условиям (8) — (11) теоремы. Можно, например, принять а4=В(й-1-1) ", А4=()4-)-1)4, й=О, 1,, (18) где положительные числа А, В, 44 определяются условиями А+44«1/2, а<(4! — 1) А =(р — 1)-'А, р>2, (19) В.=-п4ах(1.4', 9ЕЫ' (818'Р ~Х4 )4~) 'р' 4)п', (36(Ч 4Р (1+ 4Р))"' (72ЬЧ4Р) Х')'47 'р' ')'", 2В() п4); (26!) у'(о4) + р' (п4) ))н') (20) а ( — какое-либо фиксированное число, 1)96.
Нетрудно проверить, что при таком выборе (и4), (А,) все условия (8) и первые три условия (9) выполняются. Далее, поскольку (Ахм — А4) а4+4 — — В-' !()4+ 2)4 — (й -(- 1)")(л+ 2)'" = =. В-'А ((4+ ! + 8) 4 ' (й + 2)" «В-"А )(й+ 2)1(й + 1)14-4 Х х (й+ 2) ""-' «В-', где 0 < 8 < 1, то последнее из условий (9) будет выполняться, если В)Е4. Рассмотрим условия (!0), (!1). Заметим, что для последовательностей (18) зир х4 'А4 '=В ', и поэтому К =- 4) ! = (414+ 2 ~ ) * )4 д-'р'-4В-')н4.
Поскольку (а4 — а4 4) А4„а4,',« «3)(2В), то первое из условий (10) приводит к неравенству В:- (9/2) АЧг = (9!2) 7 ((гР+ 2) ) 4)4д-'р' 4В-')'" или Вз ) (81)4) 4.4(44(4В+ (81!2) 84(4, Х* )4 г(-'Р*-4. Это неРавеиство заведомо будет выполнено, если В ~ шах (94.Ы; (81(.4(4',).4 Рд 'рг-х)п4). Аналогично, (444 — а„4) Аь„а4,', « «В-', и второе из условий (10) приведет к неравенству В4) ЫЛ4((! +г!), нли В4= 9ЕЧ4Р(1+Я)4.
Поскольку (1+)4)4«2(1+)14), то предыдупгее неравенство можно заменить более сильным неравенством В4=.-18(.Ч4Р(1+ )44), откуда следует В4) 18(4ЕР(1+ гР)В+ 3644ЦР~14(4д 'р' 4. Это неравенство заведомо удовлетворяется, если В.~ гпах ((364.4ЦР (1+ У))и4; (72ЬЧ4Р) Х4 !4 ц- р4-4)п ), 285 Наконец, условие (11) с учетом равенств А, = 1, а„= В приводит к неравенству Е( ~, /' (оь) + Р' (оь) 1+ ВЕЛ( о»1~ В', которое выполняется, например, при В ==.
гпах (2Е.П)о,~1; (2Е.) ! Г (оь)+Р'(о,) )'",'. Собрав вместе все получившиеся ограничения на В, придем к неравенству (20). Трсбуемые теоремой последовательности,'а„), (А») построены. Наконец, нужно заметить, что условием (20) для выбора В практически трудно пользоваться, так как постоЯнные (., Е м с(, ~),*)е далеко не всегда известны. Тем не менее предложенная выше итеративная регуляризация метода Ньютона указывает на принципиальную возможность устранения одного из существенных недостатков этого метода, заключающегося в треоовании хорошего выбора начального приближения, и намечает пути для этого. Важно также заметить, что в отличие от 25.7 из 14) вместо сильной выпуклости от фу~ кции l (и) в теореме 1 требуется лишь выпуклость.
2. Кратко остановимся на случае ()=Н, когда в (!) ограничения д, (и) ==. О, дг(и) =0 отсутствуют. Тогда функция Тихонова имеет вид Т,(и) =/(и)+а»>~и,,'Е2, и ~ Н, И= — О, 1, ... (2!) Теорем а 2. Нустьг 1) функция,Е (и) выпукла на Н, У(и) е:-С'(Н), выполняются услогтя (2) при (/=ЕЕ и 1.Е" (и) — /" (о) '=.==) ';,и — о,', и, и ~ ЕЕ, Е.=сонэ! ~0; 2) для нормального решения и„задачи л»инимизации ,Е(и) на Н известна априорная о»(енка и„~-.:--»(; 3) числовая последовательность (ь») такова, что !цп а»=0, и»)0, 1(а»а»,', ~ »»» (пцп(2; 1+(2Щ 'а»»»), И=О, 1, где ! — фиксированное число, 1) 12; 4) начальное приближение о, для последовательности (о»), определяемол из (5), (21), и число иь пшкова, что В! ! /' (оь) + аьо»1( а».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
