Ф.П. Васильев - Методы оптимизации (1125241), страница 80
Текст из файла (страница 80)
(26) к се Х 3) Наконец, если Уй (хй) > О, то согласно (10) и из (24) имеем О < Уй(хй) < е .. (28) Из (25)-(27) вытекает, что последовательность (У(хй)) не возрастает. Так как У(хй) ) У„ > > -оо, то существует !$т У(хй) >У„и, следовательно, $$гп (У(хй) — У(х $)) =О.
Отсюда й сс й й+! и иэ (25), (26), (28) имеем 0 < )Уй(жй)! ( гпах(г„; сопз1.(У(хй) — У(хй, $))$/2) — с 0 при всех й сои. Первое из равенств (!3) доказано. Второе равенство (1 3) устанавливается так же, как в теореме 1. Пусть теперь функция У(ж) выпукла на Х. Тогда справедлива цепочка неравенств (20), иэ которой следуют равенства (1 5). Предполагая, что ей < С„ й яг, 0< р < 1, докажем оценку (1 6). Предварительно заметим, что 0 ( ай — — У(жй) — У„ < зир У(х) — у, = Сэ < сю, поэтому Х Еще раэ переберем рассмотренные выше три воэможности. 1) Если /й(хй) < О, а, = 1 ( рй/Уй(хй)//хй — хй/ 2, то иэ (20), (25), (29) имеем а — а ) В гай — ггй или й й й й4$" ай „$ < ай — гай -$- сей < ай — ай (г/Сз) -$- еСой 2 (ЗО) 2) Пусть Уй(ай) < О, ай — — рйД/й(хй)с$!хй — хй! 2 < 1. Здесь, в свеса очередь, имеются две возможности; ай > гй или 0 < ай < гс,.
Если ай > гй, то из (20), (26), 0 < а, < Сэ получим ай — айс $ >(ай — гй) й гог) азйд еог — 2Сзгйс1 эе г или $ (ай — ай(гог/д )4-2Сэгогд эсой эг (3!) Если же 0 < ай ( ей, то достаточно воспользоваться более простым следствием (26): ай+ $ < ай. Последние два неравенства можно переписать в виде 0(ай <Сей эг, ай (а <а,-$-Сей 3) Наконец, пусть Уй(х ) > О, а, = О.
Тогда иэ (20), (27) получим 0 < ай < гй, ай+ $ ( ай что снова приведет к неравенствам (32). Из (30)-(32) следует, что последовательность (ай) удовлетворяет условиям леммы 2.6.5, на которой получаем оценку (16). Теорема 2 доказана. П 4. Наконец, рассмотрим вариант метода условного градиента (4), (5),(12) 17831. Те о ре ма 3. Пусть Х вЂ” выпуклое замкнутое ограниченное множество иэ Бч, функция У(х) с С$' '(Х) и гыпукла на Х, Тогда при любом хо с Х для последогательнос и (хй), определяемой условиями (4),(5), (12), слрсгедлигы рагенстга (15), Если при этом ай — — (й -$-1) ', гй — — Сэ(й -$-1) ', й =О, 1,..., то 0 < У(хй) — У„Я С41п (й+ 1)/й, й = 1, 2, (33) а если ай =(й+ 1) р, ей = Сз(й 4!) л, й =О, 1,..., 0($3 (1, то здесь С, С4 — некоторые положительные постоянньсе, Доказательство. Заметим, что неравенства (20), (24) не зависят от способа выбора 3 4 ай, 0~ (ай < 1, в (5), поэтому сохраняют силу и в рассматриваемом случае.
Из них имеем ай — ай „$ ) ай(аь — ей) — ой Ьй /2 или 2 2 ай с $ <(1 — ай)ай +айьд /2+ асей, й =0,1, 2 2 Отсюда с учетом свойств последовательностей (ай), (гй) из (4), (12) заключаем, что (ай) удовлетворяет условиям леммы 2.6.6. Поэтому йш ай — — 0 или 1$ш У(хй) = У„. Отсюда и из й сс й сс теоремы 2.1.! получаем равенства (15). Оценки (33), (34) следуют из лемм 2.6.8, 2.6.9. 1. Вычислить несколько итераций метода (3), (5), (6) для функции У(и) =х +ху+ у при 2 2 и е Х =(и =(х, у) еН2: 0< а < 1, -1 < у <0), выбирая нов - (1, -1),( — 1, 0), (1,0) или (О 0). 2.
Для функции из примера 1 проверить выполнение условий теорем 1-3 и сформулировать условия сходимости соответствующих вариантов метода условного градиента. 3. Дать описание различных вариантов метода условного градиента для функции У(х) = = )Лх — Ь(2, где Л вЂ” матрица т х и, 6 с Е"', а множество Х является шаром или параллелепипедом. Опираясь на теоремы 1-3, доказать сходимость метода. 9 б. Метод возможных направлений 1. Продолжим рассмотрение задачи минимизации гладкой функции У(а) на заданном множестве Х С Е".
Напомним, что направление е ~ О называется возможным в точке а е Х, если ж + йе Е Х при всех 8, О < 8 < го, где Уо — положительное число, зависящее от точки х, направления е и от структуры множества Х (см. определение 4.2.3). Определение 1. Направление ефО назовем возможным направлением убывания функции /(ж) точке ж на множестве Х, если е — возможное направление в точке х и У"(х+ ае) <У(х) при всех а, О < а < $3, где О < /3 < Уо. Метод возможных направлений основан на следующей естественной и прозрачной идее: на каждой итерации этого метода определяется возможное направление убывания функции, и по этому направлению осуществляется спуск с некоторым положительным шагом.
Собственно говоря, эта идея для нас уже не новая — именно на ней были основаны многие варианты изложенных в 9 1, 2, 4 методов. В самом деле, если Х =Е", /'(ж) фО, 271 2?О Гл. З. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ 4 з. метОд ВОзмОжных нАпРАВлений то возможное направление убывания функции легко находится — это направление антиградиента е = — /'(х). Более трудным был выбор возможного направления убывания в методах $2, 4: в методе проекция градиента (см. формулы (2.2) и (2.2')) для этого нужно было проектировать точку на исходное множество Х, а в методе условного градиента — решать задачу минимизации линейной функции на множестве Х (см.
задачу (4.3)). Понятно, что если задача выбора возможного направления убывания на каждой итерации слишком сложна и требует решения вспомогательных задач минимизации, сравнимых по трудности, быть может, с исходной задачей, то такой метод минимизации будет малоэффективным. Возникает вопрос: нельзя ли указать простые и достаточно удобные для реализации на ЭВМ способы выбора возможных направлений убывания? Оказывается, для достаточно широких классов гладких задач такие способы существуют.
Покажем это на примере следующей задачи; ,1(х) — ~!и1; хЕ Х=(хЕЕ": д,.(х) <О, г =1,..., гтс), (1) где функции /(х), дс(х), 1 = 1,..., тп, определены на всем пространстве Е" и /(х), д,(х) е Сг(Х). Чтобы проще было пояснить суть метода возможных направлений для задачи (1), сначала опишем более простой вариант этого метода. Пусть х, Е Х вЂ” некоторое начальное приближение.
Пусть известно !с-е приближение х„ Е Х, й > О. Введем множество номеров 1„= (1: 1 < с < т, д, (х„) = О) Возможно, что 1„= О, — это будет означать, что дс(х,) < 0 при всех т' = = 1,..., тп, т. е. х„е !п! Х вЂ” такая возможность ниже не исклгочается. В пространстве переменных л = (е, сг) = (е',, е", о) Е Е "+' рассмотрим вспомогательную задачу о — !и1, г = (е, сг) е Иг = ((е, сг)'.
(1 (хс), е) < о, (д,.'(хл), е) < о, г Е 1„; [е'~ < 1, г' = 1,..., п1. (2) Заметим, что задача (2) является задачей линейного программирования, причем минимизируемая функция (с, г) = (О, е) + 1 о, с = (О,!) Е Е" +', явно не зависит от переменных е = (е',..., е"), Далее, ясно, что точка л = (е = О, сг = 0) = (О, 0) Е Иг„, так что Иг, ф И и !и!ст =.о, < 0 при всех !с = О, 1,... Очевидно, множество Игл замкнУто. Наконец, УсловиЯ !е'~ < 1, д' = !,...,п, называемые условиями нормировки, гарантируют ограниченность множества И',, Тогда из теоремы 2.1.1 следует, что задача (2) имеет хотя бы одно решение, Для получения решения задачи (2) могут быть использованы известные конечные методы линейного программирования (например, симплекс-метод, описанный в гл. 3). Предположим, что задача (2) решена и найдены (е...тл) е Ил такие, что о; = !п! с .
Выше было замечено, что с„< О. Сначала рассмотрим случай оь < О. Оказывается, в этом случае направление е, полученное из задачи (2), является возможным направлением у ыв н бывания функции /(х) в точке х„. В самом деле, из Условия (еы ~л) следует, что (/г(х„), е ) < о <О, (д,.!(хс)г еь) < (сгл < О, т Е 1,. Отсюда ясно, что е, ~ О, Кроме того, для любого номера г е 1, имеем д (х„+ ое,) = д (х, + ое„) — д (х„) = (д,'(х.), е,) а + о(о) < < а[сг„+о(а)/а) <О при всех а, О< а < а а >0 Если т' ф.1, т.
е. дс(хл) < О, то в силу непрерывности функции дс(х) нера- венство дс(ха+ ае,) < 0 сохранится при всех о, 0 < а < ас, где ас > О— достаточно малое число. Положим ао = ш!п(а„..., а„) > О. Тогда дс(х +аел)<0, 4=1,...,тп; 0<а<а, т. е. е„— возможное направление множества Х в точке х, Далее, взяв при необходимости число а, > 0 еще меньшим, можно до- биться выполнения неравенства /(ха + ое„) — 1(хл) = (1(хл), е,) а+ о(о) < < а[ол + о(а)/а] < 0 при всех а, 0 < а < а, Тем самым показано, что если (е,,сг„) — решение задачи (2), причем гг, < < О, то еь — возможное направленйе убывания функции /(х) в точке х„на множестве Х.
ее (гс 1)-е Используя найденное таким образом направление е„, следующее ( + )-е приближение определим так: х„л, =хл+ а„ес, 0< ал гглг < и !Зл = зпР(а; хл + !е Е Х, 0 < с < а) > О. (4) Выбирая а, в (3) различными способами, будем получать различные ва- риан ы ианты метода возможных направлений. Перечислим некоторые способы выбора а, 1) Величина аь может выбираться из условий 0 < а, < )Ус, д,(а )= !п1 д,(а)=д„,; д,(а)=/(хл+ае ). (5) 0«ял Для минимизации функции д (а) могут быть использованы известные ме(см., например, гл, 1).
Точное решение задачи (5) удается найти лишь тоды (с ., н в редких случаях; возможно также, что на некоторых направлен ниях е ве- личина !3, = оо и нижняя грань функции д,(а) при а > 0 не достигается. Поэтому вместо (5) на практике целесообразно употреблять такой способ выбора а,: 0< а„< !3, дл(аь) < дь.+ бю б„>0, ~" 6„= 6 <со (6) или а=о 1(хь + ал ел) < (1 — Л „)/(хл) + Ллдг„, 0 < Л < Л„< 1.
2) Если функция /(х) Е С" (Х) н константа Лнпшнца Ь для градиента /'(х) известна, то в (3) в качестве ал можно принять (! .;[;[ -') 272 Гк 5, МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ 273 $5, МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ 3) Возможен выбор величин ст„из следующих условий /(хл) — /(хл + сто ел) > гсс, ~пл~, 0 < ол < /Зо, 0 < г < 1/2 и — т !п1; г = (е, ст) е Ит, = ((е, о): (/'(х,), е) < о; (д,.'(х ), е) < о, ( е 1„/!е'! < 1т,7 = 1,..., п), (7) где 1, = ((: 1 < ( < тп, д (х ) = О), необходимо имеет решение (е„, о„) с ст„= ш!по = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
