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.
Applied Combinatorics IV: Newton's Binomial Theorem and the Central Binomial ConvolutionTextbook
Generating functions are the standard device of enumerative combinatorics for turning a counting sequence into a single algebraic or analytic object: a sequence {an:n≥0} is recorded as the power series ∑n≥0anxn, and operations on series (products, powers, derivatives) become operations on the counts. Chapter 8 of Keller and Trotter's App…
Discrete Convex Analysis IX: The Discrete Conjugacy TheoremTextbook
The Legendre-Fenchel transform is the single most structurally important operation in convex
analysis: for a proper closed convex function f, its conjugate f∙(p)=supx{⟨p,x⟩−f(x)} is again proper closed convex, and the transform is an
involution — f∙∙=f. This one fact underlies duality theory across
optimization:…
Partially ordered sets model precedence: tasks that must wait for other tasks, versions that
supersede others, files nested in directories, alternatives ranked by several criteria at once.
Two questions about such a structure recur in scheduling and in the design of algorithms. How
many sequential "threads" are needed so that every item lies on a thread in…
Notes on Partial Differential Equations X: Galerkin Existence of Weak Solutions of Parabolic PDEsTextbook
Linear second-order parabolic equations such as ut+Lu=f model diffusion with advection, growth or decay, and external sources. The heat equation is the prototype. For coefficients that are only bounded and measurable, classical solutions need not exist, and the natural well-posedness theory is the L2 energy theory of weak solutions. In that theory the…
Discrete Convex Analysis VIII: Quasi L-Convex Functions and the Quasi-Proximity TheoremTextbook
Milgrom and Shannon's theory of quasi-supermodularity, developed for monotone comparative
statics in economics, showed that many of the consequences of lattice submodularity survive
under a much weaker, purely ordinal relaxation of the defining inequality. Chapter 7's final
section imports this idea into discrete convex analysis: does L-convexity's…
Notes on Partial Differential Equations VIII: Strongly Continuous Semigroups and the Lumer–Phillips TheoremTextbook
Many linear partial differential equations of evolution type — the heat equation, the Schrödinger equation, linear wave and Klein–Gordon equations, linearized reaction–diffusion and Kuramoto–Sivashinsky equations — can be written as an ordinary differential equation
Markov Decision Processes XIX: Theory of Optimal Stopping ProblemsTextbook
A gambler watching a sequence unfold has to decide, at each moment and knowing only the past,
whether to take what is on the table or wait for something better. That is the whole of optimal
stopping, and it is one of the few problems in stochastic control with a clean and completely
general answer: the value of the problem is the smallest superharmonic…
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…
Golden Ratio Algorithms for Variational Inequalities II: The Explicit Golden Ratio Algorithm Converges for Locally Lipschitz Monotone OperatorsResearch Paper
Monotone variational inequalities cover convex minimisation, convex–concave saddle-point problems, Nash equilibria of monotone games and complementarity problems, and they are the standard model for these in optimization and operations research. First-order methods for them (extragradient, forward–backward–forward, reflected and projected gradient methods)…
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…