Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 96
Текст из файла (страница 96)
= О, Л. > О, либо Л = О, дг < О, В каждом из этих случаев, очевидно, равенство (17) верно. Таким образом, из (11) следует (17), Докажем обратное. Пусть имеет место равенство (17). Распишем это равенство в координатной форме Лч =(Лч+Адч)ч=гпах(Лч+Ад<0), ч=1,...,т, (17') Отсюда ясно, что Лг > 0 при всех 4 = 1,..., эг, т. е. Лч ) О. Если Лч = О, то Лчд,, = О и, кроме того, иэ (17 ) полУчим 0= (О+ Ад!)ч = Лг+Адч, т. е. д, < О. Если хге Лч > О, то из (17 ) следУет 0 < Л =(Л,+Ад,.)+ = Лч+Адч, что возможно лишь при д; =0 и Лчд, =О. Эквивалентность (16) и (17) доказана.
Далее, пользуясь определением (9) функции а", нетрудно получить, что (а+, а) = (ач, а+), (а'", Ь) < (а+, 6~) Эа, Ь Е Е". Отсюда имеем (ат — Ь+, а — 6) = (а+, а) + (Ь+, Ь) — (а+, Ь) — (Ь+, а) ~) ) (ат, а+) + (Ь+, Ь+) — (а+, Ь+) — (Ь", а+) = (а+ — Ь+, а+ — Ь+), т, е.
(а+ — Ь+, а — 6) > (а+ — Ъ+, а+ — Ь "). (18) $14. МЕТОД МОДИФИЦИРОВАННЫХ ФУНКЦИЙ ЛАГРАНЖА 321 Те о р е м а 1. Пусть Хо — гьтуклое замкнутое множество из Еэ (например, Х =Еэ), о— функции 7(х), дгх),..., д (х) выпуклы на Хо и принадлежат классу С'(Хо), У > — со, Хф МЯ, функция Лагранжа(7) имеет хотя бы одну седлозую точку (х„Л*) еХ„хйо е смысле неравенств (3). Пусть, кроме того, последовательность (бь) из (!3) неотрицательна и бь < оо, Тогда последовательность ((хго Ль)), удозлетворлющал условиям (13), (!4), ь=-о лри любом выборе начальных (хо, Ло) е Хо кЛо и любы фиксированных параметрах а >О, А > О существует и сходится к некоторой сгдлозоб точке функции Лагранжа (7). Доказательство. При сделанных предположениях функция М(х, Л) выпукла по переменной х е Хо при всех Л е Ло, А > О, поэтому при любых хь е Х, Ль е Ло, а > О, А > 0 функция Фь(х), определяемая формулой (!1), сильно выпукла на Ло с константой сильной выпуклости к = !.
Отсюда и из теоремы 4.3.1 следует, что точка эь, удовлетворяющая условиям (12), существует и определяется однозначно. Тогда существует и точка хь э!, удовлетворяющая условиям (13): например, в (13) можно взять хь+ ! — — эь. Здесь важно заметить, что многие из описанных выше методов минимизации для задачи (12) сходятся и при любом б > 0 позволяют получить точку хь ч ! из (13) за конечное число итераций. Таким образом, прй выполнении условий теоремы последовательность Охь, Л„)) сугцествует и имеются достаточно э ективные способы реализации каждой итерации метода (13), (!4). аряду с точкой Ль т !, определяемой по формуле (14), введем еще точку „„=(Л,+Ад(,))', 6=0,1,...
(! 9) Покажем, что для любой седловой точки (х„Л') функции Лагранжа (7) справедливо неравен. ство ~хь-х.(зч-Я)ль-л*)з>)эь — х,~х+ — ")Рь — л*)зц)эь — ь)э+Я)мь — ль!', 6=0,1,... (20) Согласно лемме 4.9.2 существование седловой точки (х„Л*) в задаче (6) эквивалентно соот- ношениям (7'(х„) Ц (д'(х„)) Л*, х — х,) > 0 Чх Е ХО, (21) (22) В силу эквивалентности соотношений (16), (1?) условия (22) можно переписать в следующей равносильной форме: Л' = (Л' т Ад(х„))+.
Из (2!) с учетом равенства (23) имеем (г'(х ) -1- (д'(х„)) (Л*+ Ад(х,))+, х — х ) > О, Чх с Хо. (24) Далее, из условия (12) и теоремы 4.2.3 следует (Фь'(эь), * — эь) В )О, Лгх е Хо. Отсюда с учетом формулы (10) получим (эь — ха + ау'(эь)+ а(д'(эь)) (Ля + Ад(эь))+, х — эь) ) О, Лгх еХо' (25) Примем в (24) х = эь, умножим это неравенство на а > 0 и сложим с неравенством (25) при х = х,. Получим (эь ха+а(гг'(эь) У'(х ))+ "(д'(эь)) (Ль Ь 4д(эь)) Отсюда имеем — о(д (х )) (6*+Ад(х)]+, х„— э„) >О, 6 =0,1,... (эь — хь, х, — эь ) > а (г '(эь ) — 7'(х,), эь — х,) -1- а ((Л ь + Ад(эь))+, д'(э )(э — х„))— — а((Л" + Ад(х )) ', д'(х„)(эь — х,)), Ь = О, 1, (26) Так как функции 7" (х), д,(х) выпуклы, то согласно теореме 4.2.4 (7~(эь) — 7~(х ), эь — х„) > О, дг(эь)(эь — х,) > д(эь) — д(х,) > д'(х )(эь — х„). Отсюда и из (26) следует (эь — хь, х„— эь) ) а((Ль -1- Ад(эь))+ — (Л" + Ад(х ))+, д(эь) — д(х )) = = А ((Ль ЬАд(эь))+ — (Л'+Ад(х ))т, [(Ль-1-Ад(эь))-Ль) — (Л*+Ад(х,))-Л*)).
322 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ $14. МЕТОД МОДИФИЦИРОВАННЫХ ФУНКЦИЙ ЛАГРАНЖА 323 К правой части этой оценки применим неравенство (18). С учетом формулы (19), определяю- щеи точку рь, и равенства (23) получим (еь — хь, х, — еь) > Х((Ль + Ад(еь))+ — (Л* -!. Ад(х ))+, КЛь + Ад( юь))о — Ль[ [(Л'+ Ад(х ))" Ло)) = ~х(Рь Л Рь Ль)~ т. е. (еь — хь, х, — еь)+ А (Рь — Ль, Л" — Рь) >О, й =0,1,... (27) Справедливы тождества [хь — х,[2 = [(х„— е ) -1-(е„— х„)[2 = [е — ха!2+ [»„— е„[2+ 2(еь — х, х„— е ), [ль — л*[2 = [рь — ль[г+ [л' — рь[24 2(рь — ль, л' — рь). Умножим второе из этих тохсдеств на а/А и сложим с первым. Отсюда с учетом оценки (27) получим обещанное неравенство (20).
Далее, покажем, что [ха+! — еь! < 6ти [Ль ! — рь[ <А6,, !о =О 1 (28) Поскольку функция Ф (х) сильно выпукла на Хо, то с помощью теоремы 4.3.! и первого ь неравенства (13) получим [хь ! — еь! /2 ФФ»(хь „!) — Фь(еь) ( бь/2, 2 г что равносильно первой оценке (28), Иэ формул (14), (19), определяющих точки Ль о >, рь+ !, неравенства (15) и условий (13) следует [Ль „! — рь[ ( А[д(хь „!) — д(еа)! ( А 6„.
Оценки (28) доказаны, В (а+го)меРном пРостРанстве Е" о пеРеменных х=(х, Л) =(х',,. о х", Л>, .. о Л ) вве. дем скалярное произведение (х!, »2) =(х!, хг) ч. (а/А)(Л, Л ) и соответствующую ему норму ! 2 [!»[! = ([х[2-1- (а/А)[Л[2)>/г. (29) Тогда, обозначив х„= (хь, Ль), вь — — (еь, рь), »* = (»„Л*), неравенства (20) и (28) можем записать и виде .*[!'>[! ь, [[2+[[,— ь[[', й=о,1„, [[х„, вь[! <(А„+ !)6„, й =О,1,... (30) (31) Напомним, что по условию ~; бь <со, Таким образом, последовательности (хь), (вь), ь=о (6 ) удовлетворяют условиям леммы 2.6.10. Для полной строгости, конечно, нужна заметить, ь оэ что в неравенствах (2.6.30), (2.6.31) использована евклидова поэма пространства Е , а в только что полученных неравенствах (30), (31) — норма (29), !ем не менее, рассуждая так же, как при доказательстве леммы 2.6.10, нетрудно показать, что существует конечный предел !пп [[хь — х'[! и, кроме того, ь о !!гп [[вь — »э[[=0.
Ь оо Заметим, что ш!и(1; а/А)[х[~ ( [[»[[2 ( шах(1; а/А)[х[2, т. е. нормы [х[ и [[х[! эквивалентны. Ото!ода и из существования конечного предела Ош [[хь— — х*[[ следует, что последовательность (хь -— (хь, Ль)) с Хо х Ло ограничена в Ео+х и из и+в нее можно выбрать подпоследовательность (хь — — (хь, Ль )), которая сходится в Е к некоторой точке с* =(а„Ь*), причем аг е Хо, Ь~ еЛо в силу замкнутости Хо и Ло. Покажем, что с* = (а„Ь') — седловая точка функции Лагранжа (7). Иэ (хь ) — о с" и (31), (32) следует, что (вь ) ос*, (хь + !)-ос*. Тогда из (14) при й = й„-о со получим Ь'= (Ь'+ Ад(а„))+.
(33) В силу эквивалентности соотношений (!6) и (!7) из (33) следует д(а)<0, Ь" >О, Ьгд,,(а)=0, «=1,,еь Далее, переходя в (25) к пределу при й = й„ оса будем иметь (/'(а,)+ (д'(а,)) (Ь*+ Ад(а,))+, х — а,) > О, х е Хо, нли с учетом (33) (34) (/(а,)+(д'(а„)) Ь*, х — а„) >0 Чхв Хо. (35) Из соотношений (34), (35) и леммы 4.9.2 следует, что с* = (а„Ь*) — седловая точка функции Л(х, Л) в смысле неравенств (3), а тогда согласно теореме 4.9.1 получаем, что а„— решение задачи (6). Заметим, что неравенство (30) верно для я>сбой седловой точки, в частности, оно верно и для найденной точки с* = (а„, Ь*). Поэтому существует конечный предел !!ш [[х — с'[[, ь причем в силу определения точки с' имеем йш [!»„— с'[! = Ош [[хь — с*[! = О.
Это значит, что вся последовательность (хь — — (х„, Ль)) сходится к точке с' = (а„, Ь'), и, в частности, (хь) сходится к а„— решению задачи (6). Теорема 1 доказана. О Другие методы поиска седловой точки функции Лагранжа, другие методы решения задачи (1) или (6), основанные на связи между двойственными задачами (см. теорему 4,9.6), а также библиографию по таким методам читатель найдет в[24-26; 222; 234, 286, 344; 759]. В 15. Метод штрафных функций 1. Метод штрафных функций является одним из наиболее простых и широко применяемых методов решения задач минимизации. Основная идея метода заключается в сведении исходной задачи ,/(х) - !и[; х Е Х к последовательности задач минимизации Фь(х) — > !п[; х е Х, й = 1, 2,..., (2) где Ф.
(х) — некоторая вспомогательная функция, а множество Х, содержит Х. При этом функция Ф„(х) подбирается так, чтобы она с ростом номера й мало отличалась от исходной функции /(х) на множестве Х и быстро возрастала на множестве Хо 'Л Х. Можно ожидать, что быстрый рост функции Ф,(х) вне Х приведет к тому, что при больших й нижняя грань втой функции на Х, будет достигаться в точках, близких ко множеству Х, и решение задачй (2) будет приближаться к решению задачи (1). Кроме того, как увидим ниже, имеется достаточно широкий произвол в выборе функций Ф„(х) и множества Х, для задач (2), и можно надеяться на то, что задачи (2) удастся составить более простыми по сравнению с задачей (1) и допускающими применение несложных методов минимизации.
О п р е д е л е н и е 1. Последовательность функций (Рь(х), й = 1, 2,...), определенных и неотрицательных на множестве Х, содержащем множест. во Х, называют штрафом или штрафной функцией множества Х на множестве Х, если р( ) ь" " 1, оо, ЧхЕХо'ЛХ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
