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.

1285 open missions

Missions

1226–1250 of 1285
Open1285Completed3527All4812
Markov ChainProbabilityStochastic Systems·Captain: mikedeng1

The Two-Parameter Poisson–Dirichlet Distribution Derived from a Stable Subordinator 6: n·Y_n → (1 − α)/α Almost Surely under PD(α, θ)Research Paper

In a population divided into many species, a ranked frequency VnV_nVn​ is the fraction belonging to the nnnth most common species. The Poisson–Dirichlet distribution is a model for such random ranked frequencies. It also arises from ranked jumps of a stable subordinator, which gives the model its connection to random interval partitions. Pitman and Yor's 1997…

8 thms1 active userReviewed
Control TheoryConvex OptimizationProbability·Captain: mikedeng1

Convex Duality in Constrained Portfolio Optimization II: The Dual Problem Attains Its Infimum, So an Optimal Constrained Portfolio–Consumption Pair Exists for Every Initial CapitalResearch Paper

Portfolio decisions in continuous time must respect both market uncertainty and investment restrictions. A ban on short sales, for example, restricts the vector of wealth fractions a trader may hold at every instant. The corresponding optimal consumption and investment problem is harder than its unrestricted counterpart because a candidate portfolio…

15 thms1 active userReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Graph Minors. X. Obstructions to Tree-Decomposition III: In the θ-Grid, the Separations of Order < θ With Small E(A) Form a Tangle of Order θResearch Paper

Robertson and Seymour introduced tangles as a way to describe a region of a graph that cannot be isolated by a separation of low order. A separation divides the edges into two sides, and its order counts the vertices shared by those sides. A tangle makes a consistent choice of the side regarded as small at every order below a threshold. This turns an…

9 thms1 active userReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Graph Minors. X. Obstructions to Tree-Decomposition V: A θ-Pervasive Class of Designs Gives a Tree-Decomposition over 𝒮^{3θ−2} ∪ ℛ_{4θ−3}Research Paper

Tangles were introduced by Robertson and Seymour in Graph Minors. X (JCTB 1991) to make precise the idea of a "highly connected region" of a graph. A tangle orients every low-order separation of the graph towards one side, consistently. They are the organising notion of the later papers of the Graph Minors series, which culminate in the graph structure…

7 thms1 active userReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Graph Minors. X. Obstructions to Tree-Decomposition II: Branch-Width and Tree-Width Satisfy max(β, γ) ≤ ω + 1 ≤ max(⌊3β/2⌋, γ, 1)Research Paper

Tree-width measures how closely a graph resembles a tree. It is the central width parameter of the Graph Minors series of N. Robertson and P. D. Seymour, which proves that finite graphs are well-quasi-ordered by the minor relation, and it governs the complexity of many algorithms: problems that are NP-hard in general become solvable in linear time on graphs…

10 thms1 active userReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

Weak Limit Theorems for Stochastic Integrals and Stochastic Differential Equations: Under C2.2(i), (Xₙ, Yₙ) ⇒ (X, Y) in the Skorohod Topology Implies (Xₙ, Yₙ, ∫Xₙ dYₙ) ⇒ (X, Y, ∫X dY)Research Paper

Many approximation results in probability and operations research take the form of a sequence of discrete or jump-driven systems converging to a diffusion or another limit process. When the approximating systems are written as stochastic integral equations, Xn(t)=Xn(0)+∫0tσ(Xn(s−)) dYn(s)X_n(t) = X_n(0) + \int_0^t \sigma(X_n(s-))\,dY_n(s)Xn​(t)=Xn​(0)+∫0t​σ(Xn​(s−))dYn​(s), the key step is to show that the stochastic…

15 thms1 active userReviewed
Control TheoryConvex OptimizationProbability·Captain: mikedeng1

Convex Duality in Constrained Portfolio Optimization I: Financibility, Minimality, Dual Optimality and Parsimony of an Auxiliary Market Are Equivalent and Yield the Optimal Constrained PolicyResearch Paper

An investor in a continuous-time market chooses, at every instant, how to split wealth between a bond and ddd stocks and how fast to consume, so as to maximize expected utility of consumption and terminal wealth. Without constraints on the portfolio, this problem was solved by the martingale method: Pliska (1986), Karatzas, Lehoczky and Shreve (1987) and Cox…

21 thms1 active userReviewed
Numerical AnalysisOptimization·Captain: mikedeng1

Truncated-Newton Algorithms for Large-Scale Unconstrained Optimization 1: Truncated-Newton CG Iterates Have ‖g(x_k)‖ → 0 and Converge to Any Limit Point with Positive Definite HessianResearch Paper

Large scale unconstrained optimization often makes an exact Newton step expensive. At each iterate, Newton's method asks for a solution of a linear system involving the Hessian, and the cost of solving that system can dominate the cost of evaluating the objective. Dembo and Steihaug's 1983 truncated Newton method uses conjugate gradients to stop the linear…

8 thms1 active userReviewed
CombinatoricsDiscrete GeometryGraph Theory·Captain: mikedeng1

Diameter of Polyhedra: Limits of Abstraction 1: The Base Abstraction in Dimension n/4 with n Facets Has Diameter Ω(n²/log n)Research Paper

Whether the diameter of a polyhedron is bounded by a polynomial in its number of facets is one of the central open questions of convex geometry, and it bears directly on linear programming: the diameter of the graph of a polyhedron is a lower bound on the number of pivots of any simplex method that moves along edges. Write △u(d,n)\triangle_u(d,n)△u​(d,n) for the largest…

2 thms1 active userReviewed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Optimal Rates for the Regularized Least-Squares Algorithm III: Against Every Algorithm, a Single Distribution in P(b, c) Keeps the Expected Excess Risk above ℓ^(−cB/(cB+1)) for B > b (Theorem 3)Research Paper

Regularized least squares (RLS) in a reproducing kernel Hilbert space is a basic estimator of nonparametric regression and of kernel-based learning. Its learning rate is the speed at which the expected excess risk goes to zero as the sample size ℓ\ellℓ grows. A rate is useful only if it is known to be optimal, and optimality is a lower-bound statement about…

8 thms1 active userReviewed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Optimal Rates for the Regularized Least-Squares Algorithm II: No Learning Algorithm Converges Faster than ℓ^(−bc/(bc+1)) Uniformly over P(b, c) — the Minimax Lower Rate (Theorem 2)Research Paper

Regularized least squares (RLS), also called kernel ridge regression, is one of the standard estimators of statistical learning: given a sample of input–output pairs, it fits a function from a reproducing kernel Hilbert space by minimizing the empirical squared error plus a multiple of the squared norm. Caponnetto and De Vito (FoCM 2007) proved that, over a…

7 thms1 active userReviewed
Functional AnalysisMachine LearningProbability+1·Captain: mikedeng1

Optimal Rates for the Regularized Least-Squares Algorithm I: With λ Tuned to the Effective Dimension, Regularized Least Squares Attains the Rate ℓ^(−bc/(bc+1)) Uniformly over P(b, c) (Theorem 1)Research Paper

Regularized least squares (RLS, also called kernel ridge regression or Tikhonov regularization) is the simplest learning algorithm built on a reproducing kernel Hilbert space. Given ℓ\ellℓ examples (xi,yi)(x_i,y_i)(xi​,yi​) drawn independently from an unknown distribution ρ\rhoρ, it returns the function in a hypothesis space H\mathcal HH that minimizes the empirical squared…

9 thms1 active userReviewed
Control TheoryDynamic ProgrammingProbability·Captain: mikedeng1

Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey 5: Canonical Triplets Are Exactly the Solutions of the Coupled Optimality EquationsResearch Paper

A controlled Markov process run under the long-run average cost criterion asks for a policy minimizing the asymptotic cost per stage. When every stationary policy induces a single recurrent class, the optimal average cost is a constant and is characterized by one equation, the average cost optimality equation (ACOE). In general it is not: under some…

6 thms1 active userReviewed
Control TheoryMathematical PhysicsOptimization+3·Captain: mikedeng1

Optimization of Mean-field Spin Glasses III: The Lagrangian Value of the Stochastic Control Problem Equals the Parisi FunctionalResearch Paper

The ground-state energy of a mixed ppp-spin spin glass, OPTN=max⁡σ∈{±1}NHN(σ)/N\mathsf{OPT}_N=\max_{\sigma\in\{\pm1\}^N}H_N(\sigma)/NOPTN​=maxσ∈{±1}N​HN​(σ)/N, converges almost surely to the infimum of the Parisi functional over non-decreasing order parameters (Auffinger–Chen 2017). El Alaoui, Montanari and Sellke (arXiv:2001.00904v1) study algorithms that find near-optimal configurations. They introduce…

14 thms1 active userReviewed
Mathematical PhysicsOptimizationPartial Differential Equations+1·Captain: mikedeng1

Optimization of Mean-field Spin Glasses II: Under No Overlap Gap, the Monotone Parisi Minimizer Also Minimizes the Extended FunctionalResearch Paper

