22.2Метод барьерных функций

Идеи метода штрафных ф-ий могут быть использованы для построения методов решения задачи f(x) ! inf x 2 X (6:1), позволяющих получить такую минимизирующую последовательность fxkg 2 X, каждый элемент которой будет находиться вне некоторого заданного запрещенного подмножества 2 X. В качве запрещенного подмножества может служить, например, граница множества X или какая-либо часть границы.

Определение 6.1 Пусть - некоторое подмножество множества X. Ф-ю B(x) назовем барьерной ф-ей подмножества , если B(x) определена, конечна и неотрицательна во всех точках x 2 X n , причем

lim B(vr) = +1

r!1

для всех последовательностей fvrg 2 X n , которые сходятся в точке v 2 .

В определении 6.1 подразумевается, что X n 6= . Это значит, что если граница X, то

Int X = X n 6=

Можно принять, что B(x) = +1 при x 2 так, как на границе барьерная ф-я неопределена. Аналогично построению внешних штрафных функций можно определить барьерную ф-ю для множества , задаваемых ограничениями типа равенств или неравенств.

Например, если

= fx 2 En : x 2 X; g(x) = 0g

где ф-я g(x) непрерывна на X и внутренность X n 6= , то в кач-ве барьерной ф-и можно взять

B(x) = jg(x)j 1

или

B(x) = jg(x)j 2

или

B(x) = max f ln jg(x)j; 0g

Если же

= fx 2 En : x 2 X; g(x) 6 0g

где X n 6= , и ф-я g(x) непрерывна на множестве X, то можно принять

B(x) = (max fg(x); 0g)p p > 0

22.2.1Описание метода барьерных функций (для решения задачи 6.1)

Предположим, что подмножество 2 X и некоторая его барьерная ф-я уже заданы. Введем ф-ю

Fk(x) = f(x) + akB(x) x 2 X n k = 1; 2; ::: (6:2)

fakg - положительная последовательность, сходящаяся к 0. Величины ak из (6:2) называются барьерными коэффициентами.

Рассмотрим последовательность задач

Fk(x) ! inf x 2 X n k = 1; 2; ::: (6:3)

Обозначим

Fk = inf Fk(x) k = 1; 2; :::.

Xn

Будем предполагать, что

f = inff(x) > 1

X

Так как по построению Fk(x) > f(x) при всех x 2 X n , то

45

Fk > f > 1

Тогда условия

xk 2 X n и Fk(xk) 6 Fk + "k k = 1; 2; ::: (6:4)

определяют последовательность fxkg такую, что

"k > 0 lim "k = 0

k!1

Поскольку подразумеваем, что ф-я f(x) конечна во всех точках x 2 X, то согласно у-нию (6:1) для любой последовательности fvrg 2 X n при условии, что fvrg ! v 2 , справедливо равенство

lim Fk(vr) = +1 k = 1; 2; :::

k!1

Таким образом ф-я Fk(x) неограниченно возрастает вблизи . Поэтому следует ожидать, что при фиксированном значении k ф-я Fk(x) вблизи не может принимать значения, близкие к Fk и точка xk определяемая условиями (6:4) не будет расположена на слишком близком расстоянии от .

В то же время, благодаря тому, что барьерные коэффициенты fakg ! 0 не исключается возможность того, что с увеличением номера k точки xk постепенно “преодолевая барьер” будут приближаться к .

Для приближенного решения задачи (6:3) при фиксированном значении k и определении точки xk, удовлетворяющей условию (6:4) могут быть использованы различные методы минимизации. В частности, если

= ГрX и X n = Int X 6=

то для решения задачи (6:3) может быть применен градиентный метод

xk;r+1 = xk;r rFk0(xkr)

Поскольку xkr 2 Int X, то при достаточно малом шаге r и точка xk;r+1 2 Int X. Это избавляет от неудобств, связанных с учетом границы множества X. Нужно лишь на каждой итерации следить за соблюдением включения

xk 2 Int X

апри его нарушении уменьшать длину шага r. Для этого величину r придется брать слишком малой

исходимость градиентного метода замедлится, но это является платой за выполнение этого условия.

46