Ф.П. Васильев - Методы оптимизации (1125241), страница 105
Текст из файла (страница 105)
В качестве «запрещенного» множества у может служить, например, граница Гр Х множества Х или какая-либо часть границы. Дело в том, что при применении того или иного метода решения задачи (1) при Х ф В" может случиться, что калкдое получаемое приближение ха будет принадлежать Гр Х. Однако если структура границы множества слишком сложна, то реализация такого метода может потребовать большого объема вычислительной работы и, кроме того, сходимость метода может оказаться очень медленной.
В таких случаях можно попробовать как-то построить «барьер» вблизи всей границы 7 = Гр Х или какой-либо ее части Т (нли какого-либо другого заданного подмножества 7 с Х), который искл>очал бы возможность попадания очередного приближения х„на у. 0 яр еде л е н и е 1. Пусть у — некоторое подмножество множества Х. Фуикци>о В(х) назовем барьером или барьерной функцией подмножества 7, если В(х) определена, конечна и неотрицательна во всех точках х е Е Х 1Т, причем 1!ш В(п„) = оо для всех последовательностей (ц ) Е Х Л у, >' >ч которые сходятся к какой-либо точке и ~ у.
Заметим, что в определении 1 подразумевается, что Х 17 фИ. Это значит, что если у =Гр Х, то !и! Х = Х Л у ~И. Заметим также, что в точках х е 7 барьерная функция В(х) не определена (можно принять В(х) = со, х е у). Пользуясь теми же конструкциями, которые использовались при построении штрафнгях функций, нетрудно выписать барьерные функции для множеств .у, задаваемых ограничениями типа равенств или неравенств. Например, если Т =(хе Е": хе Х д(х) =-0), где д(х) непрерывна на Х, Х>>7 фИ, то в качестве барьерной функции здесь можно взять В(х) = ]д(х)] ', или В(х) =]д(х)] ', или В(х) =гпах( — ]п]д(х)]; 0).
Если же у = (хе Е": х е Е Х д(х) < О), где Х Л у ф И, д(х) непрерывна на Х, то можно принять В х) =(д(х)) ", Р >О, или В(х) = / ]ид(х)], ха Х Л у и т. п, ерейдем к описанию метода барьерных функций для решения задачи (1), предполагая, что подмножество 7 с Х и некоторая его барьерная функция уже заданы. Введем функции Х" (х)=7(х)+а»В(х)> хЕХ 1 У, и=1,2,..., (2) где (а.) — положительная последовательность, сходящаяся к нулю. Величингя (иа) из (2) называются барьерными коэффициентами.
Рассмотрим последовательность задач РДх) — ш(; х е Х ~.у, й = 1, 2,... (3) Обозначим Ргы = !и! Рк(х), й = 1, 2,... Будем предполагать, что в исходной гы задаче (1) 7", = 1п(7(х) > — оо. Так как Ра(х) > 7(х) пРи всех х Е Х Л У, то х Ва, > 7', > — оо, Тогда УсловиЯ хлшХ1 у, Рь(х)<рь,+еь, ус=1,2,...
(4) определяют последовательность (ха), где е, > О, !пп е„ =0; если окажется, ь оо что Рь(х,) = гь„ то в (4) допускается е„ = О. Поскольку, как обычно, мы подразумеваем, что функция 7(х) конечна во всех точках х е Х, то согласно определению 1 для любой последовательно- сти (н,) Е Х Л 7, (н,) †>н б у справедливо равенство !1ш В (н„) = со при О каждом фиксированном й = 1, 2,... Таким образом, функция Гь(х) неогра- ниченно возрастает вблизи Т. Поэтому следует ожидать, что при фиксиро- ванном )с функция Вь(х) вблизи у не может принимать значения, близкие к Гь„и точка ха определяемая условиями (4), не будет расположена на слишком близком расстоянии от у.
В то же время благодаря топну, что барьерные коэффициенты (а„) — О, не исключается возможность того, что с увеличением номера й точки х„постепенно «преодолевая барьер», будут приближаться к Т, Для приближенного решения задачи (3) при фиксированном й и опре- деления точки ха удовлетворяющей условиям (4), могут быть исполь- зованы различные методьа минимизации.
В частности, если Т = Гр Х и Х Л 7 = !п1 Х ~ И, то для решения задачи (3) может быть применен, на- пример, градиентный метод (см. 9 1): хд .» = хм '«грь'(хьг)> хао = хь — > Поскольку ха, е !п1 Х, то при достаточно малых г«„> 0 точка хд„, так- же будет принадлежать !п1 Х, и мы избавлены от неудобств, связайных с 350 гл, ь, митоды минимизАции ФУнкций многих нБРБмкнных $!7. МЕТОД БАРЬЕРНЫХ ФУНКЦИЙ 55! "лл учетом границы Х, — нужно лишь на каждой итерации следить за соблю- дением включения х„е ш! Х, а при его нарушении уменьшать длину шага с«„. Правда, для этого величину а„„быть может, придется брать слишком малой, и сходимость градиентного метода, возможно, замедлится, но это уже будет «платой» за выполнение условия х« ~ !и! Х.
Дальнейшее изложение не зависит от того, с помощью какого конкретно- го метода минимизации будет найдена точка х„удовлетворяющая услови- ям (4), Поэтому мы здесь можем ограничиться предположением, что име- ется достаточно удобный метод определения точки х, из (4). Метод барьерных функций описан. Отметим, что в литературе этот ме- тод иногда называют методом внутренних штрафов (или методом вну- тренней точки), а метод штрафных функций из 9 15 — методом внешних штрафов (или методом внешней точки) 172Ц.
Для иллюстрации метода барьерных функций приведем пример. П р и м е р 1. Пусть требуется решить задачу /(х)= — х»1п1; хЕХ=(хбЕ'. д(х)=х<0). Очевидно, здесь /„=О, Х, = (0), Границей множества Х является у = =Гр Х=(хеЕ'. д(х)=х=О)=(0), а Х17=(хеЕ'. д(х)=х<0)=т'! Х. В качестве барьерной функции для у возьмем В(х) = — 1/х (х < 0).
Пусть а„= й ', й = 1, 2,... Тогда функция (2) будет иметь вид Р„(х) = — х— — (йх) ', х < О. Нетрудно видеть, что здесь Р», =!п1 Р»(х) = 2/ълй и точка *«о х» = — 1/ъУй удовлетворяет условиям (4) при е, =О, й = 1, 2,... Ясно также, что 1пп Р„„ = 1пп /(х,) = 0= /„ 1пп х„ = 0 = х,. » ю "* » » В качестве барьерной функции здесь можно также взять и В(х) = = ) 1п( — х)1 В этом случае Р (х) = — х+ ~ 1п( — х)!й ', х < О, й = 1,2, Р,„=(1+!и й)й ', а точка хь = — й ' удовлетворяет условиям (4) прн е, =О. И здесь (/(х„)) — Л, = О, (х,) — х„= О. Перейдем к исследованию сходимости метода барьерных функций.
Т е о р е м а 1. Пусть у — некоторое подмножество из Х, Х~.уфИ, и Л. =/... где /, = !п1/(х), /„, =!п1 /(х) > — оо. (5) х ' "* х~, Пусть В(х) — какая-либо барьерная функция подмножества 7, а после- довательность (х„) определена условиями (4), Тогда 1!>и Р„= 1!гп Р„(х„) = !пп /(х ) =/„, 1!т а В(х„) =О. (6) Кроме того, если множество Х ограничено и замкнуто, а /(х) полунг- прерывна снизу на Х, то (х„) сходится к Х„. До к аз а тел ь ство. Из определения У„„Р„'„, неотрицательности барьерной функции и условий (4) следует — оо < /„„< /(х„) < Р»(х„) ( Р»,+г < Р»(х)+г»=/(х)+а„В(х)+г (7) при всех х Е Х 1 у, й = 1, 2,...
Так как В(х) конечна в любой точке х Е Х ~7, (а„) — О, то из (7) при й — оо получим 7„< 1!гп Рь, ~ (1пп Р», (7(х), х Е Х 1'у. »» «о Переходя в этих неравенствах к нижней грани по х е Х ~ Т, будем иметь /,„< 1пп Р». < 1нп Р«, </,„, т. е. 11т Р, =/... Отсюда и из (7) вытекает 1пп Р„(х„) = !пп /(х„) =/,„. Так как /, =/„„то первые соотношения (6) доказаны. А тогда из 0 < а В(х.) = Р»(х») — /(х») — 0 при й — со получим и второе из соотношений ~6). Г>«ослед»нее утверждение о сходимости минимизирующей последовательности (х„) к Х, следует из теоремы 2.1,1, О Полезно заметить, что при доказательстве теоремы 1 были использованы не все свойства барьерных функций: соотношение Игп В(е„) = оо, где (о„) е Х ~ Т, (е,) — и е у, нам не понадобилось.
Поэтому теорему 1 и ряд доказываемых ниже теорем можно использовать не только как теоремы о сходимости метода барьерных функций, но и как утверждения, выражающие собой достаточные условия устойчивости нижней грани относительно возмущений (погрешностей) минимизируемой функции и некоторых типов возмущений множества, на котором ищется минимум. 2.
Рассмотрим возможности построения барьерных функций для задачи (1) в случае, когда Х = (х Е Хо, д,(х) < О, »' = 1,..., тп); (6) здесь Х, — заданное множество из Е", функции д,(х),..., д (х) определены и полунепрерывны снизу на Х,. Положим ч=(хЕ Х: д(х)=0 хотя бы для одного «, 1 <»' < тп). (9) Будем предполагать, что множество Х( — 0)=(хеХ: д(х)(0, »=1,...,т) (10) непусто. Тогда Х ~ 7 = Х( — 0)>7.
И. Довольно широкий класс барьерных функций для множества (9) дает следующая конструкция: » В(х) = 2, ~р;( — д«(х)), х Е Х( — 0), (1 1) *=1 где р,. (1) — неотрицательная Офункцня переменной 1 > 0 такая, что !пп о>,(1) = со при всех «' = 1,..., тп. В самом деле, возьмем произвольную последовательность («>,) е Х ~-у, сходящуюся к некоторой точке и е .у. Согласно (9) тогда найдется номер 7', 1 < У < т, для которого ду(е) =О. Так как д,(х) полунепрерывна снизу, а ду(и„) < О, т = 1, 2,..., то 0 = = д.(«>) < 1!гп ду(е,) < 1пп д,(и„) < О, т.
е. 1пп ду(е„) = О. Это значит, что — > » В(и,) > и>у( — ду(е„)) » оо при т -» со, так что функция (11) является барьерной для множества (9). При необходимости в (11) функции Ф«(1) нетрудно выбрать так, чтобы барьерная функция В(х) обладала различными полезными свойствами, такими, как непрерывность, гладкость, выпуклость, простота вычисления значения функции и нужных ее производных и т. п., если, конечно, исходные данные в задаче (1), (8) обладают такими свойствами. Например, взяв в (11) р«(1) = 1/1 или у«(й) = (тах( — 1и 1; 0))", р > 1, получим соответственно (12) В(х) = 2,'(тах( — 1и( — д,.(х)); 0))", х ~ Х( — 0). 353 4 17.
МЕТОД БЛРЪЕРНЫХ ФУНКЦИЙ 352 Гл. 5. МЕТОДЫ МИНИМИЗЛЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ >",(С) < !и! 7(х) < Д(С вЂ” Б) < Г (С вЂ” е) »!с-о> (13) Гр Х = Гр Х 0 у, Тд .' вд у, >2 Ф.П. Васильев Если Х, выпукло, функции д,(х), а =1,..., т„выпуклы на Х, то множество Х( — 0) = Х>7 выпукло и функции (12) также будут выпуклыми на Х( — 0)— это следует из следствий к теореме 4,2.8. Далее, функции (12) будут обладать той же гладкостью, какой обладают функции дг(х), ь = 1,..., т— у второй функции (12) для этого нужно взять параметр р достаточно большим. Может сложиться впечатление, что если функции д,(х),..., д (х) непреРывны на Хо, то множество Т, опРеделЯемое УсловиЯми (9), бУд™ет состоЯть только лишь из граничных точек множества (8).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
