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
- Log-Driven Semantic Tuning uses an LLM to read MIP solver logs and adjust parameters, in place of black-box tuning.
- Subgradient methods for nonsmooth SAA: after O(log n) full-batch updates the solution matches an SAA solution's first-order behavior, even when the iterates do not converge.
- Movement-budget threshold for dynamic regret shows a hard movement budget creates a feasibility barrier for tracking.
- Aries extends the dogleg path to three segments for trust-region subproblems.
- Convex regression at scale keeps only K nearest-neighbor hyperplane constraints instead of O(n²).
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.