A coordinated effort to formalize the mathematics of operations research in Lean 4.
Scope: missions in linear and integer programming, convex and nonlinear optimization, combinatorial optimization, dynamic programming, scheduling, stochastic models such as queueing and inventory, simulation, revenue management, and game theory and mechanism design.
Fast Polynomial Factorization and Modular Composition 1: The Inverse Kronecker Map ψ Reduces Modular Composition f(g₀, …, g_{m−1}) mod h to One Multivariate Multipoint EvaluationResearch Paper
Modular composition asks, given univariate polynomials f,g,h over a ring, for f(g(X))modh(X). It is the bottleneck step in the classical algorithms for factoring univariate polynomials over finite fields (Cantor–Zassenhaus, von zur Gathen–Shoup, Kaltofen–Shoup), for irreducibility testing and for computing minimal polynomials. Brent and Kung (1978)…
Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methods: Subgradient Rate L̃²(2√(4κ²(N+1)+1)−1)/(N+1) on Weakly Convex FunctionsResearch Paper
Many objectives in statistics and machine learning are neither smooth nor convex, yet are well behaved in a weaker sense: robust phase retrieval, blind deconvolution, robust PCA and training with piecewise-linear losses all lead to weakly convex functions, functions that become convex after adding a fixed quadratic. For such functions the plain subgradient…
An Augmented Lagrangian Based Algorithm for Distributed Nonconvex Optimization 2: Near a Regular KKT Point the Decoupled Subproblems Have Locally Unique Minimizers with ‖y−x*‖ ≤ χ₁‖x−x*‖+χ₂‖λ−λ*‖Research Paper
Many large optimization problems arising in networked control, smart grids, distributed estimation and resource allocation have a separable objective with coupled affine constraints: N agents each own a variable xi and a private cost fi, and only a linear constraint ∑iAixi=b ties them together. Distributed algorithms for such problems let each…
On the Complexity of Nash Equilibria and Other Fixed Points 4: The Fixed Points of the Division-Free Map G_I(x)ij = max(x_ij + u_i((i:j); x−i) − t_i, 0) Are Exactly the Nash EquilibriaResearch Paper
Nash's existence theorem for finite games is a fixed-point theorem: one writes down a continuous map from the set of mixed strategy profiles to itself whose fixed points are exactly the Nash equilibria, and applies Brouwer's theorem. Nash's own map (Nash 1951) divides by 1+∑jmax(0,⋅), and the choice of map matters as soon as the question is…
On the Complexity of Nash Equilibria and Other Fixed Points 2: Block Matching Pennies Gives Every Block the Same Probability and the Matching Player Full Support in Every Nash EquilibriumResearch Paper
Reductions that prove hardness for Nash equilibrium computation encode a computation (a circuit, a fixed-point problem) into the probabilities that players put on their strategies in every equilibrium. For the encoding to be meaningful, the designer has to control how each player distributes probability across groups of strategies, independently of the…
On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems 3: ARC Can Need ε^(−3/2+τ) Iterations to Reach |g| ≤ εResearch Paper
Worst-case iteration counts are the standard way to compare unconstrained optimization methods on nonconvex problems. For finding an approximate first-order critical point, a point with ∥∇f(x)∥≤ϵ, steepest descent needs at most O(ϵ−2) iterations on functions with a Lipschitz gradient. The cubic regularization of Newton's method…
Adaptive Cubic Regularisation Methods for Unconstrained Optimization. Part II: Worst-Case Function- and Derivative-Evaluation Complexity 1: Basic ARC Reaches ‖g‖ ≤ ε in O(ε^(−2)) IterationsResearch Paper
Methods for smooth unconstrained minimization, minx∈Rnf(x), are compared by how many evaluations of f and of its gradient they need, in the worst case, to reach an approximately first-order critical point, an iterate with ∥∇f(xk)∥≤ϵ. For steepest descent with a Lipschitz gradient the answer is O(ϵ−2) (Nesterov, Int…
On the Complexity of Nash Equilibria and Other Fixed Points 1: ε-Nash Equilibria Are Weak (n+1)ε-Fixed Points of Nash's Function, and Weak ε²/(4c²n³)-Fixed Points Are ε-Nash EquilibriaResearch Paper
Nash proved that every finite game has an equilibrium by exhibiting a continuous map of the set of mixed profiles into itself whose fixed points are exactly the equilibria, and applying Brouwer's fixed point theorem (Nash, 1951). Computationally, the same map is the bridge between games and fixed-point problems: complexity classes for total search problems…
Variable Metric Method for Minimization: Davidon's Rank-One Variable-Metric Update Recovers the Inverse Hessian of a Quadratic in N Steps and Then Steps to the Exact MinimumResearch Paper
Quasi-Newton methods minimize a smooth function f:Rn→R using gradients only, while building up an approximation to the inverse of the Hessian matrix from the changes of gradient they observe. They are the default algorithms of unconstrained nonlinear optimization: BFGS and its limited-memory variant L-BFGS sit inside most numerical…
Continuous-Time Average-Preserving Opinion Dynamics with Opinion-Dependent Communications 1: Every Proper Solution of the Discrete-Agent Model Converges to Clusters at Least 1 ApartResearch Paper
Bounded-confidence opinion dynamics model a population in which each individual revises an opinion, represented by a real number, by looking only at opinions close to its own. The best-known example is the discrete-time model of Krause (1997), also called the Hegselmann–Krause model, in which every agent moves to the average of the opinions within distance…
Incremental Proximal Methods for Large Scale Convex Optimization I: With a Cyclic Order and a Diminishing Stepsize, Incremental Subgradient-Proximal Methods Converge to an Optimal SolutionResearch Paper
Many optimization problems in machine learning, signal processing and distributed computation have an objective that is a sum of a large number m of component functions: one per data point, per sensor, or per processor. Evaluating the whole sum, or a subgradient of it, at every iteration is expensive when m is large. Incremental methods process one…
Lyapunov Equations, Energy Functionals, and Model Order Reduction of Bilinear and Stochastic Systems 1: States Reached from 0 Stay in Im P and Ker Q Gives Zero Output, for Gramians P, Q ≥ 0 of (3.6)Research Paper
Balanced truncation is the standard method for reducing the state dimension of a linear control system while keeping its input–output behaviour: states that are both hard to reach and hard to observe are discarded. Its justification rests on two Gramians, the solutions P and Q of a pair of Lyapunov equations, whose quadratic forms measure how much input…
Semismooth and Semiconvex Functions in Constrained Optimization I: The Pointwise Maximum or Minimum over a Compact Family of Continuously Differentiable Functions Is SemismoothResearch Paper
Many objective functions in engineering design, Chebyshev approximation and game-theoretic planning are extremal-valued: they are the pointwise maximum or minimum of a family of smooth functions, E(x)=maxu∈Uf(x,u). Such a function is typically not differentiable at points where two or more members of the family are active, so gradient methods do not…
Retail Assortment Planning in the Presence of Consumer Search V: The Heuristic Equilibrium of No-Search Assortment Planning Is Never Deeper Than OptimalResearch Paper
Retailers decide which product variants to stock, and most assortment-planning tools model consumer choice with the multinomial logit (MNL) model: a consumer who does not find an acceptable variant simply leaves without buying. Cachon, Terwiesch and Xu (Retail Assortment Planning in the Presence of Consumer Search, working paper of December 2002; published…
Retail Assortment Planning in the Presence of Consumer Search III: Under Independent-Assortment Search, the Profit Change from Adding a Variant Is Quasi-Convex in Its PreferenceResearch Paper
A retailer deciding which variants of a product to stock trades off two effects. A deeper assortment captures consumers whose favourite variant would otherwise be missing, but it splits demand among more variants, each of which then carries its operational costs (shelf space, handling, inventory) at a smaller, less efficient scale. Van Ryzin and Mahajan (Man…
A c^k n 5-Approximation Algorithm for Treewidth 1: If tw(G) ≤ k, Pushed Terminal Separations Around a 3/4-Balanced Separation Glue to a Separation of Order k+1 with Sides ≤ 7/8|V|+(|B|+k+1)/2Research Paper
Treewidth measures how closely a graph resembles a tree. Many problems that are NP-hard on general graphs can be solved in time linear in the number of vertices once a tree decomposition of bounded width is available, so computing such decompositions quickly is a basic task in algorithmic graph theory. Bodlaender, Drange, Dregi, Fomin, Lokshtanov and…
Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices 1: Every Connected P₇-Free Graph Has a Connected 2-Dominating Set of at Most Three Vertices or a K₄Research Paper
Graph coloring asks whether vertices can be assigned colors so that adjacent vertices receive different colors. Restricting the graphs by forbidden induced paths can expose structure that is absent from general graphs. Bonomo, Chudnovsky, Maceli, Schaudt, Stein and Zhong study list three-coloring when the graph has no induced path on seven vertices,…
Graphon Mean Field Systems II: The Empirical Measure of the Dense Graphon-Weighted Particle System Converges in Probability to the Averaged Graphon LawResearch Paper
Classical mean field theory describes n exchangeable diffusions, each interacting with the empirical average of all the others. As n→∞ the particles become independent copies of a McKean–Vlasov process (propagation of chaos). Many systems of interest are not exchangeable. Particles sit at the vertices of a network and interact only with their…
Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications: With Fixed Pick-up Times, the Offline Taxi Routing MIO Formulation (5)-(14) Is IntegralResearch Paper
Global Optimality Guarantees for Policy Gradient Methods 2: Under Closure, a (c, µ)-Gradient-Dominated Policy Iteration Objective Makes ℓ (κc/(1−γ), κµ/(1−γ))-Gradient DominatedResearch Paper
Policy gradient methods optimize a parameterized control policy by gradient descent on its long-run cost. They underlie much of modern reinforcement learning, from REINFORCE and actor-critic methods to trust-region and proximal policy optimization, and they are used in operations problems such as inventory control and optimal stopping. Their objective is…
More Risk-Sensitive Markov Decision Processes 5: Under Positive Harris Recurrence a Risk-Neutral Optimal Stationary Policy Is Optimal for Power-Utility Average CostResearch Paper
Classical Markov decision theory minimizes expected cost. A decision maker who dislikes variability, such as an insurer, a portfolio manager or an operator of a service system, may instead evaluate a random cost Y by its certainty equivalentU−1(E[U(Y)]) for an increasing utility (disutility) function U. Bäuerle and Rieder (More Risk-Sensitive…
The Price of Anarchy of Finite Congestion Games III: The Price of Anarchy of the Maximum Social Cost Is Theta(sqrt N)Research Paper
In a congestion game, several users choose facilities and each facility becomes more costly as more users choose it. Such games model settings in which each participant chooses a route or collection of resources for personal use while the resulting load is shared. A pure Nash equilibrium is a stable choice of routes: no single participant can lower their…
Coupling and Convergence for Hamiltonian Monte Carlo 2: Lyapunov Bounds and Local Contractivity Give W_ρ(νπⁿ, ηπⁿ) ≤ e^{−cn}W_ρ(ν, η) + βⁿλⁿ⁻¹(∫ψdν + ∫ψdη)δ(C)Research Paper
Markov chain Monte Carlo methods approximate a target probability measure by the law after n steps of a Markov chain. A quantitative guarantee for such a method is a bound on the distance between the law after n steps and the target, or between the laws of two copies of the chain started from different initial distributions. A standard route to such bounds…
Graphon Mean Field Systems I: The Law of the Graphon Particle System Depends Continuously on the Graphon in the Cut MetricResearch Paper
Large interacting diffusion systems often have different interaction strengths between different pairs of agents. A graphon gives a continuum description of such weighted networks: each agent carries a label in [0,1], and a kernel assigns the strength of interaction between two labels. The question in this mission is whether the law of the resulting…
Competitive Equilibrium with Indivisible Goods and Generic Budgets 3: Two Agents with Identical Additive Preferences and Generic Budgets Have a Competitive Equilibrium Giving Truncated SharesResearch Paper
How should a set of indivisible items (courses, shifts, inherited objects) be divided among people who have different entitlements but no money to transfer? A classical answer for divisible goods is the competitive equilibrium from equal incomes (CEEI): give every agent a budget of artificial currency, find prices at which every agent can afford her…