Optimization

Barrier Methods

Keep iterates strictly inside the feasible region by adding a barrier that grows to infinity at the boundary of inequality constraints.

Interior approach

Barrier methods handle inequality constraints g_i(x) <= 0 by adding a term that blows up as any constraint approaches its boundary. The logarithmic barrier B(x) = f(x) - mu * sum log(-g_i(x)) is defined only strictly inside the feasible region and keeps iterates there. As mu -> 0 the barrier's influence shrinks and the minimizer approaches the true optimum.

The central path

Kronos motion — thermal barrier

For each mu > 0, the barrier problem has a minimizer x(mu). As mu decreases, these minimizers trace a smooth central path through the interior that terminates at the constrained optimum on the boundary. Following this path by decreasing mu is the strategy of interior-point methods.

Why interior, not exterior

Every iterate is strictly feasible, which matters when constraint violation is meaningless or dangerous (e.g. a negative pressure).
The barrier is smooth, so Newton's method applies directly to each subproblem.
Convergence is fast: only a few Newton steps per barrier subproblem, and few mu reductions overall.

Log-barrier and self-concordance

The logarithmic barrier is self-concordant, a property that guarantees Newton's method behaves well and yields polynomial-time complexity for convex problems. This theoretical foundation, due to Nesterov and Nemirovski, extends interior-point methods from linear programming to general convex optimization.

Comparison with penalties

Penalty methods approach the optimum from outside the feasible set with increasing weight; barrier methods approach from inside with decreasing barrier. Both suffer ill-conditioning as their parameter goes to its limit, but the primal-dual interior-point framework manages this carefully and is the method of choice for large convex programs.

python

def barrier(x, mu):
    return f(x) - mu*sum(math.log(-gi(x)) for gi in G)  # need g_i(x) < 0

Barrier and interior-point methods keep iterates physically feasible throughout the search, valuable when constraints encode hard operating limits.