Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 71
Текст из файла (страница 71)
3. Исследуем сходилгость метода (4), (5), (10). Т е ар ем а 2. Пусть П вЂ” выпуклое сомкнутое ограниченное множество иг Е", грункция 1(и) принадлежит Сгл(П). Тогда при любом ил си П для последовательности (ил), определяемой условиями (4), (5), (10), справедливы равенства (13). Если, кроме того, 1(и) выпукла на П, то имеют место равенства (15), а при ел < Сгй гв, Сг = сопзг > О, 0 < р < 1, верна оцвк ка (16). Для сильно выпуклой гДункции справедлива оценка (17). Доказательство.
Так же, как неравенство (18), нетрудно покаэатьч что 1(и,) — 1(и +л)) — а,1„(и„) — а~~А(и,— ы,(е/2, й= О, 1, ... (24) В соответствии с формулой (10), определяющей величину ал, рассмотрим три возможных случая: 1) Если 1л(ил) < О, ыл = 1 < рл(1л(ил) ! (ил — ыл! г, то из (24) с учетом (П) имеем 1(ил) — 1(ильу) ) (1л(йь) ! — 5рл(1л(йл) (72 > е(1л(йл) !. (25) 2) Если 1л(йл) <О, ыл = рл)1л(йл) ! )йл — ил! г < 1, то из (24) с учетом (11) получаем 1(ый) —,1(ы + )~ р,)1„(и,) )л! ил — ил ! е — Ерге )1л(ил) )~ ! иь — иа! /2 ! 1„(и„) )з ! и„— и„! г р (1 — 5рь(2)> ~ ! 1, (ил) (гй зеве, й > епр ! и — и !. (26) и,ге н 3) Наконец, если 1л(йл) > О, то согласно (10) и иэ (24) имеем 1(ыл) — 1(ил+г) > О, (27) а из (4) следует 0 < 1л(йл) < ел (28) Из (25) †(27) вытекает, что последовательность (1(ил)) ве возрастает.
Так как 1(иь))~ 1ь > — со, то существует1(ш 1(ил) ~1г и, следоватоль- Л-тгг но, 11ш (1(и„) — 1(иь+л)) О. Отсюда и иэ (25), (26), (28) имеем 0 < Л-тгг < (1л(йл) ! < шах(ел, солям(1(ил) — 1(ил+~))ыг)-тО при всех й-ь со. пер вое из равенств (13) докааано. Второе равенство (13) устанавливается так же, как в теореме 1. Пусть теперь функция 1(и) выпукла на (7. Тогда справедлива цепочка неравенств (20), иа которой следуют равенства (15). Предполагая, что ел < Сей гг (О < р <1), докажем оценку (16). Предварительно заметим, что Оы; ал — — 1(ил) — 1е~зпр 1 (и) — 1г = С < оо, поэтому ае < епр ал а, < С аз, ~ = О, 1, ... (20) л>о Еще раэ переберем рассмотренные выше три возможности.
1) Если 1л(ил) < О, ыл = 1 < рл(1л(иь) ! (йл — ил(г, то из (20), (25), (29) имеем ал — ал+~ > еал — еел, если аз+э < аз — зал+зев~а,— аз (е/С )+ еС й ео, (30) 293 МЕТОДЫ МИНИМИЗАПИИ ФУНКПИЙ МНОГИХ ПЕРЕМЕННЫХ ~ГЛ, Э 2) Пусть 1»(дь) (О, иь = рь~уь(йь) ( ~йь — иь)-з < 1. Здесь, в свою оче редь, имеются две возможности: аь) еь илв 0(еь ( еь Если аь ) еь, то из (й), (26), (29) получим ໠— а»+ ) (о„— е»)з д ее е> а»зд 'е е — 2С ° ° е»д зе е или о а»+з < ໠— а» (еое7д ) + 2С е ед Сей (31) Если же 0 ( аь ( еь, то достаточно воспользоваться более простым следствием (26): аз+з (аь Последние два неравенства можно переписать в виде (32) аьтз < аь ( аз + Сьй зо.
0(аз<Сей зв, О~У(и») — Уе(С )п(й+1)/й, й=1,2, ..., (33) а если аь (й+ 1)-З, еь = Сз(»+1)-З (й = О, 1, ..., 0 ( 5 < 1), то О и г (и ) Ю снсзй д й 1 2» (34) здесь Сг, С4 — некоторые иоложительные постоянные. До кааат ельство. Заметим, что неравенства (20), (24) не зависят от способа выбора аь (О ( пь (1) в (5), поэтому сохраняют сплу и в рассматРиваемом слУчае. Иа ннх имеем ໠— а»+з ~ и»(а„— е„) — и»з5дз72 или а»+д(1 — а») а»+ а»5дз(2+ и,„»д, й= О, 1, Отсюда с учетом свойств последовательностей (аь), (ез) из (4), (12) заключаем, что (аь) удовлетворяет условиям леммы 2.3.6. Поэтому Пш ໠— — 0 »-тес или Нш з (и») ле. Отсюда и из теоремы 2АА получаем равенства (15). »~ы Оценки (ЗЗ), (34) следуют из лемм 2.3.8, 2.3.9. Упражнения.
1, Вычислить несколько итераций метода (3), (5), (6) для функции 1(и) = х'+ ау+ у' при и зн У = (и (х, у) зи Ез: 0 < <х<1, — 1<у<0), выбирая из=(1, — 1), ( — 1, 0), (1, 0) или (О, 0). 2. Для фуккцйи йз примера 1 проверить выполнение условий теорем 1 — 3 и сформулировать условия сходнмостп соответствующих вариантов метода условного градиента. 3. Дать описание различных вариантов ыетода условного градиента для функции 7(и) = )Аи — Ь!з, где А — матрица тл )( п, Ь ш Е'", а множество У является шаром или параллелепипедом. Опираясь на теоремы 1 — 3, доказать сходимость метода.
3) Наконец, пусть рь(йь) ) О, аь = О. Тогда нз (20), (27) получим О < аь < еы аь+з < а», что снова приведет к неравенствам (32). Иа (30) — (32) следует, что последовательность (аь) удовлетворяет условиям леммы 2.3.5, иа которой получаем оценку (16). Теорема 2 доказана. 4. Наконец, рассмотрим варнаве метода условного градиента (4), (5), (12). Теорема 3. Пусть У вЂ” выпуклое замкнутое ограниченное мнохссство ив Ек, функция г(и) он С' '(У) и выпукла на У. Тогда яри любом из ш У для последовательности (иь), определяемой условиями (4), (5), (12), справедливы равенства (15). Если при етом пе (й+ 1) ', аь Сз(й+ 1) (й 0,1,...),то 3 м МЕТОД ВОЗМОЖНЫХ НАПРАВЛВНИН з 5.
Метод возможных направлений 1. Продолжим рассмотрение задачи минимизации гладкой функции У(и) на заданном множестве У вЂ” Е". Напомним, по направление етые называется возможнььн в точке иш У, если и+1еш У при всех 5, 0< 5< 5„где 5,— положительное число, зависящее от точки и, направления е и от структуры множества У (см. определение 4.2.3).
Определение 1. Направление еФО назовем зозможяььм направлением убывания функции у(и) в точке и на множестве у, если е — возможное направление в точке и и 1(и+ ае) < у(и) при всех сс, 0<а< р, где 0< (1 < с,. Метод возможных направлений основан на следующей естественной и прозрачной идее: на ка5кдой итерации этого метода определяется возможное направление убывания функции и по етому направлению осуществляется спуск с некоторым положительным шагом.
Собственно говоря, зта идея для нас уже не новая — именно на ней были основаны многие варианты изложенных в $1, 2, 4 методов. В самом деле, если У Е", У'(и)чь 'Ф'О, то возможное направление убывания функции легко находится — это направление антиградиента е = — Х'(и). Более трудным был выбор возможного направления убывания в методах $2, 4: в методе проекции градиента (см.
формулы (2.2) и (2.2') ) для этого нужно было проектировать точку на исходное множество У, а в методе условного градиента — решать задачу минимизации линейной функции на множестве У (см. задачу (4.3)). Понятно, что если задача выбора возможного направления убывания на каждой итерации слишком сложна и требует решения вспомогательных задач минимизации, сравнимых по трудности, быть может, с исходной задачей, то такой метод минимизации будет малоэффективным. Возникает вопрос: нельзя ли указать простые и достаточно удобные для реализации на ЭВМ способы выбора возможных направлений убывания) Оказывается, для достаточно широких классов гладких задач такие способы существуют.
Покажем зто на примере следувнцей задачи: У(и)- ш1; иш У=(НЕЕ": б,(и)(0, 1=1, ..., т), (1) где функции У(и), «;(и) (1=1, ..., т), определены на всем пространстве Е" и,1(и), я,(и) ш С'(У). Чтобы проще было пояснить суть метода возможных направлений для задачи (1), сначала опишем более простой вариант этого метода.
Пусть и,~ У вЂ” некоторое начальное приближение. Пусть иавестно к-е приближение и,шУ (й>0). Введем множество номеров 1„= П: 1 < 1 < т, я~ (и,) = 0). Возможно, что 1,= И,— это будет означать, что я,(иА)<0 при всех 5'=1, ..., и, т. е. и,~и(пьУ вЂ” такая воэможность ниже не 300 МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ [ГЛ, Д исключается. В пространстве переменных е =(е, а) =(е', ..., е", о) 1Е Е"+' рассмотрим вспомогательную задачу а - 1в1, е =(е, а)ш И', ((е, о): <1'(и,), е> < а, <ед(ид), е) <<а, уя1д, ~еу[(1, у = 1, °, и). (2) Заметим, что аадача (2) является задачей линейного програм- мирования, причем минимизируемая функция <с, г> =<О, е>+ +1 о, с (О, 1)шЕ"+', явно не зависит от переменных е(е', ..., е"). Далее, ясно, что точка з (е=О, а 0)=(0, 0)ш ди дт'„, так что И~дед 9 и 1п1а = ад~ (0 при всех й = О, 1, ...
Очежд видно, множество И'„замкнуто. Наконец, условия И <1 (у = 1, ..., и), называемые условиями нормировки, гарантируют ограниченность множества И'д. Тогда из теоремы 2.11 следует, что задача (2) имеет хотя бы одно решение. Для получения решения задачи (2) могут быть использованы известные конеч- ные методы линейного программирования (например, симплекс- метод, описанный в гл.
3). Предположим, что задача (2) решена и найдены (е„, а,)ж шИ'д такие, что ад =(в1а. Выше было замечено, что о,<0. '~'д Сначала рассмотрим случай а,<0. Оказывается, в этом слу- чае направление ед, полученное из задачи (2), является возмож- ным направлением убывания функции 1(и) в точке и„.
В самом деле, из условия (е„, од) ш И/д следует, что <1'(ид), ед><ад<0, (бд(ид), ед) <од<0, ден1д. Отсюда Ясно, что едчьО. КРоме того, длЯ любого номеРа уди 1, имеем (д(ид+ аед) = яд(ид + аед) — ед(ид) = (д(ид), ед) а + о(а) ( (а[ад+ о(а)/а) <О при всех а, 0(а<а<, ад~О. Если 1Ф 1,, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
