The Barrier Method

Trade every hard wall for a smooth one, then let the wall sharpen.

The idea

The barrier method solves a convex problem with inequality constraints by replacing the constraints with a smooth penalty, so that Newton's method — from Newton's Method for Minimization, which requires a smooth objective and no constraints — can be applied. Enforced exactly, a constraint $f_{i}(x) \le 0$ adds to the objective the indicator $I_{-}(u)$, equal to $0$ for $u \le 0$ and $+\infty$ for $u > 0$, evaluated at $f_{i}(x)$. This enforces every constraint and destroys differentiability.

Replace each indicator by the smooth approximation $\widehat{I}_{-}(u) = -\frac{1}{t}\log(-u)$, defined for $u < 0$: convex, increasing, finite strictly inside the feasible set, and rising to $+\infty$ at the boundary — the more steeply, the larger $t$ is. Multiplying through by $t$, the function to minimize becomes

$t f_{0}(x) + \phi(x), \qquad \phi(x) = -\sum_{i=1}^{m} \log\big(-f_{i}(x)\big),$

where $\phi$ is the logarithmic barrier. This is an unconstrained smooth convex problem, so Newton's method can solve it; its minimizer is written $x^{\star}(t)$.

The barrier method minimizes this for a modest $t$, multiplies $t$ by a factor $\mu > 1$, solves again starting from the previous answer, and repeats. As $t$ grows, the minimizers $x^{\star}(t)$ converge to a solution of the original constrained problem, and each one certifies its own accuracy: $f_{0}(x^{\star}(t))$ exceeds the optimal value by at most $m/t$.

Ways to work on it

• Walkthrough. Build the logarithmic barrier for a small linear program, walk its central path in closed form, and read off the accuracy the method can certify.
• Proof. Prove the accuracy guarantee: every central-path point carries a dual feasible certificate of its suboptimality.
• Practice. Compute central-path points, count the outer iterations a tolerance demands, and set up a strictly feasible start.
• Hardest. Follow the central path of a degenerate linear program and test the accuracy guarantee against the truth.

Not sure where to start? Take the ten-question placement test.