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