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.
Optimality and Duality Theory for Stochastic Optimization Problems with Nonlinear Dominance Constraints 1: Under Uniform Dominance, Optimal Solutions Have Concave Utility and L∞ MultipliersResearch Paper
Stochastic programs often optimize a decision that changes several random outcomes at once. A reference outcome may be acceptable even when no fixed threshold captures its risk: one wants the new outcome to be preferable under every increasing concave assessment of gains. Second order stochastic dominance expresses that comparison. Dentcheva and Ruszczyński…
Contraction Mappings in the Theory Underlying Dynamic Programming 2: Under N-Stage Contraction and Monotonicity the Optimal Return Is the Unique Fixed Point of the Maximization OperatorResearch Paper
Infinite-horizon dynamic programs, including discounted Markov decision processes, stochastic games and semi-Markov models, are usually analysed through a single equation: the optimal return f solves the optimality equationv=Av, where A maximizes the one-step return over decisions. Denardo's 1967 paper (SIAM Review 9(2), 165–177) separated the argument…
Maximum Pressure Policies in Stochastic Processing Networks III: Strict Leontief Networks Satisfy the Extreme-Allocation-Available (EAA) AssumptionResearch Paper
A stochastic processing network (Harrison 2000) models a system in which processors carry out activities and each activity draws jobs from one or more buffers. Manufacturing lines, call centers with cross-trained agents, and data switches all fit this model. A central question is which scheduling policies are throughput optimal, meaning they stabilize the…
Coordinating Inventory Control and Pricing Strategies with Random Demand and Fixed Ordering Cost: The Finite Horizon Case 2: General Demand: Sym-k-Concave Profit-to-Go, Optimal (s, S, A, p) PolicyResearch Paper
A seller with replenishable inventory must decide how much to order and what price to charge before demand is known. A price that increases current revenue can also change the inventory left for later periods; a fixed charge for placing any positive order adds a discontinuity to the decision. Chen and Simchi-Levi study this coordination problem over a…
A Friendly Smoothed Analysis of the Simplex Method: Gaussian-Perturbed Shadows Have at Most 3 + 128πe²d²√(log n)σ⁻²(1 + 4σ√(d log n))(1 + 16σ√(log n)) Expected EdgesResearch Paper
The simplex method solves linear programs quickly in practice, yet for most pivot rules there are inputs on which it takes exponentially many steps (Klee and Minty, 1972). Smoothed analysis, introduced by Spielman and Teng (JACM 2004), explains the gap: it measures the expected running time when every constraint row of a worst-case input is perturbed by a…
The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs: Fully-Supported Problems Attain the Binomial Violation Tail ExactlyResearch Paper
Many design problems in control, finance and engineering are convex programs whose constraints depend on an uncertain parameter δ: a solution must satisfy x∈Xδ for every δ in a possibly infinite set Δ. Enforcing all constraints (robust optimization) is often intractable or overly conservative. The scenario approach draws N ind…
Convex Optimization: Algorithms and Complexity XVII: Goemans–Williamson Rounding of the MAXCUT SDP Relaxation Has Expected Value at Least 0.878 Times the Maximum CutTextbook
MAXCUT asks for a partition of the vertices of a weighted graph into two sets that maximizes the total weight of the edges between them. It is one of Karp's original NP-hard problems, so no polynomial-time exact algorithm is expected, and the natural question is how close a polynomial-time algorithm can come to the optimum. Sampling a uniformly random…
Convex Optimization: Algorithms and Complexity XVI: Random Coordinate Descent RCD(γ) on a Strongly Convex Coordinate-Smooth Function Has Rate (1 − 1/κ_γ)^tTextbook
When a problem has millions of variables, even one full gradient can be too expensive to compute, while a single partial derivative ∂f/∂xi is often cheap: in regularized regression, support vector machines and many structured problems, updating one coordinate costs a small fraction of a full gradient step. Coordinate descent methods exploit…
Convex Optimization: Algorithms and Complexity XIV: Stochastic Mirror Descent on a β-Smooth Function with Noise σ Has Rate Rσ√(2/t) + βR²/tTextbook
Many optimization problems in statistics and machine learning ask to minimize an expected loss f(x)=Eξℓ(x,ξ), or an average f(x)=m1∑i=1mfi(x) over a large data set. Exact gradients of such an f are unavailable or too expensive, but unbiased random estimates are cheap: the gradient of the loss at one sample, or of one randomly…
Convex Optimization: Algorithms and Complexity XII: Mirror Prox on a Convex β-Smooth Function Has Rate βR²/(ρt)Textbook
First-order methods for constrained convex optimization are usually analysed in the Euclidean norm, where gradient descent and its projected and accelerated variants have well-understood rates. Many constraint sets of practical interest, such as the probability simplex, the ℓ1 ball and the spectrahedron, are poorly adapted to the Euclidean geometry: the…
Online Primal-Dual Algorithms for Covering and Packing 1: The Online Fractional Packing Scheme Is B-Competitive and Violates Each Packing Constraint by at Most 2 log(1 + n·a_i(max)/a_i(min))/BResearch Paper
Many resource-allocation problems arrive one request at a time and must be answered immediately: a bandwidth request is admitted or refused when it appears, an advertiser's budget is charged when a query arrives, a job is accepted before later jobs are seen. Their linear-programming relaxations are packing problems: maximize a total profit subject to…
Convex Optimization: Algorithms and Complexity XI: Mirror Descent with a ρ-Strongly Convex Mirror Map Has Rate RL√(2/(ρt))Textbook
The projected subgradient method of Chapter 3 measures distances in the Euclidean norm, and its rate RL/t depends on the geometry only through a Euclidean radius R and a Euclidean bound L on the subgradients. For many constraint sets that occur in practice this is the wrong geometry. On the probability simplex Δn with subgradients bounded in …
Convex Optimization: Algorithms and Complexity X: Nesterov's Accelerated Gradient Descent on a β-Smooth α-Strongly Convex Function Has Rate ((α + β)/2)‖x₁ − x*‖² exp(−(t − 1)/√κ)Textbook
First-order methods, which query only function values and gradients, are the workhorse of large-scale optimization in machine learning, signal processing and operations research, because each step costs little more than one gradient evaluation. For a function that is both strongly convex and smooth, plain gradient descent converges geometrically, but the…
Convex Optimization: Algorithms and Complexity IX: Nesterov's Accelerated Gradient Descent on a Convex β-Smooth Function Has Rate 2β‖x₁ − x*‖²/t²Textbook
Minimizing a convex function f:Rn→R whose gradient is Lipschitz is the basic problem of first-order optimization, and it is the regime in which most large-scale methods of machine learning, signal processing and operations research are analysed. The natural method, gradient descent, reaches accuracy ε after O(1/ε) gradi…
Convex Optimization: Algorithms and Complexity VIII: No Black-Box Method Beats 3β‖x₁ − x*‖²/(32(t + 1)²) on β-Smooth Convex FunctionsTextbook
Upper bounds for an optimization method say how fast it converges; oracle complexity lower bounds say how fast any method of a given kind can possibly converge. Chapter 3 of S. Bubeck, Convex Optimization: Algorithms and Complexity (Foundations and Trends in Machine Learning 8(3–4), 2015, arXiv:1405.4980) proves upper bounds for subgradient descent on…
Quantifying Distributional Model Risk via Optimal Transport 1: Strong Duality — the Worst-Case Expectation over an Optimal-Transport Ball on a Polish Space Equals Its Dual over (λ, φ)Research Paper
A probability model μ for a random element X is rarely known exactly. Distributionally robust performance analysis replaces the single expectation Eμ[f(X)] by its worst case over all models within a prescribed distance of μ. When the distance is an optimal-transport cost, the neighbourhood contains models whose support differs from that of μ. That…
A Robust Optimization Approach to Inventory Theory: The Optimal Robust Policy Is the Optimal Nominal Policy for an Explicit Modified Demand, at Extra Cost (2ph/(p+h))·ΣA_kResearch Paper
Classical inventory theory chooses order quantities against a probability distribution of demand. The resulting dynamic programs are optimal in expectation but need the distribution, and they become intractable once several installations, capacities or fixed costs interact. Robust optimization replaces the distribution by an uncertainty set and asks for the…
Airline Seat Allocation with Multiple Nested Fare Classes 2: With Integer-Valued Demands an Optimal Integer Protection-Level Policy ExistsResearch Paper
Airlines sell the seats of one flight leg at several prices. Cheaper fare classes tend to book earlier, so the seller must decide, as low-fare requests arrive, how many seats to hold back for later and more valuable passengers. The standard control is nested protection levels: a number pk of seats is reserved for the k most expensive classes together, and…
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results 6: The Expected Maximum Discrepancy Lies Between R_n(F)/2 − 2√(2/n) and R_n(F) + 4√(2/n)Research Paper
Data-dependent risk bounds in statistical learning theory control the gap between the expected loss of a learned function and its empirical loss by a complexity penalty that is computed from the training data. The first such penalties were the maximum discrepancy of a function class (Bartlett, Boucheron and Lugosi, Model selection and error estimation,…
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results 5: Kernel Expansions with α′Kα ≤ B² Have Rademacher and Gaussian Complexity at Most 2B√(E k(X,X)/n)Research Paper
Kernel methods, such as support vector machines, predict with functions of the form x↦∑iαik(x,xi): finite expansions of a fixed similarity function k centred at data points. Their statistical behaviour is governed by the size of the class of such expansions that the method searches. Bartlett and Mendelson, in Rademacher and Gaussian…
Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey 4: Under Sennott's Conditions an Average-Cost Optimal Stationary Policy ExistsResearch Paper
Many controlled queueing, inventory and maintenance systems are modelled as controlled Markov processes (CMPs) on a countable state space whose one-stage cost grows without bound: the holding cost of a queue grows with its length. For such systems the natural performance measure is the long-run average cost, and the basic question is whether some simple…
Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms III: With One Unknown Parameter, Staged Re-estimation Has Regret O((log log n)(log n)^{1/2}/n^{1/2})Research Paper
A seller with a fixed stock of a single product and a finite selling season must post prices without knowing how demand responds to price. Revenue management treats this as a constrained stochastic control problem; with the demand curve known, the problem was solved by Gallego and van Ryzin (Management Science, 1994). When the curve is unknown, every price…
On the Approximability of Single-Machine Scheduling with Precedence Constraints 1: A k-Fold Realizer of Size t Yields a Vertex Cover of Expected Weight at Most (2 − 2/(t/k)) Times OptimalResearch Paper
Single-machine scheduling with precedence constraints, written 1∣prec∣∑wjCj in the notation of Graham et al., asks for an order of n weighted jobs on one machine that respects a given partial order and minimizes the weighted sum of completion times. The problem is strongly NP-hard (Lawler 1978; Lenstra and Rinnooy Kan 1978), and closing its…
Log-Barrier Interior Point Methods Are Not Strongly Polynomial 1: Every Polygonal Curve in the Wide Neighborhood of the Central Path of LW_r(t) from μ̄ ≤ 1 to μ̄ ≥ t² Has at Least 2^(r−1) SegmentsResearch Paper
Interior point methods solve linear programs in a number of arithmetic operations polynomial in the bit length of the input (Karmarkar 1984). Whether linear programming admits a strongly polynomial algorithm, one whose number of arithmetic operations is bounded by a polynomial in the number of variables and constraints alone, is open; it is the ninth of…
Data-Driven Robust Optimization V: The Order-Statistic Box U^M Built from Marginal Samples Dominates Value at Risk with Probability at Least 1 − αResearch Paper
Robust optimization replaces an uncertain constraint f(u~,x)≤0 by the requirement that it hold for every u in an uncertainty setU⊆Rd. The resulting problems are tractable for many sets, but the choice of U decides whether the solution means anything probabilistically. Bertsimas, Gupta and…