In constrainedoptimization, a field ofmathematics, abarrier function is acontinuous function whose value increases to infinity as its argument approaches the boundary of thefeasible region of an optimization problem.^[1][2] Such functions are used to replace inequalityconstraints by a penalizing term in the objective function that is easier to handle. A barrier function is also called aninterior penalty function, as it is a penalty function that forces the solution to remain within the interior of the feasible region.

The two most common types of barrier functions areinverse barrier functions andlogarithmic barrier functions. Resumption of interest in logarithmic barrier functions was motivated by their connection with primal-dualinterior point methods.

Consider the following constrained optimization problem:

minimizef(x)

subject tox ≤b

whereb is some constant. If one wishes to remove the inequality constraint, the problem can be reformulated as

minimizef(x) +c(x),

wherec(x) = ∞ ifx >b, and zero otherwise.

This problem is equivalent to the first. It gets rid of the inequality, but introduces the issue that the penalty functionc, and therefore the objective functionf(x) +c(x), isdiscontinuous, preventing the use ofcalculus to solve it.

A barrier function, now, is a continuous approximationg toc that tends to infinity asx approachesb from below. Using such a function, a new optimization problem is formulated, viz.

minimizef(x) +μ g(x)

whereμ > 0 is a free parameter. This problem is not equivalent to the original, but asμ approaches zero, it becomes an ever-better approximation.^[3]

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

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

Logarithmic barrier functions may be favored over less computationally expensiveinverse barrier functions depending on the function being optimized.

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

Minimize${\displaystyle {\mathbf{c}}^{T}x}$ subject to${\displaystyle {\mathbf{a}}_i^{T}x\le b_i,i=1,\dots ,m}$

Assume strictly feasible:

Definelogarithmic barrier

• Penalty method
• Augmented Lagrangian method

• Lecture 14: Barrier method from Professor Lieven Vandenberghe ofUCLA

• Constraint programming
• Convex optimization
• Types of functions

• Articles with short description
• Short description matches Wikidata