Ф.П. Васильев - Методы решения экстремальных задач (1981) (1158203), страница 14
Текст из файла (страница 14)
определение !6) на У, необходимо и достаточно, чтобы множество Л( (с) =(и ю У: 7 (и)(с) было замкнутым в (Х, т) при любом вещественном с. !8. Пусть У вЂ” множество из топологического пространства (Х, т), а функция l (и) определена и конечна на У. Назовем фуннцию l (и) т-счетно лолунепрсрыанод снизу на множестве У, если в любой точке и ~ У и для любой последовательности (не) ю У, для которой точка и является т-предельной (см, определение 11), справедливо неравенство 1пп 7 (иа) — / (и).
Доказать, что множество т-счетно а оз полунепрерывных снизу на У функций исчерпывается функциями ,1(и)=сопи, иезУ Указание: пусть и, ощУ, и о, /(н)р ~ 7 (о). Рассмотреть последовательность (иа): из а — — и, намет — — о, го = О, 1,..., и полу'чить противоречие. 5 4. Методы минимизации Здесь мы будем предполагать, что читатель знаком с большинством из рассмотренных в [41 методов минимизации. Заметим, что из этих методов лишь некоторые являются сугубо конечномерными, т. е.
приспособленными для решения задач минимизации лишь в конечномерных пространствах — это симплекс-метод, метод покоординатного спуска и некоторые другие методы. Большинство же описанных в [41 методов минимизации вполне могут быть применены для минимизации функций на множествах из бесконечномерных банаховых и гильбертовых пространств — это градиентный метод, методы проекции градиента, условного градиента, возможных направлений„сопряженных градиентов, штрафных функций, Ньютона и др.
Идеи и описание упомянутых методов минимизации в бесконечномерных пространствах по форме ничем не отличаются от их описания в конечномерном случае. Поэтому здесь мы можем ограничиться лишь кратким описанием этих методов, отсылая читателя за подробностями к главе 5 из [4]. Далее, формулировки и доказательства теорем сходимости для большинства упомянутых методов в беско- нечномерном случае могут быть получены путем неболь- шой корректировки соответствующих конечномерных тео- рем н их доказательства из [4!.
Для того чтобы показать, как это делается, мы ниже приведем несколько таких теорем. Кроме того, некоторые из излагаемых методов проиллюстрнруем на примере следующей задачи оптималь- ного управления, рассмотренной в Я 2, 3: ,/ (и) = ! х (Т, и) — у," ->- !п1; (1) х(1) = А (1) х(1)+В(1) и(г)+1(1), гд(1(Т; х(10) = хд' (2) и=и(1) Ииа(.,'(Г„Т) (3) (обозначения см. в ф 2); примеры других задач оптималь- ного управления см. ниже в Я 5 — 10. !. Градиентный метод может применяться для прибли- женного решения задачи У (и) — !п1; и ен Н, где Н вЂ” гильбертово пространство, г' (и) ен С' (Н), Этот метод заключается в построении последовательности (ид) по правилу идм=ид — адГ(ид), А=О, 1, (4) где и, — некоторая заданная начальная точка, яд — положительная величина. Если У (и,)ФО, то яд можно выбрать так, чтобы 1 (и„„) ( у (ид).
В самом деле, из равенства (2.1) имеем /(ид,,) — У (ид) = яд ( — ,'~ г" (ид) !д+ о (яд)/ад) ( 0 при всех достаточно малых ад)0. Если 1'(и,) ФО, то процесс (4) прекращается и при необходимости проводится дополнительное исследование поведения функции в окрестности точки ид для выяснения того, будет ли ид принадлежать У„или нет. В частности, если ((и)— выпуклая функция на Н, то согласно теореме 2.5 ид ~ Уд.
Существуют различные способы выбора величины ад в методе (4), Перечислим некоторые из них: 1) яд выбирается из условия >д(ад) = 1п1 10(а) = гдд, 'гд(а) = У(и, — а1' (ид)) (5) а)0 — этот вариант градиентного метода принято на>ывать метоуом скорейшего спуска. Точное определение вели- 3* 67 чины ал из (5) не всегда возможно, поэтому на практике вместо (5) пользуются условием 1л,()л(ал) =~лл+бл, бл)0, '5', 6л(со, с =- а или )л л = 7л (ал) ~ (1 — М Ь (0) + Мл „ 0(й~йл=-.!; величины 6„, ).л здесь характеризуют погрешность выполнения условия (5).
2) а, выбирают из условия монотонности: У(и„,) ( ( ) (ил). Для этого задают какую-либо постоянную а) 0 и в методе (4) на каждой итерации берут а„=а. Затем проверяют условие монотонности, и в случае его нарушения величину ал=а дробят до тех пор, пока не выполнится условие монотонности. 3) Если ) (и) ~С" (Н) (см. определение 2.5) и постоянная Е,) 0 из неравенства )з'(и) — Г(о)1(У.(и — о), и, о изН, известна, то величину а, в (4) можно взять из условий 0 ( е, ==.
а, ( 2)(й + 2е), где е, е„— положительные числа, являющиеся параметрами метода. 4) Возможен выбор ал из условия ,) (ил) — У (ил — ал,)' (ил)) ~зал' У' (ил) )л е) 0; для определения такого ал обычно задают а,=а и затем дробят а до тех пор, пока не выполнится выписанное неравенство. 5) Возможно априорное задание величин а, из условий СО сал)0, и=О, 1..., ~~ ал=ос, ~~ ал(со. Лев л=О Например, можно принять а„=с(й+1)-", с=сопз1) О, 1)2(а 1. Такой выбор а, прост для реализации, но не гарантирует выполнения условия монотонности ((илл,) (/(и„) и, вообще говоря, сходится медленно.
б) В тех случаях, когда заранее известна величина ,)„== (п1) (и)) — со, в (4) можно принять и ал = () (ил) — У,.),'1 )' (ил) ~л 66 На практике итерации (4) продолжают до тех пор, пока не выполннтся какой-либо критерий окончания счета. Здесь возможно использование таких критериев: )и„— иоо,"(е, или У(ио) — У(и, 1) ~.(6, или ~ 7'(ио)1- у, где е, 6, у — заданные числа; иногда заранее задают число итераций. Разумеется, к этим критериям окончания счета надо относиться критически, поскольку они могут выполняться и вдали от искомой точки минимума. Посмотрим, как выглядит градиентный метод для задачи (1) — (3) при У=(,;(1о, Т~!.
Согласно формуле (2.12) градиент функции (1) равен Г(и)=В' (()ф((, и), (о(((Т, где ф((, и) — решение задачи (2.13), (2.14). Тогда метод (4) для задачи (1) — (3) можно записать в следующем виде: иоо, (!) = ио (() — аоВг (() ф ((, ио), („~(~Т, й=о, 1, ... (6) Покажем, что в рассматриваемой задаче для параметра ах, определяемого из условия (о), можно получить явное выражение.
С этой целью вспомним формулу (2.25): х ((, ми + (1 — я) и) = ях ((, о) + (1 — а) х ((, и), (о((~Т, справедливую для всех и, о ен).о))„Т1 и всех вещественных а. Полагая здесь о = и+ й, ( = Т, получим х(Т, и+ай) =х(Т, и)+я(х(Т, и+й) — х(Т, и)), — со ( а (+ со. Отсюда с учетом равенства (2.20) имеем .( (и + яй) = ( х (Т, и + яй) — у !о = ='х(Т, и)+а(х(Т, и+6) — х(Т, и)) — у(о = = У(и)+2а(х(Т, и) — у, х(Т, и+А) — х(Т, и))+ +аз/х(Т, и+6) — х(Т, и) /о= /(и)+ г +а$ (В' (~)4'((, и), й (!)) с(!+аз ~ х(Т, и+А) — х(Т, и) /о, и — со я(+со; и, Й е=Ео((о, Т'1.
(7) 69 Из этой формулы при и=им й= — Г(и„) получим явное выражение для функции (5): Т»(а)= 1(и»)+2а(х(Т, и,) — у, х(Т, и» вЂ” Г (и„))— — х(Т, и,))+а'(х(Т, и» вЂ” Х'(и»)) — х(Т, и„) Р= т =и (и») — юхт)!Вт(!) ф(ю, и») !'дю+сюи!х(Т, и» вЂ”,ю" (и»))— — х(Т, и„)!», — со(а<+оо. (8) Может случиться, что х(Т, и» вЂ” У'(и»)) — х(Т, и») =-О. Тогда нз (8) следует 1»(сю)= l(и»)=сопз1 при всех а.
Поэтому ю»(а)=(Г(и» вЂ” сюд'(и»)), — Г(и»))=0 при всех сю. В частности, при юх=О имеем)»(0)= — (,ю" (и») 1'=О, т. е. Г(юю»)=0. В силу теоремью 2.5 тогда ив=и»=и»(Ю)— оптимальное управление, задача (1) — (3) при Сю =1»[(ь, Т! решена. Рассмотрим случай х(Т, и„— Г(и„)) — х(Т, и»)~0. Тогда функция (8) представляет собой квадратный трех- член и достигает своей нижней грани на числовой оси при (х(Т и»! — у, х(Т, и» вЂ” Г(и»)) — х(Т, и»)) ! х (Т, и» вЂ”.Ю' (и»)) — х(Т, и») 1» т ) !Вт(Ю)Ч:(Ю и»1!»аЮ 1 )О. 2 ! х(Т, и» вЂ” 3'(и»!) — х(Т, и»),» Если сю» = О, то Г (и,) = О и и, = и» (ю) — оптимальное управление; задача решена. Если а») О, тосю»=а»» удовлетворяет условию (5) и в (6) остается принять сю»=а».
Один шаг метода скорейшего спуска (4), (5) применительно к задаче (1) — (3) при 0=1.»[ю„Т! описан. Приведем теорему сходимости метода скорейшего спуска, представляющую собой обобщение теорем 5.1.1— 5.!.3 из [41 на случай гильбертовых пространств. Здесь мы ограничимся рассмотрением варианта (4), (5). Теорема 1. Пусть ю[лункю(ия /(и) определенанаеильбертовом пространстве Н, д(и) я С" (Н), д = !п! /(и)) и ~ — со. П!юсть (и») — последовательность, полученная методолю (4), (5) при некотором начальном приближении и»енН. Тогда последовательность (/(и,)', монотонно убьювает и (9) !пп (,ю'(и»)ю=О. » со 70 Если, кроме того, функция 7 (и) выпукла на Н и»сножество М(и,) =с,и ен 1/: 1(и)«У(ио)) огранич.но, то последоеательность си») минимизирует зту функцию на Н и слабо в Н сходится к множеству (с'о, причем справедлива оценка скорости сходимости 0 = о'(и») — 7 «с,сн, сс=!, 2, ..., с,=сопз1з:О.
(10) Если функция г'(и) есце и сильно выпукла на Н, то (и») сходится к единственной точке минимума и по норме Н, причем 0«2(и») — (о «(У (ио) — )о) У», ! и» вЂ” ио ,'~о (2с!») (7(ио) — У ) у» (с = 0 1 где д=! — р)Ь, О==с)(1, р)0 — постоянная из теоремьс 2.2. Д о к а з а т е л ь с т в о.
Справедливо неравенство ,) (и») — У (сс»ы) )!7(2Е.) ( Г (и») 1», (с = О, 1, ..., (1!) которое доказывается точно так же, как неравенство (5.1.12) из [4). Отсюда следует монотонность и сходимость (У(и»)), а также равенство (9). Далее с учетом выпуклости 7(и) рассуждая так же, как при доказательстве оценки (5.!.!5) из [4), устанавливаем, что О « а» =,У (и») — Уо « с(;~,l'(и»),'~, )с = О, 1, ..., (12) где с(= зцр [и — о( — диаметр множества М (и,). и, оем сии Отсюда и из (9) следует, что последовательность ',и») минимизирует г'(и) на Н. Поскольку (и„) ~М(и,), то согласно теореме 3.7 (и») сходится к сс' слабо в Н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
