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.
Approximate Markov-Nash Equilibria for Discrete-Time Risk-Sensitive Mean-Field Games 1: A Risk-Sensitive Mean-Field Game with Compact Actions and Weakly Continuous Kernel Has a Mean-Field EquilibriumResearch Paper
Mean-field games describe large populations of identical agents who interact only through the distribution of their states. Each agent solves a stochastic control problem in which the population appears through a deterministic flow of distributions, and an equilibrium requires that this flow coincide with the distribution the agents generate themselves. The…
A Case Study on Stochastic Games on Large Graphs in Mean Field and Sparse Regimes II: Large-Graph Limits of the Equilibrium Through the Laplacian Eigenvalue DistributionResearch Paper
Mean field games describe large populations of agents who interact symmetrically: every agent sees the same average of all the others. Many populations interact instead along a network, where each agent responds only to its neighbours. Lacker and Soret (arXiv:2005.14102v2, 2021; Math. Oper. Res. 2022) study a linear-quadratic stochastic differential game on…
A Case Study on Stochastic Games on Large Graphs in Mean Field and Sparse Regimes III: The Mean Field Game Control Is an ε-Nash Equilibrium on Any Finite Graph, With ε_v ∝ deg(v)^(-1/2)Research Paper
Mean field games (MFGs) describe the limit of symmetric stochastic differential games as the number of players tends to infinity, when every player interacts with the empirical distribution of all the others. Their main practical use is the converse direction: an equilibrium of the limiting game supplies a simple, decentralized control that is an approximate…
Stability Results on the Circumference of a Graph 1: A 2-Connected Graph with More Than (⌊c/2⌋−1)(n−c) Edges Off a Longest Cycle of Length c ≥ 10 Lies in W_{n,⌊c/2⌋,c} or (c Odd) in X_{n,c} ∪ Y_{n,c}Research Paper
The circumferencec(G) of a graph G is the length of a longest cycle. Extremal graph theory asks how many edges force a long cycle. The Erdős–Gallai theorem (1959) states that every n-vertex graph has at most c(G)(n−1)/2 edges. Bondy (1971) strengthened it by counting only the edges near a longest cycle: if C is a longest cycle of length c, the number of…
DC Programming and DCA: Thirty Years of Developments: For f = g − h with g, h ∈ Γ₀(ℝⁿ), at x ∈ ri(dom g) ∩ ri(dom h) d-Stationarity of f Is Equivalent to Strong Criticality ∅ ≠ ∂h(x) ⊂ ∂g(x)Research Paper
DC programming is the minimization of a function f=g−h that is a difference of two convex functions. The class contains every C2 function on a compact convex set and most nonconvex models of sparse learning, clustering, combinatorial relaxations and robust optimization, and its standard method, the DC Algorithm (DCA), replaces h by its affine minorant…
Open-Loop and Closed-Loop Solvabilities for Stochastic Linear Quadratic Optimal Control Problems 1: The Cost Is Uniformly Convex iff the Riccati Equation Has a Strongly Regular SolutionResearch Paper
The stochastic linear quadratic (LQ) optimal control problem asks to steer a linear stochastic differential equation by a control so as to minimize a quadratic cost. It is the basic model of stochastic control: Wonham studied it in 1968 (Wonham 1968), and it is the model on which feedback design, mean-field control and LQ differential games are built (Yong–Z…
Conformal Weldings of Random Surfaces: SLE and the Quantum Gravity Zipper 1: Reverse SLE_κ/GFF Coupling — Zipping Up a Free Boundary GFF by a Reverse Loewner Flow Preserves Its LawResearch Paper
Liouville quantum gravity describes random surfaces whose area measure is formally eγh(z)dz, where h is a Gaussian free field (GFF). Schramm–Loewner evolution (SLEκ) describes random fractal curves that arise as scaling limits of interfaces in critical lattice models. Sheffield's paper Conformal weldings of random surfaces: SLE and the…
On Well-Posedness of Forward–Backward SDEs—A Unified Approach 1: Under Cases I–III the FBSDE Has a Decoupling Field with Bounded Difference Quotients and a Unique L² Solution on [0, T]Research Paper
A forward–backward stochastic differential equation (FBSDE) couples a forward SDE, solved from an initial state, with a backward SDE, solved from a terminal condition that depends on the forward state. Such systems arise from the stochastic maximum principle, from quasilinear parabolic PDEs through Feynman–Kac formulas, and in mathematical finance. Whenever…
Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization 2: A Symmetric Quartic Is Nonnegative iff Each Restriction f^ω to a 2-Partition ω Is a Sum of SquaresResearch Paper
Deciding whether a real polynomial is non-negative on Rn is NP-hard already for quartics, and the standard computational substitute is to ask whether it is a sum of squares (SOS) of polynomials, which is a semidefinite feasibility problem. The two notions agree only in three cases, determined by Hilbert in 1888: univariate polynomials, quadratic…
Isotropic Gaussian Random Fields on the Sphere: Regularity, Fast Simulation and Stochastic Partial Differential Equations III: Karhunen–Loève Truncation Error ≤ κ^{−β} a.s. for β < (α−2)/2Research Paper
An isotropic Gaussian random field is a spatial random quantity whose probability law is unchanged when the sphere is rotated. Such fields model spatially distributed uncertainty when no direction is preferred. The question in this mission is concrete: if a field is simulated by retaining only finitely many spherical harmonic frequencies, how rapidly does…
Algorithms for #BIS-Hard Problems on Expander Graphs 2: On Bipartite α-Expanders, the High-Fugacity Hard-Core Partition Function Reduces to Two Kotecký–Preiss Polymer ModelsResearch Paper
The hard-core model on a finite graph G at fugacityλ>0 weights each independent set I of G by λ∣I∣. Its normalizing constant, the independence polynomialZG(λ), is a basic object of statistical physics (a lattice gas with hard-core exclusion) and of combinatorics (ZG(1) counts independent sets).
Fast Rates for Contextual Linear Optimization 1: Under the Margin Condition, ERM over a Policy Class of Natarajan Dimension η Has Regret O(B(η log(|Z∠|+1) log(n+1)/n)^((1+α)/(2+α)))Research Paper
Many operational decisions are linear programs whose cost vector is uncertain but partly predictable: shortest-path routing with uncertain travel times, portfolio choice with uncertain returns, shipment planning with uncertain costs. Before deciding, one observes features X (traffic, market signals) correlated with the costs Y. Contextual linear optimization…
Algorithms for #BIS-Hard Problems on Expander Graphs 1: On α-Expanders of Maximum Degree Δ, the Low-Temperature Potts Partition Function Reduces to a Kotecký–Preiss Polymer ModelResearch Paper
The ferromagnetic Potts model assigns a larger weight to a coloring when more adjacent vertices have the same color. Computing its partition function is an approximate counting problem with connections to statistical physics and counting complexity. For three or more colors, Goldberg and Jerrum established #BIS-hardness of approximation on general graphs,…
Isotropic Gaussian Random Fields on the Sphere: Regularity, Fast Simulation and Stochastic Partial Differential Equations II: Σ A_ℓ ℓ^{1+β} < ∞ Gives a Continuous Modification, γ-Hölder for γ < β/2Research Paper
A random field on a sphere assigns a random value to every direction. Such fields appear when the underlying data are directional, including spherical models in spatial statistics and geophysics. The covariance of an isotropic field can be recorded by an angular power spectrum: one nonnegative number for each spherical harmonic degree. This changes the…
Isotropic Gaussian Random Fields on the Sphere: Regularity, Fast Simulation and Stochastic Partial Differential Equations IV: Heat-Equation Spectral Truncation Error ≤ κ^{−β} a.s. for β < α/2Research Paper
Stochastic partial differential equations on the sphere model quantities that live on the surface of the Earth or of the sky and are perturbed by spatially correlated noise: temperature anomalies, geophysical fields, fluctuations of the cosmic microwave background. The simplest such model is the stochastic heat equation on the unit sphere S2 with…
A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem: The Asymmetric Held–Karp Relaxation Has Integrality Gap at Most 319Research Paper
The asymmetric traveling salesman problem (ATSP) asks for a shortest closed walk through every vertex of a directed graph whose edge weights need not be symmetric. It models routing with one-way streets, scheduling with sequence-dependent setup times, and many other problems in which the cost of going from u to v differs from the cost of going back. Its…
Affine Volterra Processes 3: Global Solutions with Nonpositive Real Part of the Square-Root Riccati–Volterra EquationResearch Paper
The Volterra square-root model describes a nonnegative, time-dependent state whose present value depends on a weighted history. Ordinary square-root diffusions use a constant kernel and have a Markov state; replacing that kernel by a function of elapsed time allows persistent or singular memory. This matters for the transform formulas used to characterize…
Generalization Properties of Learning with Random Features: Ridge Regression with c₀√n·log(108κ²√n/δ) Random Features Has Excess Risk at Most c₁·log²(18/δ)/√n with Probability 1 − δResearch Paper
Kernel ridge regression is a standard nonparametric estimator with optimal statistical guarantees, but it needs the n×n kernel matrix of the data: roughly O(n3) time and O(n2) memory. Random features (Rahimi and Recht, NeurIPS 2007) replace the kernel by an average over M randomly sampled feature functions, turning the problem into ridge regression…
Stochastic Model-Based Minimization of Weakly Convex Functions 3: The Projected Stochastic Subgradient Method Is an Approximate Descent Method on the Moreau Envelope for Any StepsizesResearch Paper
The projected stochastic subgradient method minimizes an expected loss f(x)=Eξ∼P[f(x,ξ)] over a closed convex set X: it samples a data point, steps against a sampled subgradient, and projects back onto X. For convex f its sample complexity has been known for decades, and for smooth nonconvex f the stochastic gradient method needs …
Spectral Gaps for a Metropolis–Hastings Algorithm in Infinite Dimensions II: The pCN Algorithm Has a Wasserstein Spectral Gap Uniform in the Dimension When the Potential Is Locally LipschitzResearch Paper
Bayesian inverse problems for functions — the initial condition of a PDE, a permeability field, a diffusion coefficient — lead to posterior measures μ on an infinite-dimensional Hilbert space H, given by a density exp(−Φ) with respect to a Gaussian prior γ. In practice μ is sampled by Markov chain Monte Carlo on an m-dimensional discretisation …
Affine Volterra Processes 2: The Exponential-Affine Transform Formula via the Riccati–Volterra EquationResearch Paper
Many stochastic models have a present state that depends on a weighted history of past drift and noise. A stochastic Volterra equation captures this dependence through a kernel K: a recent increment and an older increment can enter the current state with different weights. Classical affine diffusions arise from the special constant kernel K=I. For those…
Stochastic Model-Based Minimization of Weakly Convex Functions 4: Under Convexity, Stochastic Model-Based Minimization Reaches Expected Function Gap (½‖x₀−x*‖² + L²γ²)/(γ√(T+1))Research Paper
Many problems in statistical learning and signal processing take the form of minimizing an expectation f(x)=Eξ[F(x,ξ)] plus a regularizer or constraint r(x), where the only access to f is through samples ξ∼P. The classical tool is the stochastic (proximal) subgradient method, which replaces f at the current point by a random linear…
Affine Volterra Processes 1: Nonnegative Weak Solutions of Stochastic Volterra Equations with Resolvent-Monotone KernelsResearch Paper
Many stochastic models use a process whose response to a disturbance depends on the time elapsed since that disturbance. An ordinary stochastic differential equation uses only the current state and instantaneous coefficients. A stochastic Volterra equation instead weights its past drift and noise through a convolution kernel. Such equations include the…
Stochastic Model-Based Minimization of Weakly Convex Functions 1: Stochastic One-Sided Model Methods Drive the Moreau-Envelope Gradient E‖∇φ_{1/ρ̄}(x_{t*})‖² to Zero at Rate O(1/√T)Research Paper
Many problems in statistics, signal processing and machine learning minimize an expected loss that is neither smooth nor convex: robust phase retrieval, blind deconvolution, covariance estimation with the ℓ1 loss, training of networks with ReLU activations, and composite problems h(c(x)) with convex h and smooth c. A common structural feature of these…
Generalized Turán Problems for Even Cycles 3: The Maximum Number of Six-Cycles in a Bipartite C_8-Free Graph on n Vertices Is n³ + O(n^{5/2})Research Paper
The generalized Turán numberex(n,H,F) is the largest number of copies of a graph H in an n-vertex graph containing no member of a family F. With H=K2 it is the classical Turán number; the systematic study of general H began with Alon and Shikhelman (2016), and cycles are its most studied case: Bollobás and Győri bounded …