∇ProvenDecisions
Ctrl K

ADMM's step-size limit, ReLU networks that attain their minimum, and a BCC lattice proof

The day in optimization

Theory dominated. The main threads were the convergence of first-order methods (ADMM, fixed-point acceleration) and existence results for learned models. A third thread was exact structure in classical problems, including lattices, TSP variants and pricing. On the applied side, mixed-integer MPC and decision-focused learning both aimed at cutting solver calls.

Theory

ADMM step sizes. In classical two-block ADMM, the multiplier (dual) update is scaled by a step factor. The long-standing safe range is up to the golden ratio, about 1.618. Liu, Dai and Wen study how far that factor can go with the penalty held fixed. Their setting is closed proper convex objectives, with a KKT point existing and each subproblem attaining its minimum. They report that the constraint images and the multiplier converge for a range of factors extending beyond the golden ratio. The title also promises counterexamples, so the paper appears to mark where the guarantee stops. The abstract excerpt doesn't give the exact range.

Existence of minimizers for ReLU networks. Martinet and Bungert prove that one-hidden-layer ReLU networks with at most N neurons form a weakly closed set in W^{1,p}(Ω). Here Ω is a bounded connected open set. Weak closedness means a limit of such networks is again such a network. The consequence is that any coercive, weakly lower semicontinuous energy attains its minimum over this set. The authors list the Deep Ritz method with convex integrands, Sobolev training and Lipschitz learning as covered cases. This is an existence result: it says a best network exists, not that training will find it.

Fixed-point and Wasserstein geometry. Aksenov and Gutierrez Hernandez optimize over probability measures. They represent each measure as a neural-network pushforward of a reference distribution and give the parameter space the induced Wasserstein metric. Natural gradient descent then reads as a fixed-point iteration on a Riemannian manifold, and they accelerate it. In related work, Sartor builds a first-order calculus for functionals on nonnegative measures under the Wasserstein–Fisher–Rao distance. That calculus covers both transport and mass reweighting.

Combinatorial and discrete results. - Liu, Spalding-Jamieson and Zheng give improved approximation and hardness bounds for β-TSP. In this variant the triangle inequality is relaxed to ℓ(u,w) ≤ β(ℓ(u,v)+ℓ(v,w)), which interpolates between metric and unrestricted TSP. - Luo proves that the BCC lattice uniquely minimizes the p-th moment of the Voronoi cell among unit-covolume 3D lattices, for every finite p ≥ 1. This settles the Graf–Luschgy conjecture in 3D. - Dobson, Jog and Shiu give quasipolynomial-time planning for "decodable" POMDPs. This extends earlier quasipolynomial results for observable POMDPs. - Nemesch, Ruzika, Thielen et al. give approximation algorithms for right-hand-side parametric LPs, which are hard to solve exactly.

Conic and nonsmooth modelling. Li and Fukuda ask whether smooth equality constraints can replace exponential-cone constraints in nonlinear problems. Smooth equalities would let standard NLP solvers handle these problems. Huyen, Jiao and Tuyen derive second-order optimality conditions for C^{1,1} sparsity-constrained problems through disjunctive programming.

In practice

No new deployment report from this week turned up. The best documented case is older and comes from vendor-linked material. AWS's write-up on e-switch describes a planning-optimization system built on Timefold and run on Amazon EKS so it scales up and down. The write-up reports more than $100 million in annual cost savings and more than 10 million kg less CO₂. Treat both as claims from AWS and e-switch.

The applied papers today point at the same bottleneck: solve time. Nurkanović proposes mixed-integer nonlinear MPC that solves a continuous relaxation at a predicted state before the measurement arrives. This shortens the delay between measurement and control action. Zheng, de Nijs and Lam propose decision-focused learning for NP-hard edge-selection problems without solver calls or optimal-solution labels. Separately, Wang, Sharma and Ramachandran co-optimize battery sizing and capacity allocation to speed up data-center grid interconnection.

Worth watching

Sources: - AWS: e-switch with Timefold and AWS - The multiplier step size in classical two-block ADMM - On the (non-)closedness of the set of ReLU networks

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: