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.
Markov Chains and Mixing Times VI: Networks, Hitting Times, and Cover TimesTextbook
A reversible Markov chain is an electrical network: states are nodes, and the conductance c(x,y)=π(x)P(x,y) turns hitting probabilities into voltages and hitting times into resistances. This dictionary, going back to Kakutani and popularized by Doyle and Snell, converts probabilistic estimates into the physical laws of circuits — series/parallel…
Modern A/B tests must infer lifetime treatment effects — e.g. customer lifetime value under a new feature — from short-horizon experiment data. Chen, Simchi-Levi and Wang (arXiv:2407.19618) model the experiment as a Markov decision process and exploit a structural fact of many practical interventions: the treatment is local, modifying the system at a single…
Markov Chains and Mixing Times I: Existence and Uniqueness of the Stationary DistributionTextbook
Finite Markov chains are the basic model for memoryless random dynamics: card shuffles, random walks on graphs and groups, Monte Carlo samplers, and queueing systems are all chains on a finite state space. The single most used fact about them is that an irreducible chain has exactly one stationary distribution — a probability vector π with π=πP —…
The classical convergence theory of smooth convex minimization. For a function that is m-strongly convex and M-smooth (mI⪯∇2f(x)⪯MI), gradient descent converges linearly, while Newton's method exhibits its famous two phases: a damped phase in which every backtracking step decreases the objective by a fixed amount γ, and a quadrati…
The Karush–Kuhn–Tucker conditions are the central result of convex optimization: for a convex differentiable problem satisfying Slater's condition, a point is optimal exactly when primal feasibility, dual feasibility, complementary slackness and Lagrangian stationarity hold. This mission formalizes Chapters 4–5 of Boyd & Vandenberghe end to end — the…
Introduction to Linear Optimization XIII: Lagrangean Duality and Integer ProgrammingTextbook
Linear programming has a complete duality theory; integer programming does not — and the Lagrangean dual measures exactly how far duality reaches. This mission formalizes the duality theory of integer programming from Section 11.4 of Bertsimas–Tsitsiklis, built on the general linear programming duality of Section 4.10. For the integer program
Introduction to Linear Optimization VII: Cones, Extreme Rays, and the Resolution TheoremTextbook
How can an unbounded polyhedron be described by finitely many geometric objects? Sections 4.8-4.9 of Bertsimas-Tsitsiklis build the cone machinery: recession cones {d∣Ad≥0} and their rays, extreme rays (defined, like basic solutions, by n−1 linearly independent active constraints), the pointedness criterion (Theorem 4.12: 0 is an extreme point of…
Matrix Completion has No Spurious Local MinimumResearch Paper
Matrix completion — recovering a low-rank matrix M=ZZ⊤ from a small random subset of its entries — powers recommender systems and collaborative filtering. In practice it is solved by running (stochastic) gradient descent on the non-convex objective
Bandit feedback is only one point on a spectrum: a learner might see more than its own loss (full information) or less (a spam filter never learns what happened to mail it deleted). Chapter 37 of Lattimore–Szepesvári studies finite adversarial games G=(L,Φ) where the loss matrix and the feedback matrix are decoupled. The goal theorem is the…
Bandit Algorithms X: Stochastic Linear Bandits and LinUCBTextbook
When actions are feature vectors and the mean reward is linear — Xt=⟨θ∗,At⟩+ηt — a bandit can generalize across arms: pulling one arm reveals information about all of them. Chapter 19 of Lattimore–Szepesvári carries the optimism principle into this setting: LinUCB (a.k.a. OFUL) plays the action maximizing …
Bandit Algorithms IX: Self-Normalized Concentration and Optimal DesignTextbook
Least-squares estimation from adaptively collected data is the statistical heart of linear bandits: the actions At depend on past noise, so classical fixed-design theory does not apply. Chapter 20 of Lattimore–Szepesvári resolves this with the method of mixtures: the process Mt(x)=exp(⟨x,St⟩−21∥x∥Vt(λ)2) is a…
Quantum Field Theory on Curved Backgrounds. II. Spacetime Symmetries: every reflected or reflection-invariant isometry flow has an OS quantization exp(−αA) or exp(iαA) with A self-adjointResearch Paper
Osterwalder–Schrader (OS) quantization (Osterwalder, Schrader 1973) turns a Euclidean field theory, a probability measure on fields over a Riemannian space, into a quantum theory: a Hilbert space H of physical states. Symmetries of the Riemannian space should become symmetries of the quantum theory, but the passage is not automatic, because …
Dynamic Pricing with Menu Costs: Approximation Schemes and Applications to Grocery Retail: A Budget-Feasible Pricing Strategy Within 1 − ε of Optimal in Time (|I|/ε · ϱmax)^O(T) · ‖U¹‖∞^O(1)Research Paper
Grocery retailers set prices on a weekly calendar, but every price change has a cost: shelf labels must be reprinted and replaced, systems updated, staff scheduled. The economics literature calls these menu costs; for large US supermarket chains they were measured at a sizeable fraction of net margins (Levy, Bergen, Dutta, Venable, 1997), so retailers limit…
Markov Decision Processes with Applications to Finance VI: With Proportional Transaction Costs the Optimal Portfolio Has Buy, Hold and Sell Regions Given by ConesTextbook
In frictionless discrete-time portfolio models the investor rebalances freely, and with a homogeneous utility the optimal policy keeps a constant fraction of wealth in the stock. Real trading is costly: every purchase or sale of stock pays a fee proportional to the traded amount. A constant-fraction policy then trades every period and pays the fee every…
Markov Decision Processes with Applications to Finance XII: The Primal and Dual Linear Programs of a Contracting Markov Decision Problem Have Equal Values and Optimal SolutionsTextbook
A discounted Markov Decision Problem asks for a policy that maximizes the expected discounted sum of rewards of a controlled Markov chain. Besides value iteration and policy iteration, the third classical way to compute such policies is linear programming: the value function is the smallest function satisfying a family of linear inequalities, and the dual…
Markov Decision Processes with Applications to Finance XIV: When the One-Step Stopping Set Is Closed the One-Step-Look-Ahead Rule Is OptimalTextbook
Optimal stopping asks when to end a random process so as to maximize the expected reward. It covers house selling, the secretary problem, sequential testing and the exercise of American options. Chapter 10 of N. Bäuerle and U. Rieder, Markov Decision Processes with Applications to Finance (Springer, 2011, doi:10.1007/978-3-642-18324-9) treats these problems…
Markov Decision Processes with Applications to Finance II: In Convex Markov Decision Models the Convex Functions in Bb+ Satisfy the Structure AssumptionTextbook
In a finite-horizon Markov decision problem the value functions Vn are computed backwards by the Bellman equation Vn=TnVn+1. Bäuerle and Rieder (Springer 2011) organize the general theory around one hypothesis, the Structure Assumption(SAN): if a class of functions IMn is stable under the maximal reward operator Tn and every…
Online Policies for Efficient Volunteer Crowdsourcing: The Sparse Notification Policy Is 2−q1(1−e1)-CompetitiveResearch Paper
Nonprofit crowdsourcing platforms rely on volunteers to perform time-sensitive tasks. On Food Rescue U.S., for example, a task is a scheduled pickup of a perishable donation, and when a task goes unclaimed the platform can push a notification to a subset of volunteers. Notifying more volunteers raises the chance that the current task gets done, but…
Dynamic Pricing and Capacity Optimization in Railways: the static-price flexible-capacity policy has an O(κ) optimality gap and is asymptotically optimalResearch Paper
National railways sell tickets for a given travel day over a long sales horizon. Many of them sell two products at once: a reserved ticket, tied to a seat on one train, and an unreserved ticket, which lets the passenger board any train on the travel day and stand if no seat is free. The operator also decides how many coaches of each kind a train carries.…
Batching and Optimal Multi-stage Bipartite Allocations: PR-MWM Is (1 − (1 − 1/K)^K)-Competitive for K-Stage Fractional Vertex-Weighted MatchingResearch Paper
Matching platforms rarely decide on one request at a time. A ride-hailing marketplace clears requests in short windows, an ad exchange serves a video session's slots together, and cloud and retail systems process demand in rounds. Between the fully offline problem and the online model of Karp, Vazirani and Vazirani (STOC 1990) lies a question with an…
Condition-Based Production for Stochastically Deteriorating Systems: Optimal Policies and Learning: The Optimal Production Rate Decreases in Deterioration, Time to Maintenance and Base RateResearch Paper
Production systems such as wind turbines and assembly equipment can often be run faster or slower, and running faster usually wears them out faster. Between scheduled maintenance visits, an operator can therefore trade revenue now against deterioration later. Condition-based production, a term coined by Uit het Broek et al. (2020), makes this trade-off…
Grothendieck inequalities for semidefinite programs with rank constraintResearch Paper
The graphical Grothendieck problem with rank constraint maximizes a quadratic form over
unit vectors assigned to the vertices of a graph. Depending on the rank, the same problem is
MAX CUT, Grothendieck's inequality, the ground state of a spin model, or the value of a quantum
XOR game.
Efficient Algorithms for a Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Management: Explicit Global Convergence Bound for Mirror Stochastic GradientResearch Paper
Many operations management models choose a decision x whose effect is filtered through randomness: a booking limit x is truncated by random demand ξ, so the realized sales are x∧ξ; an order quantity is scaled by a random yield. The resulting stochastic program
Managing Customer Churn via Service Mode Control: A Myopic-or-Sandwich Interval Policy Is Optimal Among All Admissible Service-Mode ControlsResearch Paper
Subscription businesses, online platforms and service providers lose revenue when customers leave, and the marketing literature models churn as a hazard driven by the customer's state, for instance through logit hazard functions (Rust, Lemon and Zeithaml, Return on marketing: Using customer equity to focus marketing strategy, Journal of Marketing 68(1),…
Envelope Theorems for Multi-Stage Linear Stochastic Optimization: The Optimal Value Is Almost Everywhere Differentiable with the Envelope Formula Over All Optimal Primal-Dual PairsResearch Paper
Operations researchers solve multi-stage linear stochastic programs (MSLPs) to plan under uncertainty, for example in inventory planning and gas storage operation, and then ask how the optimal value reacts to a parameter: a price, a demand level, a capacity. Re-solving at many parameter values is expensive. An envelope theorem gives the derivative of the…