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 yi ≥ 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:
yk+1 = [yk + τ(Axk − b)]₊
ȳ = 2yk+1 − yk (extrapolation)
xk+1 = xk + η(c − Aᵀȳ)
where [·]₊ clips negatives to zero (prices can't go negative). The extrapolation step — using the reflected dual 2yk+1 − yk rather than yk+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 long constraint vectors 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.
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(zk), the iterate is blended with a fixed anchor point:
zk+1 = k⁄k+1 · T(zk) + 1⁄k+1 · zanchor
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
| Control | Default | What it does |
|---|---|---|
| η (primal step size) | 0.25 | How far x moves per iteration. Larger is faster until η·τ·‖A‖² ≥ 1, then divergence. |
| τ (dual step size) | 0.25 | How fast constraint prices react. Interacts with η via the same stability product. |
| Maximum iterations | 1,000 | Iteration cap (log scale, up to 100k). PDHG routinely needs thousands on hard geometry. |
| Inequality mode | on | Run directly on Ax ≤ b; off = standard-form reformulation with split variables and slacks. |
| Halpern | off | Anchored acceleration with adaptive restarts (r rows in the log). |
| Color by basis | off | Color iterates by active-set fingerprint to watch basis identification. |
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.