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.

α_max, and what a step size ratio buys

Same directions, same algorithm — only the fraction of each step that is actually taken differs. The small-step path traces the geometry; the large-step path cuts corners the small one never reaches.

Every iteration computes how far it could move before s or y hits zero, then multiplies that distance by α_max. At the default 0.1 you are watching a deliberately slowed-down solver: the trajectory is dense enough to see its curvature, and it stays well inside the region because it never spends more than a tenth of its available room. At 0.99 — what production solvers use — each step lands within one percent of the boundary, the arc collapses into a few chords, and the run finishes in about a dozen iterations. Nothing about the search direction changed; only the appetite.

The corrector threshold

The threshold is a test on the predictor's step ratio, not on the objective: it asks whether the affine direction was blocked, and only pays for a second solve when it was.

The corrector costs a second solve with the same factorized matrix, so it is worth skipping when the predictor is already doing well. The threshold is where "well" is drawn: at the default 0.9, any predictor that can move at least 90% of the way to the boundary in both the primal and the dual is taken as-is. Below that, Mehrotra's corrector is added, and its centering weight σ = (µ_aff/µ)³ scales with how badly the predictor did — barely centering when it was almost free, retreating hard toward the central path when it was blocked at a corner. Raising the threshold toward 0.999 corrects nearly every iteration; lowering it approaches pure affine scaling, which takes the greedy direction and lets the corners deal with the consequences.

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.