Ф.П. Васильев - Методы решения экстремальных задач (1981) (1158203), страница 43
Текст из файла (страница 43)
Неравенство »го», (17) доказано. Далее, из той же цепочки неравенств (27) следует, что 0 ~ А»Р (и») ( ~ Лс' ~ д) (и») + а»й„+ а»р» (1+ й „) + 1=1 +е»+(а»р»+ 2! р» ~»В») (1+ й (и»)) Ь)йо (29) » Отсюда, используя известное неравенство (11! ~~ ~а;Ь, ~~ 1=1 ир ,Чо а(~ )и») ) [~ ~ЬН ), р)1, ц) 1, ц-'+В-'=1, и ~с=1 ! ц=~ уже доказанную оценку (28), имеем ,о» Оа=А»Р(и») ~('), '.~д',, (и»),»~ ~Л* »+а»С,+г» =,Л" , '(Р(и„))о»+а С,+е», /г))со, си» где )Л" ~»= ~ Л)!») Сс= зцр [йо+р»(1+й )+ + (р„+ 2()»о ', В»а»') (1+й, + енр у»Л.
Если обозначить »~». г»=(Р(и»))и», то последнее неравенство можно переписать в виде 0(А»г»»() Л*) г,+С,а,+еь или О ( г»о ( г»Ь»+ дь й ~ йо (30) где Ь»= ~ Ло)о А»', с(» =(С а„+»») А»'. Из (30) и леммы 2.3.1! из )4) имеем 0 ( Р (и») ( г»1» = Ь»» + Щ = = ) Л* )» "» ' + с) (сс С, + е») А» 1 -1- 0 при я-д-оо. Соотношение (18) лля случая р) 1 доказано. Если же р=1, то (29) можно переписать в виде 0 ( А,Р (и,) < гпах ( Ло ! Р (и,) + С,ад+ е», Я) й,, 1 <д(д Учитывая, что Ад) шах /Л7~ прн всех й)й„отсюда 1(д(5 имеем 0<Р(и„) <(С а»+е,)(А» — шах ~Л; ~)-'-+О 1(1(я при й — ~со.
Соотношение (18) для случая р=1 также доказано. Предлагаем читателю убедиться в том, что на самом деле доказано более сильное утверждение: 0 < ~А Р(и»)<сопз! (А» о+ад+в») пРи Р)1 и 0~ <А Р(ид)<сопя! (а»+ед) при р=!. )Талее, из неравенства (22) при и=иден (»о» с учетом оценки (28) имеем гпах( шах й» (и,); шах (й~ (и»)()( ь<у<д д»! <1(~ <20»(1+»»»+у») й)йо При й-эоо отсюда получим соотношения (19).
Осталось доказать неравенство (16). Снова обращаясь к цепочке неравенств (27), имеем 1 (ид) + А,Р (и,) ( < 1„+ад(»1 „+ рд (1+ Й„)+рд (1+ д» (и,))1+ е» ( < 1»+ С,ад+ ем й == йо Так как А,Р(и») ~О, то отсюда следует оценка 1(и») ~ <1»+()д, /г= ао, где р»=Сдад+е»-д-0 при )е — ~ж. Неравенство (18) также доказано. Теперь, чтобы убедиться в справедливости всех утверждений теоремы 1, остается обратиться к лемме 1 или лемме 2. 6. Отдельно остановимся на случае, когда все ограничения тйпа равенств и неравенств нз (1) учитываются с помощью штрафных функций. А именно, пусть (1 = (и: и ен ()„д; (и) < О, 1= 1, и; д, (и) = О, 1 = и+ 1 я). (31) Возьмем какой-либо стабилизатор 1! (и), и ен (7я — (Лм задачи минимизации функции 1(и) на множестве (31).
Пусть, по-прежнему, 1»(и), ддд(и), »1»(и), й= 1, 2, ...,— приближения функций 1(и), й;(и), »1(и), а штрафные функции Р (и), Р» (и) определяются посредством формул 231 (4) — (6). Составим функцию Тихонова Т»(и) = /» (и) + А,Р, (и) + а»!г» (и), и я (/!!, я = 1, 2, ..., и рассматривая задачу минимизапии Т, (и) пг множестве (/! как задачу первого типа, с помощью какого-либо ме- тода минимизации определим точку ид из условий Т» = !п( Т,(и/~Т,(ид) (Т*,+ею и, я (/а, (32) иа где е,) О, У=1, 2, ..., !!гп е„=О.
Зад»етим, что если нижняя грань Т„(и) на (/а достигается хотя бы в одной точке и», то в (32) не исключается возможность ед=О. Справедлива Т е о р е м а 2. Пусть; 1) выполнены условия 1), 2) леммы ! или леммы 2; 2) функция Лагранжа 1. (и, Л) = / (и) + .У, 'Л»у! (и), и ~ !=1 я (/ы Л я Л = ((Л„Л,..., Л ):Л ец Е', Л, ) О, ..., Л ) О) имеет седловую точку (и„Л*) ~ (/о кЛо, т. е. Е (и„, Л) = Е (и„„Л») = Е (и, Л*), и ~ (/о, Л е= Ло! (33) 3) при к!женньсе значения /» (и), дм (и), »л» (и) финк- ций /(и), д,(и), 11(и) на (/я удовлетворяют неравенсгп- кам (7), (8,, (10); 4) пас!еда»отел»ности (б»), (ч»), (а»), )А»), (ед) та- ковы, что ь»)0, ч»)0, а»)0, А»)0, ед)0, й=!, 2,...,зцрч»(1, 1!пт(Ь»+о +а,+е,+Ад')=О,!ипб»А,а„'= > !»-сс » оэ !цп е»а„' =О,!(гп Ау-!а»=со, где д =р(р — 1)-' (при р=! последнее равенство не нужно). Тогда послгдовательность (ид), опргделяемая гсловиями (32), су»цес!пвует, минимизирует функцию ./(и) на мно- жестве (31), р-регулярна и р-сходится к множеству (/*а.
Если, кроме того, »1 (и) р-полунепрерьсвна снизу, то Пгп»1 (и,) = »1», !!пз р(и», 1/„„)= — О, где (/„„=(и: и ен (lа, » о» д со »л (и) = (п!»г(и) = »ло ) — лтожестло Сьнорлтльных оетений о*а Доказательство этой теоремы проводится с использо- ванием леммы 1 или лед!л»ы 2 и дословным повзоречнем доказательсзва теоремы 1 при й/(и)=й/д(и)=0, р,=О, ! = 1, г; Од = О, /е = 1, 2, 232 6. Проиллюстрируем возможность применения описанного выше метода Тихонова и теорем 1, 2 к некоторым классам некорректных задач минимизапии, П р и м е р 5. Рассмотрим задачу линейного программирования: минимизировать функцию,/(и) = (с, и) на м!южешве 1/=(и=(и', ..., и"): и е= Е", и!звО, /~ /, (а,, и) — Ь,(0, !'=1, т; !а„и) — Ь, =О, ! =т+ 1, а!,, где с, а,, ..., а,— некоторы.
векторы из евклидова прост: аиства Е", Ь,, ..., Ь, — некоторые числа, ! — заданное множество индексов /, 1(! == и. Предполо>кнм, что (/~ чь ф и эта задача имеет хотя бы одно решение, т. е. ./„= !п((с, и)) — сю, (/ =(и: ив=(/, ./(и) =,!„) =~ ф. и Тогда согласно геореме 4.8.4 из 141 функция Лагранжа 5 !, (и, )) =(с, и)+ 2,')ч ((а„и) — Ь!) на (/» х Л, имеет седло!=! аую точку в с»хы ле неравенств (33); здесь 1/„=',и: и св ~Е", и/>О, !'я!), Л»=(Х=(Л», ..., /!»): ЛяЕ', Х»ть )О, ..., Х =.=О). Пусть вместо точных с, аь Ь; известны лишь их приближения с,, а;„, Ь,» с погрешностями ~с» — с((о„(а!» — а,(~о„, ! Ь,„— Ь, )=о„, !=1, з; о»~0, /с=1, 2, ... 1'пи о„=О. Тогда вместо точных функций /(и) = (с, и), /б (и) = =- (аь и) — Ь, придется пользоваться их приближениями ,/„(и) =(с„и), д!»(и) =(ам, и) — Ь!», ! =1, з, /г =1, 2, ...
Как показывает пример 3, в этом случае задача линейного программирования, вообще говоря, будет некорректна в метрике Е". Покажем, что для ее решения может быть исполь !оиан описанный выше метод стабилизации. Ограничения типа равенств и неравенств, задаваемые функциями и!(и), учтем с помощью штрафной функции Р»(и) = ',~~ ~!пах((а»„и) — Ь;,; О) ~»+ ~ 1(ам, и)— ~=:и-~- ! — Ь!,';, р В качестве стабилизатора возьмем функпию () (и) =! и 1а при !/)р, которая определена и непрерывна на множестве (/а =-(/» (например, можно взять »! =Р=2).
Так как (/ — выпукло и замкнуто, то функция 1и!' и, сле- 233 довательно, Й(и)=)и!" достигает своей нижней грани на (/„в единственной точке и сна», т. е. 11-нормальное решение существует и определяется однозначно. Поиажем, что погрешности в задании функций У(и), рй(и) согласованы со стабилизатором в смысле неравенств (7), (8). Для этого заметим, что )гпах(а; О) — гпах(Ь; 0) !« «',а — Ь), )!а! — !Ь,'!«(а — Ь! при всех действительных а, Ь, так что с учетом обозначений (5), (6) будем иметь /д,„(и) — а. (и) ~«)дм(и) — д;(и) ! (34) для любых функций дм(и), дс(и).
В нашем случае из (34) следует ~Е;»(и) — др(и)1«! (а;„и) — Ьгя — (ап и)+Ьр ! = «о»(!+ !и!), и~Е». (35) Пользуясь формулой конечных приращений Лагранжа для функции д(г) =гг, из определения (4) ! Р»(и) — Р(и)!= Б ~ч~ ~(да (и) — д; (и)) р ~д; (и)+ 0 (ди (и) — д; (и))~ ! с=~ о«в С учетом (35) тогда (Р„(и) — Р( )!»ч~р~ро,(1+.
С=1 + /и!)г(!а;/+!Ьс!+о»)г-'. Поскольку знр(1+!и!)г(1+ в» + ! и (4)-'=А (р, с()(со, то !Р,(и) — Р(и) )«о,рА (р, с!),г, (!а;',+) Ьр (+о,) (1+!и(4), и е Е» Аналогично ! у» (и) — у (и) ! = ((сы и) — (с, и) ! « «о, (1+ ! и /)» о„А (1, с() (1+ ! и /4), и е= Е". Таким образом, погрешности согласованы со стабилизатором 11(и)=-!и!4 в смысле неравенств (7), (8) при любых г( г ь р = 1. Составим функцию Тихонова Т4 (и) = (сы и)+ + А4Р» (и) -1- а» ! и (4 и с помощью какого-либо метода 234 минимизации определим точку и, ~ У„удовлетворяющую условию (32).
Если параметры а~, А„пы е„согласованы так, чтобы 1!ш а„=!!гп Аь' =1!гп (о„А„+ а~) аГ = =О, !пи А~-'и„оо (при р=! последнее равенство не л нужно), то из теоремы 2 следует сходимость (и„) к (знормальному решению и в метрике Е". Предлагаем читателю самостоятельно рассмотреть случай, когда некоторые из ограничений типа равенств и неравенств в рассматриваемой задаче линейного программирования учитываются посредством множества ))7, согласно (11). Заметим, что хотя множество (и: (а, и)— — Ь(0) выпукло, но множество [и:(а, и) — Ь(0(1+ -)- /и/") прн а'»О, 3>1 невыпукло, так что множество !р„здесь также может оказаться невыпуклым.
Пример 6. Рассмотрим задачу выпуклого программирования в гильбертовом пространстве Н. Пусть У,— выпуклое замкнутое множество из Н (например, У, = Н), функции у(и), д,(и), ..., д,(и) выпуклы и полунепрерывны снизу на У, в метрике Н, а функции ньы(и), ... д,(и) имеют вид д;(и) =(аь и) — Ь;, где а; — некоторые элементы из Н, Ь| — числа, (а;, и) — скалярное произведение в Н. Пусть на множестве У = (и: и ен У, йй(и)(0, 1=1, т; д;(и)-0, ( т+1, з), т»г, функция у(и) ограничена снизу и достигает своей нижней грани хотя бы в одной точке, т.
е. У,.» — со, У„ ~ ф. Предположим, что функция Лагранжа Ь(и, Х) ((и)+ + ~Л,дю(и) имеет седловую точку на множестве У„хд ! ! в смысле неравенств (33) (достаточные условия существования седловой точки см. в теореме 1.2.8; см. еще гл. 4 [4]). Будем пользоваться штрафными функциями (4) при некотором р» 1.
Возьмем функцию 11 (и) = ! и !з, »шах(р; 2), которая строго равномерно выпукла на Н и является слабым стабилизатором рассматриваемой задачи. Таким образом, множество У, и функции l (и), д„(и), ..., д,(и), 11(и) удовлетворяют условиям 1), 2) леммы 2. Кроме тогб, У, — выпукло, замкнуто, и согласно теореме 1.3.9 !1-нормальное решение и, существует и определяется единственным образом. Пусть вместо точных значений,Ци), д,(и) известны их приближения (~(и), дм(и), 1=1, з, й=1, 2, 235 причем погрешности согласованы со стабилизатором () (ц) =йи1!и в смысле неравенств (7), (8) при некотором с(- шах(р; 2). Составим Функцию Тихонова Ть(и) = =,lь (и) + АьРь (и) + аа( и ~~' и при каждом )г = 1, 2, ...
определим точку иь'~ (уц мм (/о из условия (82). Если параметры б„тм а„Аь, зь удовлетворяют условию 4) теоремы 2, то из этой теоремы следует сходимость построеннои последоватепьности (иа( к ()-нормальном) решению и по норме Н. 7. Лля решения рассматриваемых некорректных задач минамизации наряду с методом стабилизации могут быть применены и другие методы регуляризации. Здесь мы остановимся на одном варианте метода невязки, предполагая, что множество У имеет вид (31).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
