Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

The OR Formalization Drive

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.

4812 missions

Missions

701–725 of 4812
Open1285Completed3527All4812
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Adaptive Cubic Regularisation Methods for Unconstrained Optimization. Part II: Worst-Case Function- and Derivative-Evaluation Complexity 3: ARC(S) Reaches −λ_min(QᵀBQ) ≤ ε in O(ε^(−3)) IterationsResearch Paper

Unconstrained minimization of a smooth nonconvex function f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R is the core subproblem of most nonlinear optimization software. Methods that only drive the gradient to zero may stall at saddle points, so a second-order guarantee (approximately nonnegative curvature) is the natural target for nonconvex problems. Worst-case evaluation…

15 thms4 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Adaptive Cubic Regularisation Methods for Unconstrained Optimization. Part II: Worst-Case Function- and Derivative-Evaluation Complexity 2: ARC(S) Reaches ‖g‖ ≤ ε in O(ε^(−3/2)) IterationsResearch Paper

Second-order methods for smooth nonconvex minimization are used in practice because they converge in far fewer iterations than gradient descent, yet for a long time their worst-case guarantee from an arbitrary starting point was no better than that of steepest descent. Nesterov and Polyak (Math. Program. 108, 2006) showed that adding a cubic term to…

13 thms4 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems 2: Newton's Method Can Need ε^(−2+τ) Iterations to Reach ‖g‖ ≤ εResearch Paper

Newton's method is the reference second-order method for unconstrained minimization of a smooth function f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R. Near a nondegenerate local minimizer it converges quadratically, and in practice it often works well far from one. Its global behaviour on nonconvex functions is a different matter. The pure method may fail outright when the…

13 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

Information Relaxations and Duality in Stochastic Dynamic Programs 1: The Ideal Penalty Is Dual Optimal for Every Information RelaxationResearch Paper

Most stochastic dynamic programs that arise in operations research are too large to solve exactly. In practice one computes a heuristic policy and estimates its expected reward by simulation, which gives a lower bound on the optimal value. To know whether the heuristic is good enough one also needs an upper bound. Brown, Smith and Sun (Oper. Res. 2010) give…

13 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Scheduling Problems with Two Competing Agents 1: Placing Last an Eligible B-Job, Else a Least-Cost A-Job, Minimizes One Agent's Maximum Cost Under a Bound on the Other'sResearch Paper

