Docs / PDHG

PDHG: primal-dual hybrid gradient

PDHG solves a linear program using nothing but matrix–vector products and projections — no factorizations, no linear systems. That simplicity is why it powers modern GPU-scale solvers like Google's PDLP. In lpviz you can watch its signature behavior up close: iterates that spiral into the optimum.

The idea

Instead of attacking maximize cᵀx s.t. Ax ≤ b directly, PDHG works on its saddle-point (Lagrangian) formulation with a dual price y_i ≥ 0 per constraint. The primal player nudges x uphill on the objective minus what the current prices charge for constraint violation; the dual player raises the price of any constraint that is violated. In lpviz's default inequality mode, one iteration is:

y_k+1 = [y_k + τ(Ax_k − b)]₊
ȳ = 2y_k+1 − y_k  (extrapolation)
x_k+1 = x_k + η(c − Aᵀȳ)

where [·]₊ clips negatives to zero (prices can't go negative). The extrapolation step — using the reflected dual 2y_k+1 − y_k rather than y_k+1 itself — is what makes the scheme convergent (this is the Chambolle–Pock method, 2011). Each iteration costs exactly one multiply by A and one by Aᵀ, which is why PDHG scales to LPs with billions of nonzeros where factorization-based methods (Simplex, IPM) run out of memory.

Unchecking Inequality mode switches to the textbook standard-form variant: the problem is rewritten with split variables and slacks (x = x⁺ − x⁻, Ax + s = b, all variables ≥ 0), the projection moves to the primal update, and the extrapolation moves to the primal side. The LP is the same, but the splitting geometry — and therefore the trajectory you see — is different.

Step sizes and divergence

The sliders η (primal) and τ (dual) are the two step sizes, 0.25 by default. PDHG converges when η·τ·‖A‖² < 1; beyond that the spiral stops contracting and the iterates fly apart. lpviz doesn't hide this — push both sliders toward 0.75 on a region with many facets and you can watch the divergence live (the run halts once the residuals overflow). Divergence from too-aggressive step sizes is a real failure mode first-order methods must manage; production solvers pick and adapt these step sizes automatically.

The shape of that condition is worth knowing before you drag the sliders. lpviz normalizes every constraint to a unit normal, so ‖A‖ depends only on how many edges your region has and how their normals are spread: for m normals pointing in evenly spread directions, ‖A‖² is exactly m/2, and the condition becomes η·τ < 2/m. The default η = τ = 0.25 gives η·τ = 0.0625, which clears that bar for regions up to 32 edges — so the defaults are safe on essentially every preset, and the way to leave the safe zone is to draw a region with many facets and then push both sliders up. Past the bar convergence is no longer guaranteed rather than immediately impossible: the condition is sufficient, not necessary, and on a small region you will often still converge — faster, in fact — while on a many-faceted one the iterates run away.

Convergence and termination

PDHG is a first-order method: cheap iterations, but many of them. The average iterate converges at a sublinear O(1/k) rate, and you'll see the signature long tail — early iterations cover most of the distance, then the spiral tightens excruciatingly slowly. lpviz stops when the scaled KKT error

ε = max( primal infeasibility, dual infeasibility, duality gap )

drops below 10⁻⁵ (each term relative-scaled) or when the iteration cap is hit. The eps column of the log tracks ε, and Infeas shows the raw constraint violation of the current point — unlike Simplex, PDHG iterates are only feasible in the limit.

Halpern acceleration and restarts

The Halpern checkbox enables the acceleration scheme used by recent PDLP-family research (restarted Halpern PDHG). Instead of taking the raw PDHG step T(z_k), the iterate is blended with a fixed anchor point:

z_k+1 = ^k⁄_k+1 · T(z_k) + ¹⁄_k+1 · z_anchor

The pull toward the anchor damps the spiraling, and periodically the anchor is restarted to the current iterate. lpviz restarts adaptively, when the fixed-point residual has dropped to 20% of its value at the last restart, when it has dropped below 50% and begins rising again, or after a fixed fraction of the total iteration budget. Restart iterations are marked with an r in the log and highlighted along the path. With restarts, the convergence rate on LPs improves from sublinear to linear — flip Halpern on and off with Trace enabled and compare both the shape of the path (straighter, punctuated segments vs. a smooth spiral) and the final iteration counts.

Color by basis

Color by basis colors each iterate by a fingerprint of its active set — which constraints currently have a positive dual price (inequality mode) or which variables sit at zero (standard-form mode). The color typically flickers early, then locks in well before the numbers converge: the iterates have identified which constraints will be tight at the optimum — the optimal basis — even though the point itself is still spiraling. This "basis identification" behavior is exactly what advanced implementations exploit to jump to an exact solution early.

The controls

Behavior to watch for

• The spiral is the saddle. The primal iterate orbits the optimum because it is one half of a primal-dual pair circling a saddle point; what looks like overshooting is the dual prices catching up. The x/y numbers oscillate above and below their limits.
• Conditioning bites. On the Needle preset (a long, thin region), the spiral flattens into a slow crawl — first-order methods inherit the geometry of the problem. Compare with IPM, which barely notices.
• Cheap iterations, many of them. PDHG might take 50× more iterations than IPM on the same drawing, yet each iteration is only two matrix–vector products. That trade is the entire story of first-order LP solvers.
• Restarts change the shape. With Halpern on, the path advances in near-straight "sprints" between restart markers instead of circling.