Barrier Methods

Optimization · Axiom Academy

LESSON Barrier Methods for Constrained Optimization Interior Point Methods: Staying Inside the Feasible Region Consider the constrained optimization problem: A barrier function keeps iterates strictly inside the feasible region by adding a penalty that grows to infinity as we approach the boundary where g i (x) = 0. 2. Logarithmic Barrier Function The most common barrier function is the logarithmic barrier : Here, the parameter mu (barrier parameter) controls the strength of the barrier. As we approach a constraint boundary where g i (x) approaches 0, the term -log(-g i (x)) approaches infinity, preventing us from leaving the feasible region. Only defined for g i (x) < 0 (strictly feasible points) Continuously differentiable in the interior Grows to infinity as any constraint is approached 3. Decreasing the Barrier Parameter The barrier method works by solving a sequence of unconstrained problems with decreasing values of mu: As mu decreases, the barrier has less influence, and the solutions approach the true constrained optimum on the boundary. 4. Barrier vs. Penalty Methods Barrier methods and penalty methods take opposite approaches to handling constraints: Iterates stay strictly inside feasible region Approach boundary from interior Require strictly feasible starting point Iterates can violate constraints Approach boundary from exterior Increase penalty to enforce constraints

This is the written version of the interactive lesson above. See the full Optimization course.