Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 70
Текст из файла (страница 70)
Если <» = (и ш Е": ! и — о, ! < г) — шар радиуса г с центром в точке Р„то с помощью неравенства Коши — БУнЯковского <з'(ид), и> = <У'(ид), и — Р,>+ + <у'(ид), п,> ~ — !у'(ид) !г+ <»'(и„), п,>, и»и у, получаем, что й, = о. — гз'(и,) У'(и,) (-'. Разумеется, так просто получить вспомогательное приближение й, удается далеко не всегда, и вместо точного решения аадачи (3) часто приходится довольствоваться определением какого-либо приближенного решения. А именно, будем предполагать, что оно определяется из следующих условий: иден У, Уд(ид) <ппп Хд(и) + ед, ед' » О, 11шед = О. (4) и д сю Допустим, что точка й„удовлетворяющая условиям (4) (илп (3)), уже найдена.
Тогда следующее (й+1)-е приближение будем искать в виде иди = ид+ ад (йд — ид), 0 < ад < 1. (5) В силу выпуклости множества».» всегда и,+, ш <». Заметим, что при й,=и„(это может случиться, например, когда з'(ид)=0) имеем и„+,=и, независимо от способа выбора а, в (5). Если при этом и, было определено точно из условий (3), то имеем Хд(ид) = Хд(ид) = 0 = ш1п Хд(и) или <,»"'(ид), и — ид>)0 и при всех иш У. Согласно теореме 4.2.3 это означает, что точка и„удовлетворяет необходимому условию минимума в задаче (1).
В этом случае итерации прекращаются, и для выяснения того, будет лп идя(»д, при необходимости проводится дополнительное исследование поведения функции з(и) в окрестности точки и,. В частности, если У(и) выпукла, то согласно теореме 4.2.3 идее <»д, т. е. Задача (1) решена. Если случай й„=и, реализовался при определении йд из условия (4), то будем иметь — ед~ш(п.»д(и)(Хд(ид) = Хд(ид) = О,и при ед) 0 здесь тео- и метОд услОВнОГО гтьдивнтА рему 4.2.3 применять нельзя. В этом случае согласно (5) полагаем и„+, =и, и переходим к проверке условия (4) для номера й+ 1 и т.
д. В вависимости от способа выбора величины ад в (5) можно получить различные варианты описанного метода, часто именуемого в литературе методом условного градиента. Укажем некоторые наиболее употребительные способы выбора ад в (5). 1) Величина а, может выбираться иа условий О ( ад ( 1, ~д (ад) = шш Дд (а) = 7до, 7д (а) =Х (ид + а(ид — ид)). осасд (6) Для некоторых классов задач удается получить иа (6) явное выражение для а„. Пример 1. Пусть с (и) = — <Аи, и) — (Ь, и), 1 где А — симметричная положительно определенная матрица порядка п >< п, Ь ов Е".
Тогда 7'(ид) Аи, — Ь. Пользуясь формулой (4.2АО), имеем Яа) 7(ид)+а<о'(ид), й,— и,>+ + (ао/2) <А (йд — ид), й„— и,>. (7) О, ад<0, ад = ад, 0<ад(1,, ад > 1. (8) Кстати, если точка й„в (7) найдена из условий (3), то Хд(йд)~ ~Яд(ид)=0 и, следовательно, ад>0 — в этом случае формула Э (8) для а, запишется в виде ад = шш (1; ад).
Однако точное определение а, нз условия (6) возможно далеко не всегда. Поэтому вместо (6) можно ограничиться определением величины а„из условий 0<~ад(<1; Уд(ад)(~ада+ бю бд >О, ~ бд= 5<со (9) д-о Если <А (йд — ид), й„— и„> = О, то и„= йд и, как было укааано выше, тогда полагаем и,+, — — и„. Поэтому пусть <А(йд — ид), й„— — и„> >О. Тогда функция (7) представляет собой квадратный трехчлен, достигающий своего наименьшего значения на числовой оси — < а <+ при ад = — <.)" (ид), ид — ид) ((А (ид — ид), ид — ид)) ~. о о Ф Рассматривая возможные случаи ад<0, 0(ад<1, ад>1, из условий (6) тогда получаем 294 методы минимиздции ФункциЙ многих пеРеменных 7гл, д и ли 0(ад((1, Хд(ад) (~(1 — Лд) Хд(0) + Лье„, 0 ( Л( (Л7, ~ ~1.
Здесь могут быть использованы известные методы минимизации функций одной переменной (например, методы из гл. 1). 2) Если Х(и)7ИС''((Х) и константа Липшица Ь для Х'(и) известна, то возможен выбор а, в (5) из условий ад = шш(1; рд~Хд(ид)иид — ид|-г), Хд(ид)(0, (10) О, Хд(ид))0, где 0 < ею < рд < 2 (1 — з) /Ь, (11) Рис. 6.6 в„е — параметры метода, 0 ( е < 1. 3) Другой способ выбора а,: прн Х,(й,))0 полагают а, О, а если Х,(й„) < О, то ад = Л ',где 1, — минимальный номер среди номеров ъ 'л- О, удовлетворяющих условию Х(ид) Х(ид+ Л (ид ид) ) ~ Л з7Хд(йд)! где Л, з — параъгетры метода, 0<Л; е(1. 4) Величины а„в (5) можно априорно задавать из условий С 0(ад~(1, 11шад= О, ~~Р~ ад= со7 (12) д-~ФО д о например, ад=(к+1) ' (77=0, 1, ...) (предложен М. Ячимовичем). Такой выбор а, очень прост для реалиаации на ЭВМ, но, вообще говоря, не гарантирует выполнение условия монотонности 77' Х(и,д,) < Х(и,).
5) Возможны и другие способы выбора а„в (5). Например, можно задавать а, = 1 и прове- 777 .' Вг рать условие монотонности Х(и,д,) < Х(и,), а затем при необходимости дробить а„до тех пор, пока не выполнится условие монотонности. На рнс. 5.6 поясняется геометрический смысл метода (3), (5) в двумерном случае. 2. Рассмотрим теперь сходимость метода (4), (5), (9). Теорема 1.
Пусть П вЂ” выпуклое замкнутое ограниченное мнолсество из Е", 1бунк7(ия Х(и)7ИС''(П). Тогда при любом выборе и,7и П для последовательности (и„), определяемой условиями (4), (5), (9), справедливы равенства 1пп (Х'(ид), ид — ид> = О, 11ш р(ию Яв) = О, (13) д+оэ д ю МЕТОД УСЛОВНОГО ГРАДИЕНТА 295 где Яв = (и: и я (/, <./' (и), о — и))0 при всех оси с/) — множество стационарных точек функции /(и) на </, Если, кроме перечисленных условий, /(и) выпукла на с/ и ес+ бл ~ <Ссй со, Сс = сопзсо) О, 1/2 < Р ~ <1, (14) то (15) Пш / (иь) = Хе, 1пп р (ид, (/ ) = О, Й-»со Ь со и справедлива оценка 0< /(иь) — / =. С„й е, й = 1, 2, ...; С, = сопз1) О. (16) Наконец, если, кроме того, Х(и) сильно выпукла на </, то )и„— и (г((С,/к)й Р, й = 1, 2, ...
(17) Доказательство. При сделанных предположениях /в) ) — со, Не чь Я. Так как множество с/ огРаничено, то впр ~ и — о) (~ й < со.ИВ условия (9) следует./(ид+г)=/ь(аь) ~( о,оап (/го+ бь(о (и„+ а(и„— иь)) + бь при всех а (0<а<1).
Поэтому пользуясь неравенством (2.3.7), имеем /(и„) — /(и„+,)+ 6, > /(и„) — 7(и, + а(й„— и„) ) > > — а<У'(ис), йь — ис> — а~И йа — иоР/2 > > — а/,(й,) — а*Бас/2, 0<а<1, й=О, 1, ... (18) Множество дс (О, 1, 2, ...) разобьем на два множества 1т+ = (й: й ~н /т', </' (и,), й„— и„> =» 0) и /ч' //'Р/+. Так как 1п1 Хь(и)(гь(и„) = О, то ив (4) получаем 0</„(й„)< з„при всех й ся Р/+. Поэтому если /т+ — бесконечное множество, то /, (й,) - 0 при й - оо, й сн 6/+. Теперь пусть /с — 1т' . Тогда из (18) имеем 0 < — /ь(й„) <(/(и,) — /(икы)+ 6,)/сс+ аЕсу/2 (19) при всех а (О < а < 1), /с си 1т'-. Далее, из (9) следует, что !(и»+с) </(ис)+6„(й= О, 1, ...).
Так как Х (ид) )~ /е) — со (й= О, 1, ...), то из леммы 2.3.2 вытекает существование ко« печного предела Иш /(иь) ) г . Следовательно, 11ш (Х (и„)— ь-» А~со — Х(ид+,)) =О. Если Л' — бесконечное множество, то при ййс/т', из (19) имеем 0(1пп ) Хь(и„)1(11ш ) Хь(иь)) (аЫг/2 й- при всех а (0<а<1). Устремляя а- +О, отсюда получим Хс(й„)- 0 при й-, йж/т'-.
Объединяя оба случая йснд/+ и йсв)т'-, приходим к первому равенству (13). Так как с/ ограничено и (и„) си с/, то последовательность (и,) имеет хотя бы одну 296 мктоды минимизации Фгнкцпн многих пвввмкнных [гл, 3 предельную точку. Пусть ид — произвольная предельная точка (и,), пусть (ид ) -».ид. Согласно (4) 1»(ид) — сд(1в1.1»(и)( ((.1'(ид), и — ид,» при всех и~ С и й= О, 1, ... Отсюда при й = й — с учетом первого равенства (13) получим, что (1'(и„), и — и ',»)0 при всех и~ С. Тем самым показано, что любая предельная точка последовательности (и„) принадлежит Б .
Отсюда следует второе равенство (13). Пусть теперь 1(и) выпукла на С и ид — произвольная точка из 11 . Тогда из теоремы 4.2.2 и условия (4) имеем 0(ад = 1(ид) — 1(ид) ((1' (ид), ид — ид) = = — 1» (и. ) ( — шш 1» (и) ( — 1» (ид) + сд, й = О, 1..., (20) и Отсюда и из первого равенства (13) следует 1пв Х(ид) = Ую т. е. (и,) — минимизирующая последовательность. Из теоремы 2АА тогда получаем Пшр(ию С ) =О.
Равенства (15) доказаны. Зад метим, что неравенство (20) может служить полезной апосте- риорной оценкой прн практическом использовании метода (4), (5), (О). Остается получить опенку (16). Для етого множество 11' ° (О, 1, 2, ...) разобъем на два множества 1,-(й: йю61, а») >з»),1, (й: йе11»1, 0<а»<с»).
Из оценки О~а» е»~~ 1»(й»)~ й»и1», (21) Отсюда и из (21) с учетом условия (14) имеем ад+1(~ад — (ад — сд)д~(21йд) + 6» — ад11(2Ы') + + (япр ад) Ь 'д 'ед + 6»(ад — ад/А + Ай '~, ~ дэд й ~ 1„(23) где А = шах (21а', (япр ад) Ь 'а 'Сд; С,). ~»~о Если й~ 1о то О~а»< з,<С,й-". Кроме того, из (18) при а +О получим а„— а„+,+6»)0 или а„+,<а»+6»<а»+С,й" для всех й =О, 1, ... Таким образом, последовательность (а,) являдощейся следствием неравенства (20), следует, что 1,— )1' . Поэтому (18) можно переписать в видо ໠— а„+, > а~1„(й»)! — сс'Лй»/2 — 6», 0 < а < 1, й ш 1,.
(22) Так как в силу (13) (У»(й,) П ограничена, то взяв при необходимости й еще большим, можем сделать 0 ( а» = У»(й») Ы Ч ' < при всех й О, 1, ... Принимая в (22) а=а„, получим а„— а»+, > 1/(21й') ~1„(и») Р— 6» й я1,. й л! мнтод услсвнОГО ГРАдиннтА 297 удовлетворяет условиям леммы 2.3.5, иэ которой следует оценка (16). Наконец, оценка (17) вытекает из неравенства (4.3.2) и оценки (16). Теорема 1 доказана.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
