Ф.П. Васильев - Методы решения экстремальных задач (1981) (1158203), страница 46
Текст из файла (страница 46)
Допустим, что мы выбрали один из таких методов — назовем его методом А — и построили последовательность (в„) ~ Ж'» такую, что 1ип Т»(и„) = Т». » о» По определению предела найдется конечный номер и», при котором Т»(п„„)(Т>"',+е>ь и следовательно, в (!) мсжно принять и»=п„». Заметим, однако, что с увеличением номера й свойства функции Т,(и), вообще говоря, ухудшаются, а задачу минимизации Т,(и) на %'» согласно (1) приходится решать со все более высокой точностью.
Поэтому число итераций и» метода А, необходимое для определения и»=п„, из (1), может оказаться слишком большим при больших й, и может даже случиться, что 1пп и»=+ со. Понятно, что это обстоятельство может создать определенные трудности при практической реализации метода стабилизации. Для преодоления возникающих здесь трудностей на практике часто поступают следующим образом: при каждом фиксированном й делают несколько шагов метода А применительно к функции Т,(и) и затем переходят к функции Т„,(я), применительно к которой снова делают несколько шагов метода А и т. д. Конечно, при таких действиях условие (1) вряд ли будет выполняться при всех й = 1, 2, ...
Однако если надлежащим образом согласовать параметры метода стабилизации с параметрами метода А или, как еще говорят, провести итеративную регуляризацию метода А, то на этом пути возможно получение минимизирующих последовательностей, регулярных в требуемой метрике. Мы здесь не будем подробнее останавливаться на принципе итеративной регулярнзации и его применениях к различным методам миними- 244 5 Р'(и) = У, 'р !йтс(и) )о-ся; '(и), != ! Р» (и) =,У', р !д7» (и) !!' сд,'» (и), !=! ияУо.
Будем считать, что погрешности в задании градиентов функций с (и), рй(и) таковы, что снах ( (,с" (и) — У» (и) !!, !! Р' (и) — Р', (и) Ц ( =8 (1+)и!!), не=(уо, (3) где 5».==0, (с=1, 2, ..., !пп 6„=0. Введем функцию Тихонова Т„(и) = з'» (сс)+ А»Р» (и) + а»!! и!»!2, и ен (I„(4) где А»)0, а»)0, )»=1, 2, ..., 1!ш А»=со, !!!па»=0, » са » Со а стабилизатором служит функция»с (и) =(и !о!2.
При сделанных предпол'жаннах функпия (4) дифференцируема, причем ее градиент имеет вид Т» (и) = с'» (и) + А,Р» (и) + а»и, и е- =Уо (5) 243 зации — по этим вопросам отсылаем читателя к работам [24 — 26, 58, 61, 65 — 67, 90, 97, 1! 8, 233! — и сразу же перей- дем к изложению итеративной регуляризации метода проекции градиента. 2. Пусть Уо — выпуклое замкнутое множество из гиль- бертова пространства Н, пусть функцни,/(сс), дс(и), ... ..., до(и) и их приближения У»(и), д!»(и), ..., и,»(и) определены и дифференцируемы на У„а множество У имеет внд У = (и: и ен У„с! (и) ( О, с=1, лс; лс(и)=0, с=сп+1, з).
(2) В качестве штрафных функций, как и выше, возьмем функции Я ! Р (и) = 'У', !д; (сс) !о, Р, (и) = 'У', /ф, (и) !о, !=1 с=! где ис'(и), дс»(и) определены формулами (8.5), (8.6). Будем рассматривать лишь случай р) 1. Тогда функции Р(и), Р,(и) дифференцируемы на Уо и их градиенты имесот вид Построим последовательность (о») по следующему правилу: ой+» Ри, (ий — ои»7'» (ий)), lг = 1, 2, ...; иг е= Но, (6) шах(!Г(и)1, !Р'(и)!)~Е»(!+!и!), иенУо, (7) Е,о=сапа( ° 0; множество (2) непусто, У =1п(,((и)) — со, и (/ = (и: и е= У,,( (и) = У ) ~ ((г; 2) функция Лагранжа (. (и, Л) = г' (и) + ~ ~Лгуг (и), 1 ив=Уй, ЛенЛо=(Л (Л„..., Л): Лг)0, ..., Л )О) на множестве(/,хЛо имеет седловуго точку (и, Л*) енУ,ьсЛ„ т, е.
Е,(ио, Л) =Л(и, Ло)(Ь(и, Л*) пРи всех иенУ», ЛяЛо; 3) погрешности в задании приближений дй(и), г7г»(и) для ерадиентов Г(и), уг'(и) удовлетворяют условиям (3); 4) последовательности (6»), (А»), (ай), (рй) из (3) — (6) таковы, что 6»эО, 0<А»-=.А»йг, ссй)0 6»)0, (с 1, 2, !пп 6» 1!ш А»'= 1!гп ай !пп рй » аа й оа » оа й ао = !1гп 6,А,ай '=-11гп А» "сс» '-О, г(=р(р — 1)-', й ао й ао 1пп р»А1а»' = (8) = 1гш (Айы — А»)а»'р»'= !ип !а»йг — ай/а»'6»' О. й со й оо где Ри, (и) — проекция точки о на множество Уо, 6» ) О, !пп ()й О.
Согласно теореме !.4.2 проекция Ри,(и) сущей оа ствует и определяется однозначно, так что последовательность (и») из (6) определится тотчас же, как только будут заданы Аго сс„, р„ (г = 1, 2, ... Оказывается, параметры б„, Аю а„ из (3) — (5) и длину шага р» метода проекции градиента (6) можно согласовать таким образом, что при определенных требованиях иа исходные данные последовательность (и») будет минимизирующей и будет сходиться по норме Н к »1-нормальному решению. А именно, справедлива Теорема 1. Пусть 1) функции У(и), дг(и), ... ..., д (и), ~й „,(и)!, ..., !д,(и)! выпоклы на выпуклом замкнутом множестве У~ из гильбертова пространства Н; градиенты функций У(и), аг(и) таковы, что Тогда последовательность (оь), определяемая из (6), сходится по норме Н к П-нормальному решению задачи минимизации У(и) на К Д о к аз а т ел ьство. Прежде всего заметим, что последовательности А„а,, б,, удовлетворяющие условиям (8), существуют.
Их, например, можно искать в виде А„=й" ", а„= й-и", р„=-я-иэ, где А, а, 8 — любые натуральные числа, удовлетворяющие системе неравенств 2сс-'+ ()-'+ А-' ( 1, а-'+ 2А-'( 8-', А ( (о — 1) а. Очевидно, что если сначала взять достаточно большим число р, затем А и, наконец, а, можно удовлетворить этой системе. В частности, при р= 2 можно взять А, = = йи', аь=(г-иь, рь=й-из, й=1„2, ... Остальные условия 1!п1 бь = 1(гп бьАьаь' = 0 из (8) указывают, какие требования предъявляются к погрешности задания градиентов в соответствии с неравенствами (3).
Лалее, из выпуклости и замкнутости множества (/, и выпуклости и непрерывности функций д;(и), 1=1, т, !у; (и) !, 1 = т+ 1, з, следует выпуклость и замкнутость множества У, а отсюда и из выпуклости и непрерывности /(и) тогда имеем выпуклость и замкнутость множества У . Поэтому сильно выпуклая функция й(и) =)и!4)2 на ~/, достигает своей нижней грани в единственной точке и,. Таким образом, й-нормальное решение задачи минимизации г (и) иа множестве У существует и единственно.
Из выпуклости д; (и), ! = 1, т, ! дс (и) !, 1= т-+ 1, э, следует выпуклость штрафной функции Р(и). Л для выпуклых дифференцируемых функций л'(и), Р (и) согласно теореме 1.2.1 имеем (г" (и) — Г(о), и — о)~0, (Р'(и) — Р'(о),и — о))0, и о~Уь. Поэтому для точной функции Тихонова Т„(и) = л" (и) + А,Р (и) +сс„) и )Я!2 при ка кдом и= 1, 2, ... получаем (Т„'(и) — Т„'(о), и — о) =(Г(и) — Г (о), и — о)+ +(Р'(и) — Р'(о), и — о)+а„(и — о, и — о)) )иь(и — о!,', и, о енУ,. (9) 247 Так как ад ~ О, то в силу теоремы 1.2.2 отсюда получаем сильную выпуклость функции Т,(и) на выпуклом замкнутом множестве Уд.
Тогда по теореме 1 3.8 существует, и притом единственная, точка ид такая, что идяУм Тд(ид)=!и!Т,(и), сс=1, 2 (10) и. Замечая, что множество (с', и фус.кции у(и), д,(и), 1с(и) удовлетворяют условиям 1), 2) леммы 8.2, и применяя теорему 8.2 при бд=тд= ад = О к последовательности (ид) из (10), получаем !пп (,ид — и, с=О. д Для величины (ид — и„~, где вд определяется условиями (6), имеем (пд — и, (,сод — ид!+!,'ид — и„', !с=!, 2, ... (11) Только что было показано, что последнее слагаемое стремится к нулю.
Поэтому для доказательства теоремы достаточно установить, что !пп "пд — ид !=О. д оз Обозначим Ьд =)ид — ид~!, Ь= 1, 2,, Покажем, что последовательность дсд = Ьд, й = 1, 2, ... удовлетворяет условиям леммы 2.3.6 из [4!. С этой целью заметим, что Ь„, =' ,пд„— ссд„!! ( (!пд„— ид'+(ид — ид„С, сс=1, 2, ... (12) Сначала оценим !'ид — и,„, . Напомним, что и„определяется из условия (10), которое в силу теоремы 1.2.5 равносильно неравенству (Тд(ид), и — ид))0, и= — У„сс=1, 2, ...
(13) В частности, взяв здесь и = ид„ ен сС„, получаем (14) (Тд(ид), ид,— ид))0, сс= 1, 2, Аналогично доказывается, что (Т;„(ид„), ид — и„,с) )О, сс=!, 2, ... (15) Кроме того, нз 1!си !ид — и„1=0 следует оценка д ю !!ид((!!ид — и,!+!и„(=-С„!с=1, 2, ...; (16) здесь и ниже через фф... будем обозначать положительные постоянные, не зависящие от сс. Тогда из (9) 248 с учетом неравенств (7), (14) — (16) имеем а» ! ивы — и» !» «(Т» (ид„) — Тд (и»), и»», — и») =.
«(Т;(и,д,), иды — и„)«(Т;(и,»д) — Т»„(и, ), и»ы — и,) = = (А» — А „») (Р' (и»,»), ид„— и») + +(ид — иды) (ад»м и»д, — и») «0 А» — Ам.,',(.(!+~!и»+, !)+ + ~ бах» — ад„~ ! идд» '),", и» „— и»1 « «С, (, 'А» — Ад„~+,'ад — ад», !) ~ и»ы — ид), илн, после деления на,и»„, — ид!им ! и„, — и»! «С, (~ Ад — А„, (а„'+ + ~ад — ад+,)а»'), й = 1, 2, ... (17) Теперь перейлем к оценке слагаемого !!од„ вЂ” ид! нз (12). Согласно теореме 1.4.2 !Ри,(и) — Ри,(и)!«(и — о! для всех и, о ~ Н, поэтому с учетом (6) имеем (оды — и» 1» = ! Ри (о» вЂ” ()»Т» (и»)) — Ри, (ид) (д « «! о» вЂ” (!»Т» (ид) ид )д = =(од — ид)д — 2рд(Т;,(о»), и» вЂ” и»)+ +Я(Т»(о»),», 1=1, 2, ...
(18) Заметим, что из выражения Тд(и) =,('(и)+ А,Р' (и) + -(- сд»и для градиента точно6 функция Тихонова, формулы (5) и неравенств (3) слелует оценка ~ Т» (и) — Т„'(и) ' «(6»+ А»6») (1+" ,и !) «С,6,А„(1+!и(), иенУм 1=1, 2, ... В частности, при и =од отсюда имеем 1Т;,(о») — Тд(о,)!«С,6,А,(!+)и„,'), 6=1, 2, ... (19) Кроче того, приняв в (13) и=и», приходим к неравенству (Т, '(и»), сд — и») ) О, (г = 1, 2, ... Стсюла и из неравенств (9), (19) получаем (Т» (о»), ид — и») = = (Тд (о„), с» — и») — (Т» (ид) — Т» (од), од — ид) ) .=» (Т»(и,) — Т»(и»), о» вЂ” ид) — С»6»А»(14,ид ) о» вЂ” и»,~= )ссд,,ид — и, — С,6„А„(1+ и»,);,ид — и»1, (20) 1 = 1, 2, 249 Лалее, из условия (7) и оценки (19) имеем ,,Т»(од)!»«((Т„'(о,) [+Сдб»А»(!+[од!))д« «(7»+ А»7»+ а»+ С»б»А») '(1+ ! од [)' « «С»А»(!+[о»))', 1=1, 2, ...
(21) Подставим оценки (20), (21) в (18): ! о»»» — и» !' = ) од — ц» 1' — 2а»дн» ( од — и» Р+ + 2(»»б» А» С, (1+; о» )); о» вЂ” и» ! + +Сф»А»»(1+)од!)д, Ь=1, 2, ... (22) Заметим, что в силу (! 6) 1+ [ с»1«1+ ! од — ид )+ ! и» ! « «=(о» вЂ” и»!+С»+1 и, кроме того, 2!од — ид!«! + + ! од — ид [д. Поэтому оценку (22) можно переписать в виде ~ ид+,— ид!д« «[1 — 2а»р»+ (р» б»А»+ ()»А») С»] ! од — ид )~д+ +С,(8»б»А»+8»А») = = (1 — 2а»р»-~- а»[)ду») ! о» вЂ” ид )»+ а»[)»уд, (23) Ь=1,2,..., где у»=С,(б»А,+р»А1)а„'- 0 при Ь-».со в силу условий (8).
Подстзвнм опенки (17), (23) в (!2) и, вспомнив обозначение Ьд=)о» вЂ” ид,, получим 0 «Ьд»» «((1 — 2а»()»+ а»!)»У») ЬД+ а»Р»У») н»+ + (! Ад — А»„! ад '+ ! а, — ад„! а»') Си Ь = 1, 2, ... Так как (а+ Ь)' = ад+ Ь'+ 2аЬ =-. ад + Ь'+ ада»8» + .(- Ьд(а»рд)-'=(1+а»р»)(а»-)-Ь»а,.'р,'), то возведя прелыдудцие неравенства в квалрат, будем иметь 0 «Ь»»д «(!+а»[!») (1 — 2афд+ а»1!»У») Ь»д+ + (1+ а»р») [а»[)»у»+ (! А» — Ад„~ а»'+ + (໠— ада !а»')'С а,'[)»''!« «Ь» [! — а»рд — 2а»рд + а»()дуд (1+ а»рд)! -!- +(1+а»Р») ~а»!)»У„+а»8» ~! ", »+"! + "", »м ~ ) Сф или О Ь1„«Ь»(1+а»()»р»-а»8»)+а»()»р„ /:=1, 2, гле рд)0 и рд-»-0 при л-»-оо в силу условий (8).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
