Misplaced Pages

In constrained optimization, a field of mathematics, a barrier function is a continuous function whose value increases to infinity as its argument approaches the boundary of the feasible region of an optimization problem. Such functions are used to replace inequality constraints by a penalizing term in the objective function that is easier to handle. A barrier function is also called an interior 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 are inverse barrier functions and logarithmic barrier functions. Resumption of interest in logarithmic barrier functions was motivated by their connection with primal-dual interior point methods.

Motivation

Consider the following constrained optimization problem:

minimize f(x)

subject to x ≤ b

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

minimize f(x) + c(x),

where c(x) = ∞ if x > b, and zero otherwise.

This problem is equivalent to the first. It gets rid of the inequality, but introduces the issue that the penalty function c, and therefore the objective function f(x) + c(x), is discontinuous, preventing the use of calculus to solve it.

A barrier function, now, is a continuous approximation g to c that tends to infinity as x approaches b from above. Using such a function, a new optimization problem is formulated, viz.

minimize f(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.

Logarithmic barrier function

For logarithmic barrier functions, ${\displaystyle g(x,b)}$ is defined as ${\displaystyle -\log(b-x)}$ when ${\displaystyle x<b}$ and ${\displaystyle \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 expensive inverse barrier functions depending on the function being optimized.

Higher dimensions

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})}$.

Formal definition

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

Assume strictly feasible: ${\displaystyle \{\mathbf {x} |Ax<b\}\neq \emptyset }$

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

See also

• Penalty method
• Augmented Lagrangian method

References

1. Nesterov, Yurii (2018). Lectures on Convex Optimization (2 ed.). Cham, Switzerland: Springer. p. 56. ISBN 978-3-319-91577-7.
2. Nocedal, Jorge; Wright, Stephen (2006). Numerical Optimization (2 ed.). New York, NY: Springer. p. 566. ISBN 0-387-30303-0.
3. Vanderbei, Robert J. (2001). Linear Programming: Foundations and Extensions. Kluwer. pp. 277–279.

External links

• Lecture 14: Barrier method from Professor Lieven Vandenberghe of UCLA

v t e Optimization: Algorithms, methods, and heuristics
Unconstrained nonlinear Functions Golden-section search Powell's method Line search Nelder–Mead method Successive parabolic interpolation Gradients Convergence Trust region Wolfe conditions Quasi–Newton Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1) Other methods Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton Hessians Newton's method
Constrained nonlinear General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming
Convex optimization Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke Active-set method
Combinatorial Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch and bound/cut Graph algorithms Minimum spanning tree Borůvka Prim Kruskal Shortest path Bellman–Ford SPFA Dijkstra Floyd–Warshall Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow
Metaheuristics Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search
Software

• Constraint programming
• Convex optimization
• Types of functions