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.
Contact Interactions on a Lattice II: If λₖ/μ < k/(2d − 1), the Expected Size of a Contact Process Is Integrable in TimeResearch Paper
The contact process is the basic model of an infection spreading on a graph: infected sites recover at a constant rate, and healthy sites are infected at a rate that depends on how many of their neighbours are infected. T. E. Harris introduced it in Contact Interactions on a Lattice (Ann. Probab. 2, 1974, doi:10.1214/aop/1176996493), and it became one of…
Global Convergence Properties of Conjugate Gradient Methods for Optimization II: Conjugate Gradient Methods with β_k ≥ 0 and Property (*) Are Globally Convergent under Sufficient DescentResearch Paper
Nonlinear conjugate gradient methods minimize a smooth function f of n variables using only function values, gradients and a few vectors of storage. They are the standard choice when n is too large for quasi-Newton matrices, and they remain building blocks of large-scale solvers in optimization, scientific computing and machine learning. The method of Polak…
Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints 2: Near the Optimal Ratio, a Maximum-Weight Initial Set Is ρ-MaximalResearch Paper
The single-machine sequencing problem with precedence constraints, written 1∣prec∣∑wjCj, asks for an order of n jobs on one machine that respects a given acyclic digraph of precedences and minimizes the weighted sum of completion times. It is NP-hard in general (Lawler 1978; Lenstra and Rinnooy Kan 1978), and much of its structural…
Dynamic Instabilities and Stabilization Methods in Distributed Real-Time Scheduling of Manufacturing Systems 3: Clear-a-Fraction Policies Are Stable From Every Initial State When ρ′ₘ < 1Research Paper
A flexible manufacturing system processes several part types on shared machines, and a machine that switches from one part type to another pays a set-up time. Real-time, distributed scheduling rules for such systems decide locally, at each machine, when to switch and to which buffer. The simplest such rules are clearing policies: a machine keeps working on…
Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms III: Every Directed Uniform Multicommodity Flow Problem Has Ω(𝒮/log n) ≤ f ≤ 𝒮Research Paper
Many graph problems in routing, VLSI layout and scheduling ask for a cut that separates a lot of demand while cutting little capacity. For a single commodity, the max-flow min-cut theorem of Ford and Fulkerson says that the largest flow equals the smallest cut. For several commodities sharing one network this equality fails, and the question becomes how far…
A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite Element Approximation 2: Internal Approximations Under (4.1)–(4.3) Have Solutions v_h Converging Strongly to vResearch Paper
An infinite dimensional variational problem can be described by continuous linear operators and convex functionals, yet numerical work needs finite dimensional spaces. The question is whether a solution computed in a finite dimensional approximation still approaches the solution of the original problem when the approximation is refined. Gabay and Mercier's I…
Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms II: Every Product Multicommodity Flow Problem with k Commodities Has Ω(𝒮/log k) ≤ f ≤ 𝒮Research Paper
For a single commodity, the Ford–Fulkerson theorem says that the maximum flow between two nodes equals the minimum capacity of a cut separating them. Many routing and partitioning problems involve many source–sink pairs at once, and for those the equality fails: the largest fraction of every demand that can be routed simultaneously can be strictly smaller…
Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming 4: Nonquadratic Multiplier Methods for Inequality Constraints Find an Optimal MultiplierResearch Paper
Convex programs with inequality constraints arise when a decision must meet capacity, resource, or performance limits. Their Lagrange multipliers assign a price to each constraint. Finding an optimal multiplier gives a dual certificate and can guide a primal optimization method. Classical quadratic multiplier methods update these prices through a particular…
Convergence Properties of the Nelder–Mead Simplex Method in Low Dimensions I: In Dimension 1, Both Endpoints Converge to the Minimizer of a Strictly Convex Function When ρχ ≥ 1Research Paper
The Nelder–Mead simplex method (Nelder and Mead, 1965) is one of the most widely used methods for minimizing a function without derivatives. It is the default unconstrained derivative-free minimizer in several numerical libraries (fminsearch in MATLAB, method="Nelder-Mead" in SciPy) and is used routinely in chemistry, engineering and statistics, where the…
Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming 3: The Nonquadratic Method of Multipliers for Linear Equality Constraints ConvergesResearch Paper
The method of multipliers (augmented Lagrangian method) of Hestenes and Powell is one of the standard algorithms for constrained convex optimization. Each iteration minimizes the Lagrangian plus a quadratic penalty on the constraint residual, then updates the multiplier estimate. Rockafellar showed in 1976 that this method is the proximal point algorithm…
Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming 2: Bregman Proximal Point Sequences Exist When im ∇h Is ℝⁿ, or Is Open and 0 ∈ im TResearch Paper
The proximal point method seeks a zero of an operator by repeatedly solving an implicit equation. For a maximal monotone operator, the ordinary quadratic proximal step is available throughout a Hilbert space. Eckstein's 1993 paper replaces the quadratic penalty with a Bregman function, allowing a step to reflect the geometry of a constrained problem. Before…
Dynamic Pricing and Inventory Control of Substitute Products 3: Optimal Dynamic Prices When the Other Variates Keep Fixed PricesResearch Paper
A retailer that sells a line of substitutable products — sizes, colours or models of one item — over a short season without replenishment must decide how to price each variate as inventory runs down. Customers substitute: when one variate is expensive or sold out, part of its demand moves to the others. Dong, Kouvelis and Tian (M&SOM 2009) model this with a …
Linear Programming and Markov Decision Chains 2: Representatives of Average Optimal Stationary Policies Are Optimal Dual Solutions, and Every Optimal Dual Solution Gives an Average Optimal PolicyResearch Paper
A finite Markov decision process may have several recurrent classes under one policy. In that setting, its long-run reward depends on the initial state, and a single stationary distribution does not describe the whole decision problem. Hordijk and Kallenberg developed a linear program with two families of variables to handle this multichain case. Their…
Distribution Function Inequalities for Martingales 3: For Brownian Motion Stopped at Any Stopping Time τ, EΦ(X*(τ)) and EΦ(τ^{1/2}) Are ComparableResearch Paper
The size of a martingale can be measured in two ways: by its maximal function, the largest absolute value it reaches, and by a quadratic quantity that records how much it has moved, the square function in discrete time or the elapsed time in the case of Brownian motion. The Burkholder–Davis–Gundy inequalities say that these two measurements are comparable…
Planning and Acting in Partially Observable Stochastic Domains: The Witness Theorem, a Set of Useful Policy Trees Is Incomplete iff Replacing One Subtree Improves on It at Some Belief StateResearch Paper
A partially observable Markov decision process (POMDP) models an agent that acts in a stochastic world whose state it cannot see directly. The agent sees only noisy observations. POMDPs are the standard model for planning under uncertainty in robotics, dialogue systems, medical decision making and machine maintenance. The exact finite-horizon theory goes…
Residual Life Time at Great Age 5: If |c − ((1 − F)/F′)′| ≤ ε for t ≥ t₀, the Residual Life Normed by (1 − F(t))/F′(t) Is Within ε of Π_{0,c} for t ≥ t₀Research Paper
The residual life time of a lifetime X at age t is the excess X−t given survival, X>t. How it behaves at great ages is a question in reliability (remaining life of an item that has already lasted long), in insurance and demography (remaining life at old age), and in the peaks-over-threshold method of extreme value statistics, where exceedances over a…
Implicit Renewal Theory and Tails of Solutions of Random Equations 1: The Implicit Renewal Theorem — If E|M|^κ = 1 Then P(R > t) ~ C₊t^{−κ} and P(R < −t) ~ C₋t^{−κ}Research Paper
Many stochastic models produce a stationary quantity R that solves a random equationR=dΨ(R), with Ψ a random map independent of R. The random difference equation R=dQ+MR (perpetuities in insurance and finance, the ARCH and GARCH volatility models, random walks in random environments), the Lindley equation …
Distribution Function Inequalities for Martingales 2: Gundy's Decomposition of an L¹-Bounded Martingale, with One Stopping TimeResearch Paper
Many operators of harmonic analysis are bounded on L2 by an orthogonality argument but fail to be bounded on L1; what survives at p=1 is a weak-type estimate λP(∣Tf∣>λ)≤c∥f∥1. For singular integrals the standard route to such an estimate is the Calderón–Zygmund decomposition, which splits a function at height λ into a bounded…
Software Protection and Simulation on Oblivious RAMs: Every Oblivious Simulation of t Steps Makes max{|y|, Ω(t log t)} AccessesResearch Paper
Programs often reveal information through the memory locations they touch, even when the contents of those locations are hidden. An oblivious RAM simulation aims to conceal this access pattern. Goldreich and Ostrovsky studied the cost of doing so for arbitrary RAM programs and showed that the access sequence itself imposes a lower bound on simulation…
Inapproximability of Edge-Disjoint Paths and Low Congestion Routing on Undirected Graphs: A Random Hypergraph Instance Gives the Flow Relaxation an Integrality Gap of β₁/(4c) at Congestion c − 1Research Paper
In the edge-disjoint paths problem (EDP) one is given an undirected graph and a list of source–sink pairs, and asks how many pairs can be connected simultaneously by paths that share no edge. Its relaxation EDP with congestion (EDPwC) allows every edge to carry up to a fixed number of paths. Both are central problems of network routing and of approximation…
Cooperative Fuzzy Games 2: A Game with Side Payments Has a Nonempty Core Iff It Is Balanced, and Then Its Core Is the Core of Its Concave Fuzzy ExtensionResearch Paper
A cooperative game with side payments assigns to each coalition of players the total payoff it can secure on its own and share freely among its members. The core is the set of ways of dividing the payoff of the grand coalition that no coalition can improve upon. It is the basic stability notion of cooperative game theory and of its applications in…
Paths, Trees, and Flowers II: Invariance of the Dual — the Outer Vertices O(G) Are Exactly the Vertices Left Exposed by Some Maximum MatchingResearch Paper
A maximum matching of a graph is a largest set of edges no two of which share a vertex. Maximum matchings are rarely unique, and a basic question is which features of them are forced by the graph. J. Edmonds' paper Paths, trees, and flowers (Canad. J. Math. 17 (1965), 449–467) gave the first polynomial-time algorithm for maximum matching in general graphs.…
Cooperative Fuzzy Games 4: The Fuzzy Core of an Exchange Economy Coincides with Its Set of Walras EquilibriaResearch Paper
The core of an exchange economy is the set of allocations that no group of consumers can improve upon by trading only among themselves. The Walras equilibria (competitive equilibria) are the allocations supported by a price system at which every consumer maximizes preference on a budget set. Every Walras equilibrium is in the core, but for a fixed finite…
Smart "Predict, then Optimize": Under a Continuous, Centrally Symmetric Cost Law Every Minimizer of the SPO+ Risk Equals E[c|x] and Minimizes the SPO RiskResearch Paper
Many decisions are made before their objective coefficients are known. A planner may know the feasible decisions and the form of a linear optimization problem, but must predict its cost vector from available features. Squared prediction error measures how close a forecast is to the eventual coefficients; it need not measure the quality of the decision…
Learning Models with Uniform Performance via Distributionally Robust Optimization 1: The Plug-In Cressie–Read Robust Risk Concentrates at Rate n^(−1/(k*∨2))·√(t + log n) (Theorem 2)Research Paper
A model trained to minimize its average loss EP0[ℓ(θ;X)] can perform poorly on subpopulations that are rare under the training distribution P0. Distributionally robust optimization replaces the average loss by its worst case over all distributions Q close to P0 in an f-divergence, which upweights the tail of the loss and controls…