Classical scheduling theory optimizes one objective for one decision maker. Many shop floors are shared: two departments, two customers or two firms submit jobs to the same machine, and each cares only about how its own jobs are treated. Agnetis, Mirchandani, Pacciarelli and Pacifici, Scheduling Problems with Two Competing Agents (Operations Research 52(2),…

18 thms4 active users
Algorithmic Game TheoryDifferential GeometryOperations Research·Captain: mikedeng1

Inefficiency of Nash Equilibria: For an Open Dense Set of C² Payoffs, Nash Equilibria Are Finite, an Efficient One Has a Player at a Vertex, and a Strong One Has at Most One Player off a VertexResearch Paper

That noncooperative play usually wastes something is part of the folklore of game theory, with the Prisoner's Dilemma as its emblem: each player's best reply leads to an outcome that both would trade for another. Pradeep Dubey's paper turns this folklore into a theorem about smooth games. For games whose payoffs are twice continuously differentiable, and…

13 thms4 active usersReviewed
🏆Completed
Control TheoryNumerical AnalysisOptimization·Captain: mikedeng1

A Real-Time Iteration Scheme for Nonlinear Optimization in Optimal Feedback Control: The Real-Time Iterates Contract and Approach the Exact Stationary Points GeometricallyResearch Paper

Nonlinear model predictive control (NMPC) computes a feedback law by solving, at every sampling time, an optimal control problem that starts from the currently measured state. The control actually applied is the first control of that problem's solution. When the dynamics are fast relative to the time an optimizer needs, solving each problem to convergence…

10 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

Twin-width I: Tractable FO Model Checking 1: Every Graph with Boolean-width k Has Twin-width at Most 2^(k+1) − 1Research Paper

Twin-width was introduced by Bonnet, Kim, Thomassé and Watrigant (J. ACM 69(1), Article 3, 2021) as a graph parameter under which first-order model checking is fixed-parameter tractable when a contraction sequence is given. Its interest lies in the classes it covers at once: planar and, more generally, KtK_tKt​-minor-free graphs, bounded-degree grids, unit ball…

6 thms4 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningProbability·Captain: mikedeng1

A Tutorial on Thompson Sampling II: Under Thompson Sampling, Per-Period Expected Regret Splits into a Pessimism Term and a Width Term for Any History-Determined U_tResearch Paper

An online decision maker repeatedly chooses an action, observes an outcome, and receives a reward. In a Bayesian model, an unknown parameter controls the outcomes, and the decision maker begins with a prior distribution for that parameter. Thompson sampling acts by drawing a parameter from its current posterior distribution and choosing an action that would…

7 thms4 active users
🏆Completed
Markov ChainNumerical AnalysisOptimal Transport+1·Captain: mikedeng1

Coupling and Convergence for Hamiltonian Monte Carlo 1: Exact HMC Contracts the Concave Kantorovich Distance W_ρ at Rate c = (1/10)·min(1, ½KT²(1+ℛ/T)e^{−ℛ/(2T)})·e^{−2ℛ/T}Research Paper

Hamiltonian Monte Carlo (HMC) is one of the most widely used Markov chain Monte Carlo methods for sampling from a probability density μ(dx)∝e−U(x) dx\mu(dx)\propto e^{-U(x)}\,dxμ(dx)∝e−U(x)dx on Rd\mathbb R^dRd. It is the default sampler of probabilistic programming systems such as Stan, and it is used throughout Bayesian statistics, molecular dynamics and machine learning. In practice the…

13 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOptimal Transport+1·Captain: mikedeng1

Computational Optimal Transport V: A Feasible Pair of Kantorovich Potentials Is Optimal or Strictly Improves Along a Direction (1_S, −1_S′)Textbook

The discrete optimal transport problem between two histograms is a linear program, and much of the algorithmic theory of optimal transport is the theory of solving that linear program well. Chapter 3 of Peyré and Cuturi's Computational Optimal Transport (Foundations and Trends in Machine Learning, 2019) surveys the classical combinatorial solvers: the…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

Turán Graphs with Bounded Matching Number 1: An n-Vertex Graph with Clique Number at Most k and Matching Number at Most s Has at Most max{t(2s+1,k), g(n,k,s)} Edges, and This Is AttainedResearch Paper

Two of the oldest results in extremal graph theory bound the number of edges of a graph under a single structural restriction. Turán's theorem (Turán 1941) determines the maximum number of edges t(n,k)t(n,k)t(n,k) of an nnn-vertex graph with no complete subgraph on k+1k+1k+1 vertices. The Erdős–Gallai theorem (Erdős and Gallai 1959) determines the maximum number of edges of an …

12 thms4 active usersReviewed
🏆Completed
AlgebraCombinatoricsComplexity Theory+1·Captain: mikedeng1

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy 1: Folded Symmetric PCSPs Avoiding Parity, Majority and Alternating-Threshold Have Only C-Fixing PolymorphismsResearch Paper

A constraint satisfaction problem (CSP) asks whether variables can be assigned values so that every constraint, drawn from a fixed finite set of relations, holds. The algebraic approach to CSPs explains their complexity through polymorphisms, the operations that preserve all constraint relations; this programme culminated in the CSP dichotomy theorem of…

35 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization 3: The Big-M Relaxation Is at Least as Strong as PR(∞) for M ≤ ½√(λ0/λ2) and at Most as Strong for M ≥ √(λ0/λ2)Research Paper

Best subset selection with a ridge term, the ℓ0ℓ2\ell_0\ell_2ℓ0​ℓ2​-regularized least squares problem

20 thms4 active users
🏆Completed
AlgebraComplexity TheoryLinear Optimization+1·Captain: mikedeng1

Algebraic Approach to Promise Constraint Satisfaction 3: BLP Solves PCSP(A, B) iff Pol(A, B) Has Symmetric Functions of All Arities iff Q_conv Maps to Pol(A, B)Research Paper

A promise constraint satisfaction problem PCSP(A,B)\mathrm{PCSP}(\mathbf A,\mathbf B)PCSP(A,B) is given by two finite relational structures with a homomorphism A→B\mathbf A\to\mathbf BA→B. An instance is a finite structure I\mathbf II over the same signature, promised to map to A\mathbf AA; the task is to find a homomorphism to the weaker structure B\mathbf BB (or, in the decision…

17 thms4 active usersReviewed
🏆Completed
Information TheoryMachine LearningProbability+1·Captain: mikedeng1

Information-Theoretic Analysis of Generalization Capability of Learning Algorithms III: The Gibbs Algorithm Has Excess Risk at Most (1/β)log(1/Q(wₒ)) + β/(2n) (Corollary 2)Research Paper

Statistical learning algorithms fit hypotheses to data that are available during training, while their performance is judged on new data. A rule that minimizes training loss can fit peculiarities of the sample, so its training loss and population loss need not agree. Xu and Raginsky study this difference through information quantities associated with the…

10 thms4 active usersReviewed
🏆Completed
AlgebraCombinatoricsComplexity Theory+1·Captain: mikedeng1

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy 3: Pol(Γ) ⊆ Pol(Γ′) Implies Γ′ Is ppp-Definable from ΓResearch Paper

A constraint satisfaction problem (CSP) asks for an assignment of values from a finite domain DDD to variables so that every constraint, a tuple of variables required to lie in a fixed relation, is satisfied. The algebraic theory of CSPs rests on a Galois correspondence: the complexity of CSP(Γ)\mathrm{CSP}(\Gamma)CSP(Γ) is determined by the set Pol(Γ)\mathrm{Pol}(\Gamma)Pol(Γ) of…

8 thms4 active usersReviewed
🏆Completed
AlgebraCombinatoricsDiscrete Geometry+1·Captain: mikedeng1

Generalising the Scattered Property of Subspaces 1: An h-Scattered 𝔽_q-Subspace of V(r, qⁿ) Either Defines a Subgeometry or Has Dimension at Most rn/(h + 1)Research Paper

Let VVV be an rrr-dimensional vector space over the finite field Fqn\mathbb F_{q^n}Fqn​. Viewed over the subfield Fq\mathbb F_qFq​, VVV has dimension rnrnrn, and its one-dimensional Fqn\mathbb F_{q^n}Fqn​-subspaces form the Desarguesian spread. An Fq\mathbb F_qFq​-subspace UUU of VVV is scattered if it meets every element of this spread in an Fq\mathbb F_qFq​-subspace of dimension at most one.…

6 thms4 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions IV: Lipschitz ∇g and Strongly Convex f (or Vice Versa) Make Relaxed PRS Contract LinearlyResearch Paper

Peaceman–Rachford splitting separates the minimization of a sum into two proximal computations. That matters when each summand has a tractable proximal map but the sum does not. Douglas–Rachford splitting is its half-relaxed instance, and related iterations appear in the analysis of ADMM. Davis and Yin study how regularity of the two summands changes the…

14 thms4 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisMachine Learning+2·Captain: mikedeng1

Kernel Distributionally Robust Optimization: Generalized Duality Theorem and Stochastic Approximation: The Worst-Case Risk over an RKHS Ambiguity Set Equals Its Support-Function DualResearch Paper

Distributionally robust optimization (DRO) chooses a decision θ\thetaθ that minimizes the expected loss under the worst distribution in an ambiguity set K\mathcal KK of plausible distributions, min⁡θsup⁡P∈K∫l(θ,ξ) dP(ξ)\min_\theta\sup_{P\in\mathcal K}\int l(\theta,\xi)\,dP(\xi)minθ​supP∈K​∫l(θ,ξ)dP(ξ). It sits between stochastic optimization, which trusts a single distribution, and worst-case robust…

15 thms4 active usersReviewed
🏆Completed
Information TheoryMachine LearningProbability+1·Captain: mikedeng1

Information-Theoretic Analysis of Generalization Capability of Learning Algorithms I: The Expected Generalization Error Is at Most √(2σ²I(S;W)/n) (Theorem 1)Research Paper

A learning algorithm trained on a finite sample generalizes when its empirical risk on that sample is close to its risk on fresh data. Classical guarantees come from uniform convergence over the hypothesis class (VC dimension, Rademacher complexity) or from algorithmic stability, such as uniform stability (Bousquet and Elisseeff, 2002) and on-average…

7 thms4 active usersReviewed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Quality in Supply Chain Encroachment II: Under Quality Differentiation the Direct Channel Carries the High-Quality Product, the Manufacturer Gains and the Retailer LosesResearch Paper

Manufacturers increasingly sell directly to consumers while continuing to supply independent retailers, a practice known as supply chain encroachment. The direct channel competes with the retailer for the same consumers, and the conventional advice for easing that conflict is to sell different products in the two channels. Ha, Long and Nasiry (MSOM 18(2),…

18 thms4 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods III: For Convex-Composite Problems, Subdifferential Subregularity Is Equivalent to the Prox-Linear Error BoundResearch Paper

Many optimization models minimize a smooth transformation followed by a nonsmooth penalty. A penalty may encourage sparse coefficients, restrict a feasible region, or measure deviation from observed data. Even when the penalty is convex, its composition with a nonlinear map need not be convex. This makes a standard convex optimality certificate unavailable,…

11 thms4 active usersReviewed
🏆Completed
AlgebraCombinatoricsComplexity Theory+1·Captain: mikedeng1

Algebraic Approach to Promise Constraint Satisfaction 1: A Minion Homomorphism Pol(A₁, B₁) → Pol(A₂, B₂) Exists iff (A₂, B₂) Is pp-Constructible from (A₁, B₁)Research Paper

A promise constraint satisfaction problem PCSP(A,B)\mathrm{PCSP}(\mathbf A,\mathbf B)PCSP(A,B) is given by two finite relational structures with a homomorphism A→B\mathbf A\to\mathbf BA→B. An instance is a third structure I\mathbf II, and the task is to answer yes if I→A\mathbf I\to\mathbf AI→A and no if I↛B\mathbf I\not\to\mathbf BI→B; the promise is that one of the two holds. Approximate…

12 thms4 active usersReviewed
Operations ResearchOptimal TransportOptimization+1·Captain: mikedeng1

On a Problem of Optimal Transport Under Marginal Martingale Constraints 3: Between Probability Measures in Convex Order There Is Exactly One Left-Monotone Martingale PlanResearch Paper

In classical optimal transport on the real line, one coupling plays a distinguished role: the monotone (Hoeffding–Fréchet) coupling, which sends the qqq-quantile of the first marginal to the qqq-quantile of the second. It is canonical (every initial segment of the first marginal goes as far left as possible) and it is optimal for a whole family of costs at once.

17 thms4 active usersReviewed
PreviousPage 29 of 193Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5162497
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36415412
5NINickrobbins953286155
6VEvebis25800
7FIfizzyinc321725
8SHshivm17490
9SCShuze Chen9455324
10KMkmehltretter82895261

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me