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.

3568 completed missions

Missions

2451–2475 of 3568
Open1244Completed3568All4812
🏆Completed
Algorithmic Game TheoryMarkov ChainOperations Research·Captain: mikedeng1

Trust and Reciprocity in Firms’ Capacity Sharing: A Non-Trivial Trading-Favors Equilibrium Exists if and only if Each Firm’s Discounted Return on a Favor Exceeds Its Opportunity and Service CostResearch Paper

Service firms with idle capacity often turn away customers while a nearby competitor sits idle, and the reverse happens an hour later. Sharing capacity would help both, but contracting on every transfer is costly, and monitoring the partner's state is usually impossible. Informal arrangements in which favors are returned rather than paid for are a natural…

11 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems: Recursive Greedy Is an O(log k/log log k)-Approximation in (n log B)^O(log^(1+ε) k) TimeResearch Paper

Directed network design asks which connections can be bought under a limited budget when traffic follows the directions of arcs. In directed tree orienteering, the reward comes from vertices reached by a rooted directed tree. The submodular version allows the reward of a new vertex to depend on which vertices have already been reached. This captures…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Modelling Multiperiod Carbon Markets Using Singular Forward-Backward SDEs: The q-Period Allowance-Price FBSDE with Emission-Dependent Caps Has a Unique Solution and a Unique Decoupling FieldResearch Paper

In a cap-and-trade scheme such as the EU Emissions Trading System, a regulator issues a limited number of emission allowances, firms trade them, and at each compliance date every firm must surrender one allowance per unit emitted or pay a penalty. The allowance price is the quantity regulators and firms care about: it is the marginal cost of emitting.…

14 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear-Equality-Constrained Optimization with Rank-Deficient Jacobians: A Vanishing Merit Parameter Forces liminf ‖J_kᵀc_k‖ = 0Research Paper

Many problems in machine learning, optimal control and data-driven engineering design take the form of minimizing an expected loss f(x)=E[F(x,ι)]f(x) = \mathbb E[F(x,\iota)]f(x)=E[F(x,ι)] subject to deterministic nonlinear equality constraints c(x)=0c(x) = 0c(x)=0. When fff is an expectation over a large or unknown distribution, only stochastic gradient estimates gk≈∇f(xk)g_k \approx \nabla f(x_k)gk​≈∇f(xk​) are…

11 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: mikedeng1

Sequential Mechanisms with Ex Post Individual Rationality: The Revenue-Optimal Dynamic Mechanism Is Built by Backward Induction on Cumulative Surplus-Utility Tradeoff FunctionsResearch Paper

Many goods are sold to the same buyer repeatedly: advertising impressions, cloud capacity, seasonal tickets. The buyer's value for each sale is learned only shortly before it, and a seller who knows the distribution of future values can extract more revenue with a dynamic mechanism, one whose terms on later days depend on what the buyer reported earlier.…

8 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Interior Point Algorithms VII: The Homogeneous Model for Monotone Complementarity and Its Central StepTextbook

The monotone complementarity problem (MCP) asks, for a continuous monotone map fff on the positive orthant, for a pair (x,s)(x,s)(x,s) with s=f(x)s=f(x)s=f(x), x≥0x\ge0x≥0, s≥0s\ge0s≥0 and xjsj=0x_js_j=0xj​sj​=0 for every jjj. It contains linear programming, convex quadratic programming, the monotone linear complementarity problem and the Karush–Kuhn–Tucker conditions of smooth convex programs.…

10 thms2 active usersReviewed
🏆Completed
Linear OptimizationNumerical AnalysisOperations Research+1·Captain: Shuze Chen

Interior Point Algorithms VI: Predictor Directions Are O(μ) on the Optimal PartitionTextbook

Primal-dual interior-point methods for linear programming come with two kinds of guarantee. The worst-case one is a bound of O(nlog⁡(R/ϵ))O(\sqrt n\log(R/\epsilon))O(n​log(R/ϵ)) iterations to reduce the duality gap below ϵ\epsilonϵ. The asymptotic one says what happens to the duality gap near the end of the run, where practical codes spend their final iterations. For the…

11 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: Shuze Chen

Interior Point Algorithms V: Random Gaussian Feasibility Problems Are Strictly Feasible on One SideTextbook

