Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 107
Текст из файла (страница 107)
Г(оследйее утверждение доказывается так же, как аналогичное утверждение теоремы 4. П 5. Отдельно остановимся на условии (27), которое существенно использовалась при дока. зательстве равенств (28). Нетрудно привести примеры задач (1), (19), когда это условие не выполняется. ПРимеР 4. ПУсть г(х)= е, Х= (х ЕЕ~ = Хо.' д(х) =(хз — 1)(! +х«) ! <О) Ясно, что Х =(хе Е': (х/< П, й =!п(7(х)=е 1. Возьмем уй — — (х ЕЕ'. д(х) ( дй -1/Ьз). Так как ' * х х„= ге у при г в >ь, то йш 7(х ) =О=за„ь =1,2,...
таким образом, здесь !нп уй„— — 0< й — — й. й « < е ' = 7" — условие (27) не выполняется. Заметим, что в рассмотренном примере множество Х(6) = (х е Е" д(х) < 6) не является компактным нн при каком 6 > О. Приведем теорему, дающую достаточные условия для выполнения условия (27). Теорема б, Пусть множество Хс замкнуто, функции 7(х),д!(х),...,дт(х), !д +1(х)(,..., !д,(х)! определень«и полунепрерызны снизу на Хо. Кроме того, пусть множестго Х(С)=(хеЕ": хеХо, ду(х)<С «=1, г) непусто, а множестео Х(С+ ео) ограничено и замкнуто лри некотором ес > О, Тогда (см.
обозначения (15)) шп у„(с«- г) =Л(сч-о) =Л(с). (36) «+о Доказательство. Так как Х(С) СХ(С+ 6) «Х(С+ г) при любых 0< 6 < г < ео, то уцС+ г) < 7"„(С+ 6) < 7",(С). Таким образом, функция Г (С) переменной С не возрастает и существует предел !«ш ЦС+ г) =7«(С+О) ( ЦС). Возьмем произвольную последова««о * тельность (г ), 0 < е < го, сходящуюся к нулю.
При сделанных предположениях множества Х(С+е ) «Х(С+го) при каждом А =1, 2,... ограничены и замкнуты, Согласно теореме 2 1.1 й тогда существует точка юй е Х(С+ зй) такая, что 7(юй) = 7",(С + ей), й = 1, 2,... Поскольку Х(С Ч- ео) — компактное множество й юй Е Х(С+ ей) С Х(С+ го), то последовательность (юй) имеет хотя бы одну предельную точку.
Пусть ю„— какая-либо предельная точка (юй). Не умаляя общности, можем считать, что сама последовательность (юй)-«ю.. По построению юй е Х(С ч- гй), т. е. юй 6 Хо, д«й(юй) < С+ гй, « = 1,,«., з, Используя замкнутость множества Х, полунепрерывность рассматриваемых функций, отсюда при Ь -«оо получаем ю, е Х(С). А тогда 7,(с) < 7(ю„) < 11ш 7(юй) = !!ш 2,(С+ гй) = ?,(С+ 0). Сравнивая с о й ю й ю ранее установленным неравенством ЦС+ 0) ( й(С), получаем равенство (36). Нетрудно видеть, что при С = 0 нз (Зб) вытекает условие (27).
Различные аспекты метода барьерных функций исследованы в 1222; 286; 319; 390; 613; 721; 759; 7741. Упражнении 1. Применить метод барьерных функций к задачам: а) у(и)=к+у — «!п1; иеХ=(и=(х у)еЕ: д!(и)=х -у <О, дз(и)=-х<0); 2. 2 2 б) у(и) = у — «1п1; не Х = (и = (х, у) 6 Ез: д(и) = з!их+ х — у < О); в) Пи) = (и — 1) — ««п1; и е Х = (и = (х, у) Е Е ', д(и) = — и — ! < 0); г) к задачам из упражнений 15.1; д) к задачам иэ примеров б 2.3, если считать, что множество т совпадает с границей множества Х. 9 18.
Метод нагруженных функций 1. Методы, рассмотренные в $15, 1?, объединяет общая идея — в ней исходная задача минимизации заменяется свойством вспомогательных задач минимизации, в которых множество имеет более «простую» структуру, а целевая функция становится более «сложной» и содержит штрафные или б 18 МЕТОД НАГРУЖЕННЫХ ФУНКЦИЙ 35? барьерные слагаемые, учитывающие ограничения, задайощие множество исходной задачи. К методам такого типа относится также метод модифицированных функций Лагранжа нз $14, в котором вместо исходной задачи минимизации решается задача поиска седловой точки функции Лагранжа на «простом» множестве Хо х Ло.
К упомянутым методам идейно примыкает и излагаемый ниже метод нагруженных функций. Как и выше будем рассматривать задачу ?(х) !п1; Х = (х Е Е": х Е Х„ д (х) < О, 2 = 1,...,пз; д (х) =О, 2 = ой+ 1,..., зу. (1) В методе нагруженных функций задача (1) сводится к задачам минимизации некоторых вспомогательных функций на множестве Хо,и к поиску минимального решения (корня) некоторого уравнения. Для учета ограничений типа равенств и неравенств в этом методе также используется идея штрафов, но, в отличие от метода штрафных функций, в нем нет неограниченно возрастающих коэффициентов, аналогичных штрафным коэффициентам.
Заметим также, что метод нагруженных функций применим к более широкому классу задач, чем метод модифицированных функций Лагранжа. Введем семейство функций Ф(х, 1) = 5! шах(7(х) — 1; О)!«ь+ МР(х), х Е Хо, (2) зависящее от скалярного параметра 1, — оо < 1 < оо, где Р(х) — уже знакомая нам штрафная функция множества Х: Р(х) = 2;(!пах(д2(х); 0))» + 2 !дз(х)!к, (3) «=! '=з«+ ! величины рз > 1, з =О,..., з, Х > О, М > О фиксированы и являются параметрами метода. Положим р(8) = !п( Ф(х, 1). (4) Поскольку Ф(х, 1) > О при всех 6 и хе Х, то р(1) >О при любом 2.
Предположим, что в задаче (1) 7" > — со, Х, ~Я. Возьмем произвольную точку х, я Х„. То~да Р(х.) = О н «12(х„у'„) = О. Следовательно, р(~,) = О, т. е.гу, является корнем уравнения р(«) =О. (5) С другой стороны, Ф(х, 1) > О при всех 1 < 7", и х Е Х, и поэтому можно ожидать, что для широкого класса задач будет выполняться неравенство р(1) > О при всех 8 < 7,. Если это в самом деле так, то задача поиска У„ сведется к поиску минимального корня уравнения (5). Такое сведение задачи минимизации привлекательно тем, что для поиска минимального корня уравнения (5) с одной неизвестной могут быть использованы такие широко известные методы решения уравнений, как методы деления отрезка пополам, простой итерации н т.
п. 159; ?4; 89). Основная идея метода нагруженных функций описана. Заметим, что в этом методе могут быть использованы и другие конструкции функции Ф(х,б), отличные от (2). Например, можно принять Ф(х, «)=Х /У(х) — «!«ь+МР(х), хюХо, — ос< 8 <оо, (6) где функция Р(х) взята из (3), Ь > О, М > О, р, > 1. Повторив предыдущие рассуждения для функции р(1), определяемой из условий (4), (6); можно 359 й Га. МЕТОД НАГРУЖЕННЫХ ФУНКЦИЙ 358 Гл. З. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЪ|Х показать, что здесь также р(/„) = О, и высказать гипотезу о том, что для ши- рокого класса задач (1) число /„по-видимому, будет минимальным корнем уравнения (5). 2.
Прежде чем переходить к формулировке условий, при которых выска- занная гипотеза в самом деле будет справедлива, рассмотрим п2оиме ы. Во всех примерах ограничимся рассмотрением функций Ф(х, й) из ( ) и (б) при Пример 1. Задача: /(х)= — х- !п1, хЕ Х =(хе.Е'г д(х)= х <О). Здесь /„= О, х, =О. Функция (2) имеет вид Ф(х, й) = тах( — х — й; 0) + тах(х; О), х Е Хл —— .Е'. Если й >О, то Ф(0, й)=0=!п1Ф(х, й)=р(й).
Если же й <О, тоФ(х, й)=х при х > — й, Ф(х, й) = — й при О < х < — й; Ф(х, й) = — х — й при х < 0 (нарисуйте график функции Ф(х, й) при различных й). Поэтому!п(Ф(х, ) = р(й) = — й при й < О. Таким образом, р(й) = тах( — й; О). Очевидно, минимальный ко- рень уравнения (5) здесь совпадает с ~„ =О.
Функция (6) будет иметь вид Ф(х, й)=~ — х — й!+шах(х;О), х ЕЕ'. Если й > О, то, взяв х=-й, получим Ф( — й; й)=0= р(й). Если же й <О, то Ф(х, й) = 2х + й при х > — й; Ф(х, й) = -й при 0 < х < — й; Ф(х, й) = — х — й при х <О, и, следовательно, р(й) =-й при й < О.
В рассматриваемой задаче функции р(й), построенные на основе функций (2) и (6), совпали. Пример 2. Пусть/(х)=х, Х=(хеЕ'. д(х)=хй — 1<0). Ясно, что здесь Х = (х Е Е '. — 1 < х < 1), /, = — 1, х, = — 1. Если согласно (2) принять Ф(х, й) = |пах(х — й; 0) + тах(х' — 1; О), х Е Хй = Е', то нетрудно показать, что р(й) = !п1Ф(х, й) = тах( — —; ).
( — й — 1;0). Если же за основу взять функцию (6), то Ф(х,й)=!х — й!+ гпах(х' — 1; О), хеЕ', р(й)= !п(Ф(х, й)= гпах(!й~ — 1; О). В ассматриваемой задаче функции р(й), построенные с помощью функ- Р ции (2) и (6), оказались разными, но минимальный корень уравнени г ) обоих случаях совпадает с /, = -1. Пример 3. Пусть/(х)=х, Х=(хЕЕ', д(х)=х'=О). Тогда Х=(0), /, = О, х, = О.
Для функции (2), Ф(х, й) = тах(х — й; 0) + хй, х Е Хз = Е г, получим О, % р(й) = — 1/2< й <О, -й — 1/4, й < -1/2. Если взять функцию (6), то Ф(х, й ) = !х — й ) + х, х б Е, и ( й', )й)<1/2, '( !й~ — !/4, !Ц >1/2. Здесь также минимальный корень уравнения (5) совпадает с „', = „г =О. Однако нетрудно привести примеры задач (1), когда минимальный корень уравнения (5) строго меньше /,. Пример 4.
Пусть Г(х)=х, Х =(хе.Е'. д(х) =(хй — 1)(х'+1) ' < <0). Здесь Х =(х Е гЕг: — 1 < х < 1) и, очевидно, ~'„= — 1, х. = — 1. Если согласно (2) примем, Ф(х, й)=тах(х — й;О)+шах(д(х);0), хЕХ =Ег, то при й > — 1 получим Ф( — 1, й) =0=!п1Ф(х, й) = р(й). При й < — 1, взяв Е' ха=-й < й, также будем иметь 1пп Ф( — й, й)= 1!т д( — й)=0=1п1Ф(х, й)= й оа й со Е' = р(й). Таким образом, в рассматриваемом случае р(й) йвО при всех й.
Если в качестве минимального решения уравнения (5) здесь взять й, =-со, то получим й, </„= — 1. Рассмотрим функцию (6) Ф(х, й) = !х — й!+ тах(д(х); О), х е Хй =.Е'. Если ) й ) < 1, то при х = й получим Ф(й, й) = 0 = р(й). Пусть (й ( > 1. Введем множества А,=(хЕЕ'. !х — й!< ), А =(хеЕ~: !х — й)> ). Так как А, ОА, = Е, А, П Ай =И, то тогда р(й) =!п1Ф(х, й) =пни(1п(Ф(х, й); з~ А' гп! Ф(х, й)) > т!п(т1п д(х); (!й ~ — 1)/2) > 0 при всех й, !й) > 1. На первый взгляд создается впечатление, что здесь /„= — 1 — минимальный корень уравнения (5).
Однако 0< р(й) <Ф(й, й)=д(й) при !'й)> 1 и 11гп р(й)= = !!т д(й) =О. Поэтому есть основание считать, что минимальный корень й — аа уравнения (5) и в этом случае равен й. = — сс < /,. Любопытно сравнить задачи из примеров 2 и 4. В них функции /(х) и множества Х совпадают. Но эти задачи отличаются способом задания множества Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
