# Barrier function

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Barrier_function
> Markdown URL: https://mediated.wiki/source/Barrier_function.md
> Source: https://en.wikipedia.org/wiki/Barrier_function
> Source revision: 1338551662
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Continuous function whose value increases to infinity}}
{{About|the topic in optimization |the topic in dynamical systems|Barrier certificate}}{{Redirect|Barrier method|the method of safer sex|Barrier methods}}
In constrained [optimization](/source/Mathematical_optimization), a field of [mathematics](/source/mathematics),  a '''barrier function''' is a [continuous function](/source/continuous_function) whose value increases to infinity as its argument approaches the boundary of the [feasible region](/source/Candidate_solution) of an optimization problem.<ref>{{cite book|title = Lectures on Convex Optimization |edition=2 | first=Yurii| last = Nesterov | year=2018| publisher=Springer | location=Cham, Switzerland | isbn=978-3-319-91577-7 | page=56}}</ref><ref>{{cite book|title = Numerical Optimization |edition=2 | first=Jorge| last = Nocedal |first2=Stephen |last2=Wright| year=2006| publisher=Springer | location=New York, NY| isbn=0-387-30303-0 | page=566}}</ref> Such functions are used to replace inequality [constraint](/source/constraint_(mathematics))s 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 function](/source/inverse_barrier_function)s and [logarithm](/source/logarithm)ic barrier functions. Resumption of interest in logarithmic barrier functions was motivated by their connection with primal-dual [interior point method](/source/interior_point_method)s.

==Motivation==
Consider the following constrained optimization problem:

:minimize {{math|''f''(''x'')}}
:subject to {{math|''x'' ≤ ''b''}}

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

:minimize {{math|''f''(''x'') + ''c''(''x'')}},
:where {{math|''c''(''x'') {{=}} ∞}} if {{math|''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 {{mvar|c}}, and therefore the objective function {{math|''f''(''x'') + ''c''(''x'')}}, is [discontinuous](/source/discontinuous_function), preventing the use of [calculus](/source/calculus) to solve it.

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

:minimize {{math|''f''(''x'') + ''μ''&thinsp;''g''(''x'')}}

where {{math|''μ'' > 0}} is a free parameter. This problem is not equivalent to the original, but as {{mvar|μ}} approaches zero, it becomes an ever-better approximation.<ref>{{cite book |first=Robert J. |last=Vanderbei |authorlink=Robert J. Vanderbei |title=Linear Programming: Foundations and Extensions |year=2001 |publisher=Kluwer |pages=277–279}}</ref>

==Logarithmic barrier function==

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

This introduces a gradient to the function being optimized which favors less extreme values of <math>x</math> (in this case, values lower than <math>b</math>), 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](/source/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 <math>x_i</math> which should be limited to be strictly lower than <math>b_i</math>, add <math>-\!\log(b_i - x_i)</math>.

===Formal definition===
Minimize <math> \mathbf c^Tx</math> subject to <math>\mathbf a_i^T x \le b_i, i = 1,\ldots,m</math>

Assume strictly feasible: <math> \{\mathbf x \mid A x < b\}\ne\emptyset </math>

Define '''logarithmic barrier''' <math>g(x) = \begin{cases}

\sum_{i=1}^m -\!\log(b_i - a_i^Tx) & \text{for } Ax<b \\
+\infty & \text{otherwise}
\end{cases}</math>

==See also==
* [Penalty method](/source/Penalty_method)
* [Augmented Lagrangian method](/source/Augmented_Lagrangian_method)

==References==
{{reflist}}

==External links==
* [http://www.seas.ucla.edu/~vandenbe/ee236a/lectures/barrier.pdf Lecture 14: Barrier method] from Professor Lieven Vandenberghe of [UCLA](/source/UCLA)

{{optimization algorithms|constrained}}

Category:Constraint programming
Category:Convex optimization
Category:Types of functions

---
Adapted from the Wikipedia article [Barrier function](https://en.wikipedia.org/wiki/Barrier_function) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Barrier_function?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.