Барьерная функция

Барьерная функция — непрерывная функция, значение которой в точке стремится к бесконечности при приближении точки к границе области допустимых решений.

Барьерная функция используется в задачах оптимизации как поправочный член чтобы гарантировать наличие решений в допустимой области. Например, когда ищется оптимальное значение функции $f(x)$$f(x)$, переменная $x$$x$ может быть ограничена значением, строго меньшим, чем некоторая константа $b$$b$, путём замены функции на

$f(x)-<!--\; -\; -->\log <!--\; \; -->(b-<!--\; -\; -->x).$$f(x)-\log(b-x).$

При этом функция

$x\mapsto <!--\; \mapsto \; -->-<!--\; -\; -->\log <!--\; \; -->(b-<!--\; -\; -->x)$$x\mapsto -\log(b-x)$

играет роль барьерной функции.

Двумя наиболее используемыми типами барьерных функций являются обратные барьерные функции и логарифмические барьерные функции. Возобновление интереса к логарифмическим барьерным функциям вызвано их связью с двойственно-прямыми методами внутренней точки.

Логарифмическая барьерная функцияПравить

Для логарифмических барьерных функций $g(x,b)$$g(x,b)$  определяется как $-<!--\; -\; -->\log <!--\; \; -->(b-<!--\; -\; -->x)$$-\log(b-x)$  для $x<b$  и $\mathrm{\infty <!--\; \infty \; -->}$$\infty$  в противном случае (в размерности 1. Смотрите ниже для более высоких размерностей). При таком определении опираются на факт, что $\log <!--\; \; -->(t)$$\log(t)$  стремится к минус бесконечности, когда $t$$t$  стремится к 0.

Это даёт большие значения градиента для оптимизируемой функции вблизи $b$$b$ , в то время как изменения функции вдали от $b$$b$  мало изменяются.

Вместо логарифмической барьерной функции может быть удобнее использовать обратную барьерную функцию, имеющую меньшую вычислительную сложность, но это зависит от оптимизируемой функции.

Если переменных несколько, то следует добавить по барьерной функции для каждой переменной $x_i$$x_{i}$ , которая должна быть строго ограничена значением $b_i$$b_{i}$ , добавляем $-<!--\; -\; -->\log <!--\; \; -->(b_i-<!--\; -\; -->x_i)$$-\log(b_{i}-x_{i})$ .

Формальное определениеПравить

Минимизировать ${\mathbf{c}}^{T}x$$\mathbf {c} ^{T}x$  при условиях ${\mathbf{a}}_i^{T}x\le <!--\; \le \; -->b_i,i=1,\dots <!--\; \dots \; -->,m$$\mathbf {a} _{i}^{T}x\leq b_{i},i=1,\ldots ,m$ 

Принимаем строгие ограничения: $\{\mathbf {x} |Ax<b\}\neq \emptyset$ 

Определим логарифмический барьер $\Phi (x)={\begin{cases}\sum _{i=1}^{m}-\log(b_{i}-a_{i}^{T}x),Ax<b\\+\infty ,Ax\geq b\end{cases}}$ 

ЛитератураПравить

• Jorge Nocedal, Stephen Wright. Numerical Optimization. — New York, NY: Springer, 1999. — ISBN 0-387-98793-2.
• Lecture 14: Barrier method Архивная копия от 23 ноября 2015 на Wayback Machine from Professor Lieven Vandenberghe of UCLA