Retrospective approximation meets interior points, and a conditional look at network games
The day in optimization
Two new Optimization Online postings, and no more. One is a algorithmic paper on constrained stochastic optimization. The other is a conditional complexity paper that takes recent, unverified claims as its premise.
Theory
Interior points for expectation objectives. A new paper proposes, analyzes and tests a retrospective-approximation interior-point method. It targets problems whose objective is an expectation over a random variable. The constraints are inequalities, and possibly equalities, that may be nonconvex. Retrospective approximation replaces the expectation with a sample-based problem, solves it to some accuracy, then repeats with a better sample. The interior-point part handles the constraints. The abstract says the method combines the two ideas. It does not give convergence rates or benchmark numbers, so those details need the full paper.
Equilibria under a hypothetical ETH collapse. The second paper, Exact Equilibrium Analysis of Sparse Network Games in Subexponential Time, starts from a premise. It says two independent groups claimed in October 2026 to have deterministic algorithms that count satisfying assignments of a k-CNF formula in 2^{o(n)} time. That would refute the Exponential Time Hypothesis (ETH), which says such algorithms cannot exist. In plain words, 2^{o(n)} means the running time grows more slowly than any fixed exponential 2^{cn}. The authors ask what this would imply for exactly analyzing equilibria in games where each player interacts with a bounded number of others. The result is conditional on the claims. The abstract is truncated in the item, so the exact guarantees are not shown here. The claims themselves are not established by this paper, and the conclusions hold only if they are confirmed.
In practice
Little new deployment news surfaced this week. One older example is a vendor case study. Atoptima, a routing-optimization vendor, reports that the SAFO Group cut its transportation costs by 20% through better filling rates and fewer kilometers. This is the vendor's own claim. The page is undated and has not been independently verified.
Worth watching
- Confirmation or refutation of the October k-CNF counting claims. The network-games result stands or falls with them. See the conditional analysis.
- Whether the retrospective-approximation interior-point paper reports numerical tests against existing stochastic constrained solvers. See the paper page.
Sources: - Exact Equilibrium Analysis of Sparse Network Games in Subexponential Time - A Retrospective-Approximation Interior-Point Method - Atoptima: Optimization solvers for vehicle routing optimization in SaaS
Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.