To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Barrier function

From Wikipedia, the free encyclopedia

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 of an optimization problem.[1][2] 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.

YouTube Encyclopedic

  • 1/5
    Views:
    679
    6 629
    13 287
    24 666
    4 286
  • Graph Sparsification II: Barrier Functions and Rank-one Updates
  • Mod-10 Lec-40 Barrier and Penalty Methods, Augmented Lagrangian Method and Cutting Plane Method
  • Penalty function and Augmented Lagrangian methods 2013
  • Mod-04 Lec-14 Tunneling through a Barrier
  • Quantum tunneling wavefunction derivation, part 1

Transcription

Motivation

Consider the following constrained optimization problem:

minimize f(x)
subject to xb

where b is some constant. If one wishes to remove the inequality constraint, the problem can be re-formulated 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.[3]

Logarithmic barrier function

For logarithmic barrier functions, is defined as when and otherwise (in 1 dimension. See below for a definition in higher dimensions). This essentially relies on the fact that tends to negative infinity as tends to 0.

This introduces a gradient to the function being optimized which favors less extreme values of (in this case values lower than ), 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 which should be limited to be strictly lower than , add .

Formal definition

Minimize subject to

Assume strictly feasible:

Define logarithmic barrier

See also

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


This page was last edited on 29 November 2023, at 07:09
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.