∇ProvenDecisions
Ctrl K

Tight bounds and a sharper barrier: theory sets the pace while solvers go first-order

The day in optimization

Most of today's news was theory. Several papers settled how hard certain problems are: the power-cone barrier, Goldstein stationarity, and high-order smooth minimization. A second thread was how to get more out of first-order and GPU-friendly solvers, through better stepsizes, reformulation and preconditioning. The industry evidence for the week was thin and came mostly from vendors.

Theory

Barrier parameter of the power cone. Zhang, Fu and Dai determine the best logarithmically homogeneous self-concordant barrier parameter for the three-dimensional power cone (arXiv 2611.06404). For exponent c in (0,1), they prove it equals 3/(1+min{c,1−c}). Except at c = 1/2, this is strictly smaller than the parameter 3−2·min{c,1−c} of Chares' conjectured barrier. The barrier parameter drives the worst-case iteration count of interior-point methods, so a smaller value means a better worst-case bound. The abstract does not say whether a barrier attaining the optimum is practical.

Complexity bounds for nonsmooth, high-order and finite-sum problems. Several papers pin down what any method can achieve: - Ding and Yuan study deterministic oracle complexity for (δ,ε)-Goldstein stationary points of constrained Lipschitz functions. They use a resisting-oracle construction for closed feasible sets that are star-shaped with respect to an interior ball, which includes all convex bodies (arXiv 2611.06739). This is a lower bound on what any deterministic algorithm needs. - Bai gives tight lower bounds for minimizing functions with Hölder-continuous p-th derivatives (degree ν) that are uniformly convex of degree q, when the orders match (q = p+ν) (arXiv 2611.05527). - Zhou shows that finding approximate local minima of nonconvex finite sums, in the high-accuracy regime, takes Θ̃(n^{3/4} L^{1/2} ρ^{1/4} Δ ε^{-7/4}) component queries. Here n is the number of components and ε the accuracy (arXiv 2611.05807). The paper gives matching upper and lower bounds. - Rudomanov, Fomin, Gasnikov and co-authors derive upper and lower oracle bounds for sums of convex (L₀,L₁)-smooth functions, where the Hessian norm is bounded by an affine function of the gradient norm (arXiv 2611.04171).

Gradient descent, analyzed by computer. Hong and Ling formulate N-step worst-case analysis of constant-stepsize gradient descent under the Polyak–Łojasiewicz condition as a semidefinite relaxation (arXiv 2611.06713). Zhang and Jiang build stepsize schedules of arbitrary length for smooth strongly convex problems. Their families reach iteration complexity Θ(κ^ρ log(1/ε)) for a fixed condition number κ = L/μ, where κ is the ratio of the largest to the smallest curvature (arXiv 2611.05242). The abstract excerpt does not give the value of ρ.

Games and the sum-of-squares hierarchy. Nan and Kroer show that alternating mirror descent in zero-sum games reaches near-constant (logarithmic) regret. This settles an open question after earlier O(T^{1/3}) and O(T^{1/5}) bounds (arXiv 2611.05243). Henrion, Ibrahim and Magron turn a floating-point SOS solution into an exact rational certificate by rounding, repairing each block residual, and absorbing constants along a recession direction (arXiv 2611.06315).

Complexity of KKT points. Deligkas, Fasoulakis and Ioannidis prove that finding a KKT point of a quadratic over the unit hypercube stays CLS-complete even when coefficients are written in unary (arXiv 2611.03945). The abstract calls it the first problem shown to remain CLS-hard under unary input.

In practice

PDLP and reformulation. Dentes and Lu argue that reformulating an LP, which is thought to matter little for interior-point methods, does matter for first-order solvers based on primal-dual hybrid gradient such as PDLP. They apply this to QUBO and joint replenishment (arXiv 2611.05076). This is a research claim, not a deployment report.

Vendor-reported deployments. A Timefold and AWS case study on e-switch's planning system reports, in the vendor's own figures, more than $100 million in annual savings and more than 10 million kg of avoided carbon emissions (AWS blog). This is not new this week, and the figures are self-reported. An eCommerceNews interview from May 2026 says Jetstar uses Gurobi for scheduling, crew allocation and disruption handling, and reports gains in fuel efficiency and resilience (eCommerceNews).

Worth watching

Sources: - arXiv 2611.06404 - arXiv 2611.06739 - arXiv 2611.05527 - arXiv 2611.05807 - arXiv 2611.04171 - arXiv 2611.06713 - arXiv 2611.05242 - arXiv 2611.05243 - arXiv 2611.06315 - arXiv 2611.03945 - arXiv 2611.05076 - AWS blog - eCommerceNews

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: