Ф.П. Васильев - Методы решения экстремальных задач (1125244), страница 15
Текст из файла (страница 15)
До к а з а тель с т в о. Первое утверждение теоремы вытекает из оценки 7(а„) — 1(илью)е(иь — иь„,(', й=О, 1, 2 „... которая доказывается так же, как соответствующая оценка (5.2.11) из 141. Доказательство второго утверждения тео- ремы для выпуклых функций полностью аналогично дока- зательству теоремы 5.2.2 из 14] с той лишь разницей, что вместо теоремы 2.1.2 здесь нужно использовать тео- рему 3.7.
Утверждения теоремы для сильно выпуклых функций являются следствием предыдущих утверждений и теоремы 3.8. Для сильно выпуклых функций можно предложить другой вариант метода проекции градиента, имеющий бо- лее высокую скорость сходимости 178). Теорема 5. Пусть (7 — вьтуклое замкнутое множе- ство из Н, функция 7(и) принадлежит С" (П) и сильно выпукла на (7 и пусть 0(и(ай-, гдг постоянные р, Е, р=.Е, взяты из определения 2.5 и теоремы 2.2. Тогда послгдовательность (иь), получаемая из (14) при иь = и, А=О, 1, ..., сходится к точке минимулча и по норме Н, причем справедлива оценка (иь — и„(()иь — и,((д(и))ь, у=О, 1, ..., где у (и) = (1 — 2ри+ иЧ,')"', 0 ( д (и) " 1, Доказательство этой теоремы проводится дословно так же, как и доказательство аналогичной теоремы 5.2.3 из 14).
3. Метод условного градиента может применяться для приближенного решения задачи Х (и) э- (п1; и ен (7, где П вЂ” выпуклое замкнутое ограниченное множество из гильбертова пространства Н, л'(и) ен С'((7), Этот метод 7б заключается в построении последовальности по следующему правилу: по известному и-му приближению находят вспомогательное приближение и, ~(У из условия (У' (и»), ид — и») = !п1(У' (и»), и — ид), и или, что равносильно, из условия ид -= (7, (д" (и»), й») =(и((/'(и»), и), (20) и и затем полагают и»„= ид+а» (и, — и,), 0 (а» ( 1, (21) Заметим, что линейная функция (Г (и»), и) слабо непрерывна на У, а множество У согласно теореме 3.4 слабо компактно.
Отсюда и из теоремы 3.2 следует, что нижняя грань в (20) достигается хотя бы на одном элементе и, ~ У. Если при некотором )г оказалось, что и» = им то процесс (20), (21) прекращают. В этом случае в силу условия (20) )п1(Г(ид), и — и»)=(У'(и»), и,— и,'; =О, т. е. и (./' (и»), и — и»)» 0 при всех и ~ (У. Согласно теореме 2.5 это означает, что точка и» удовлетворяет необходимому условию оптимальности, и для выяснения того, будет ли и, ~ (/„, нужно дополнительно исследовать поведение функции в окрестности точки и».
В частности, если )(и) — выпуклая функция, то согласно теореме 2.5 и,я(l„. Существуют различные способы выбора величины ад в (21). Приведем некоторые из иих: 1) а, выбирается из условия 1»(яд) = !п1 1»(а) =1»д, 1»(а) = У(и»+а(йд — ид)). о<»<~ (22) В тех случаях, когда точное определение а» из этого условия затруднительно, то вместо (22) можно пользоваться условием )»(а»)()» +б» б»- 0 ~'б»<со, »=о или 1' (Я„) < (1 — ) „) !' (0) + Ч „О < Х.
Хд ~ 1; 77 величины б„, Л„здесь характеризуют погрешность выполнения условия (22). 2) Можно задать а, = 1, проверить условие монотонности: у(и»„,) ( У(и„), а затем прн необходимости дробить а, до тех пор, пока не выполннтся условие монотонности. 3) Если 7(и) ен С" (У) н константа Липшица Л для Г(и) известна, то возможен выбор а, в (21) из условия а„=гп!п (1; р„! (Л(и,), й,— и,) ((й» вЂ” и»Г»), где 0 ( е, ~ р» ( 2!(1. + 2е), е», е — параметры метода, е' ~0. 4) Можно принять а»= Л'Ч где !» — минимальный среди номеров (=-О, удовлетворяющих условию ,) (и,) — У(и,+ Л'(й» вЂ” и,)) =-Л'е' ,(Л (и,), и» вЂ” и,) /, где Л, е — параметры метода, 0(Л; е(1. 5) Возможно априорное задание величин а„из условий 0(а»(1, Уг=О, 1, ..., 1!ш а»=0, ~а»=+-сх>.
» со »=о В том случае, когда задачу (20) точно решить не удается, то вспомогательное приближение и» ен У можно определить из условия (Г (и,), й» вЂ” и„) == |п! (Л (и»), и — и») + е», о е» ) О, А = О, 1, ..., И гп е» = О. Посмотрим, как выглядит метод условного градиента для задачи (1) — (3), когда множество У имеет вид (!7) пли (19). Согласно (20) для определения й»=й»(!) нужно на множестве У минимизировать линейную функцию г г ~ (В (!)ф((, и»), и(!)).,й(=~ У,' (В (!)»р((,и„));и'(!)йй и Отсюда видно, что в случае множества (!7) будем иметь и»(!) =(и»(!), ..., й»(!)), !»(((Т, где и»(!) = ! а;(!) при (В (!)»р(1, и„));-==О, ~ р;(!) при (В (!)»р(г, и»)); -О, та а если У вЂ” шар (19), то с помощью неравенства Коши— Буняковского получим и ((~ р (7) )1 Н (О 11 (П ид) (, й (г) лг (и ид),в~ йг! („~(~Т.
Параметр ад, определяемый условиями (22) в рассматри- ваемой задаче, может быть выписан явно. В самом деле, из формулы (7) при и=их, й=ид — ид имеем Если х(Т, ид) — х(Т, ид)=0, то (д(а)=7(ид)=сова( при всех а. Следовательно, )д (а) = (Г (ид+ а(ид — и„)), ид — ид) =0 при всех а. Отсюда с учетом условия (20) получаем )д(0)=0=(Г(ид), ид — и,)(()'(и,), и — и„') для любого и ~ (7. Согласно теореме 2.5 тогда и, =и, = = и, И) — оптимальное управление в задаче (1) — (3) (здесь подразумевается, что У вЂ” выпукло амкнутое ограниченное множество из Ц((„Т]). Теперь рассмотрим случай х(Т, ид) Фх(Т, ид).
Тогда функция (23) представляет собой квадратный трехчлен и достигает своей нижней грани на числовой оси грн т 1 (нт (О д (б ид), й„(с) — и (г)), йг й а=а, 2,,' х(Т, ад) — х(Т, и ) ~ х (х (Т, ид) — и, х(Т, йд) — х(Т, ид)) !х(Т, ид) — х(Т, ид) /'„ (24) Так как в силу (20) )т (В (()лР((, ид), йд(() — ид(())а,с((= = (,/' (ид), ид — ид) — (У' (ид), и„ вЂ” ид)= О, 79 )д (а) = ) (ид) + 2а ('х (Т, ид) — и, х (Т, йд) — х(Т, и,) ) + +ад ~х(Т, и„) — х(Т, ид) !'= т =- У(ид)+а( '(В' (() лр((, ид), и,(() — и,(()),с((-1- с.
-(-ад~х(Т, ид) — х(Т, ид) ~л, — оо(а . +ос. (23) то ясно, что а»=0. Возможен случай и»=0. Согласно условию (20) и формуле (24) это значит, что 0 = (Г (и„), й» вЂ” и»): — (Г (и„), и — и») при всех и ен(/. В силу теоремы 2.5 тогда и„=и,=и»(()— оптимальное управление в задаче (1) — (3). Если сг$)0, то квадратный трехчлен достигает своей нижней грани на отрезке О.==а=-! пои и»=ппп(1; сг»). Это и есть искомое явное выражение для а», удовлетворягощее условию (22). Для получения (/г+1)-го приближения остается положить и» сг (/) = и» (() + а» (и» (/) — и» (/)), /ь (1 ~ Т. Сходнмость метода условного градиента для задачи (1)— (3) вытекает пз следующей теоремы. Теорезга 6.
Пусть Н вЂ” выпуклое замкнутое ограниченног лгножсстсо из гильбгрпюва пространства Н, функг(ия /(и) принадлежит Сгд((/). Тогоа для последовательности (и»), определяемой методом (20) — (22) при лгобом емборе начального приближения иь е= (/, справедливо равенство (2б) ! ! гп (Г (и»), и» вЂ” и») = О. » са Если, кролге того, функиия /(и) выпукла на Н, и;о последовательность (и») минимизирует эти фг/нкииго на !/ и слабо в Н сходится к множеству (/„, причем справедлги,а ог(енгса О~У(и») — / =с„г/г, /г=1, 2, ...; с»=сонь( ~0.
(27) Если /(и) гиге и сильно выпукла на (/, то (и») сходится к единственной точке минимума и„по норме Н, причем (г㻠— и, 1» . с,/|г, /г=1, 2, ...; с»=сонэ()0. Д о к а з а т е л ь с т в о. Прежде всего заметим, что нз ограниченности ~шожества 1/, условия /(и) ~С»д((/) и леммы 2.1 следует, что 3/(и) )(// (и,/, +(.У' (иь)1(и — и,)->сЕ ~ и — иь)»/2 =:- . ) '(и»/!+„,/'(и,) д -РЕа'/2 <оз во при всех иен(У; здесь д(= ьпр (и — о! — диаметр множеи, чаи ства (У. Это значит, что функция о'(и) ограничена па ЕУ. Следовательно, У, — оо. Обозначим Уд (и) = (У' (ид), и — ид). Из (20) следует, что ,Уд(йд)(,)д(ил)=0, й=О, 1, ...
Далее, справедливо неравенство ,У(ид) — У(ил,,) ) а ~,Уд(ид)! — аЧлРУ2 (28) при всех а, О ( а ~ 1, Уг = О, 1, ..., которое доказывается так же, как аналогичное неравенство (5.4.18) пз 141. Отсюда 0 ~ д Уд (и,) ! ~ аЕг(дУ2+(,У (ид) — /(ид„))Уа, (29) )о=О, 1, ...; 0(а(1. Так как У(ид) не возрастает и ,У(и„) ~,Уд ) — оо, то (,У(ид)) сходится и .У (ид) —,У (ид„)— 0 прн Уг-д. оо. Поэтому, переходя в неравенстве (29) к пределу при Уо-о- оо, будем иметь 0 = !пп 'Уд (ил),'~ !(п1 ),Ул (ид),,' =аЕо(дУ2 д ю л со при всех а, 0(а(!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
