Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 85
Текст из файла (страница 85)
После опре- деления и,+» точка ),ь+, находится по формуле Х,~! =()»,+Ад(~,+!))+. (14) Правила получения (к+1)-го приближения из+» ш У», Х»+ шЛ» изложены. Описанный метод кратко будем называть методом (13), (14). Для по- следования сходпмостк метода (13), (14) кам понадобятся некоторые свой- стве функции а+, определеввой равенствами (9). Из теоремы 4.4.2 сле- дует, что 366 ми?Оды минимизации Функций многих Переменных [Гл, в н.
в, у, ~ О. Если же Х» > О, то из (17') следует О ( Л< = (Л<+ Ау<)+ = = Х<+ Ау„что воаможно лишь прн у< = О и Х<у< = О. Эквивалентность (16) и (1?) доказана. Далее, пользуясь определением (9) функции а+,нетрудно получить, что (а+, а) = (а+, а+), (а+, Ь) ((а+, Ь+) »<а< Ь ен Е". Отсюда имеем (а+ — Ь+, а — Ь) = (а+, а) + (Ь+, Ь) — (а+, Ь) — (Ь+, а) )~ > (а+, а+) + (Ь+, Ь+) — (а+, Ь+) — (Ь+, а+) = (а+ — Ь+, а+ — Ь+), н. е. +! "ь иа! + А (рь — Л„(, у=О, 1, ... (29) Согласно лемме 4.9А существование седловой точки (ив, Лч) в аадаче (6) зквивалентно соотношениям Е (и„Л') ( 6 (и, Л*) и и Пе, у(и )(О, Х*>О, Хоу(и )=О, <=1, ..., т.
(21) (22) В силу эквивалентности соотношений (16), (17) условия (22) можно переписать в следующей равносильной форме; Х* = (Ло + АУ (ио])+. (23) (а+ — Ь+, а — Ь) > (а+ — Ь+, а+ — Ь+). (18) Теорема 1. Пусть Уо — вотуклов гамкиутов г<ножвство ив Е" (иа яримвр, Уо Е"), <рункции 1(и), у»(и), ..., уы(и) выкуклы иа По и принадлвжат классу С»(([о), г'о > — аг, Уо.Ф 8, функция Лагранжа (7) имеет хотя бы одну свдловую точку (ио, Х") <н Ь» Х Ло в смысле неравенств (3). Пусть, кроме того, коглгдоватгльность (6<) ив (13) нготрицатвлъна и ° о ~~'! 6Ь ( оо.
Тогда коглвдоватвльиость ((аг, Хо)), удовлетворяющая услса-е виям (13), (14), кри любом выборе нач льиых (ио, Ло) ш Уо )( Ло и любых [рикгированных карамгтрах и > О, А > О существует и сходится к некоторой сгдловой точке <рункции Лагранжа (7). Дока з а те лье тв о. Прн сделанных предположениях функция дг(и, Л) выпукла по переменной ион Уг при всех Х<иЛ„А > О, поэтому при любых и< ш Уо, Ло <н Ло, а > О, А > О функция <ро(и), определяется формулой (11), сильно выпукла на Уо с константой сильной выпуклости н = 1(2. Отсюда и из теоремы 4.3.1 следует, что точка во, удовлетворяющая условиям (12), существует и определяется одноаначно.
Тогда существует и точка и<+<, удовлетворяющая условиям (13): например, в (13) можно взять и<+< оо. Здесь важно заметить, что многие из ойисанных вьппе методов минимизации для задачи (12) сходятся и при любом бо > О позволяют получить точку шл, из (13) за конечное число итераций.
Таким образом, при выполнении условий теоремы последовательность ((ио, Хь)] существует и имеются достаточно аффективные способы реализации каждой итерации метода (13), (14). Наряду с точкой Хо+<, определяемой по формуле (14), введем еще точку рь = (Ло+ Ау(ио))+, Ь = О, 1, ... (19) Покажем, что для любой седловой точки (ио, Хг) функции Лагранжа (7] справедливо неравенство а з з ! а ! + А!)а — Л ! >! "ь — и ! +А!Ра — ) !+ ыитод модифицированных м'нкций ллгглнжл Эц 6 1а) Кроме того, функция Ь(и, Х») выпукла на Уь и принадлежит С'(Уь), а тоги да согласно теореме 4.2.3 неравенство (21) эквивалентно условию (Ь (и, )ь»), и — и»] = (Х' (и ) + (д' (и ))гй», и — и») ~ О при всех и ьм У».
Отсюда с учетом равенства (23) имеем (о'(и ) +(я' (и,)) (Х»+ Ау(и»))+, и — и ) ~ О, иеи У . (24) Далее, из условия (12) и теоремы 4.2.3 следует 'ь д(од)ь и — дГ>О, импе Отсюда с учетом формулы (10) получим (оь — иь+ иу'(оь) + а(6'(оь))" (Ха+Ау(од))», и — оь> )О, иьин» (25] Примем в (24) и = оь, умножим ото неравенство на а ) О и сложим с не- равенством (25) при и = и . Получим (од — ид+ а (Х' (од) — Х' (и»)) + а (д' (од)) (ад+ Ау (од))+— — а(д'(и»)) (Х»+Ад(и»))+, и,— од)~0, й 0,1... Отсюда имеем ~од — ид, и — од]) а (Х'(од) — Х'(и„), о, — и»]+ + а ((ха+ Ад(од))+, л' (од) (од — и»))— — а((Х»+ Ау(и»))+, д'(и„) (од — и»)), й О, 1, „, (26) Так как функции Х(и), уь(и) выпуклы, то согласно теореме 4.2.4 (Х' (од) — Х' (и„), од — и»2 )~ О, Л' (од) (од — и») ~ )д (од) — у (и,) Ъ д' (и») (од — и»).
Отсюда и из (26) следует (од — и„, и» вЂ” од] ) а ((Хд + Ад (од))+ — (Х» + Ад (и ))+, я (о,) — д (и»)у=» =А ((йд+АУ (од))~ — О,»+АУ(и ))+, [(Ха+Ад(од)) — Рд) — ((й»+Ад(и»)) — ]»)). К праьой части атой оценки применим неравенство (18). С учетом форму лы (19), определяющей точку рь, и равенства (23) получим (од — ид, и» од) ив йь 1 ((йд+ А» (од))+ — (л~+ АЫ (и»)) ь [(лд+ А» (од))+ — Хд]— — [(й»+ Ад(и,))+ — д»)У = А (Рд — Зь»ь Рд — лд]ь (од — и,, и» вЂ” од'ь+А (Рд — )ьд, Х» — Рд]))0, й О, 1...
(27) Справедливы тон<лестна [ и — и [ =[(ид — о,)+(од — и»))»=[од — ид[т+[и„— од[~+2(од — ид, и» вЂ” од)ь [)ьь — Х»(' = (рь — дь( + ()ь» — рь[ь+ 2<рь — Ль, )ь» — Ид]. 362 ынтодтя ынннынвз цнм югнкцнн многих цнркыкннгях !гн. з Ь-О, 1,..., РО) (31) Напомним, что по условию ~ бз ( е». Таким образом, последователь. а-о ности (зь), (юь), (бь) удовлетворяют условиям леммы 2.3.10. Для полной строгости, конечно, нужно заметить, что в неравенствах (2.3.30), (2.3.31) использована евклйдова норма линейного пространства И"+, а в только что полученных неравенствах (30), (31) — норма (29). Тем не менее, рассуждая так же, как при доказательстве леммы 2.3АО, нетрудно показать, что существует конечный предел Иш)зь з»)! и, кроме того, а»» Иш '! и (32! з-»а» Заметим, что шш (1; а(А) ! з !' ий !(з!!з ( шах (1; а/А) ! з !', т. е.
нормы )з! и !Ы энвивалентны. Отсюда и из существования конечного предела Нш !(зд — з»!( следует, что последовательность (зь = (им Ль)) ш з е» ш О» х Лз ограничена в Е»+'" и из нее можно выбрать подпоследовательность (заг (иаг Ла„)), которая сходится в Е "+" к некоторой точке с» (а„, Ь»), причем а»шУе, Ь»еяй» в силу замкнутости Уе и Ли Покажем, что с» (а», Ь») — седловая точка функции Лагранжа (7). Из (зз ) -» с» и (31), (32) следует, что (юа ] -г с», (за + ~ -» с», Тогда из (14) при Ь = Ь, -»»» "г ° + получим Ь» = (Ь» + Ах (а»))+. (33) В силу аквивалентности соотношений (16) и (17) из (33) следует 8(а)<О, Ь >О, Ьл (а)=О, 1=1,...,ю. (34) Умножим второе ие этих тождеств на и/А и сложим с первым.
Отсюда с учетом оценки (27) получим обещанное неравенство (20). Далее, покажем, что (иь»~ гь! ~ бь (Л»»1 — рз! ~ (2бм Ь = О, 1..., (28) Поснольку функция Фь(и) сильно выпукла на (7и то с помощью творе. мы 4.3.1 и первого неравенства (13) получим ! иа+з "а Г/2 < фз (иа+г) 0'з ("а) < Ф2 что равносильно первой оценке (28). Из формул (14), (19), определяющих точки Лз+ь рь+и неравенства (15) и условий (13) следует )Лз+1 — дь! ( А (8(иь+~) — 8(иь) ! ( Аби Оценки (28) доказаны. В (и + ю)-мерном линейном пространстве И" +» переменных з = = (и, Л) = (и', ..., и", Ль ..., Л„) введем скалярное произведение 4(зи зз)) = (ии из) + (и/А) (Л', Лз) и соответствующую ему норму ()з!! =. (!иР+ (а/А) !Л(з)мз.
(29) Тогда, обозначив зз (иь, Ль), юе (им р»),з»=(и», Л»), неравепства (20) и (28) можем записать в виде (!зь — з»Р ~!!юь — з*Р+ (!и» вЂ” з»Р, !!г»»1 — юь!!~(Ап+1)бз, Ь О, 1, „. митод штРАФных Функции Далее, переходя в (25) к пределу при Ь Ь, -» оо, будем иметь (У'(а») + (Г'(ае)) (Ье+ Ая(а ))+, и — а ))О, и ~в бге, или с учетом (33) (У'(ае)+(Г'(а )) Ь», и — а ) =(бе(а», Ъ"), и — а )>О при всех и ш Уе. В силу выпуклости ь(и, Ь*) последнее неравенство зкви валентно неравенству У(а~,Ь)<б(и,Ь), иаУш (35) Из соотношений (34), (35) и леммы 4.9А следует, что се (ае, Ье)— седловая точка функции б(и, Х) в смысле неравенств (3), а тогда согласно теореме 4.9.1 ее — решенпе задачи (6). Заметим, что неравенство (30) верно для любой седловой точки, в частности, ойо верно и для найденной точки се = (а„, Ь»).Поэтому существует конечный предел 1(ш((зд се(, причем в силу определения точки се ь-ко имеем 11ш [)зд — с»))= )пп((зз — с»~ О. Это значит, что вся последов-к» г.»» з вательность (гз (из, Хз)) сходится в точке с»=(ае, Ь"), и, в частности, (из) сходится к ае — решению задачи (6).
Теорема 1 доказана. Другие методы поиска седловой точки функции Лагранжа, другие методы решения задачи (1) или (6), основанные на связи между двойствен ными задачами (см, теорему 4.9.6), а такнге библиографию по таким мего. дам читатель найдет в [8, 29, 111, 116, 152, 330). 9 14. Метод штрафных функций 1. Метод штрафных функций является одним из наиболее простых и широко применяемых методов решения задач минимизаци. Основная идея метода заключается в сведении исходной задачи Х(и)- ш1; иш У к последовательности задач минимизации Фз(и)- ш1; иш У„я=О, 1, ..., (2) где Ф„(и) — некоторая вспомогательная функция, а множество У, содержит У.
При атом функция Ф,(и) подбирается так, чтобы она с ростом номера й мало отличалась от исходной функции У(и) на множестве У и быстро возрастала на множестве Уз~У. Можно ожидать, что быстрый рост функции Фз(и) вне У приведет к тому, что при больших й нижняя грань этой функ ции на У, будет достигаться в точках, близких ко множеству У, и решение задачи (2) будет приближаться к решению вада чи (1). Кроме того, как увидим ниже, имеется достаточно ши рокий произвол в выборе функций Ф,(и) и множества У, для задач (2), и можно надеяться на то, что задачи (2) удастся составить более простыми по сравнению с задачей (1) и допуска юп(ими применение несложных методов минимизации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
