Ф.П. Васильев - Методы решения экстремальных задач (1981) (1158203), страница 16
Текст из файла (страница 16)
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(а(!. Отсюда при а-д.+сю получим равенство (26).
Пусть теперь У(и) выпукла на ЕУ. Согласно теореме 3.6 тогда ЕУ, Ф ОУ. Возьмем произвольную точку и, ~ е-=(Уд. Из теоремы 2.1 и условия (20) имеем 0(ил= У(ил) — У(и„) «= (/'(и„), ид — и„'; =- = — 1д(ил) ( —,Уд(йд) =( Ул(йд) (, )о=О, 1, ... (30) Отсюда и из равенства (26) следует, что (ид) — миннмизн- руюгцая последовательность. Согласно теореме 3.6 тогда (ид) слабо сходится к ЕУ,, Докажем оценку (27). Так как Уд(йл)-о-0 прн й — со, то найдетсЯ номеР й, такой, что 0(Ул= ~ Хд(йл) ~У(Ег(о) ( (! при всех Уо=»)го.
Тогда максимальное значение функ- ции а~ lд(йд) / — аоидЕУ2 переменной а при — оо (а< (+оо, которое достигается при а=ум будет совпадать с максимальным значением этой функции на отрезке 0( (и( 1 прп всех Уо) ио. Поэтому, полагая в оценке (28) а=у„ получим ид — ад „= о' (и,) — У (идол) ~ ! о'л (йд) 1дУ(2ЕУ(д), й =- Уго. 8! Отсюда и из неравенств (30) следуст ал — а„,~аЦ2ЙР), сс~Ао.
Остается применить лемму 2.3.4 из (4) и убедиться в справедливости оценки (27). Последнее утверждение теоремы для сильно выпуклых функций следует из оценки (27) и неравенства хссс,— и„:,' — 1(ис) — 1(и„), /с=О, 1,... Заметим, что описание метода условного градиента и теорема 6 сохраняют силу и в том случае, когда У вЂ” выпуклое замкнутое ограниченное множество из рефлексивного банахова пространства.
4. Метод возможных направлений может применяться для прнблси>кенцого решения задачи 1(и)- (п1; ива(1=(иенВ: а,(и)(0, с=1, т), (31) где  — банахово простоанство, 1(и), дс (и), ..., д„, (сс) еи ~С>(В) Для описания этого метода нам понадобятся следующие два понятия. О п р е д е л е н и е 2. Пусть У вЂ” некоторое множество из В и ияли.
Направление е я В, ечиО, называется возможным в точке и, если существует число С,)0 таксе, что и + Се ен (1 и р н всех с, О ( С ( (,. Определение 3. Направление е~В, е~О, называется возможным направлением убывания функции 1 (и) в точке сс на множестве У, если е — возможное направление в точке и и, кроме того, 1(и+(е) <1(сс) при всех с, 0< (<(с, ГдЕ 0<(ск=.йл Метод возможных направлений заключается в следующем. Пусть и, ен У, е, ) 0 — некоторое начальное прибли>кение. Допустим, что )с-е приближение (иы е„), ив(1, е,)0 прп каком-то сс)0 уже известно.
Определим множество номеров 1с = (сй 1 ( с < т, — ес ( дс (и,) ( 0) н в пространстве переменных г=(е, о) ен В>сЕс рассмот- рим вспомогательную задачу о-~)п1; г=(е, о) ~(Г,=>с(е, о): (1'(ис), е)(о, (д,'(и,), е) =.о, с ~1в', 1'е1(1). (32) Множество %'„вьспукло, замкнуто и ограничено, поэтому если В является рефлексивным банзховыч пространством, 82 то согласно теореме 3.6 задача (32) имеет решение. Пусть (е» од) — решение задачи (32), т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
