Interior-Point Methods

Walk inside the feasible region, not along its walls. A barrier keeps you interior while Newton steps pull central, then the barrier fades to the corner.

The central path runs from a deep interior point at barrier weight 1.0 to the vertex as the weight falls to 0.001

Why Does This Exist?

Simplex crawls on some LPs (exponential worst case) and nonsmooth active-set chatter stalls on degenerate walls. Large sparse LPs, QPs, SOCPs, and SDPs need polynomial-time reliability, not corner-hopping luck.

Interior-point adds a log barrier $-\\mu\\sum\\log(\\text{slack})$ holding iterates strictly inside, Newton-steps the smoothed KKT system (the central path), and shrinks $\\mu \\to 0$ . Primal-dual variants track both sides with $O(\\sqrt{n}\\log(1/\\epsilon))$ iterations. They solve the programs in linear programming and convex optimization at scale.

The one idea you need first

Slack $s_i = b_i - a_i^\\top x > 0$ measures wall distance. $-\\log s_i$ explodes at walls, gently inside: the barrier tolls proximity without forbidding approach. Central path points minimize $c^\\top x - \\mu\\sum\\log s_i$ per $\\mu$ .

Think of It Like This

Hallways, not walls

Simplex slides along walls feeling for corners. Interior-point walks the hallway middle, guided by guard rails (barrier) that push back near walls. As the hallway narrows ( $\\mu$ shrinks), the middle converges to the exit corner.

Hallway walking ignores corner count, which is why it wins huge rooms. Where it stops: narrow doorways (ill-conditioning) still squeeze Newton steps, needing careful linear algebra.

How It Actually Works

Each iteration: Newton-solve the perturbed KKT ( $Ax + s = b$ , $A^\\top y + c = 0$ ... with $s_i z_i = \\mu$ ), step to stay interior, shrink $\\mu$ by 0.1-0.5x on progress. Mehrotra predictor-corrector adapts $\\mu$ per step in practice. Cross over to a vertex afterward if a basic solution is needed. Sparse Cholesky/KKT factorization dominates cost; ordering and regularization decide speed.

Worked example

Minimize $-x$ over $0 \\leq x \\leq 1$ (push right). Barrier $B(x) = -\\log x - \\log(1-x)$ . Minimize $-x + \\mu B$ : derivative $-1 - \\mu/x + \\mu/(1-x) = 0$ . At $\\mu = 0.1$ : solve $-1 - 0.1/x + 0.1/(1-x) = 0$ . Try $x = 0.916$ : $-1 - 0.109 + 1.19 = 0.081$ ; $x = 0.909$ : $-1 - 0.11 + 1.099 = -0.011$ . Root near $0.910$ . At $\\mu = 0.001$ : root near $0.999$ . Path $0.910 \\to 0.999 \\to 1$ : interior points sliding to the vertex as $\\mu$ fades.

Code

1mu = 0.12x = 0.53for _ in range(50):  # Newton on -x + mu*B4    g = -1 - mu / x + mu / (1 - x)  # gradient5    h = mu / x**2 + mu / (1 - x)**2  # Hessian6    x = min(max(x - g / h, 1e-6), 1 - 1e-6)7print(round(x, 3))  # -> 0.91

Newton lands at 0.910 for $\\mu = 0.1$ , matching the hand root. Shrink $\\mu$ and repeat toward 1.

Watch Out For

Starting on the boundary

Barrier $\\log 0$ is infinite: boundary starts crash immediately. Strict interior starts are mandatory, and aggressive steps that cross walls diverge next iteration.

Initialize strictly inside (analytic center heuristics) and backtrack to stay interior. If iterates stick at $10^{-12}$ slack, the step logic is broken.

Solving KKT systems naively dense

Dense factorization of million-variable KKT systems exhausts memory in one step. Teams blame the algorithm while the linear algebra choice kills it.

Exploit sparsity, use iterative solvers with preconditioners, or switch to first-order for extreme scale. Profile the factorization before the iteration count.

The Quick Version

Barriers hold iterates interior; Newton tracks the central path; shrinking $\\mu$ lands the corner.
Example $-x$ on $[0,1]$ : path 0.910 at $\\mu=0.1$ sliding to 0.999.
Primal-dual path-following runs polynomial time on LP, QP, SOCP, SDP.
Predictor-corrector adapts $\\mu$ ; crossover recovers vertices when needed.
Start strictly interior and step to stay there.
Sparse KKT algebra decides large-scale speed.