∇ProvenDecisions
Ctrl K

GPU first-order methods spread to feasibility pumps, and BFGS loses a convergence bound

The day in optimization

Primal-dual hybrid gradient (PDHG) was the main theme. It now appears in semidefinite programming and in a mixed-integer primal heuristic, and a pair of Halpern Peaceman-Rachford (HPR) surveys covers the same GPU-friendly family. The sharpest negative results were a counterexample for BFGS and a worst-case limit on subspace acceleration. Complexity theory also had a good day, with hardness and rank results for integer optimization.

Theory

PDHG keeps widening its scope. TriLog-PDHG (Ding, Yang) uses a triangular log-determinant Bregman kernel to study which solution a first-order SDP method lands on. The question is whether it can provably pick a strictly complementary solution when one exists, and a maximally complementary one otherwise. The title also claims global linear convergence. PDFP (Liu, Lu, Mazumder) applies PDHG to the projection step of the feasibility pump, a standard MILP primal heuristic. The abstract notes that earlier PDHG pump heuristics pose the projection as an LP, which needs auxiliary variables and constraints for general integers. Two surveys of HPR methods, one for linear programming and one for convex composite quadratic programming, cover the GPU-oriented Halpern-type family.

Limits of classical methods. Xu and Hu disprove a three-step error estimate for BFGS with exact line search. They build a smooth, strongly convex function in three variables, with Hessian between ½I and 3/2 I, whose trajectory makes the ratio ‖x_{k+3}‖/(‖x_{k+2}‖‖x_k‖) unbounded. In plain words, the three-step bound fails even on a very well-conditioned problem. Kuruzov et al. show that sequential subspace optimization (SESOP) does not, in the worst case, accelerate without knowing the strong convexity parameter. This holds for subspace methods that forget slowly. It refutes a conjecture and does not rule out other methods.

Ball-proximal methods. Richtárik and Tovmasyan show Frank-Wolfe is an approximation of Broximal Gradient Descent. That method minimizes a linearized objective over the feasible set intersected with a ball. A companion paper, Abdikarimova et al., gives convergence guarantees for the Broximal Point Method under perturbations. It is a first step toward implementable variants, since the exact method needs exact minimization over a ball.

Integer and combinatorial results. Bhardwaj and Narayanan prove that in fixed dimension a rational pure-integer polytope has a polynomial-size split proof of its integer hull. This establishes a conjecture of Basu, Conforti, Di Summa and Jiang for bounded pure-integer polyhedra. On Optimization Online, cubic optimization over three nonnegative integers is NP-hard, a sharp dimension boundary. Aduén gives a quartic in three variables whose only critical point is a local minimum but not a global one. This resolves a 1980 question from Calvert and Vamanamurthy.

Other items. Ding et al.'s successors in the Wasserstein setting (Ushiyama, Feng, Fujii et al.) give accelerated proximal gradient methods on the Wasserstein space, covering KL minimization. Friedlander gives a priori lower bounds on stability radii for the assignment problem under smoothed analysis. Wang, Díaz and Jiang show that benign population landscapes do not transfer to empirical risk minimization in nonsmooth optimization.

In practice

NVIDIA's cuOpt GPU solver was the main item found. o9 Solutions reports a test on real enterprise data, an 8-core CPU baseline against an NVIDIA B200 running cuOpt 26.06. It reports roughly 10x speedup with near-parity solution quality. This is the vendor's own account, with no independent verification. AMPL's early results report some instances solving in under two seconds, and note that convergence stability remains a challenge. Gurobi takes a cautious line, saying GPUs fit sparse linear algebra poorly. The PDFP and TriLog papers above show the research side moving in the GPU direction.

Worth watching

Sources: - o9 Solutions on cuOpt - AMPL early cuOpt results - Gurobi support article

Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.

What do you want to optimize?

Type the math, describe it in words, snap a photo or say it. ProvenDecisions builds the model, solves it, checks it and walks you through it.

One constraint per line, or separated by commas. Add integer: x, y or binary: z for whole-number decisions. LaTeX works too.

Try: