Heavy-ball momentum gets a sharp constant, and Wolfe's method inherits simplex's worst cases
The day in optimization
Most of the day's new theory was about how fast classical methods can run, and about where they fail. Heavy-ball momentum got a tight constant on smooth strongly convex functions, and Wolfe's method got an exponential lower bound. Two further papers asked when a standard trick helps: learning-rate decay for SGD, and iterative refinement for LPs. On the computational side, there were new valid inequalities for dial-a-ride, a GPU global solver, and a low-rank SDP method.
Theory
Worst-case rates for classical methods. Hernanz asks how much heavy-ball momentum can beat plain gradient descent on smooth strongly convex functions. Heavy ball with fixed parameters accelerates on quadratics, but no tuning of the two parameters does so on this wider class. The paper writes the best worst-case rate as 1 − c(κ)/κ, where κ is the condition number (so c measures the speedup over a rate of 1 − 1/κ). It proves that c(κ) tends to 8 in every dimension of two or more. This gives a precise measure of the partial speedup that tuned heavy ball can still deliver.
Disser and Mosis settle an open question about Wolfe's method for finding the minimum-Euclidean-norm point in the convex hull of finitely many points. They prove that Wolfe's original insertion rule can take exponentially many iterations. They also connect the method closely to the simplex method for linear programming, so that many simplex lower bounds transfer. This is a statement about worst cases of that rule. It does not say the method is slow on typical inputs.
Ozgul and colleagues study the folk belief that decaying the SGD learning rate helps. They exhibit a natural class of nonconvex functions where, they prove, SGD with decay needs exponentially fewer steps than the alternative they compare against. The abstract excerpt does not say which comparison. The result is for a specific function class, not for all nonconvex problems.
On adaptive methods, Su, Chen and Liu analyze AdamW as a dynamical system. Its fixed points match the stationary points of a constrained, regularized problem, but not all of them are stable. Stability depends on curvature, weight decay and momentum settings.
Precision and exactness. Graven and Nannicini show a limit of iterative refinement for LPs. Refinement raises precision by solving a sequence of related problems. They build a problem class where the size of the solutions in that sequence grows exponentially with the number of refinement steps. They also report evidence that this is not just an artifact of the construction.
Cartis and Zhu show that adding a strong enough Euclidean regularizer, (σ/2d)‖s‖^{2d}, to a polynomial with a nonzero linear coefficient helps sum-of-squares (SoS) methods. Here 2d exceeds the polynomial's degree, and the added term keeps the polynomial's growth in check. The abstract excerpt we have is cut off before the conclusion, so only the setup is stated here.
In practice
Today's search turned up no deployment reported this week, so these are vendor-published examples. Treat the figures as the vendors' claims.
A Slalom write-up describes a rail repair scheduling tool built with Kawasaki on NVIDIA cuOpt. It reports that weekly scheduling that took hours now takes 10 minutes or less. It also says the last-mile leg often accounts for 40–50% of total logistics cost.
Gurobi's case study index lists recent customer stories. These include an October 2026 airline tail-assignment study by M2P Consulting and a September retail-logistics study at ZOZO. We did not see details of either.
Worth watching
- GEAR is a GPU global solver for bounded nonlinear programs. It borrows linear bound propagation from neural-network verification.
- Golak and Schulz add ride-time valid inequalities to the event-based dial-a-ride formulation. They report computation-time cuts of up to 99% on benchmark instances.
- HALLaR+ is a low-rank augmented Lagrangian Frank-Wolfe method for large SDPs. It needs no trace-bounding constraint.
Sources: - Hernanz, heavy-ball rate - Disser and Mosis, Wolfe's method - Ozgul et al., SGD learning-rate decay - Su, Chen, Liu, AdamW stability - Graven and Nannicini, iterative refinement - Cartis and Zhu, SoS-exactness - Slalom, cuOpt route optimization - Gurobi case studies - GEAR - Golak and Schulz, dial-a-ride - HALLaR+
Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.