Ф.П. Васильев - Методы оптимизации (1125241), страница 107
Текст из файла (страница 107)
в=! Тогда при й -в со из (30) с учетом условия (27) получим 1, < 1пп Г, <(!ш Гь, <7"(х) при всех хбХ. * — „, ' ь Переходя к нижней грани по х 6 Х, отсюда имеем йш Гь„— — 7",. Тогда из (ЗО) следует Ь ю 1нп Гь(хь)= 1!гп 7(хь)югв. Наконец, 0» (аьВь(хь) = Гь(хь) — г(хь) — вО при й оо. Ра- венства (28) доказаны. Пусть теперь выполнены все условия теоремы. Так как (Оь) †в, то !гь С Х(б) при всех й > йо, Тогда хь 6 Х(б), й > йо. В силу компактности Х(б) йоследовательность (хь) имеет хотя бы одну предельную точку.
Пусть х„ — произвольная предельная точка (хь), пусть под- последовательность (хь ) -вх,. В силу замкнутости Хо тогда х, б Хо. Из полунепрерывности снизУ фУнкций дг(х), , д (х), !д + г(х)1,...в!Ов(хИ и УсловиЯ хь 6 !гь следУет, что дг(х,)< !!ш дг(хь )< йгп Вь=О, в=1,...,т, !дг(х,)!< Вш /дг(х )!< !пп Вь — — 0 в д,.(х,)вю О, в'= т+ 1, .. юг.
Таким образом, хв 6 Х. Отсюда с учетом полунепрерывности снизу 7(х) на Х(б) получим гв < 7(хв) < 1!ш 7" (хь ) = !нп 7(хь) = гв, т. е. 7(хв) = гв или х, Н Х,, Тем самым показано, что любая предельная точка последовательности (хь) принадлежит Х,. Отсюда следует, что (х -в Х„.
Теорема 4 доказана, П ри некоторых более жестких ограничениях на данные задачи (!), (19) можно получить оценки погрешности метода (20)-(26). Теорема 5, Пусть для задача (!), (19) справедливо неравенство в — со<7„<7(х)+ д сг(дч(х)) !7х6 Хе, с! >О, ы>0 (32) в= ! (см, определение 15.3 и леммы 15.1,!5.5). Тогда последовательность (хь), определяемою условиями (20)-(26), существует и справедливы оценки -)с(гдь" м !"(хь) — г' ( Гь(хь) — 7", ц 2аь З; рг(Вь)-1-еь, ! ™ 356 Гл. 5.
МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Далее, иа соотношений 0 < а Вь(хь) = (Рь(хь) — Х,) — (Пхь) — 7„) и улге доказанной оцен- ки (ЗЗ) вытекает оценка (34), (]оследйее утверждение доказывается так же, как аналогичное утверждение теоремы 4. Ш б. Отдельно остановимся на условии (27), которое существенно использовалось при дока- зательстве равенств (28). Нетрудно привести примеры задач (|), (19), когда зто условие не выполняется. Пример 4.
Пусть Х(х) = е, Х =(х ЕЕ' =Хо! д(х) =(х — 1)(14х ) ! <О), Ясно, что Х =(х ЕЕ; ]х] (1), 7 =|в!7(х) =е, Возьмем 1|, — — (хЕВ: д(х) (дь — — 1/й~). Так как х х„=» Е г' при» > й, то 11ш 7(х )=О=у|вы й=1,2,... Таким образом, здесь Зш Хь,— — 0< ь ь*' Ь оо с е ' = Ä— условие (27) не выполняется. Заметим, что в рассмотренном примере множество Х(б) = (х е В'. д(х) < Б) не является компактным ни при каком б >О, Приведем теорему, дающую достаточные условия для выполнения условия (27), Теорема б.
Пусть множество Хо замкнуто, функции Х(х),д|(х),..од (х), ]д,(х)],, ]д,(х)] определены и лолукелрерызкы снизу ка Хо. Кроме того, пусть мно- ж™ест го Х(С) =(хеЕ": хе Х!» д,.+(х) <С «=1,») непусто, а множество Х(С+ го) ограничено и замкнута лри некотором го > О. Тогда (см. обозначения (|5)) ||гл Х,(С+а)=Х,(С«0)=Х,(С). (36) о «о Доказательство. Так как Х(С) С Х(С+ у) СХ(С-ге) при любых Ос б < г < е, то 7 (С+ г) < 7„(С+ б) < Г (С).
Таким образом, функция 7 (С) переменной С не возрастает и существует предел От 7 (С+ е) = Х„(С+ 0) ( Х„(С). Возьмем произвольную последова-«в " тельность (г ), 0 ( г < го, сходяшуюсв к нулю. При сделанных предположениях множества Х(С+ гь ) СХ(С+го) при каждом й = 1, 2,... ограничены и замкнуты. Согласно теореме 2 1.! тогда существует точка юь Е Х(С+ еь) такая, что Х(юь) = Х (С ~- еь), й = 1, 2,, Поскольку Х(С Е го) — компактное множество й юь Е Х(С+ еь) Е Х»(С+ го), то последовательность (юь) имеет хотя бы одну предельную точку. Пусть ю, — какая-либо предельная точка (юь).
Не умаляя общности, можем считать, что сама последовательность (юь) -«ю,, По постро- ению юь Е Х(С ! г ), т. е. юь Е Хо, дд(юь) < С ! г, 1 = 1,.:., г. ИспользУв эамкнУтость мнохгества Хо, полунепрерывность рассматриваемых «рункций, отсюда при й о ос получаем ю, еХ(С). А тогда Л(С) < Х(ю,) ( 1|ш Х(юь) = 1|ш Х„(С«- гь) =Х,(С 40) Сравнивая с ь о ь ранее установленным неравенством Х (С+ 0) < 7«(С), получаем равенство (36), Нетрудно видеть, что при С = 0 из (36) вытекает условие (27).
Различные аспекты метода барьерных функций исследованы в [222; 286; 319; 390; 613; 721; 759; 774]. Упражнении 1. Применить метод барьерных функций к задачам: а) Х(и) = х+ у «!п(! и Е Х =(и =(х у) Е Е; д|(и) = х — у < О, и>(и) = -х <О); 2. 2 2 б) Х(и) = у — «|и 1; и е Х = (и = (х у) е Ьз; д(и) = э!и х+ х- у < 0); в) Х(и)=(и — 1) -«!п1; иеХ=(и=(х,у)ЕЕ .
д(и)= — и — 1<0); г! к задачам иа упражнений 15.1; д) к задачам из примеров 4 2.3, если считать, что множество 7 совпадает с границей мно жества Х. 9 18. Метод нагруженных функций 1. Методы, рассмотренные в 9 15, 17, объединяет общая идея — в ней исходная задача минимизации заменяется свойством вспомогательных задач минимизации, в которых множество имеет более «простую» структуру, а целевая функция становится более «сложной» и содержит штрафные или 4 18 МЕТОД НАГРУЖЕННЫХ ФУНКЦИЙ 357 барьерные слагаемые, учитывающие ограничения, задающие множество исходной задачи.
К методам такого типа относится также метод модифицированных функций Лагранжа из 9 14, в котором вместо исходной задачи минимизации решается задача поиска седловой точки функции Лагранжа на «простом» множестве Х х Л . К упомянутым методам идейно примыкает и излагаемый ниже метод нагруженных функций. Как и выше будем рассматривать задачу ,Х(х) — «1п1; Х = (х Е В": х Е Хо, д|(х) < <О, 2 = 1,..., т; д|(х) = О, 2 = т+ 1,..., э]-.
(1) В методе нагруженных функций задача (1) сводится к задачам минимизации некоторых вспомогательных функций на множестве Хо,и к поиску минимального решения (корня) некоторого уравнения. Для учета ограничений типа равенств и неравенств в этом методе также используется идея штрафов, но, в отличие от метода штрафных функций, в нем нет неограниченно возрастающих коэффициентов, аналогичных штрафным коэффициентам. Заметим также, что метод нагруженных функций применим к более широкому классу задач, чем метод модифицированных функций Лагранжа. Введем семейство функций Ф(х, 1) = Х ( шах(Х(х) — 1; О)1"'+ МР(х), х Е Х, (2) зависящее от скалярного параметра 1, — со < 1 < оо, где Р(х) — уже знакомая нам штрафная функция множества Х: Р(х) = Х„"(ШаХ(дч(х)!О))г + Х ]д|(х)|г«, (3) г=! «=хо ! величины р,. > 1, 2 = О,, э, Х > О, М > О фиксированы и являются параметрами метода.
Положим р(1)= (п( Ф(х,(). (4) Поскольку Ф(х, 1) > О при всех 1 и х Е Х, то р(1) > О при любом 1. Предположим, что в задаче (1) Х > — оо, Х, /И. Возьмем произвольную точку х, е Х,. Тогда Р(х,) = О и г(>(х„Х,) = О. Следовательно, р(Л) =О, т. е. '1' является корнем уравнения р(1) =О. (5) С другой стороны, Ф(х, 1) > О при всех 1 < Х„и х Е Х, и поэтому можно ожидать, что для широкого класса задач будет выполняться неравенство р(1) > О при всех 1 < Х„. Если это в самом деле так, то задача поиска Х сведется к поиску минимального корня уравнения (5), Такое сведение задачи минимизации привлекательно тем, что для поиска минимального корня уравнения (5) с одной неизвестной могут быть использованы такие широко известные методы решения уравнений, как методы деления отрезка пополам, простой итерации и т.
и. 159! 74; 89). Основная идея метода нагруженных функций описана. Заметим, что в этом методе могут быть использованы и другие конструкции функции Ф(х, 1), отличные от (2). Например, можно принять Ф(х, 1) = Х ],>'(х) — 1]гь + МР(х), х Е Хо« -со < ( < оо, (6) где функция Р(х) взята из (3), Х > О, М > О, р! > 1. Повторив предыдущие рассуждения для функции р(1), определяемой из условий (4), (6); можно 358 Гл.
5, МЕТОДЪ! МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ показать, что здесь также р(/„) = О, и высказать гипотезу о том, что для ши- рокого класса задач (1) число /„по-видимому, будет минимальным корнем 2. П еж е чем переходить к формулировке условий, при которых выскарежд ванная г ипотеза в самом деле будет справедлива, рассмотри р з 2 и 6 пи всех примерах ограничимся рассмотрением функций Ф(х, г) из (2) ~ ) р Пример 1.
Задача: /(х)=-х- 2п1, хЕХ=(хеба'. д(х)=х<0). Здесь /„=О, х, =О. Функция (2) имеет вид ! Ф(х, 2) = гпах(-х — г; 0) + шах(х; О), х Е Х,= Е . Если г >О, то Ф(0, г)=0=!п(ф(х, г)=р(г).'Если же 1 <О, тоф(х, г)=х при х — г, Ф(х, г) = — г при 0 < х < — г; Ф(х, г) = — х — 2 при х < 0 (нарисуйте график функции Ф(х, 2) при различных 2).
Поэтому !и!Ф(х, Г) = р(1) =-г при г < О, таким образом, р(г) = шах(-2;0). Очевидно, минимальный ко- рень уравнения (5) здесь совпадает с ~. =О. Функция (6) будет иметь' вид Ф(х, 1) = ~ — х — г~+ шах(х;О), х е Л!. Если 2 > О, то, взяв х = — 2, получим Ф( — 1; !) =0 = р(2). Если же 1 < О, то Ф(х, ь) = 2х+ ь' при х > — ь'; Ф(х, 2) = — 1 при О < х < — !'; Ф(х, 1) = — х — ь' при х < О, и, следовательно, р(г) = — г при г < О. В рассматриваемой задаче функции р(!), построенные на основе функций (2) и (6), совпали. Пример 2. Пусть |(х)=х, Х=(хЕЕ'.
д(х)=х' — 1<0). Ясно, что здесь = (х Е: — х Х вЂ” ( Е.Е'. — 1< х< Ц, /,= — 1, х,= — 1. Если согласно(2) принять Ф(х, 2) = шах(х — 1; О) + !пах(х' — 1; О), х б Х = Ж !, то нетрудно показать, что р(2) = !п(Ф(х, г) = ах(— = гп ( — ! — 1;01. Если же за основу взять функциго (6), то Ф(х,т)=!х — 1!+ шах(х'-1; О), хЕЕ', р(1)= !п(ф(х, г)= шах(!г!-1; О). В рассматриваемой задаче функции р(г), построенные с помощью функ- ций (2) и (6), оказались разными, но минимальный корень уравнения (5) в обоих случаях совпадает с /, = — 1. Пр имер 3. Пусть |(х)=х, Х=(хеЕ!; д(х)=хг=О).
Тогда Х=(0(,, /, = О, х, = О. Для функции (2), Ф(х, г ) = щах(х — 1; О) + хг, х Е Хь = Н, получим О, 12 — 1/2 <1 <О, -г — 1/4, г < -1/2. р,! и Если взять функцию (6), то Ф(х, 1) = !х — г!+ х, х Е л,, и !' 22 !1! < 1/2 '( ~1! — 1/4, !Г!) 1/2. Здесь также минимальный корень уравнения (5) совпадает с /, = О. Однако нетрудно привести примеры задач (1), когда минимальный корень уравнения (5) строго меньше /,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
