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.
Notes on Partial Differential Equations II: The Newtonian Potential and Hölder Estimates for Poisson's EquationTextbook
Poisson's equation−Δu=f is the model elliptic partial differential equation. It describes the electrostatic potential of a charge density, the gravitational potential of a mass density, and the steady temperature of a body with internal heat sources. Its solution on the whole space by convolution with a point-source potential, and the fact that…
Calibrated Learning and Correlated Equilibrium II: For Almost Every Game, Limits of Calibrated Learning Are Exactly the Correlated EquilibriaResearch Paper
A correlated equilibrium (Aumann, 1974) is a joint distribution over the players' strategy profiles from which no player gains by deviating from a recommended strategy. A central question of learning in games is which equilibria repeated play of simple, myopic rules can reach. Foster and Vohra (1997) answered it for calibrated forecasting: if each player…
Discrete Convex Analysis XXI: The Exchange Axiom as Local OptimalityTextbook
Convexity on the integer lattice cannot be defined by the classical secant-line inequality alone:
a function can be midpoint-convex along every line and still admit no useful global optimality
theory, because integer points off a chosen line are invisible to it. M-convex functions,
introduced by Murota, resolve this by replacing the secant condition with an …
Star-Shaped Risk Measures 2: law-invariant star-shaped risk measures as robustified Value-at-RiskResearch Paper
Financial regulators and risk managers summarise the loss distribution of a position by a single number, the capital that must be held against it. The two standards in practice are Value-at-Risk (VaR), a quantile of the loss, and expected shortfall (ES), an average of the upper quantiles; ES is the standard of the Basel framework. Both depend on the…
Notes on Partial Differential Equations I: Mean Values, Maximum Principles and Analyticity of Harmonic FunctionsTextbook
Laplace's equationΔu=0 is the prototype of an elliptic partial differential equation. Its solutions, the harmonic functions, describe equilibrium states in potential theory (gravitation, electrostatics, steady heat flow), are the real and imaginary parts of holomorphic functions in the plane, and are the stationary states of Brownian motion. Many…
Star-Shaped Risk Measures 1: star-shaped risk measures are the minima of convex risk measuresResearch Paper
A risk measure turns the random loss of a financial position into a single number: the amount of capital a regulator or a risk manager requires to hold the position. Two families of risk measures dominate practice and theory. Value-at-Risk (VaR), a quantile of the loss distribution, is used in banking and insurance regulation; it is positively homogeneous…
Discrete Convex Analysis VI: Quasi M-Convex Functions and the Quasi-Proximity TheoremTextbook
Convexity is normally defined additively — a function's value at a mixture is bounded by the
mixture of its values — but many of the properties that make convexity useful in optimization
(a local minimum is global, level sets are well-behaved) survive under a much weaker, purely
ordinal notion: quasi-convexity, which compares function values rather than…
Markov Decision Processes XV: Optimal Play in Red-and-Black and the Gittins IndexTextbook
Chapter 7's abstract machinery — contracting Markov Decision Models, the Structure Theorem, value
iteration with an explicit convergence rate — earns its keep by solving concrete problems.
Section 7.6 works through four kinds of application: a return to the classical cash-balance
inventory problem, now over an infinite horizon; the "red-and-black" gambling…
Discrete Convex Analysis V: The M-Optimality Criterion and the Proximity TheoremTextbook
Scaling algorithms are one of the standard techniques for solving discrete optimization
problems efficiently: instead of searching a huge integer domain directly, an algorithm first
solves a coarsened version of the problem — checking optimality only against neighbors reached
by a large step size α — and then refines the resulting approximate solution…
Existence of an Equilibrium for a Competitive Economy II: Equilibrium Exists When Every Consumer Can Supply Productive LaborResearch Paper
A competitive equilibrium is a list of production plans, consumption plans and prices at which every firm maximizes profit, every consumer maximizes utility within the budget, and no market has excess demand. Whether such prices exist at all is the consistency question behind general equilibrium theory, the welfare theorems, and applied equilibrium models…
Discrete Convex Analysis XIX: Discrete Separation for M-Convex SetsTextbook
Submodular set functions are the combinatorial stand-in for convexity: a function
ρ:2V→R on the subsets of a finite ground set V is submodular if
ρ(X)+ρ(Y)≥ρ(X∪Y)+ρ(X∩Y), and this single diminishing-returns
inequality drives an enormous range of combinatorial optimization — matroid rank functions,
graph cut…
Discrete Convex Analysis XVIII: Integral Convexity of Minimizer SetsTextbook
A classical convex function's global minimality is equivalent to its local minimality — the
single fact that makes convex optimization tractable, since checking a small neighborhood
suffices to certify a global guarantee. The discrete analogue is not automatic: a function on
the integer lattice can fail to have any well-behaved "local" notion at all, and…
Discrete Convex Analysis XVII: Fenchel Duality and Linear-Programming IntegralityTextbook
Duality is the organizing principle of convex optimization: a minimization problem's optimal
value equals a maximization problem's optimal value, and this coincidence, rather than being a
lucky accident, follows from a separating-hyperplane argument that applies whenever the two
problems' feasible regions are shaped compatibly enough. Werner Fenchel…
Markov Decision Processes VII: Consumption-Investment Problems and Regime SwitchingTextbook
Real investors do not merely accumulate wealth for a single terminal payoff; they consume along
the way, and the market they invest in is rarely a single fixed statistical regime for years at
a time — bull and bear markets, business cycles, and volatility regimes shift the distribution
of returns. Bäuerle and Rieder's §4.3 extends the terminal-wealth theory…
Maximizing Non-Monotone Submodular Functions V: Beating 1/2 for Symmetric Functions Requires Exponentially Many Value QueriesResearch Paper
Maximizing a nonnegative submodular set function without constraints contains Max Cut, Max Directed Cut and facility-location problems as special cases. In the value-oracle model an algorithm knows nothing about the function except the values f(S) of the sets S it queries, and it is judged by the number of queries it makes. Feige, Mirrokni and Vondrák (SIAM…
Lifts of Convex Sets and Cone Factorizations II: Antichain and Face-Count Lower Bounds on the Nonnegative Rank of a PolytopeResearch Paper
Many polytopes that arise in combinatorial optimization, such as the matching, cut, stable set and travelling salesman polytopes, have exponentially many facets, yet some of them can be written as the linear projection of a polyhedron with far fewer facets. The smallest number of facets of such a lift decides whether the polytope admits a compact…
Maximizing Non-Monotone Submodular Functions IV: Smooth Local Search Achieves 2/5 of the OptimumResearch Paper
Many optimization problems ask for a subset of a finite ground set that maximizes a submodular function, a set function with diminishing marginal returns. Max Cut and Max Directed Cut in graphs, facility location with fixed costs, and the maximization of mutual information or entropy of a subset of random variables are all of this form. Unlike the monotone…
On Polyhedral Approximations of the Second-Order Cone II: A Lower Bound on the Size of Polyhedral ApproximationsResearch Paper
A conic quadratic program minimizes a linear objective subject to constraints of the form ∥Aℓx−bℓ∥2≤cℓTx−dℓ. Interior-point methods solve such programs in polynomial time, but around 2000 the available solvers handled far smaller instances than linear programming codes did. Ben-Tal and Nemirovski (Math. Oper. Res. 26(2), 2001) asked…
Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix IV: Sample Bound for Hutchinson's Trace EstimatorResearch Paper
Many computations need the trace of a matrix A that is never formed explicitly and can only be applied to vectors: the trace of a matrix function such as trace(A−1) or logdetA=trace(logA) in statistics and lattice QCD, the Frobenius norm ∥B∥F2=trace(BTB) of an operator, or the number of triangles of a graph. The…
Markov Decision Processes II: Existence of Optimal Policies under Compactness and ContinuityTextbook
The finite-horizon theory of chunk 02a-model-bellman-equation (Bäuerle and Rieder's Theorem
2.3.8, the Structure Theorem) reduces the existence of an optimal policy and the validity of the
Bellman equation to a single abstract hypothesis: the Structure Assumption (SAN), the existence
of function classes IMn and decision-rule classes Δn closed…
Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix II: Exact Rank of a Projection Matrix from the Gaussian Trace EstimatorResearch Paper
Many matrices in scientific computing are available only implicitly: one can multiply a vector by A, for instance by solving a linear system or applying a matrix function, but the entries of A are never formed. Quantities such as the trace must then be estimated from a small number of matrix–vector products. Randomized trace estimators do exactly this: draw…
Monotonic Solutions of Cooperative Games 1: For Five or More Players No Core Allocation Rule Is Coalitionally MonotonicResearch Paper
Cooperative games model the division of a jointly produced surplus, or a jointly incurred cost, among the participants of an enterprise: towns sharing a water supply system, divisions of a firm sharing overhead, members of a consortium sharing the savings of joint investment. In such applications allocations are rarely fixed once and for all. Costs and…
Processing Networks XI: Maximal Stability of Workload-Weighted Task AllocationTextbook
Large-scale data-intensive computing splits a job into many small "map tasks," each of which must
be assigned to one of thousands of general-purpose servers in a data center — the MapReduce
paradigm introduced by Dean and Ghemawat (2008). Because a task's input data is stored on only a
few of those servers, routing it to a server that already holds its data…
Optimal Policy for a Multi-Product, Dynamic, Nonstationary Inventory Problem: The Base Stock Ordering Policy Is OptimalResearch Paper
An inventory manager who stocks many products, faces random demand and pays ordering, holding and shortage costs must decide each period how much of each product to order. In general the optimal decision depends on the whole state and is found by solving a dynamic programme, which becomes impractical as the number of products grows. Myopic (or base stock)…
Processing Networks X: Maximal Stability of Proportionally Fair ControlTextbook
Mission IX (09-proportional-fairness-core) formalized proportional fairness (PF) as a control
policy and proved the technical core of its stability theory: under a load condition, the PF
fluid model is stable (Theorem 10.5), via an entropy Lyapunov function that is genuinely not
Lipschitz continuous — a departure from every other stability argument in J. G.…