The mixed ppp-spin model is a random polynomial on the hypercube {−1,+1}N\{-1,+1\}^N{−1,+1}N: a centered Gaussian process HN(σ)H_N(\boldsymbol\sigma)HN​(σ) with covariance E{HN(σ)HN(σ′)}=Nξ(⟨σ,σ′⟩/N)\mathbb E\{H_N(\boldsymbol\sigma)H_N(\boldsymbol\sigma')\} = N\xi(\langle\boldsymbol\sigma,\boldsymbol\sigma'\rangle/N)E{HN​(σ)HN​(σ′)}=Nξ(⟨σ,σ′⟩/N). Its maximum OPTN=max⁡σHN(σ)/N\mathrm{OPT}_N = \max_{\boldsymbol\sigma} H_N(\boldsymbol\sigma)/NOPTN​=maxσ​HN​(σ)/N is a canonical…

11 thms1 active userReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

Convergence in law of the minimum of a branching random walk: The Minimum Centred at (3/2) ln n Converges to a Gumbel Law Shifted by the Derivative MartingaleResearch Paper

A branching random walk is the simplest model of a population that both reproduces and moves: every particle dies and leaves a random cloud of children displaced relative to it. Its extreme particles control the speed of travelling waves in reaction–diffusion equations (the KPP/Fisher equation), the free energy of directed polymers on trees, the cover and…

13 thms1 active userReviewed
Linear algebraNumerical AnalysisOptimization·Captain: mikedeng1

Projection-like Retractions on Matrix Manifolds IV: Within σ_r(X̄)/2 of a Rank-r Matrix, the Truncated SVD Is the Unique Nearest Matrix of Rank Exactly rResearch Paper

Optimization over sets of matrices of fixed rank comes up in low-rank matrix completion, model reduction, and the low-rank approximation of solutions of large matrix equations. A standard approach treats the constraint set as a Riemannian manifold and runs gradient or Newton-type methods on it (Absil, Mahony & Sepulchre 2008). Each iteration takes a step in…

8 thms1 active userReviewed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Dynamic Pricing Strategies with Reference Effects I: Under Loss Aversion the Steady States Form an Interval and Optimal Paths ConvergeResearch Paper

Consumers judge a price against a reference price, an internal standard formed from the prices they have seen before. A price below the reference is perceived as a gain and stimulates demand; a price above it is perceived as a loss and depresses demand. Prospect theory (Kahneman and Tversky 1979) adds that losses loom larger than gains of the same size:…

13 thms1 active userReviewed
Dynamic ProgrammingLinear OptimizationOperations Research+2·Captain: mikedeng1

On the Choice-Based Linear Programming Model for Network Revenue Management I: The CDLP Is Asymptotically Optimal under Proportional ScalingResearch Paper

Airlines, hotels and railways sell a fixed stock of perishable capacity (seats on flight legs, room-nights) to customers who arrive over a finite selling horizon. Network revenue management decides, at each moment, which products to keep open for sale. In the classical independent-demand model each product has its own demand stream. In practice customers…

7 thms1 active userReviewed
Operations ResearchOptimization·Captain: mikedeng1

The d-Level Nested Logit Model: Assortment and Price Optimization Problems II: The Push-Up-Then-Push-Down Prices Converge to a Stationary PointResearch Paper

Retailers that sell many substitutable products must set all their prices at once, and a customer's reaction to one price depends on what else is on the shelf. The nested logit model captures this by grouping similar products into nests, so that raising one price shifts demand mostly to close substitutes. The ddd-level nested logit model extends the familiar…

6 thms1 active userReviewed
Bandit AlgorithmsDynamic ProgrammingOperations Research+1·Captain: mikedeng1

The Complexity of Optimal Queuing Network Control II: Restless Bandits with Deterministic Transitions are PSPACE-hardResearch Paper

Among queueing control problems, a small class admits efficiently computable optimal policies: a single server choosing among several customer streams (Klimov 1974). These problems can be recast as multi-armed bandit problems, whose optimal policies are given by Gittins indices (Gittins 1979), and those indices are computable in polynomial time. The most…

8 thms1 active userReviewed
Dynamic ProgrammingMarkov ChainOperations Research+1·Captain: mikedeng1

The Complexity of Optimal Queuing Network Control I: NETWORK OF QUEUES is EXP-completeResearch Paper

Multiclass queueing networks model manufacturing lines, computer systems and communication networks. In these systems jobs of several types move between shared resources, and a controller decides where to send a job next (routing) and which waiting job a free resource works on (sequencing). The central design question is to find a control policy that…

10 thms1 active userReviewed
Dynamic ProgrammingMarkov ChainOperations Research+1·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems V: The Average Cost Optimality Equation and Value Iteration for Finite State SpacesTextbook

Average cost Markov decision chains model systems that run indefinitely and are judged by their long-run cost per step: admission and routing control in queues, inventory replenishment, machine maintenance. For a finite state space the classical tool is the average cost optimality equation (ACOE)

13 thms1 active userReviewed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Lost-Sales Problems with Stochastic Lead Times: Convexity Results for Base-Stock Policies: Expected Discounted Cost Is Convex in the Base-Stock LevelResearch Paper

In many inventory systems, demand that cannot be met from stock is lost rather than backordered: a customer who finds the shelf empty buys elsewhere. For such lost-sales systems with positive lead times the optimal replenishment policy is known to be complex and to depend on the whole pipeline of outstanding orders (Karlin and Scarf, 1958; Morton, 1969). In…

10 thms1 active userReviewed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Minimization Methods for Non-Differentiable Functions IX: Convergence of the r-Algorithm with Exact Directional MinimizationTextbook

The r-algorithm of N. Z. Shor is a variable-metric method for minimizing functions that are not differentiable everywhere, such as maxima of smooth functions, penalty functions and Lagrangian dual functions of integer and decomposition problems. It combines a subgradient step with a space dilation along the difference of two successive almost-gradients, and…

7 thms1 active userReviewed
PreviousPage 50 of 52Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5162497
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36515432
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