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 Role of Lookahead and Approximate Policy Evaluation in Reinforcement Learning with Linear Value Function Approximation: Error Bound for Least-Squares Policy Iteration with LookaheadResearch Paper
Approximate policy iteration is the template behind most practical reinforcement-learning systems for large state spaces: alternate between choosing a policy that looks good under the current value estimate and estimating the value of that policy, with errors in both steps. Game-playing systems such as AlphaZero add two ingredients to this template: a…
The Continuous-Time Joint Replenishment Problem: ϵ-Optimal Policies via Pairwise Alignment: Ψ-Pairwise Alignment Yields a Replenishment Policy Within Factor 1 + 5ϵ of Any PolicyResearch Paper
The joint replenishment problem is a basic model of coordinated inventory control. A firm stocks n commodities, each of which follows its own Economic Order Quantity (EOQ) model, but every order also incurs a joint ordering costK0, regardless of which commodities it contains. Ordering commodities together therefore saves money, and the question is how to…
Corruption-Robust Exploration in Episodic Reinforcement Learning II: Uniformly Action-Eliminating Algorithms Suffer Expected Regret at Least K/8 for K ≤ A^H/4Research Paper
In stochastic multi-armed bandits, a robust way to explore is action elimination: keep confidence intervals for every arm, discard an arm once its upper confidence bound falls below another arm's lower confidence bound, and sample uniformly among the arms that survive. Uniform sampling is what makes the first corruption-robust bandit algorithm work (Lykouris…
Markov Decision Processes with Observation Costs: Framework and Computation with a Penalty Scheme: The Quasi-Variational Inequality with Inspection Operator Has a Unique Bounded SolutionResearch Paper
In many sequential decision problems the state of a system is not observed for free. A controller monitoring a machine, a patient or an inventory must pay to inspect it, and between inspections it acts on a belief rather than on the state. The observation cost model (OCM) makes this precise for a finite Markov chain: at each time the controller either pays…
A Model of Shoppertainment Live Streaming: Zero Entertainment Bandwidth Is Never Optimal, the Optimal Bandwidth Lies Beyond the Traffic Peak, and Is Full Entertainment When vₑ > v(1+q)/4Research Paper
In shoppertainment live streaming a single streamer sells products from many manufacturers during live sessions that mix product presentation with entertainment. Some of the most successful streamers spend much of their air time on content unrelated to the products; the paper cites Dong Yuhui, who devotes his sessions to English lessons. Traditional TV…
Coordinating Inventory Control and Pricing Strategies for Perishable Products 1: With Backlogging, the Profit-to-Go Is L♮-Concave and the Optimal Policy Is Monotone with Bounded SensitivityResearch Paper
Food, blood and pharmaceuticals are perishable: a unit not sold within its lifetime is thrown away. A seller decides each period how much to order, which price to charge, and whether to dispose of stock early. A large stock of old units argues for a lower price and a smaller order.
A Distributionally Robust Perspective on Uncertainty Quantification and Chance Constrained Programming: Individual Chance Constraints over Markov Ambiguity Sets Are Finite Conic SystemsResearch Paper
Many engineering and operations problems must guarantee that a system operates safely with high probability, when the uncertain parameters z~ are only partially known. A chance constraint asks that the safety condition Sz~≤t hold with probability at least 1−ϵ for a tolerance ϵ∈(0,1). When the distribution of z~ is…
Rendezvous search asks how two agents who cannot communicate should move so as to meet as quickly as possible. It was introduced as a mathematical problem by Alpern (The rendezvous search problem, SIAM J. Control Optim. 1995) and developed systematically in Alpern and Gal's monograph The Theory of Search Games and Rendezvous (Kluwer, 2003). Besides its…
Convergence Analysis of Sampling-Based Decomposition Methods for Risk-Averse Multistage Stochastic Convex Programs 2: Subdifferential of the Value Function of a Convex ProgramResearch Paper
Stochastic dual dynamic programming (SDDP) and related decomposition methods solve multistage stochastic programs by approximating each stage's recourse function from below by a maximum of affine cuts. Every cut needs a value and a slope: the value of a convex subproblem at a trial point, and a subgradient of that subproblem's optimal value as a function of…
Strict Constraint Qualifications and Sequential Optimality Conditions for Constrained Optimization III: SAKKT-Regularity Is the Weakest Strict Constraint Qualification for SAKKTResearch Paper
Algorithms for smooth constrained optimization stop when an approximate optimality test passes. The tests used in practice are sequential optimality conditions: properties of a sequence of iterates xk→x∗ rather than of the limit point alone. Every local minimizer satisfies them, with or without a constraint qualification. The price is that a point…
Strong and Weak Equilibria for Time-Inconsistent Stochastic Control in Continuous Time 4: Limits of Equilibria of the Time-Discretized Problems Are Weak Equilibria in Continuous TimeResearch Paper
A decision maker is time-inconsistent when the plan that is optimal today stops being optimal tomorrow. The standard source is non-exponential discounting: a reward t units of time ahead is weighted by δ(t), and unless δ is exponential the relative weight of two future dates changes as time passes. Hyperbolic and pseudo-exponential discount…
Prophet Secretary Through Blind Strategies 2: No Stopping Strategy Can Guarantee More Than √3 − 1 of the Prophet's Expected Maximum in Random OrderResearch Paper
In a prophet inequality a gambler sees the realizations of independent nonnegative random variables one at a time and must decide irrevocably, at each step, whether to stop and keep the current value. Her performance is compared with that of a prophet who sees everything in advance and takes the maximum. The ratio between the two is the standard benchmark…
Strict Constraint Qualifications and Sequential Optimality Conditions for Constrained Optimization II: AGP-Regularity Is the Weakest Strict Constraint Qualification for AGPResearch Paper
Algorithms for smooth constrained optimization stop when an approximate optimality test passes. The tests used in practice are sequential optimality conditions: properties of a sequence of iterates xk→x∗ rather than of the limit alone. Every local minimizer satisfies them, with or without a constraint qualification, which makes them natural stopping…
On the Convergence of Decomposition Methods for Multistage Stochastic Convex Programs 2: Under τ-Admissible Random Node Selection, Cuts Become Exact Almost Surely at Every Tree NodeResearch Paper
Stochastic dual dynamic programming (SDDP) and its relatives are the standard algorithms for multistage stochastic programs: hydro-thermal scheduling, energy storage and long-horizon capacity planning are solved with them in industry. They approximate each future cost function from below by a maximum of affine cuts, compute new cuts only at a few randomly…
Strict Constraint Qualifications and Sequential Optimality Conditions for Constrained Optimization I: MFCQ or a Full Active-Gradient Cone Is the Weakest Strict CQ for Scaled-AKKTResearch Paper
Practical algorithms for nonlinear programming do not stop at an exact Karush–Kuhn–Tucker (KKT) point; they stop when an approximate stationarity test passes. Sequential optimality conditions formalize what such tests certify: they are properties of a feasible point x∗ phrased through sequences xk→x∗ and multiplier estimates, and every local…
Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation 2: SONATA with Push-Sum Converges R-Linearly over Time-Varying Directed GraphsResearch Paper
In distributed optimization a network of m agents minimizes a sum of private functions while each agent talks only to its neighbours. Applications include federated and decentralized learning, sensor networks and multi-robot systems, where the data cannot be pooled at one site. Many of these networks are directed (communication links are one-way, for…
Quadratic Matrix Inequalities with Applications to Data-Based Control II: Matrix Finsler's Lemma — Z⁰ᵣ(N) ⊆ Zᵣ(M) iff M − αN ⪰ 0 for Some α ≥ 0Research Paper
Finsler's lemma (P. Finsler, 1937) states that for symmetric matrices M,N∈Sn, the quadratic form x⊤Mx is positive on every nonzero x with x⊤Nx=0 if and only if M−αN>0 for some real α. Together with the S-lemma of Yakubovich it is one of the basic tools for converting a statement about all vectors satisfying a quadratic…
On Solving Multistage Stochastic Programs with Coherent Risk Measures: The Inner-Approximation Policy's Nested Risk-Adjusted Cost Is at Most the Upper Bound yResearch Paper
Multistage stochastic linear programs model decisions taken over time under uncertainty: reservoir releases in hydro-thermal scheduling, production and inventory plans, capacity expansion. Their standard solution method, stochastic dual dynamic programming (SDDP, Pereira and Pinto 1991), approximates each stage's cost-to-go function from below by cutting…
Inf-Convolution, Optimal Allocations, and Model Uncertainty for Tail Risk Measures IV: The Comonotonic Inf-Convolution of Tail Risk Measures Is a Tail Risk Measure with the Maximal Tail ParameterResearch Paper
A risk sharing problem distributes an aggregate random loss X among n agents, each of whom evaluates its share with a risk measure ρi. The smallest achievable aggregate risk is the inf-convolution□i=1nρi(X), and allocations that attain it are optimal. In insurance and in regulated banking the allocation is often required to be comonotonic:…
Inf-Convolution, Optimal Allocations, and Model Uncertainty for Tail Risk Measures III: The Inf-Convolution of Tail Risk Measures Is a Tail Risk Measure with the Summed Tail ParameterResearch Paper
A risk measure assigns a number, typically a capital requirement, to a random financial loss. When a total loss X is shared among n agents, each judging its share by its own risk measure ρi, the smallest achievable aggregate risk is the inf-convolution
Online Stochastic Matching: New Algorithms with Better Bounds 1: Every Random-Lists Algorithm Has ALG/OPT ≥ E[ALG]/E[OPT] − 2ε/(c+ε) with Probability at Least 1 − 2exp(−2nε²)Research Paper
Online bipartite matching with stochastic arrivals models the assignment of display-advertising impressions to advertisers: requests arrive one at a time, each must be assigned irrevocably on arrival or dropped, and the arrival sequence is random rather than adversarial. Since Feldman, Mehta, Mirrokni and Muthukrishnan beat the 1−1/e barrier in the i.i.d.…
Product Price, Quality and Service Decisions under Consumer Choice Models VI: Consumer Surplus Rises as the Firm Also Controls Service Duration, and Again as It Also Controls QualityResearch Paper
A firm that sells differentiated products sets more than prices. It chooses quality levels (features, materials, reliability) and the ancillary services that come free with a product, such as a factory warranty or free maintenance for a fixed period. Wang, Ke and Cui (SSRN 3766191; Manufacturing & Service Operations Management, 2022, doi:10.1287/msom.2020.09…
Product Price, Quality and Service Decisions under Consumer Choice Models II: The Oligopoly Has a Unique Nash Equilibrium, with Monopoly Qualities and Service Durations and Lower PricesResearch Paper
Firms that sell durable goods set three things at once: a price, a quality level, and the length of an ancillary service that comes free with the product, such as a warranty. Wang, Ke and Cui (SSRN 3766191; Manufacturing & Service Operations Management, 2022, doi:10.1287/msom.2020.0947) study these joint decisions under multinomial logit (MNL) demand. For a…
Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation 1: SONATA Converges R-Linearly over Undirected Graphs for Small Step SizesResearch Paper
In distributed optimization, m agents connected by a communication network jointly minimize the average of their private losses, exchanging vectors only with their neighbours. This is the computational model of decentralized machine learning (data held by many machines, no central server), of sensor networks and of multi-agent control. A central family of…
Inf-Convolution, Optimal Allocations, and Model Uncertainty for Tail Risk Measures II: The Inf-Convolution of a VaR and a Monetary Tail Risk Measure, Its Optimal Allocation and Its Tail ParameterResearch Paper
Banks and insurers hold capital against the risk of their positions, and regulators compute that capital with a risk measure, a functional that maps a random loss to a number. The two standard ones are the Value-at-Risk (VaR), a quantile of the loss, and the Expected Shortfall, an average of the upper quantiles (BCBS 2019). Both look only at the upper tail…