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.
Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons 1: A Fixed Price Earns at Least 1 − 1/(2√min{n, λ*t}) of the Optimal Expected RevenueResearch Paper
A firm holds a fixed stock of a perishable or seasonal product: airline seats, hotel rooms, fashion goods, tickets. It must sell the stock over a finite season, and whatever is left at the end is worth nothing. The firm can change its price at any time, and demand responds to the price at random. Should it adjust its price continually as sales occur and…
Computational Issues in an Infinite-Horizon, Multiechelon Inventory Model 3: A Closed Form for the Induced Penalty Cost under Normal DemandResearch Paper
Multiechelon inventory theory studies supply systems in which stock is held at several levels: here, a depot that orders from an outside supplier and a retail outlet that is replenished from the depot and faces random customer demand. The question is how much to order and ship in each period so as to minimize expected holding, shortage and ordering costs…
Optimal Control of Markov Processes with Incomplete State Information 1: Reduction to Complete State Information on the Conditional State Distributions, with the Same Optimal LawResearch Paper
A controller often cannot see the state of the system it steers. It sees only measurements that are noisy functions of that state. In operations research this happens in machine maintenance and inspection, in queues observed only partially, and in inventory systems with inexact stock records. In control engineering it is the usual case. The question is what…
Contraction Mappings in the Theory Underlying Dynamic Programming 1: Under the Contraction and Monotonicity Assumptions the Solution of the Functional Equation Is the Optimal ReturnResearch Paper
Dynamic programming often replaces a search over whole plans with an equation for a value function. That replacement is useful only when solving the equation recovers the value actually available through policies. In his 1967 paper, Eric Denardo isolated conditions on an abstract return function that make this identification possible, without committing to…
On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift 1: Projected Gradient Ascent on the Simplex Is ε-Optimal After 64γ|S||A|D∞²/((1−γ)⁶ε²) IterationsResearch Paper
Policy gradient methods optimize a parameterized policy of a Markov decision process by gradient ascent on its expected discounted return. They are among the most widely used methods in reinforcement learning, from REINFORCE (Williams 1992) and the policy gradient theorem to natural policy gradient and trust-region methods. The objective is not concave in…
Simultaneously Learning and Optimizing Using Controlled Variance Pricing 2: Certainty Equivalent Pricing Fails to Converge to the Optimal Price with Positive ProbabilityResearch Paper
A seller who does not know how demand responds to price has to learn the demand curve from its own sales while it is selling. The most natural policy is certainty equivalent pricing (also called myopic pricing or passive learning): after every period, estimate the unknown demand parameters from all data collected so far, and charge the price that would be…
Robust Wasserstein Profile Inference and Applications to Machine Learning 1: Square-Root LASSO Is Wasserstein DRO — the Worst-Case Squared Loss over D_c(P, P_n) ≤ δ Equals (√MSE_n(β) + √δ‖β‖_p)²Research Paper
Regularized least squares is the standard tool of high-dimensional linear regression. The square-root LASSO of Belloni, Chernozhukov and Wang (Biometrika, 2011) minimizes MSEn(β)+λ∥β∥1. Unlike the LASSO, its optimal regularization parameter does not depend on the unknown noise level. Regularization is usually justified…
Oracle-Based Robust Optimization via Online Learning 1: The Dual-Subgradient Meta-Algorithm Returns a 2ε-Approximate Robust Solution or Certifies Infeasibility within ⌈G²D²/ε²⌉ Oracle CallsResearch Paper
Robust optimization protects a decision against every realization of uncertain data in a prescribed uncertainty set. The standard approach replaces the uncertain constraints by a deterministic robust counterpart and solves that counterpart directly (Ben-Tal, El Ghaoui, Nemirovski, Robust Optimization, 2009). The counterpart is often a harder problem than…
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results 4: A Fixed Boolean Combination of k Classes Has Gaussian Complexity at Most 2 Σ_j G_n(F_j)Research Paper
Data-dependent risk bounds in statistical learning replace combinatorial quantities such as the VC dimension with averages of how well a function class can fit random noise on the observed sample. Bartlett and Mendelson's article (JMLR 3, 2002) established these averages, the Rademacher and Gaussian complexities, as a general tool: a risk bound (their…
Optimization with Stochastic Dominance Constraints: Lagrange Multipliers of a Second-Order Dominance Constraint Are Concave Nondecreasing Utility FunctionsResearch Paper
A decision maker choosing a random outcome X (a portfolio return, a policy's cost savings, a schedule's throughput) often has a reference outcomeY, the result of a benchmark policy, and wants the new outcome to be preferable to it for every risk-averse decision maker, not just on average. Expected-utility theory (von Neumann and Morgenstern) makes this…
Uniformly Bounded Regret in the Multi-Secretary Problem 2: When (f₁+ε)n ≤ k ≤ (1−fₘ−ε)n, Every Non-Adaptive Policy Has Regret at Least M√nResearch Paper
The multi-secretary problem is the basic model of selecting under a budget from a stream of offers. Hiring a fixed number of candidates, accepting a fixed number of requests for a perishable resource, and admitting customers into a capacity-limited service all have this structure. Each item must be accepted or rejected on arrival, and the comparison point…
Uniformly Bounded Regret in the Multi-Secretary Problem 1: The Budget-Ratio Policy Has Regret at Most a₁M(ε), Uniformly in the Number of Candidates n and the Budget kResearch Paper
The multi-secretary problem is the simplest model of capacity allocation under uncertainty: a decision maker sees n candidates one at a time and may hire at most k of them, with every decision final. The same structure underlies single-resource revenue management (accepting or rejecting booking requests against a fixed inventory; see Talluri and van Ryzin, T…
Assortment Optimization under Variants of the Nested Logit Model 4: With Dissimilarity Parameters at Most One, the Knapsack-Relaxation and Singleton LP Optimum Scaled by 2 Is Feasible for the Full LPResearch Paper
Assortment optimization asks which set of products a firm should offer when customers choose among the offered products according to a discrete choice model; it underlies shelf-space planning in retail and fare-class control in airline revenue management (Talluri and van Ryzin, 2004). Under the nested logit model products are grouped into nests, and a…
Assortment Optimization under Variants of the Nested Logit Model 2: With Dissimilarity Parameters at Most One and Fully-Captured Nests, a Nested-by-Revenue Assortment in Every Nest Is OptimalResearch Paper
A retailer choosing which products to display, or an airline choosing which fare classes to open, solves an assortment optimization problem: pick the set of offered products that maximizes expected revenue when customers choose among what is offered according to a discrete choice model. Under the multinomial logit model the answer has a simple form: an…
On the Power and Limitations of Affine Policies in Two-Stage Adaptive Optimization IV: When A ≥ 0 the Best Affine Policy Costs at Most 3√m Times the Fully Adaptable OptimumResearch Paper
Two-stage adaptive optimization models decisions taken in two steps: a first-stage decisionx is fixed before an uncertain right-hand side b is revealed, and a second-stage decisiony(b) is chosen after it, as a function of b. The objective protects against the worst b in an uncertainty setU. Computing an optimal fully adaptable solution is…
Explicit Expanders of Every Degree and Size 1: For Distinct Primes q₁, q₂, Every Large n Has an LPS Vertex Count Q(q₁, q₂, s, t) Between n and n + o(n)Research Paper
An (n,d,λ)-graph is a d-regular graph on n vertices in which every eigenvalue of the adjacency matrix other than the top eigenvalue d has absolute value at most λ. Graphs of this kind with λ small compared with d are expanders. They are used in derandomization, error-correcting codes, sorting networks and many other constructions in…
Conditional Logit Analysis of Qualitative Choice Behavior 3: The Conditional Logit Likelihood Has a Maximum Exactly When No Direction Makes Every Observed Choice Weakly BestResearch Paper
The conditional logit model is the workhorse of discrete choice analysis in transportation, marketing, labour and industrial organization. McFadden's 1974 chapter derived it from a theory of population choice behaviour and showed how to estimate it by maximum likelihood; this line of work was recognized by his 2000 Nobel Prize in Economic Sciences, awarded…
Reversibility and Stochastic Networks IX: Partial Balance — Equivalent Characterizations via Truncation, Rate Changes and Time ReversalTextbook
Equilibrium distributions of Markov models of networks are rarely computed by solving the full equilibrium equations directly. In the classical product-form results (migration processes, Jackson and Kelly networks, loss networks, clustering processes) the equilibrium distribution satisfies a stronger, local family of equations, and that is what makes it…
A Primal–Dual Splitting Method for Convex Optimization Involving Lipschitzian, Proximable and Linear Composite Terms I: Iterates Converge Weakly to a Primal–Dual Solution When 1/τ − σ‖L‖² ≥ β/2Research Paper
Many convex optimization models combine a smooth loss, a nonsmooth penalty whose proximity operator is easy to compute, and a second penalty applied after a linear map. Imaging models, for example, often place a data-fitting term on the image and a regularizer on its transformed coefficients. The resulting objective has the form F(x)+G(x)+H(Lx). Condat's…
Conditional Logit Analysis of Qualitative Choice Behavior 2: Random Utility Maximizers Choose by Logit Exactly When Taste Shocks Are Extreme-Value DistributedResearch Paper
The conditional logit model assigns to an alternative i in a finite choice set the probability eVi/∑jeVj, where Vj is a "representative utility" built from observed attributes of the alternative and the decision maker. It is the workhorse of discrete choice econometrics, transportation demand forecasting, marketing and revenue management,…
Twice Regularized MDPs and the Equivalence Between Robustness and Regularization 2: The Greedy Policy of the R2 Optimal Value Is the Unique Optimal R2 PolicyResearch Paper
A robust Markov decision process (robust MDP) evaluates a policy against the worst transition kernel and reward in an uncertainty set around a nominal model (P0,r0). It is the standard model for planning when the dynamics are estimated from data (Iyengar 2005; Nilim and El Ghaoui 2005; Wiesemann, Kuhn and Rustem 2013). Its Bellman update contains an…
Reversibility and Stochastic Networks VIII: Markov Fields — A Positive Random Field Is Markov iff It Factorizes over the Simplices of the GraphTextbook
Many systems consist of a finite number of sites whose states influence one another only locally: fruit trees in an orchard that are diseased or healthy, power sources that are working or broken, individuals holding one of several views. Chapter 9 of F. P. Kelly, Reversibility and Stochastic Networks (Wiley, 1979) asks which joint distributions such systems…
Reversibility and Stochastic Networks V: Optimal Capacity Allocation in a Network of QueuesTextbook
Chapter 4 of F. P. Kelly's Reversibility and Stochastic Networks (Wiley, 1979) applies the product-form theory of Chapter 3 to concrete systems. Two of its results have numbered statements, and they answer two practical questions.
Projection-like Retractions on Matrix Manifolds II: The Metric Projection onto a C^k Submanifold Is Locally Unique and C^(k−1), so Projecting a Tangent Step Is a RetractionResearch Paper
Many optimization problems in statistics, signal processing and control are posed over sets of matrices with a constraint that makes them curved: matrices of fixed rank, matrices with orthonormal columns, symmetric matrices with a prescribed spectrum. Algorithms on such sets ("optimization on manifolds") compute a step in the tangent space at the current…
Reversibility and Stochastic Networks III: Open Networks of Queues with General Customer Routes Have Product-Form EquilibriumTextbook
Networks of queues model systems in which jobs visit a sequence of service stations: items in a manufacturing job-shop, packets in a communication network, patients moving between hospital departments. The open migration process of Chapter 2 of F. P. Kelly, Reversibility and Stochastic Networks (Wiley, 1979), and the job-shop networks of Jackson (Jackson…