Ф.П. Васильев - Методы решения экстремальных задач (1125244), страница 42
Текст из файла (страница 42)
Соотношение (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). В качестве штрафных функций возьмем те же функции Р (и), Рь(и), определяемые соотношениями (4) — (6), и положим Фь (и) = »'ь (и) + А »Рь (и), Фь(и) =-»'(и)+Аьр(и), иле У», (36) где Аь)0, !пп А„=+со.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
