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.
Stochastic Orders III: The Convex Order and Strassen's Martingale CouplingTextbook
Chapter I's usual stochastic order compares "how large" two random variables tend to be. A
different, equally common question in operations research is "how spread out" a random variable
is: two portfolios with the same expected loss can differ sharply in how much that loss varies,
and a risk-averse decision maker or a convex cost function cares about…
Stochastic Orders II: The Mean Residual Life OrderTextbook
A device's mean residual life at age t — its conditional expected remaining lifetime given
that it has survived to t — is one of the oldest and most interpretable summaries in
reliability and survival analysis: it is what an insurer, a maintenance planner, or a hospital
outcomes researcher actually wants to know about a unit still in service. Comparing two…
Introduction to Online Convex Optimization V: RFTL and the Regret Bound of Follow-the-Regularized-LeaderTextbook
Online convex optimization (OCO) asks a learner to repeatedly pick a point in a convex
set K, pay a cost that an adversary reveals only after the choice is made, and be judged
against the best fixed point in hindsight. Chapter III of this series formalized the
simplest general-purpose answer, online gradient descent (OGD): take a gradient step,
project back…
Introduction to Stochastic Programming VIII: Multistage Jensen Bounds and AggregationTextbook
A multistage stochastic program's exact deterministic equivalent grows exponentially with the
number of periods, even when each period's random data takes only a handful of values (Chapter 9's
concern was the growth in the number of realizations; Chapter 10 adds growth in the number of
periods). One remedy, generalizing Chapter 8's single-period Jensen…
Introduction to Stochastic Programming III: The L-Shaped Method and Its Finite ConvergenceTextbook
Two-stage stochastic programs with recourse — choose a first-stage decision x now, observe a
random outcome ξ, then choose a second-stage recourse decision y(ξ) to repair whatever
x left infeasible or suboptimal — are the workhorse model of the field, used for capacity
planning, inventory and financial portfolio problems since the 1950s (Dantzig 1955;…
Stochastic Networks IV: Decentralized Optimization and Wardrop EquilibriaTextbook
A network of resistors solves an optimization problem. Nobody tells the electrons what to do;
each one moves under a purely local rule, and the current distribution that emerges minimizes
energy dissipation over all distributions satisfying Kirchhoff's node law. Add a wire and the
network can only become easier to traverse. This is the encouraging case, and…
Stochastic Networks II: Migration Processes and Product FormTextbook
A queueing network is a collection of service stations through which customers — jobs, packets,
telephone calls, patients — move one at a time. The state of such a network is a vector of
occupancy counts, one per station, and the number of states grows exponentially in the number of
stations, so solving the equilibrium equations directly is hopeless for any…
Supermodularity and Complementarity II: Topkis's Monotonicity Theorem for Parameterized OptimizationTextbook
A recurring question in economics and operations research is: when a decision problem
depends on a parameter, does the optimal decision move monotonically as the parameter
changes? A firm's optimal input mix as a price rises, a consumer's optimal consumption
bundle as income grows, a Cournot firm's optimal output as a rival's output changes — in
each case…
Introduction to Stochastic Programming II: The Value of Perfect Information and of the Stochastic SolutionTextbook
Every stochastic program is, in practice, compared against a shortcut. A decision maker
facing genuine uncertainty is tempted either to replace the random data by its mean and solve
one deterministic problem, or to imagine that perfect information about the future were
available and solve a separate deterministic problem per scenario. Both temptations have…
Algorithmic Game Theory V: Stable Matching and Trading without MoneyTextbook
When money is off the table and the Gibbard–Satterthwaite theorem (Mission III of this series) blocks general strategyproof choice, restricted preference domains reopen the door. The two great examples both come from allocation: Shapley–Scarf's housing market (1974), where Gale's Top Trading Cycle algorithm finds the unique core allocation and Roth (1982)…
Algorithmic Game Theory IV: VCG and the Limits of TruthfulnessTextbook
Mission III of this series ends at an impossibility: without money, incentive compatibility over three or more alternatives means dictatorship. This mission formalizes the classical escape route — quasilinear utilities and payments — and the exact price of it. Vickrey (1961) discovered that a second-price auction makes truth-telling dominant; Clarke (1971)…
Dynamic Programming and Optimal Control VII: Infinite Horizon ProblemsTextbook
Infinite-horizon dynamic programming is the mathematical core of Markov decision processes and reinforcement learning: Bellman equations, value iteration, policy iteration, and their guarantees. Chapter 7 of Bertsekas, Dynamic Programming and Optimal Control, Vol. I (3rd ed., 2005) develops the finite-state theory in its cleanest generality — stochastic…
Vector Space Methods V: Convex Separation and Distance DualityTextbook
Linear approximation is only one instance of distance minimization. Feasible sets in optimization are typically convex rather than subspaces, so a useful certificate must compare a target point with an entire convex set and must allow an affine offset. Chapter 5 of Luenberger's Optimization by Vector Space Methods builds this certificate through geometric…
Vector Space Methods IX: Global Lagrange DualityTextbook
Many convex programs impose inequalities valued in a vector space: componentwise inequalities, positive-semidefinite constraints, and families of ordered resource constraints are all instances of one cone order. Chapter 8 of David G. Luenberger's Optimization by Vector Space Methods develops a global theory for this setting. A perturbation of the constraint…
Vector Space Methods VIII: Fenchel DualityTextbook
Convex duality converts an optimization problem over points into one over linear functionals. It supplies lower bounds, certificates of optimality, and alternative formulations whose geometry can be simpler than the primal problem. In §§7.8–7.12 of David G. Luenberger's Optimization by Vector Space Methods, this theory is developed for finite-valued convex…
Every full-dimensional convex body is sandwiched between an ellipsoid and its n-fold dilation: shrinking the minimum-volume covering (Löwner–John) ellipsoid E about its centre x0 by the factor 1/n lands inside the body,
Introduction to Linear Optimization XII: Interior Point Methods and Path FollowingTextbook
Interior point methods solve linear programs by moving through the interior of the feasible set instead of along its edges — the approach that turned Karmarkar's 1984 breakthrough into today's practical large-scale solvers. This mission formalizes the primal path following algorithm of Chapter 9 of Bertsimas–Tsitsiklis. For μ>0 the logarithmic barrier
Introduction to Linear Optimization XI: The Ellipsoid MethodTextbook
Can the feasibility of a system of linear inequalities be decided in a provably small number of iterations? The ellipsoid method — the algorithm with which Khachiyan showed in 1979 that linear programming is polynomially solvable — answers this with pure convex geometry. This mission formalizes Chapter 8 of Bertsimas–Tsitsiklis. An ellipsoid is
Introduction to Linear Optimization IX: Network Flow IntegralityTextbook
Why do network linear programs return integer answers for free? This mission formalizes the structural theory of the minimum cost network flow problem of Chapter 7 of Bertsimas & Tsitsiklis: a directed graph G=(N,A) with external supplies bi, arc costs cij, and the node-arc incidence matrix A — an n×m matrix in which…
Introduction to Linear Optimization VIII: Sensitivity Analysis and Subgradients of the Optimal CostTextbook
How does the optimal cost of a linear program respond when the problem data change? Chapter 5 of Bertsimas-Tsitsiklis studies the standard form problem min{c′x∣Ax=b,x≥0} (rows of A linearly independent) as the requirement vector b and the cost vector c vary. On the convex set S={b∣P(b)=∅} of feasible right-hand sides,…
Introduction to Linear Optimization V: Duality TheoryTextbook
Every linear programming problem has a shadow. To the primal minc′x we associate the dual maxp′b, whose variables price the primal constraints: one dual variable per primal constraint and one dual constraint per primal variable, with signs governed by the correspondence of Table 4.1. This mission formalizes §4.1–4.5 of Bertsimas–Tsitsiklis: the dual of…
Introduction to Linear Optimization IV: The Simplex MethodTextbook
How does one actually solve a linear program? Chapter 2 showed that if a standard-form problem minc′x subject to Ax=b, x≥0 has an optimal solution, it has an optimal basic feasible solution; the simplex method searches among basic feasible solutions, moving along edges of the feasible set in cost-reducing directions. This mission formalizes the…
Introduction to Linear Optimization I: Polyhedra and Basic Feasible SolutionsTextbook
Every linear programming problem asks to minimize a linear cost c′x over a polyhedron — a set of the form P={x∈Rn∣Ax≥b}, or in standard form {x∣Ax=b,x≥0}. Chapter 2 of Bertsimas–Tsitsiklis develops the geometry of these feasible sets, and its central achievement is making the intuitive notion of a "corner point"…
Bandit Algorithms I: Concentration of MeasureTextbook
How quickly does the empirical mean of independent random variables concentrate around the true mean? This question is the analytic engine of the entire theory of stochastic bandits: every optimistic algorithm (Explore-Then-Commit, UCB and its relatives) is calibrated by a tail bound on the sample mean. This mission formalizes the subgaussian framework of…
Markov Entanglement: Decomposition Error via Agent-wise TV DistanceResearch Paper
Multi-agent reinforcement learning approximates a global value function by summing per-agent local value functions learned independently — a trick that works surprisingly well in practice (ride-hailing dispatch, restless bandits) but had no general theoretical justification. Chen and Peng (arXiv:2506.02385) explain why: they define a Markov entanglement meas…