Worst-case analysis of interior-point methods gives iteration bounds of order n L\sqrt n\,Ln​L or nlog⁡(1/ϵ)\sqrt n\log(1/\epsilon)n​log(1/ϵ), while practical codes finish in a number of iterations that barely grows with the problem size. Chapter 6 of Yinyu Ye's Interior Point Algorithms: Theory and Analysis (Wiley 1997, doi:10.1002/9781118032701) addresses the gap…

6 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Interior Point Algorithms III: The Primal-Dual Potential Function Falls by a Constant Every StepTextbook

Karmarkar's 1984 algorithm solved linear programs in polynomial time by reducing a logarithmic potential function by a constant at every step (doi:10.1007/BF02579150). Its successors replaced Karmarkar's projective transformations with a primal-dual potential that measures the duality gap and the distance from the central path together. Tanabe, and Todd and…

7 thms2 active usersReviewed
🏆Completed
Linear OptimizationNumerical AnalysisOperations Research+1·Captain: Shuze Chen

Interior Point Algorithms II: Proximity Measures and Newton Steps for the Analytic CenterTextbook

Interior-point methods for linear programming do not move along the boundary of the feasible region; they follow a curve of points that stay "central". The basic notion of centrality is the analytic center of a polytope, the interior point that maximizes the product of the slacks of its defining inequalities (Sonnevend, 1986, doi:10.1007/BFb0043914). Every…

8 thms2 active usersReviewed
🏆Completed
Linear OptimizationNumerical AnalysisOperations Research+1·Captain: Shuze Chen

Primal-Dual Interior-Point Methods V: Below a Threshold μ̄ the Projection Step Returns a Strictly Complementary SolutionTextbook

Primal-dual interior-point methods for linear programming generate strictly positive iterates that approach the solution set but never reach it: the duality measure μ\muμ tends to zero, yet no iterate is ever an exact solution. Many applications need more than an approximate point — an exact optimal basis, a vertex, or the optimal partition of the variables…

9 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Primal-Dual Interior-Point Methods VI: The Simplified Homogeneous Self-Dual Form Decides Whether an LP Has a SolutionTextbook

Interior-point methods for linear programming are usually analysed under the assumption that the primal-dual pair has a strictly feasible point, or at least a solution. A solver used in practice cannot assume this: it must either return a solution or report that the primal or the dual problem is infeasible. The homogeneous self-dual approach embeds the…

10 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Primal-Dual Interior-Point Methods IV: The Infeasible Path-Following Method Drives μ to Zero Q-LinearlyTextbook

Primal-dual interior-point methods solve a linear program by following the central path from a point with strictly positive primal variables xxx and dual slacks sss. The classical analysis assumes that the starting point is feasible: it already satisfies the equality constraints Ax=bAx = bAx=b and ATλ+s=cA^{\mathsf T}\lambda + s = cATλ+s=c. In practice such a point is rarely…

10 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Primal-Dual Interior-Point Methods III: A Full Short Step Keeps the Iterate in the Neighborhood N₂(θ)Textbook

Primal-dual interior-point methods are the standard polynomial-time algorithms for linear programming and the basis of most commercial LP solvers. Among them, path-following methods are the ones with the cleanest complexity theory: they keep every iterate inside a neighborhood of the central path and shrink the duality measure by a fixed factor per step.…

10 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Primal-Dual Interior-Point Methods II: The Kojima–Mizuno–Yoshise Step Lowers the Potential Φ_ρ by 0.15Textbook

Interior-point methods solve linear programs by moving through the interior of the feasible region instead of along its edges. Two families dominate the theory: path-following methods, which keep the iterates near a central path, and potential-reduction methods, which instead measure progress by a single merit function and only ask that it fall by a fixed…

10 thms2 active usersReviewed
🏆Completed
Functional AnalysisMachine LearningNumerical Analysis+2·Captain: Shuze Chen

The Nature of Statistical Learning Theory VII: Tikhonov Regularization of Ill-Posed ProblemsTextbook

Estimating a probability density, a conditional probability or a conditional density from data can be written as solving a linear operator equation Af=FAf = FAf=F whose right-hand side FFF is a distribution function. The true FFF is unknown; only its empirical estimate FℓF_\ellFℓ​ is available, built from ℓ\ellℓ observations. The Glivenko–Cantelli theorem and the…

8 thms2 active usersReviewed
🏆Completed
AnalysisHarmonic AnalysisMachine Learning+2·Captain: Shuze Chen

The Nature of Statistical Learning Theory VI: Kernels Generating Regularized Fourier ExpansionsTextbook

