Docs / Interior Point

Interior point methods

Where Simplex crawls the boundary, an interior point method (IPM) cuts straight through the middle: it keeps every iterate strictly inside the constraints and follows a smooth arc to the optimum. lpviz implements a Mehrotra-style primal-dual predictor–corrector method — the algorithm at the core of most modern LP solvers.

An infeasible start: the first iterates may sit outside the region, then the path bends inward and converges to the optimal vertex.

The idea

For the LP maximize cᵀx s.t. Ax ≤ b, introduce a slack s = b − Ax ≥ 0 and a dual multiplier y_i ≥ 0 for each constraint. A point is optimal exactly when the KKT conditions hold:

Ax + s = b, Aᵀy = c, s_i y_i = 0 for all i, s, y ≥ 0.

The hard part is complementarity (s_iy_i = 0): it forces every constraint to be either exactly tight or carry zero price, which is combinatorial. IPMs relax it to s_iy_i = µ for a positive parameter µ, solve that smooth system approximately with Newton's method, and drive µ → 0. The solutions of the relaxed system, traced over µ, form the central path — the smooth curve the iterates loosely follow. This is what makes IPMs polynomial-time in theory (the line of work started by Karmarkar in 1984) and remarkably consistent in practice: iteration counts barely grow with problem size.

What one iteration does

lpviz's IPM keeps a triple (x, s, y) with s, y > 0 and, at every iteration, measures the average complementarity µ = sᵀy/m, then:

Predictor. Solve the Newton (KKT) system for the affine-scaling direction — the step aiming straight at µ = 0 — via a dense LU factorization of the full (n + 2m)-dimensional system.
Step length. Compute the largest steps that keep s and y strictly positive (the fraction-to-boundary rule), separately for the primal and dual.
Corrector (adaptive). If the predictor can move nearly unimpeded — both step ratios at least the corrector threshold — lpviz just takes the affine step. Otherwise it adds Mehrotra's corrector: a second solve with the same matrix that (a) recenters toward the central path with weight σ = (µ_aff/µ)³, where µ_aff is the complementarity the predictor would reach, and (b) compensates for the second-order error Δs_iΔy_i the linearization ignores. When the predictor did well, σ is tiny (barely center); when it got blocked, σ approaches 1 (retreat toward the path).
Move. Update (x, s, y) using the fraction-to-boundary steps scaled by the α_max slider.

Convergence is declared when the primal residual, the dual residual, and the relative duality gap are all below 10⁻⁵.

Infeasible start

The method starts at x = 0 (the canvas origin) with s = y = 1 — which typically does not satisfy Ax + s = b. That's deliberate: this is an infeasible-start IPM, and the Newton steps shrink the constraint violation and the duality gap simultaneously. Watch the Infeas column of the log: it decays to zero alongside µ. If your polygon doesn't contain the origin, the first few iterates visibly sit outside the region before the path dives in.

The controls

Control	Default	What it does
α_max (max step size ratio)	0.1	Scales every step. The default is intentionally tiny so you get a long, smooth trajectory to look at. Real solvers use ≈ 0.99; try it to see the algorithm converge in a dozen iterations, cutting corners the small-step arc never would. At exactly 1, iterates may land on the boundary itself.
Corrector threshold	0.9	The step quality above which the corrector is skipped. Raise it toward 0.999 and nearly every iteration is corrected — the path stays well-centered. Lower it and the method degenerates toward pure affine scaling — greedier steps that hug the boundary and can stall near corners.
Maximum iterations	1,000	Iteration cap (log scale, up to 100k). Small α_max values need more iterations to converge.

Reading the log

 Iter        x        y        Obj     Infeas          µ
    1     0.00     0.00    0.0e+0    2.4e+1    1.0e+0
    2     1.13     0.62    1.4e+1    1.1e+1    4.2e-1

Obj: current objective value cᵀx — unlike Simplex it need not increase monotonically, especially while infeasible.
Infeas: the primal residual ‖b − Ax − s‖_∞ — how far the iterate is from satisfying the constraints.
µ: average complementarity sᵀy/m — the "distance along the central path"; optimality is µ → 0.

Behavior to watch for

It shadows the central path. Enable Trace, run IPM with α_max = 0.1, then run Central Path on the same region: the IPM arc runs alongside the central path in a loose neighborhood — the theory made visible.
Geometry-independent iteration counts. Switch between Pentagon and Many Facets with α_max ≈ 0.99: the iteration count barely changes, while Simplex pivot counts scale with the number of vertices crossed.
The endgame is superlinear. Look at the µ column: once the iterate is near the optimum, µ collapses by orders of magnitude per iteration.
It converges to the analytic center of the optimal face. Make the objective exactly perpendicular to an edge (so a whole edge is optimal): IPM lands in the middle of that edge, while Simplex picks one of its endpoint vertices.