∇ProvenDecisions
Ctrl K

Muon under shuffling, a Polyak-Łojasiewicz retrospective, and a polynomial-time result for slope change

The day in optimization

The day's items split into three groups. Optimizer theory covered Muon, auto-conditioned multiobjective descent and trust-region methods. Structured discrete problems covered hardness and tractability results. Power-grid optimization covered both data and methods. The practice section draws on vendor-reported case studies. None of them is dated this week.

Theory

Muon under shuffling. Muon keeps a momentum buffer of stochastic gradients and orthogonalizes it to get each update direction. In practice it is run with shuffling, meaning each epoch visits the data in a permuted order without replacement. Huang, Pu and Johansson title their paper "Muon Attains O(ε⁻³) Iteration Complexity under Shuffling". The snippet says nothing further about assumptions, so read the paper before relying on the rate. Here O(ε⁻³) is the iteration count needed to reach accuracy ε, up to constants. This is an upper bound on Muon's cost, not a claim that the rate is optimal.

The PL condition, ten years on. Karimi, Nutini and Schmidt look back at their 2016 paper that named the Polyak-Łojasiewicz condition for an older idea. They received the 2026 PKDD ECML Test of Time Award. The note covers the paper's origins and offers an "AI-assisted refined version" of the main theorem. It is informal and candid, and a useful read for students.

Other first-order and multiobjective methods. - Jiang proposes two linesearch-free steepest-descent methods for smooth multiobjective problems, AC-SDM and AC-NGDM. They estimate the local Lipschitz constant (a bound on how fast the gradient can change) from earlier function and gradient values. - Jiang and Luo propose an accelerated multiobjective gradient flow with implicit Hessian-driven damping. It is written as two first-order equations that use a single projection operator. - Tang and Lu build a penalty-based min-max-min formulation, ParetoM³. It minimizes a preference function over the weak Pareto set of nonconvex objectives. - Shashaani, Cartis and Dzahini analyze the adaptive-sampling trust-region method ASTRO-DF in random subspaces along almost every sample path. That is a guarantee about the run in hand, not only about its average behaviour.

Conic and equilibrium solvers. Cummins, Santamaria and O'Donoghue define a central path for the homogeneous embedding of quadratic cone programs. Its equations are strongly monotone, with the barrier parameter as the modulus. They prove the path exists, is unique and smooth, and lies on a sphere of fixed radius. They also derive Josephy-Newton steps that exploit the embedding operator's closed-form resolvent. Separately, Bemporad and Tatarenko adapt the parametric active-set method of Best (1996) and qpOASES into gPAQ. It targets monotone linear-quadratic generalized Nash equilibrium problems with shared constraints.

Discrete problems. - Narula and Dey show polynomial-time solvability for fitting a multidimensional time series with continuous piecewise-linear functions that share one breakpoint. They treat both the dense and the k-sparse settings. The underlying problems are nonconvex mixed-integer programs. - Sparse PCA with overlapping supports establishes NP-hardness and an FPTAS. The abstract describes the fixed-rank covariance setting. - Pacheco, Carvalho and Yu characterize valid inequalities for bilevel programs with a binary leader and a shortest-path follower. Even with ideal formulations for the leader and follower primal sets, fractional solutions can still appear in the continuous relaxation. - Sun and Udwani give a (1−1/e)² approximation for joint assortment and inventory under any ranking-based choice model. It applies to identically priced products with uncertain total demand. The factor is about 0.40 of the optimal sales.

In practice

Timefold and AWS describe a rail-maintenance deployment for e-switch. They report coordinating 1,200 field technicians, work that once took 60–70% of 120 dispatchers' time and now takes a few hours. They also report savings above $100 million a year and more than 10 million kg of carbon reduction. These are vendor-reported, unaudited figures, and the page is not dated this week. Source: AWS Alps blog.

On the grid side, Donkiewicz, Gaul and Lübbecke present a mixed-integer linear program that jointly handles line switching, substation reconfiguration, generator commitment and redispatch, and transformer settings. It uses branch-and-Benders-cut for real-world transmission congestion management. EPIGRIDS releases seven open synthetic transmission cases of 250 to 78,484 buses, built with an optimization-based method.

Worth watching

Sources: - AWS Alps blog on e-switch, Timefold and AWS

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: