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 Two-Parameter Poisson–Dirichlet Distribution Derived from a Stable Subordinator 6: n·Y_n → (1 − α)/α Almost Surely under PD(α, θ)Research Paper
In a population divided into many species, a ranked frequency Vn is the fraction belonging to the nth most common species. The Poisson–Dirichlet distribution is a model for such random ranked frequencies. It also arises from ranked jumps of a stable subordinator, which gives the model its connection to random interval partitions. Pitman and Yor's 1997…
Convex Duality in Constrained Portfolio Optimization II: The Dual Problem Attains Its Infimum, So an Optimal Constrained Portfolio–Consumption Pair Exists for Every Initial CapitalResearch Paper
Portfolio decisions in continuous time must respect both market uncertainty and investment restrictions. A ban on short sales, for example, restricts the vector of wealth fractions a trader may hold at every instant. The corresponding optimal consumption and investment problem is harder than its unrestricted counterpart because a candidate portfolio…
Graph Minors. X. Obstructions to Tree-Decomposition III: In the θ-Grid, the Separations of Order < θ With Small E(A) Form a Tangle of Order θResearch Paper
Robertson and Seymour introduced tangles as a way to describe a region of a graph that cannot be isolated by a separation of low order. A separation divides the edges into two sides, and its order counts the vertices shared by those sides. A tangle makes a consistent choice of the side regarded as small at every order below a threshold. This turns an…
Graph Minors. X. Obstructions to Tree-Decomposition V: A θ-Pervasive Class of Designs Gives a Tree-Decomposition over 𝒮^{3θ−2} ∪ ℛ_{4θ−3}Research Paper
Tangles were introduced by Robertson and Seymour in Graph Minors. X (JCTB 1991) to make precise the idea of a "highly connected region" of a graph. A tangle orients every low-order separation of the graph towards one side, consistently. They are the organising notion of the later papers of the Graph Minors series, which culminate in the graph structure…
Graph Minors. X. Obstructions to Tree-Decomposition II: Branch-Width and Tree-Width Satisfy max(β, γ) ≤ ω + 1 ≤ max(⌊3β/2⌋, γ, 1)Research Paper
Tree-width measures how closely a graph resembles a tree. It is the central width parameter of the Graph Minors series of N. Robertson and P. D. Seymour, which proves that finite graphs are well-quasi-ordered by the minor relation, and it governs the complexity of many algorithms: problems that are NP-hard in general become solvable in linear time on graphs…
Weak Limit Theorems for Stochastic Integrals and Stochastic Differential Equations: Under C2.2(i), (Xₙ, Yₙ) ⇒ (X, Y) in the Skorohod Topology Implies (Xₙ, Yₙ, ∫Xₙ dYₙ) ⇒ (X, Y, ∫X dY)Research Paper
Many approximation results in probability and operations research take the form of a sequence of discrete or jump-driven systems converging to a diffusion or another limit process. When the approximating systems are written as stochastic integral equations, Xn(t)=Xn(0)+∫0tσ(Xn(s−))dYn(s), the key step is to show that the stochastic…
Convex Duality in Constrained Portfolio Optimization I: Financibility, Minimality, Dual Optimality and Parsimony of an Auxiliary Market Are Equivalent and Yield the Optimal Constrained PolicyResearch Paper
An investor in a continuous-time market chooses, at every instant, how to split wealth between a bond and d stocks and how fast to consume, so as to maximize expected utility of consumption and terminal wealth. Without constraints on the portfolio, this problem was solved by the martingale method: Pliska (1986), Karatzas, Lehoczky and Shreve (1987) and Cox…
Truncated-Newton Algorithms for Large-Scale Unconstrained Optimization 1: Truncated-Newton CG Iterates Have ‖g(x_k)‖ → 0 and Converge to Any Limit Point with Positive Definite HessianResearch Paper
Large scale unconstrained optimization often makes an exact Newton step expensive. At each iterate, Newton's method asks for a solution of a linear system involving the Hessian, and the cost of solving that system can dominate the cost of evaluating the objective. Dembo and Steihaug's 1983 truncated Newton method uses conjugate gradients to stop the linear…
Diameter of Polyhedra: Limits of Abstraction 1: The Base Abstraction in Dimension n/4 with n Facets Has Diameter Ω(n²/log n)Research Paper
Whether the diameter of a polyhedron is bounded by a polynomial in its number of facets is one of the central open questions of convex geometry, and it bears directly on linear programming: the diameter of the graph of a polyhedron is a lower bound on the number of pivots of any simplex method that moves along edges. Write △u(d,n) for the largest…
Optimal Rates for the Regularized Least-Squares Algorithm III: Against Every Algorithm, a Single Distribution in P(b, c) Keeps the Expected Excess Risk above ℓ^(−cB/(cB+1)) for B > b (Theorem 3)Research Paper
Regularized least squares (RLS) in a reproducing kernel Hilbert space is a basic estimator of nonparametric regression and of kernel-based learning. Its learning rate is the speed at which the expected excess risk goes to zero as the sample size ℓ grows. A rate is useful only if it is known to be optimal, and optimality is a lower-bound statement about…
Optimal Rates for the Regularized Least-Squares Algorithm II: No Learning Algorithm Converges Faster than ℓ^(−bc/(bc+1)) Uniformly over P(b, c) — the Minimax Lower Rate (Theorem 2)Research Paper
Regularized least squares (RLS), also called kernel ridge regression, is one of the standard estimators of statistical learning: given a sample of input–output pairs, it fits a function from a reproducing kernel Hilbert space by minimizing the empirical squared error plus a multiple of the squared norm. Caponnetto and De Vito (FoCM 2007) proved that, over a…
Optimal Rates for the Regularized Least-Squares Algorithm I: With λ Tuned to the Effective Dimension, Regularized Least Squares Attains the Rate ℓ^(−bc/(bc+1)) Uniformly over P(b, c) (Theorem 1)Research Paper
Regularized least squares (RLS, also called kernel ridge regression or Tikhonov regularization) is the simplest learning algorithm built on a reproducing kernel Hilbert space. Given ℓ examples (xi,yi) drawn independently from an unknown distribution ρ, it returns the function in a hypothesis space H that minimizes the empirical squared…
Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey 5: Canonical Triplets Are Exactly the Solutions of the Coupled Optimality EquationsResearch Paper
A controlled Markov process run under the long-run average cost criterion asks for a policy minimizing the asymptotic cost per stage. When every stationary policy induces a single recurrent class, the optimal average cost is a constant and is characterized by one equation, the average cost optimality equation (ACOE). In general it is not: under some…
Optimization of Mean-field Spin Glasses III: The Lagrangian Value of the Stochastic Control Problem Equals the Parisi FunctionalResearch Paper
The ground-state energy of a mixed p-spin spin glass, OPTN=maxσ∈{±1}NHN(σ)/N, converges almost surely to the infimum of the Parisi functional over non-decreasing order parameters (Auffinger–Chen 2017). El Alaoui, Montanari and Sellke (arXiv:2001.00904v1) study algorithms that find near-optimal configurations. They introduce…
Optimization of Mean-field Spin Glasses II: Under No Overlap Gap, the Monotone Parisi Minimizer Also Minimizes the Extended FunctionalResearch Paper
The mixed p-spin model is a random polynomial on the hypercube {−1,+1}N: a centered Gaussian process HN(σ) with covariance E{HN(σ)HN(σ′)}=Nξ(⟨σ,σ′⟩/N). Its maximum OPTN=maxσHN(σ)/N is a canonical…
Convergence in law of the minimum of a branching random walk: The Minimum Centred at (3/2) ln n Converges to a Gumbel Law Shifted by the Derivative MartingaleResearch Paper
A branching random walk is the simplest model of a population that both reproduces and moves: every particle dies and leaves a random cloud of children displaced relative to it. Its extreme particles control the speed of travelling waves in reaction–diffusion equations (the KPP/Fisher equation), the free energy of directed polymers on trees, the cover and…
Projection-like Retractions on Matrix Manifolds IV: Within σ_r(X̄)/2 of a Rank-r Matrix, the Truncated SVD Is the Unique Nearest Matrix of Rank Exactly rResearch Paper
Optimization over sets of matrices of fixed rank comes up in low-rank matrix completion, model reduction, and the low-rank approximation of solutions of large matrix equations. A standard approach treats the constraint set as a Riemannian manifold and runs gradient or Newton-type methods on it (Absil, Mahony & Sepulchre 2008). Each iteration takes a step in…
Dynamic Pricing Strategies with Reference Effects I: Under Loss Aversion the Steady States Form an Interval and Optimal Paths ConvergeResearch Paper
Consumers judge a price against a reference price, an internal standard formed from the prices they have seen before. A price below the reference is perceived as a gain and stimulates demand; a price above it is perceived as a loss and depresses demand. Prospect theory (Kahneman and Tversky 1979) adds that losses loom larger than gains of the same size:…
On the Choice-Based Linear Programming Model for Network Revenue Management I: The CDLP Is Asymptotically Optimal under Proportional ScalingResearch Paper
Airlines, hotels and railways sell a fixed stock of perishable capacity (seats on flight legs, room-nights) to customers who arrive over a finite selling horizon. Network revenue management decides, at each moment, which products to keep open for sale. In the classical independent-demand model each product has its own demand stream. In practice customers…
The d-Level Nested Logit Model: Assortment and Price Optimization Problems II: The Push-Up-Then-Push-Down Prices Converge to a Stationary PointResearch Paper
Retailers that sell many substitutable products must set all their prices at once, and a
customer's reaction to one price depends on what else is on the shelf. The nested logit
model captures this by grouping similar products into nests, so that raising one price
shifts demand mostly to close substitutes. The d-level nested logit model extends the
familiar…
The Complexity of Optimal Queuing Network Control II: Restless Bandits with Deterministic Transitions are PSPACE-hardResearch Paper
Among queueing control problems, a small class admits efficiently computable optimal policies: a single server choosing among several customer streams (Klimov 1974). These problems can be recast as multi-armed bandit problems, whose optimal policies are given by Gittins indices (Gittins 1979), and those indices are computable in polynomial time. The most…
The Complexity of Optimal Queuing Network Control I: NETWORK OF QUEUES is EXP-completeResearch Paper
Multiclass queueing networks model manufacturing lines, computer systems and communication networks. In these systems jobs of several types move between shared resources, and a controller decides where to send a job next (routing) and which waiting job a free resource works on (sequencing). The central design question is to find a control policy that…
Stochastic Dynamic Programming and the Control of Queueing Systems V: The Average Cost Optimality Equation and Value Iteration for Finite State SpacesTextbook
Average cost Markov decision chains model systems that run indefinitely and are judged by their long-run cost per step: admission and routing control in queues, inventory replenishment, machine maintenance. For a finite state space the classical tool is the average cost optimality equation (ACOE)
Lost-Sales Problems with Stochastic Lead Times: Convexity Results for Base-Stock Policies: Expected Discounted Cost Is Convex in the Base-Stock LevelResearch Paper
In many inventory systems, demand that cannot be met from stock is lost rather than backordered: a customer who finds the shelf empty buys elsewhere. For such lost-sales systems with positive lead times the optimal replenishment policy is known to be complex and to depend on the whole pipeline of outstanding orders (Karlin and Scarf, 1958; Morton, 1969). In…
Minimization Methods for Non-Differentiable Functions IX: Convergence of the r-Algorithm with Exact Directional MinimizationTextbook
The r-algorithm of N. Z. Shor is a variable-metric method for minimizing functions that are not differentiable everywhere, such as maxima of smooth functions, penalty functions and Lagrangian dual functions of integer and decomposition problems. It combines a subgradient step with a space dilation along the difference of two successive almost-gradients, and…