A support vector machine never computes its feature map. It only evaluates a kernel K(x,y)K(x, y)K(x,y), the inner product of the feature vectors of xxx and yyy. When the features are the first NNN terms of an expansion, or infinitely many terms damped by regularizing weights, the learning algorithm is practical only if that inner product has a closed form. Chapter 6 of V.…

10 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research+1·Captain: Shuze Chen

Primal-Dual Interior-Point Methods I: The Primal-Dual Log Barrier Has a Unique Minimizer, So the Central Path ExistsTextbook

Primal-dual interior-point methods are the standard polynomial-time algorithms for linear programming and the basis of most commercial LP solvers. They do not move along the boundary of the feasible polyhedron, as the simplex method does. Instead they follow a curve through its interior, the central path, toward the solution set. Every convergence and…

6 thms2 active usersReviewed
🏆Completed
CombinatoricsMachine LearningProbability+1·Captain: Shuze Chen

The Nature of Statistical Learning Theory III: The Growth Function Is Linear or LogarithmicTextbook

Statistical learning theory asks when minimizing the error on a finite sample also controls the error on unseen data. For a set of classifiers, the answer given by Vapnik and Chervonenkis is governed by a single combinatorial quantity: how many different ways the set can label ℓ\ellℓ points. Bounds on the generalization error of empirical risk minimization…

11 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling XV: Independence of Level and Phase in QBDsTextbook

A Jackson network of exponential single-server queues has a stationary distribution of product form: the numbers of customers at the nodes are independent in steady state, each geometric (Jackson, 1957; Jackson, 1963). The same property holds for a large family of networks (Kelly, Reversibility and Stochastic Networks, 1979), and it is what makes…

7 thms2 active usersReviewed
🏆Completed
EconomicsOperations ResearchOptimization·Captain: Shuze Chen

Pricing and the Newsvendor Problem: A Review with Extensions: If 2r(z)² + r′(z) > 0 and a − b(c − 2s) + A > 0, the Additive-Demand Pricing Newsvendor Has a Unique Optimal Stocking Factor z*Research Paper

A retailer of a seasonal or perishable product must commit to a stock level before demand is known, and must also choose the price at which to sell. The two decisions interact: the price shifts the demand distribution, and the stock level determines how much of that demand can be served. The price-setting newsvendor is the single-period model of this…

10 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling XIII: M/G/1- and GI/M/1-Type Chains as QBDsTextbook

Many queueing, inventory and storage models are Markov chains on a two-dimensional state space (n,i)(n, i)(n,i): a level n≥0n \ge 0n≥0 (a queue length, a stock level) and a phase iii (the state of an arrival or service environment). When customers arrive in batches, the level can jump up by several units in one step but comes down one unit at a time; when services are…

9 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling XIV: The Matrix-Product Form for Tree-Structured ProcessesTextbook

A quasi-birth-and-death process moves on levels 0,1,2,…0, 1, 2, \dots0,1,2,… and, within a level, among finitely or infinitely many phases; its stationary distribution is matrix-geometric, πn=π0Rn\pi_n = \pi_0 R^nπn​=π0​Rn, which is the central result of the matrix analytic method (Neuts, Matrix-Geometric Solutions in Stochastic Models, 1981; Latouche & Ramaswami 1999, Chapter 6).…

15 thms2 active usersReviewed
🏆Completed
Linear algebraMarkov ChainNumerical Analysis+3·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling XI: First Passage Times by Reduction and BisectionTextbook

In a quasi-birth-and-death process (QBD) a queue length or buffer content (the level) moves up or down by at most one per step while an auxiliary Markov environment (the phase) modulates the rates. When buffers are bounded the level lives in {0,1,…,M}\{0,1,\dots,M\}{0,1,…,M}, and a basic performance question is how long it takes, on average, for an initially empty buffer to…

8 thms2 active usersReviewed
🏆Completed
Linear algebraMarkov ChainNumerical Analysis+3·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling VIII: The Logarithmic Reduction Series for GTextbook

Quasi-birth-and-death processes (QBDs) are Markov chains on pairs (level, phase) in which the level moves by at most one at each step. They model queues in random environments, priority queues, and many other systems treated by matrix-analytic methods (Latouche & Ramaswami 1999). Their stationary distribution, when it exists, is matrix-geometric, and…

8 thms2 active usersReviewed
PreviousPage 99 of 143Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5262500
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR37095550
5NINickrobbins953290156
6VEvebis25800
7FIfizzyinc321735
8SHshivm17520
9KMkmehltretter821002265
10SCShuze Chen9455327

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