Docs / Central Path

The central path

The central path is the smooth curve that interior point methods chase: it starts at the most "central" point of your feasible region and ends at the optimum. Unlike the other buttons in lpviz, this one doesn't visualize a practical solver — it computes the ideal object itself.

The log barrier

Take the LP maximize cᵀx s.t. a_iᵀx ≤ b_i and replace the hard constraints with a logarithmic barrier. For a parameter µ > 0, solve

maximize  cᵀx + µ Σ_i log(b_i − a_iᵀx)

The log of each slack acts as an infinitely tall wall at the boundary: as the point approaches any constraint, its slack goes to zero and the barrier term plunges to −∞. The objective is strictly concave, so each µ has a unique maximizer x*(µ) strictly inside the region. The curve of these maximizers, traced as µ varies, is the central path:

• µ → ∞: the objective term becomes irrelevant and x*(µ) approaches the analytic center — the point maximizing the product of slacks, the region's barrier-native notion of "middle". Notice it doesn't depend on c.
• µ → 0: the barrier fades and x*(µ) converges to an optimal point — specifically the analytic center of the optimal face (the midpoint of an optimal edge, or a vertex if the optimum is unique).

How lpviz traces it

The N slider picks how many points to compute (default 75, up to 100). lpviz spaces N values of µ evenly on a log scale from 10³ down to 10⁻⁵ and, for each one, maximizes the barrier objective with damped Newton's method:

1. Form the gradient c − µ Σ a_i/s_i and Hessian curvature µ Σ a_ia_iᵀ/s_i² from the current slacks s_i = b_i − a_iᵀx, and solve for the Newton step.
2. Backtrack the step (halving, with an Armijo sufficient-increase test) until it improves the barrier objective while staying strictly feasible — the barrier itself rejects any step that would cross the boundary.
3. Stop when the gradient's ∞-norm falls below 10⁻⁴.

Each solve is warm-started from the previous µ's optimizer, which is exactly why path-following works: neighboring points on the path are close, so a few Newton steps suffice. The very first solve starts from the centroid of your polygon (or the interior point supplied in 3-variable mode) — the method needs a strictly feasible starting point, which is also why the Central Path button disables when your region is unbounded in the objective direction (the path would escape to infinity).

Reading the picture

• Dot spacing is information. The µ values are evenly spaced in log scale, so wherever dots cluster the path is barely moving. Typically it idles near the analytic center at large µ, sprints through a transition band where the objective overtakes the barrier, and creeps into the optimum.
• The log lists each point with its µ and objective value cᵀx, which increases monotonically along the path as µ decreases.
• In the 3D view, the central path curve is lifted by the full barrier objective cᵀx + µ Σ log(·) — the smoothed landscape it actually climbs — while solver paths are lifted by the plain objective.

Connection to interior point methods

A path-following IPM never computes x*(µ) exactly; it takes one Newton-ish step per µ and stays within a loose neighborhood of the path. To see this correspondence, enable Trace, run Central Path, then run IPM with a small α_max: the two curves shadow each other, converging to the same point of the optimal face. Central Path is the platonic route; IPM is the practical approximation with error bars.

Behavior to watch for

• The flower. Enable Trace and click Rotate Objective: as c sweeps a circle, every central path grows from the same root — the analytic center, which doesn't depend on c — and bends to a different vertex. The resulting bouquet is lpviz's signature picture.
• Optimal faces, not just vertices. Aim c exactly perpendicular to an edge: the path ends at the middle (analytic center) of that optimal edge, not at one of its endpoints like Simplex would.
• Centrality vs. shape. The analytic center is not the centroid: drag one edge to have many nearly-parallel copies (or load Flat Facets) and watch the whole path get pushed away from the crowded side — every constraint contributes its own log term, so redundant constraints still bend the path.
• Small N tells the story too. Set N = 2: you get just the two ends of the path — the analytic center and (nearly) the optimum.