imported>PuppyMonkey: hat note

2024-09-09T22:00:02Z

hat note

New page

{{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 [[Mathematical optimization|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 [[Candidate solution|feasible region]] 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 (mathematics)|constraint]]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]]s and logarithmic barrier functions. Resumption of interest in logarithmic barrier functions was motivated by their connection with primal-dual [[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 function|discontinuous]], preventing the use of [[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 above. Using such a function, a new optimization problem is formulated, viz.

:minimize {{math|''f''(''x'') + ''μ'' ''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]] 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|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]]
* [[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]]

{{optimization algorithms|constrained}}

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

Barrier function - Revision history

imported>PuppyMonkey: hat note