Barrier function

In constrained optimization, a field of mathematics, a barrier function is a continuous function whose value on a point increases to infinity as the point approaches the boundary of the feasible region (Nocedal and Wright 1999). It is used as a penalizing term for violations of constraints. The two most common types of barrier functions are inverse barrier functions and logarithmic barrier functions. Resumption of interest to logarithmic barrier function was motivated by its connection with primal-dual interior point method.

When optimising a function f(x), the variable $x$ can be constrained to be strictly lower than some constant $b$ by instead optimising the function $f(x)+g(x,b)$. Here, $g(x,b)$ is the barrier function.

Logarithmic barrier function

For logarithmic barrier functions, $g(x,b)$ is defined as $-\log(b-x)$ when $x<b$ and $\infty$ otherwise (in 1 dimension. See below for a definition in higher dimensions). This essentially relies on the fact that $log(t)$ tends to negative infinity as $t$ tends to 0.

This introduces a gradient to the function being optimised which favours less extreme values of $x$ (in this case values lower than $b$), while having relatively low impact on the function away from these extremes.

Logarithmic barrier functions may be favoured over less computationally expensive inverse barrier functions depending on the function being optimised.

Higher dimensions

Extending to higher dimensions is simple, provided each dimension is independent. For each variable $a_{i}$ which should be limited to be strictly lower than $b_{i}$, add $-\log(b_{i}-x_{i})$.

Formal definition

minimize :${\mathbf {c}}^{T}x$

subject to: ${\mathbf {a}}_{i}^{T}x\leq b_{i},i=1,\ldots ,m$

assume strictly feasible:$\{{\mathbf {x} }|Ax<b\}\neq 0$

define logarithmic barrier $\Phi (x)={\begin{cases}\sum _{i=1}^{m}-\log(b_{i}-a_{i}^{T}x)&{\text{for }}Ax<b\\+\infty &{\text{otherwise}}\end{cases}}$

References

• Nocedal, Jorge (1999). Numerical Optimization. New York, NY: Springer. ISBN 0-387-98793-2. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

• [1] lecture on barrier method.