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.
Dynamics of Stochastic Approximation Algorithms 5: If V(Λ) Has Empty Interior for a Lyapunov Function V, Every Internally Chain Transitive Set Lies in ΛResearch Paper
A stochastic approximation algorithm is a recursion xn+1=xn+γn+1(F(xn)+Un+1) with decreasing steps γn and noise Un. Stochastic gradient descent, the Robbins–Monro procedure, reinforcement-learning updates and learning dynamics in games all have this form. The ODE method compares such a recursion with the deterministic dynamics …
Reinforcement Learning: An Introduction IX: Average Reward and the Futility of Discounting in Continuing ProblemsTextbook
Reinforcement learning formulates control as maximizing reward accumulated over time. For continuing tasks, where interaction never terminates, the standard textbook objective is the discounted return with a discount rate γ<1. Chapter 10 of Sutton and Barto, Reinforcement Learning: An Introduction (2nd ed., MIT Press, 2018), argues that once values…
On Conjugate Convex Functions: Conjugation Is a Symmetric Correspondence Between Lower Semicontinuous Convex FunctionsResearch Paper
Convex duality in optimization rests on one transformation: to a convex function f one associates the function φ(ξ)=supx(Σxξ−f(x)), which records, for each slope ξ, the best affine lower bound of f with that slope. Lagrangian duality, the duality theory of linear and conic programming, the analysis of first-order methods through…
An Inventory Model with Limited Production Capacity and Uncertain Demands I. The Average-Cost Criterion: With Finite Storage a Modified Base-Stock Policy Is Strongly Average-Cost OptimalResearch Paper
A manufacturer that makes one product to stock faces random demand, can produce at most b units per period, and can store at most U units. The classical result without the production limit is that a base-stock policy is optimal: raise inventory to a fixed level yˉ each period. With a production limit, the natural modification is to produce up to yˉ w…
SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives II: The 4n/k Rate of the Averaged Iterate without Strong ConvexityResearch Paper
Many problems in statistics and machine learning minimize an average of n losses, one per data point, plus a regularizer: least squares, logistic regression, and their ℓ1- or ℓ2-penalized versions. When n is large, a full gradient costs n component gradients, while stochastic gradient descent, which uses one component per step, needs decreasing step…
Twice Regularized MDPs and the Equivalence Between Robustness and Regularization 1: The Robust Value Function Is the Optimum of a Policy- and Value-Regularized Convex ProgramResearch Paper
A Markov decision process (MDP) is solved for one model of its dynamics and rewards, but in practice that model is estimated from data, and a policy that is optimal for the estimate can perform poorly on the true system (Mannor et al., 2007). Robust MDPs address this by evaluating a policy against the worst model in an uncertainty setU (Iyengar,…
SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives I: Linear Convergence under Strong ConvexityResearch Paper
Many problems in machine learning and statistics are finite sums: an empirical risk f(x)=n1∑i=1nfi(x) over n data points, often plus a regulariser h such as an ℓ1 penalty. When n is large, a full gradient of f costs n component gradients, while stochastic gradient descent uses one component per step but converges only sublinearly because…
Open Queueing Networks in Heavy Traffic: Reflected Brownian Motion Limit for the Queue Length ProcessResearch Paper
Open networks of single-server queues with general interarrival and service distributions are the standard model of job shops, communication networks and service systems. Outside the product-form (Jackson) case their queue-length distributions are not known in closed form. When every station is close to saturation, a heavy-traffic limit replaces the network…
Reinforcement Learning: An Introduction IV: Policy Iteration for ε-Soft PoliciesTextbook
Policy iteration alternates two steps: evaluate the current policy, then replace it by a policy that is greedy with respect to the evaluated action values. The policy improvement theorem guarantees that each greedy step does not make the policy worse, and that the process stops only at an optimal policy. When the action values are estimated from experience…
Quantifying the Bullwhip Effect in a Simple Supply Chain: The Impact of Forecasting, Lead Times, and Information 1: Centralizing Demand Information Does Not Eliminate the Bullwhip EffectResearch Paper
The bullwhip effect is the observation that the variability of orders increases as one moves up a supply chain, from the retailer towards the manufacturer and its suppliers. It was documented in industry and in classroom experiments such as the Beer Game (Sterman 1989), and analysed by Lee, Padmanabhan and Whang (1997), who named demand forecasting, lead…
Exponential Lower Bounds for Polytopes in Combinatorial Optimization: The TSP Polytope Has Extension Complexity 2^Ω(√n)Research Paper
Combinatorial optimization problems are routinely solved by writing the convex hull of their feasible solutions as the feasible region of a linear program. When that convex hull has exponentially many facets, a classical trick is to add auxiliary variables: a polytope with many facets may be the linear projection of a higher-dimensional polyhedron with few.…
A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in O(n log n) or O(n) Time: Minimal Optimal Predecessor Lists Are Characterized by Strictly Increasing BreakpointsResearch Paper
The dynamic lot size model asks when, and how much, to order of a single item over a planning horizon of n periods with known, time-varying demands, setup costs, unit order costs and holding costs. It is the textbook model of production planning and the building block of material requirements planning, multi-item scheduling and many decomposition schemes…
An Efficient Algorithm for Computing an Optimal (r, Q) Policy in Continuous Review Stochastic Inventory Systems: Algorithm OPT Returns an Optimal Reorder Point and Order QuantityResearch Paper
(r, Q) policies are the standard replenishment rule for a single item under continuous review: whenever the inventory position (stock on hand plus on order minus backorders) drops to the reorder pointr, an order of size Q is placed. They are known to be optimal in the classical models with Poisson or compound renewal demand, constant or exogenous lead…
Multi-parameter Mechanism Design and Sequential Posted Pricing 3: Order-Oblivious Posted Prices 2-Approximate the Optimal Revenue under a Uniform Matroid ConstraintResearch Paper
Myerson's optimal auction (Myerson 1981) maximizes a seller's expected revenue when buyers have independent private values, but it is a sealed-bid mechanism: every buyer reports a value, and the allocation and payments are computed from all reports at once. Real sellers more often post prices: buyers arrive, each sees a take-it-or-leave-it price, and buys…
Project Scheduling with Time Windows and Scarce Resources VIII: A Vertex Schedule Maximizes the Net Present Value iff Its Spanning-Tree Subprojects Have the Right SignsTextbook
Long-running projects such as construction, plant engineering or software development involve payments to and from the contractor at many points in time: disbursements when activities are carried out, progress payments when milestones are reached. When the planning horizon is long, money received later is worth less, and the natural financial objective is…
One-Machine Sequencing to Minimize Certain Functions of Job Tardiness I: SPT Order Minimizes Total Tardiness When Each Due Date Plus Processing Time Is at Most the Next SPT Completion TimeResearch Paper
A shop that promises delivery dates is judged by how late its orders are, not by how early. For a single machine processing n jobs that are all available at time 0, the total tardiness of a processing order,
On the Variational Principle II: Under Linearly Independent Active Constraint Gradients, a Bounded-Below Problem Has ε²-Optimal Feasible Points Satisfying the Lagrange Multiplier Rule up to εResearch Paper
The classical Lagrange multiplier rule and its inequality-constrained form, the Karush–Kuhn–Tucker (KKT) conditions, are necessary conditions satisfied at a minimizer of a constrained problem. In finite dimensions, a continuous function bounded below on a closed bounded feasible set attains its minimum, so the rule describes an actual point. In an…
On the Variational Principle I: Near Every ε-Minimizer of a Lower Semicontinuous Function Bounded Below on a Complete Metric Space Lies a Strict Minimizer of F + (ε/λ)d(v, ·)Research Paper
A function that is bounded below need not attain its infimum: ex on R has infimum 0 and no minimizer. The classical "variational principle" says that at a minimizer uˉ of a differentiable functional, F′(uˉ)=0. Without compactness there may be no minimizer, and the principle has nothing to say. In 1974 Ivar Ekeland showed that a weaker…
Dimensioning Large Call Centers I: The Rationalized Staffing Function Is Asymptotically OptimalResearch Paper
A call center with N agents facing Poisson arrivals at rate λ and exponential service at rate μ is the M/M/N (Erlang-C) queue. Choosing N trades the cost of agents against the cost of customers waiting, and in practice it is done with the square-root safety-staffing ruleN≈R+yR, where R=λ/μ is the offered load. Borst,…
Fundamentals of Queueing Theory IX: Kingman's Upper Bound on the G/G/1 Queue WaitTextbook
The single-server queue with general independent interarrival and service times, the G/G/1 queue, is the basic model of a congested resource: a machine, a link, a checkout. For Markovian arrivals or services the mean wait has a closed form (the Pollaczek–Khintchine formula for M/G/1, the geometric law for G/M/1). For general distributions it has none, and…
A Multicut Algorithm for Two-Stage Stochastic Linear Programs 2: Multicut for Simple Recourse Stops Within J·m2 + 1 IterationsResearch Paper
Two-stage stochastic linear programs model decisions taken before uncertainty is resolved (first stage) and corrected afterwards at a cost (second stage, the recourse). The standard solution method for problems with finitely many scenarios is the L-shaped method of Van Slyke and Wets (1969), an outer linearization in the style of Benders decomposition: a…
The Price of Anarchy of Finite Congestion Games IV: For Symmetric Games the Maximum Social Cost Price of Anarchy Is at Most 5/2Research Paper
The price of anarchy measures how much a system of selfish agents loses compared with a centrally optimized one: it is the worst ratio, over all Nash equilibria, between the social cost of the equilibrium and the optimal social cost. Koutsoupias and Papadimitriou introduced it in 1999 (Worst-case equilibria, STACS 1999), and bounding it for routing and…
The Price of Anarchy of Finite Congestion Games I: The Pure Price of Anarchy of the Average Social Cost Is 5/2Research Paper
When many independent users share a resource whose cost grows with use (links of a network, servers, machines), each user chooses for itself, and the outcome is a Nash equilibrium rather than a socially optimal allocation. The price of anarchy, introduced by Koutsoupias and Papadimitriou (STACS 1999), measures the cost of this decentralisation: the worst…
The Dantzig Selector: Statistical Estimation When p Is Much Larger than n 1: ℓ2 Error Bound for Sparse Parameters under the Uniform Uncertainty PrincipleResearch Paper
In many statistical applications the number of unknown parameters p is far larger than the number of observations n: gene-expression studies with tens of samples and thousands of genes, imaging problems with fewer measurements than pixels, and nonparametric curve estimation from finitely many noisy samples. Least squares is useless in this regime, since the…
Reinforcement Learning: An Introduction XII: The Policy Gradient TheoremTextbook
Policy gradient methods learn a parameterized policy π(a∣s,θ) directly, by stochastic gradient ascent on a scalar performance measure J(θ), instead of deriving the policy from learned action values. They are how reinforcement learning handles continuous action spaces, stochastic optimal policies and prior knowledge built into the policy's…