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 Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming 1: Under Cyclic Control Every Limit Point Is a Common PointResearch Paper
Many problems in optimization and numerical analysis reduce to finding a point in the intersection of finitely many closed convex sets: solving a system of linear equations or inequalities, reconstructing an image from projections, or finding a feasible point of a convex program. The classical methods for this convex feasibility problem project the current…
Stochastic Optimal Control: The Discrete-Time Case V: Semicontinuous Functions — a Borel-Measurable Minimizing Selector for Lower Semicontinuous CostsTextbook
Every step of the dynamic programming algorithm on a general state space does three things: it takes a conditional expectation of the cost-to-go under a transition kernel, it minimizes the resulting function of state and control over the control, and, if a policy is to be produced, it picks a control for each state that attains or nearly attains that…
The Price of Stability for Network Design with Fair Cost Allocation I: The Price of Stability of Fair Cost Sharing Is at Most H(k), and This Is TightResearch Paper
Many networks are built and paid for by the users they serve: multicast trees, virtual overlays, shared subnetworks of the Internet. A protocol proposes a design and a rule for splitting its cost, and each participant is free to accept the proposal or defect to a cheaper alternative. The designer therefore cannot impose the global optimum; the best it can…
Mean Field Games: Numerical Methods for the Planning Problem I: The Discrete Planning Scheme Has a Solution, Given by a Fenchel–Rockafellar Saddle PointResearch Paper
Mean field games (Lasry and Lions, 2006–2007; Huang, Malhamé and Caines, 2006) model the limit of a large population of identical rational agents. Each agent solves an optimal control problem whose cost depends on the distribution m of all agents, and the distribution is in turn transported by the agents' optimal feedback. In the continuous setting this…
Variance-based Regularization with Convex Objectives II: A Covering-Number Certificate and Oracle Inequality for the Robust MinimizerResearch Paper
Empirical risk minimization (ERM) chooses, from a class F of loss functions, the one with the smallest average loss on a sample X1,…,Xn. Its standard guarantees bound the excess population risk by a term of order 1/n, whatever the variance of the losses. When good functions in F have small variance, a better trade-off is…
Two Theorems in Graph Theory: A Matching Is Maximum If and Only If No Alternating Chain Joins Two Neutral PointsResearch Paper
A matching of a graph is a set of edges no two of which share a vertex. A matching with as many edges as possible is a basic object of combinatorial optimization. Assignment problems, pairing and scheduling problems, and the Chinese postman problem reduce to it, and it is the standard example of a problem with a polynomial-time algorithm that is not an…
Approximation Algorithms for Stochastic Inventory Control Models 2: The Triple-Balancing Policy Costs at Most Three Times the Optimum for Stochastic Lot-SizingResearch Paper
Periodic-review inventory control with a fixed ordering cost is one of the oldest problems in operations research. A firm reviews its stock at the beginning of each of T periods, decides whether to place an order, pays a fixed cost K for every order it places, and pays holding costs on leftover stock and penalties on unmet (backlogged) demand. When demand…
The Complexity of Computing a Nash Equilibrium 2: The Three-Colorable Addition-Multiplication Gadget Has Error Amplification 81Research Paper
Nash's theorem guarantees that every finite game has a mixed equilibrium, but says nothing about how hard one is to find. Daskalakis, Goldberg and Papadimitriou (SIAM J. Comput. 39(1), 2009) showed that computing a Nash equilibrium is complete for the class PPAD of total search problems whose solutions are guaranteed by a parity argument on a directed graph…
One-Machine Sequencing to Minimize Certain Functions of Job Tardiness II: EDD Order Minimizes Any Sum of Convex Nondecreasing Tardiness Penalties When No Job Starts After Its Due DateResearch Paper
A single machine must process a set of jobs, each with a processing time and a due date, and the cost of a schedule depends on how late the jobs finish. Total tardiness is the classical criterion, but in many applications lateness is penalised more than proportionally: a job one week late costs more than twice a job half a week late, and a quadratic or…
Secretary Problems: Weights and Discounts 5: A 3e-Competitive Algorithm for the Graphic Matroid Secretary ProblemResearch Paper
In the secretary problem, n items with nonnegative values arrive one at a time in a uniformly random order, and an online algorithm must decide on each arrival, irrevocably, whether to keep it. The classical version keeps one item; the rule that observes a 1/e fraction of the arrivals and then takes the first item better than everything seen picks the best…
Discrete Dynamic Programming 2: A Stationary Policy Is Nearly Optimal as the Discount Factor Tends to 1 Exactly When It Maximizes x(g) and, Among Those, y(g)Research Paper
A finite Markov decision problem with discounting is solved by Howard's policy improvement routine: start from a stationary policy, switch to actions that do better against its value, repeat. When the discount factor β tends to 1 the total discounted income typically diverges, and the natural targets become the long-run average income and, among…
Consensus of Subjective Probabilities: The Pari-Mutuel Method: Equilibrium Track Probabilities Exist and Are UniqueResearch Paper
A group of m individuals each hold a subjective probability distribution over the same n outcomes, and one wants a single distribution representing their consensus. Averaging and convolution are the obvious candidates. Eisenberg and Gale (Ann. Math. Statist. 30(1), 1959) observe that a real institution already performs such an aggregation: the pari-mutuel…
The Dantzig Selector: Statistical Estimation When p Is Much Larger than n 2: Oracle Inequality within a Logarithmic Factor of the Ideal Mean Squared ErrorResearch Paper
Many regression problems have far more unknown coefficients p than observations n: gene expression studies with tens of samples and thousands of genes, imaging from few measurements, nonparametric curve recovery from a finite number of noisy samples. Estimation is hopeless in general, but becomes possible when the parameter is sparse, that is, has few…
Minimization of Functions Having Lipschitz Continuous First Partial Derivatives: Gradient Steps with Sufficient Decrease δ|∇f(x_k)|², 0 < δ ≤ 1/4K, Converge to the MinimizerResearch Paper
The gradient method minimizes a differentiable function f on Rn by moving from the current point xk along the negative gradient, xk+1=xk−λk∇f(xk). Every practical implementation has to choose the step λk. A fixed step requires knowing a Lipschitz constant of ∇f; an exact line search is expensive. Larry Armijo's…
Discrete Dynamic Programming 1: Every Finite Markov Decision Problem Has a Stationary Policy That Is Optimal for All Discount Factors Sufficiently Near 1Research Paper
A Markov decision problem models a system that is observed once per period and controlled by choosing an action: the action earns an immediate income and determines the probabilities of the next state. Inventory control, machine replacement, queue admission and many reinforcement-learning benchmarks are of this form. With future income discounted by a…
The Price of Anarchy of Finite Congestion Games II: For Symmetric Games the Average Social Cost Price of Anarchy Is (5N-2)/(2N+1)Research Paper
Selfish routing and resource sharing are modelled by congestion games: each player picks a set of shared resources, and the cost of a resource grows with the number of players using it. The price of anarchy, introduced by Koutsoupias and Papadimitriou (STACS 1999), measures how much worse the social cost of a worst Nash equilibrium is than the optimum. For…
Theory of Reproducing Kernels II: One Reproducing Kernel Class Contains Another iff a Multiple of Its Kernel Dominates the Other KernelResearch Paper
A reproducing kernel Hilbert space (RKHS) is a Hilbert space of functions in which evaluation at each point is a continuous functional. Each such space is determined by its kernel, and in practice spaces are usually given by their kernels: Gaussian or Sobolev kernels in kernel methods and Gaussian-process regression, the Bergman and Szegő kernels in complex…
Stability and Generalization 4: Relative-Entropy Regularization of Mixtures Has Uniform Stability M²/(λm)Research Paper
A learning algorithm generalizes when its error on fresh data is close to its error on the training sample. Bousquet and Elisseeff (JMLR 2, 2002) showed that a single property of the algorithm, uniform stability, controls this gap with exponential concentration: if removing any one example from a training set of size m changes the loss of the output at…
Stability and Generalization 2: Exponential Generalization Bounds for Uniformly Stable AlgorithmsResearch Paper
A learning algorithm is judged by its generalization error: the expected loss of the hypothesis it outputs on a fresh example. That quantity depends on an unknown distribution, so it is estimated from the training data, by the empirical error (the average loss on the training set) or the leave-one-out error (the average loss on each training point of the…
Dynamics of Stochastic Approximation Algorithms 6: An Attractor Whose Basin Meets the Attainable Set Contains the Limit Set with Positive ProbabilityResearch Paper
A stochastic approximation algorithm is a recursion xn+1=xn+γn+1(F(xn)+Un+1) with decreasing step sizes γn and a noise term Un+1. Recursions of this form appear in stochastic gradient methods, adaptive control, learning in games (fictitious play, reinforcement learning) and urn models. The ODE method compares the iterates…
Gradient Convergence in Gradient Methods with Errors I: With Deterministic Errors Proportional to the Stepsize, Either f(x_t) → −∞ or f(x_t) Converges and ∇f(x_t) → 0Research Paper
Gradient methods are the workhorse of large-scale nonlinear optimization and of the training of statistical models. In practice the direction actually used is rarely the exact negative gradient: it may be scaled, computed incrementally one data component at a time, or perturbed by approximation error. The classical convergence theory of such methods often…
Dynamics of Stochastic Approximation Algorithms 3: Martingale Noise with Bounded q-th Moments and Summable γ_n^(1+q/2) Satisfies Assumption A1 Almost SurelyResearch Paper
A stochastic approximation algorithm is a recursion
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…