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.
Inventory Control VIII: The Clark-Scarf Decomposition for a Serial SystemTextbook
Chapter 10 of Axsäter's Inventory Control turns to reorder points and safety stocks in
multi-echelon systems, where the installations cannot be treated separately: a large stock
downstream lets an upstream site run lean, and a long upstream lead-time argues for stock at
the top. The best-known exact technique for serial systems is the decomposition of Clark…
Fundamentals of Supply Chain Theory VI: Pooling and FlexibilityTextbook
A firm that holds inventory in five warehouses needs more safety stock than one that holds the
same inventory in one warehouse, because the demands of five regions do not all run high at
once. Eppen (1979) made this precise for a multi-location
newsvendor and gave it its name, the risk-pooling effect. Chapter 7 of Snyder and Shen's
Fundamentals of Supply…
Fundamentals of Supply Chain Theory V: The Bullwhip EffectTextbook
Procter & Gamble observed in the 1990s that the orders its distributors placed for diapers were
far more variable than the retail sales of diapers, and that its own orders to suppliers were more
variable still, although the end demand for diapers is about as stable as demand gets. The
phenomenon, a growing amplification of variability as one moves upstream…
Markov Decision Processes III: The Average Reward Optimality Equation for Unichain ModelsTextbook
When a system is controlled indefinitely and decisions are frequent — a router admitting
packets, a queue accepting jobs, a machine being maintained — discounting future rewards is
often unjustified, and what matters is the long-run average reward per period. Puterman's
Chapter 8 (doi:10.1002/9780470316887) develops the
theory of this criterion, and its…
Convex Polytopes V: Recognition from projections (GRU-M05-PROJECTION-RECOGNITION)Textbook
A convex set can be studied through its images in spaces of smaller dimension. Each image records part of the geometry, while losing the information along the directions that are collapsed. A finite convex hull always has finite convex hulls as its affine images. The converse asks whether sufficiently rich projection data can force the original set to have…
Markov Processes: Characterization and Convergence IV: Martingale characterization of Markov processesTextbook
A stochastic process can be described through the way functions of its state change over time. For a suitable pair of functions f and g, the difference between f evaluated along the process and the accumulated integral of g has zero conditional drift. A martingale problem specifies a collection of such pairs. The question is whether these local conditions…
Resource Allocation and Cross-Layer Control in Wireless Networks III: Lyapunov Optimization for Utility and FairnessTextbook
Chapters 3-4 of Georgiadis, Neely & Tassiulas's survey Resource Allocation and Cross-Layer
Control in Wireless Networks (Foundations and Trends in Networking, 2006) answer "can the
network stay stable?" — the backpressure algorithm's throughput optimality (Theorem 4.5) says
yes, for any arrival rate inside the capacity region. But networks are usually…
Resource Allocation and Cross-Layer Control in Wireless Networks II: The Dynamic Backpressure AlgorithmTextbook
Every stability result in Georgiadis, Neely & Tassiulas's survey Resource Allocation and
Cross-Layer Control in Wireless Networks (Foundations and Trends in Networking, 2006) — the
throughput optimality of the dynamic backpressure algorithm (Theorem 4.5), the utility-optimal
Lyapunov drift bound of Chapter 5, the energy-constrained control algorithm of…
Convex Polytopes XVIII: Complete characterization of simplicial face vectorsTextbook
A convex polytope has finitely many faces in each dimension, and their numbers form its f-vector. Determining which integer vectors occur is a basic realization problem in discrete geometry: necessary identities such as Euler's relation do not by themselves decide whether a proposed vector comes from a polytope. For simplicial polytopes, whose facets are…
The Design of Competitive Online Algorithms via a Primal-Dual Approach VI: Maximizing Ad-Auctions RevenueTextbook
Search-engine ad-auctions sell items (ad slots) to buyers who arrive with per-item bids and a
fixed daily budget, online: each item must be allocated the moment it appears, with no ability to
revisit past allocations, and no buyer may ever be charged more than its budget. Buchbinder and
Naor's survey [1] models this as a generalization of online bipartite…
Convex Polytopes X: Recognition from projectionsTextbook
A convex set can be studied through its images in lower-dimensional spaces. Each image retains part of the geometry while discarding information along the directions that are collapsed. Finite convex hulls behave well under affine maps: the image of a convex hull of finitely many points is again the convex hull of finitely many points. The converse is…
Convex Polytopes V: Face-lattice recovery from ray queriesTextbook
A polytope can be given by a list of vertices, a list of inequalities, or much less explicit access. The last case arises when geometric information is available through queries to a physical or computational object but a full description is unavailable. Grünbaum's account of a result by Gritzmann, Klee, and Westwater asks how much of a polytope can be…
Foundations of Machine Learning XIV: Finite Markov Decision Processes and Bellman's EquationsTextbook
Reinforcement learning formalizes a scenario supervised learning cannot: an agent that
actively interacts with an environment, choosing actions that change both the state it
observes next and the reward it receives, rather than passively receiving an i.i.d. labeled
sample. Every practical treatment of this scenario — from classical dynamic programming to…
First-Order and Stochastic Optimization Methods for Machine Learning I: The Separation Theorem, Strong Duality and the KKT ConditionsTextbook
Every convex optimization algorithm in machine learning — from projected gradient descent to
support vector machines to the mirror-descent methods of later chapters of this book — is
justified by a small set of optimality certificates: a checkable condition on a candidate
solution that guarantees it actually solves the problem, without searching the whole…
High-Dimensional Probability XI: Dvoretzky-Milman's TheoremTextbook
A striking fact discovered by Dvoretzky in the 1960s (conjectured by Grothendieck, and sharpened
into its modern quantitative form by Milman in 1971) is that every high-dimensional convex body,
however irregular, contains a round slice: a random low-dimensional section (or projection) of
any bounded convex set in Rn is, with high probability, close…
Support Vector Machines V: Bernstein's Inequality for Independent Hilbert-Space-Valued Random VariablesTextbook
Every statistical guarantee for a learning algorithm ultimately rests on a concentration
inequality: a bound on how far an empirical average can stray from its expectation. For
real-valued averages, Bernstein's inequality (1924, refined through the 20th century) is the
classical tool — sharper than Hoeffding's inequality whenever the summands' variance is…
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 VI: Bandit Convex Optimization via Gradient EstimationTextbook
Every algorithm in Chapters I–V observes the full cost function ft after playing xt. Many
applications only reveal the scalar cost ft(xt) incurred — routing a network and observing
total latency, or placing an ad and observing the click-through revenue, without ever seeing the
cost of a path or bid not taken. This is the bandit feedback model, and…
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…
Foundations of Reinforcement Learning V: General Decision Making and the Decision-Estimation Coefficient Lower BoundTextbook
Online decision-making problems — multi-armed bandits, contextual bandits, structured bandits,
and episodic reinforcement learning — look superficially different but share a common shape: a
learner repeatedly acts, observes feedback, and is scored by regret against the best action in
hindsight. Foster, Kakade, Qian and Rakhlin's Foundations of Reinforcement…
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…