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.
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…
Supplier Centrality and Auditing Priority in Socially Responsible Supply Chains II: A Stable Joint-Auditing Coalition Audits the Common Supplier and Shares Costs FairlyResearch Paper
Brands that sell consumer goods are held responsible by the public for the labour and safety practices of their suppliers. After the 2013 Rana Plaza collapse in Bangladesh, about 200 clothing brands and retailers signed the Accord on Fire and Building Safety and inspect roughly 1,600 factories jointly; pharmaceutical companies such as Pfizer and GSK audit…
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy 2: The LP Algorithm Decides PCSPs with Majority or Alternating-Threshold Polymorphisms of All Odd AritiesResearch Paper
A constraint satisfaction problem (CSP) asks whether variables can be assigned values so that every constraint of a given instance holds. Feder and Vardi conjectured, and Bulatov and Zhuk proved in 2017, that every CSP over a finite set of relations is either polynomial-time solvable or NP-complete, and that the answer is governed by the polymorphisms of…
An Optimal Algorithm for Stochastic and Adversarial Bandits II: α-Tsallis-INF With Symmetric Regularization Has Anytime Adversarial Pseudo-Regret 2√(min{1/(α−α²), log K/α, log T/(1−α)}·KT) + 1Research Paper
In the adversarial multi-armed bandit problem a learner repeatedly picks one of K arms and observes only the loss of the arm it picked, while an adversary chooses the losses, possibly reacting to the learner's past choices. The minimax pseudo-regret of this problem is of order KT after T rounds, and the classical algorithm Exp3 achieves only …
Computational Optimal Transport XII: The Entropic Barycenter Scalings Are (e^{f_s/ε}, e^{g_s/ε}) for the Solutions of a Dual Program with Σ_s λ_s f_s = 0Textbook
A barycenter summarizes several objects by minimizing a weighted sum of distances to them. For probability histograms, ordinary coordinatewise averages depend strongly on how the bins are labeled. Optimal transport instead lets mass move between bins and charges for those moves through a cost matrix. The resulting Wasserstein barycenter can reflect the…
Computational Optimal Transport IX: The Entropic Cost L^ε_C(a, b) Equals max ⟨f, a⟩ + ⟨g, b⟩ − ε⟨e^{f/ε}, K e^{g/ε}⟩, with Optimal Scalings (e^{f/ε}, e^{g/ε})Textbook
Optimal transport compares two distributions by finding the least expensive way to move mass between them. For finite histograms, the resulting linear program is precise but its optimal coupling can be sparse. In applications where the coupling represents traffic, matching, or a differentiable loss, a sparse plan may be undesirable or expensive to compute…
Supplier Centrality and Auditing Priority in Socially Responsible Supply Chains I: Under Downstream Competition No Buyer Audits the Common Supplier in Any EquilibriumResearch Paper
Brands are routinely held responsible for the labour and environmental practices of their suppliers. A brand that is linked in public to a non-compliant supplier loses consumer willingness to pay, and firms answer this risk by auditing their suppliers. Supply networks are not trees, however: one supplier often serves several competing brands. Chen, Qi and…
Generalising the Scattered Property of Subspaces 2: If h + 1 Divides r and n ≥ h + 1, Maximum h-Scattered 𝔽_q-Subspaces of V(r, qⁿ) of Dimension rn/(h + 1) ExistResearch Paper
A scattered subspace is an Fq-subspace U of an Fqn-vector space V that meets every one-dimensional Fqn-subspace of V in an Fq-subspace of dimension at most one. Scattered subspaces produce scattered linear sets in projective spaces over finite fields, and through them two-intersection sets, two-weight codes,…
Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization 5: Dual Bounds from Active-Set Primal Solutions Lose Only O(kε), Independent of pResearch Paper
Best-subset selection with ridge shrinkage, minβ21∥y−Xβ∥22+λ0∥β∥0+λ2∥β∥22, is a mixed-integer program that statisticians want to solve to certified optimality at the scale of modern data (p up to 107 features). Hazimeh, Mazumder and Saab (arXiv:2004.06152, Mathematical Programming 2022) built a…
Computational Optimal Transport VII: The Entropic Optimal Coupling P_ε Tends to the Maximum-Entropy Optimal Plan as ε → 0 and to a ⊗ b as ε → ∞Textbook
The discrete optimal transport problem of Kantorovich asks for the cheapest way to move a probability histogram a onto a histogram b when moving a unit of mass from i to j costs Ci,j. Its optimal couplings are vertices of a polytope and are typically sparse: they rely on a few routes. Two communities have reasons to blur them. In…
Tikhonov Regularization of a Second Order Dynamical System with Hessian Driven Damping 3: If ∫ ε(t)/t dt = +∞, the Trajectory Converges Strongly in the Ergodic Sense to the Minimum-Norm MinimizerResearch Paper
Second order dynamical systems with vanishing damping are continuous-time models of accelerated first-order methods. The system x¨+tαx˙+∇g(x)=0 is the continuous limit of Nesterov's accelerated gradient method (Su, Boyd, Candès 2016), and its trajectories converge weakly to a minimizer of a convex g when α>3 (Attouch,…
An Optimal Algorithm for Stochastic and Adversarial Bandits I: Tsallis-INF Has Square-Root Adversarial Pseudo-Regret and Logarithmic Pseudo-Regret Under a Self-Bounding ConstraintResearch Paper
A multi-armed bandit learner repeatedly chooses one of several actions, observes only the loss of the chosen action, and tries to perform nearly as well as a single fixed action selected in hindsight. Two common loss models make different demands on the learner. In a stochastic model, each arm has a stable mean loss and the learner can gradually distinguish…
A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization III: Every Limit Point of BSCA with Armijo Steps Is a Stationary PointResearch Paper
Large optimization models often split their variables into blocks that can be handled separately. A method can then solve one smaller approximation problem per iteration instead of the full problem. The block successive convex approximation (BSCA) method of Razaviyayn, Hong and Luo allows the block approximation to guide the search without requiring it to…
Convergence and Dynamical Behavior of the ADAM Algorithm for Nonconvex Stochastic Optimization 6: Decreasing-Step Adam Iterates Are Almost Surely BoundedResearch Paper
Adam (Kingma and Ba, arXiv:1412.6980) is the default optimizer for training neural networks. It combines a stochastic gradient step with two exponential moving averages: a momentum term mn and a coordinatewise second-moment estimate vn that rescales each coordinate of the step. Its convergence theory is delicate: Reddi, Kale and Kumar (arXiv:1904.09237)…
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy 4: F = Pol(Γ) for a Finite Γ iff F Is Projection-Closed, Finitizable and Contains the IdentityResearch Paper
A constraint satisfaction problem (CSP) asks whether variables ranging over a finite domain D can be assigned values so that every constraint from a fixed finite list of relations is satisfied. A central organizing principle of the algebraic theory of CSPs is that the complexity of CSP(Γ) is governed by its polymorphisms, the functions …
A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization II: Limit Points of Cyclic BSUM with Unique Block Minimizers Are Coordinatewise StationaryResearch Paper
Many large optimization problems in signal processing, statistics and machine learning have a variable that splits naturally into blocks, and are solved by updating one block at a time. The classical method of this kind, block coordinate descent (BCD), minimises the objective exactly in one block while the others are held fixed. In practice the exact block…
Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions III: With Lipschitz ∇g and Small Stepsize, the DRS Objective Error Is O(1/(k+1)) and o(1/(k+1))Research Paper
Douglas–Rachford splitting is a method for minimizing a sum of two convex functions when each function has an accessible proximal operator. Its iterates are easy to state, but the speed of convergence of the objective at an individual proximal point is less immediate than convergence of an averaged point or of a residual. For optimization models in which…
Quality in Supply Chain Encroachment I: With Endogenous Uniform Quality, an Encroaching Manufacturer Gains and the Retailer Always LosesResearch Paper
Manufacturers increasingly sell directly to consumers through their own stores and websites, alongside the independent retailers that carry their products. This practice is called supply chain encroachment. Retailers routinely resent it, and examples range from beer brewers to personal computers. Arya, Mittendorf and Sappington (Marketing Science, 2007)…
Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions II: With One Lipschitz Gradient, the Best Relaxed PRS Objective Error Is o(1/(k+1))Research Paper
Many problems in signal processing, statistics and machine learning ask to minimise a sum f+g of two convex functions, each of which is easy to handle on its own through its proximal operator but not jointly. Operator-splitting methods exploit exactly that structure. The Douglas–Rachford (DRS) and Peaceman–Rachford (PRS) splitting schemes, introduced for…
Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization 4: Lagrangian Duals of the Reduced Relaxation and Their Closed-Form Optimal Dual VariablesResearch Paper
Best subset selection with ridge shrinkage, the ℓ0ℓ2-regularized least squares problem
Approximation Algorithms for Product Framing and Pricing 3: Under MNL Pricing, Optimal Framing Fills Pages in Descending Quality Order with One Price per PageResearch Paper
Online retailers show their catalogue on a sequence of pages, and most visitors never reach the last one. Which products appear on the first page, and at what prices, therefore decides what a typical consumer can buy at all. Gallego, Li, Truong and Wang (Operations Research, 2020) model this as the product framing problem: the consideration set of a…
Tikhonov Regularization of a Second Order Dynamical System with Hessian Driven Damping 1: For α > 3 and ∫ tε(t) dt < +∞ the Trajectory Converges Weakly to a Minimizer of gResearch Paper
Minimizing a convex function g on a real Hilbert space H by first-order methods has a continuous-time counterpart: second-order differential equations whose trajectories descend g. Su, Boyd and Candès (20) showed that Nesterov's accelerated gradient method is a discretization of x¨+tαx˙+∇g(x)=0 with α=3, along…