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

651–675 of 4812
Open1285Completed3527All4812
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Multistage Distributionally Robust Mixed-Integer Programming with Decision-Dependent Moment-Based Ambiguity Sets I: Under Moment Bounds, the Stage Bellman Equation Is One LP-Dual MinimizationResearch Paper

In many planning problems the decision changes the uncertainty it faces. Opening a facility raises the demand observed near it; a maintenance decision changes the failure distribution of a component; a price shifts the demand law. Decision-dependent uncertainty of this kind breaks the standard assumption of stochastic programming that the probability…

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

Linear Convergence of First Order Methods for Non-Strongly Convex Optimization V: Fast Gradient on Quasi-Strongly Convex f Has f(x^k) − f* ≤ 2(1 − √μ)^k (f(x^0) − f*) if All y^k Share One ProjectionResearch Paper

Many convex problems met in practice — least squares with a rank-deficient matrix, dual problems of linearly constrained programs, min⁡xg(Ax)\min_x g(Ax)minx​g(Ax) with a strongly convex ggg and a wide matrix AAA — are not strongly convex: their optimal set is a whole affine piece rather than a point. The classical linear-rate theory of first order methods assumes strong…

10 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Multistage Distributionally Robust Mixed-Integer Programming with Decision-Dependent Moment-Based Ambiguity Sets II: Under Mean and Covariance, the Stage Bellman Equation Is One LP-Dual MinimizationResearch Paper

Many planning problems are solved in stages. A decision is taken, uncertainty is revealed, and the next decision reacts to it. Facility location, capacity expansion and network design all fit this pattern. In a growing class of such problems, the distribution of the uncertainty depends on the decision: opening a facility changes the demand it attracts, and…

6 thms4 active usersReviewed
🏆Completed
Control TheoryConvex OptimizationGraph Theory+1·Captain: mikedeng1

Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs 1: DIGing Converges R-Linearly over Time-Varying Undirected Graphs for Every Step Size Below 1.5(1−δ)²/(μ̄J₁)Research Paper

In distributed optimization, nnn agents each hold a private function fi:Rp→Rf_i:\mathbb R^p\to\mathbb Rfi​:Rp→R and must jointly solve

11 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature I: Swap-Local Optima of the Non-Oblivious Potential Are (1 − c/e)-Approximate for Submodular MaximizationResearch Paper

Maximizing a monotone submodular function over the bases of a matroid is the standard model for coverage, facility location, sensor placement and welfare maximization. The best possible approximation factor in the value-oracle model is 1−1/e1 - 1/e1−1/e (Nemhauser–Wolsey 1978; Călinescu–Chekuri–Pál–Vondrák 2011). Many functions met in practice are far from the worst…

9 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationDynamical Systems·Captain: mikedeng1

Learning in Games via Reinforcement and Regularization 1: Under Regularized Reinforcement Learning, Every Iteratively Dominated Strategy Becomes ExtinctResearch Paper

A basic test of any model of learning in games is whether it respects strict dominance: a strategy that does worse than another against every behaviour of the opponents should eventually be abandoned, and, after it is gone, so should every strategy that becomes dominated in what remains. For the replicator dynamics of evolutionary game theory this is…

13 thms4 active usersReviewed
🏆Completed
Functional AnalysisNumerical AnalysisOptimization·Captain: mikedeng1

Projected Reflected Gradient Methods for Monotone Variational Inequalities 2: Under Strong Monotonicity the Projected Reflected Gradient Method Converges R-LinearlyResearch Paper

A variational inequality asks for a point of a convex set at which a vector field points "inward" against every feasible direction. It is the common form of convex minimization (with FFF a gradient), of saddle-point problems (with FFF the monotone operator of a convex–concave function), of Nash equilibria of convex games, of complementarity problems and of…

12 thms4 active usersReviewed
Convex OptimizationOperations ResearchOptimal Transport+1·Captain: mikedeng1

Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls 1: Copositive Programs (28) Are Exact under Complete Recourse and Converge to (1) as δ ↓ 0Research Paper

Two-stage decision problems split decisions into a here-and-now decision xxx, taken before an uncertain parameter ξ\xiξ is observed, and a wait-and-see (recourse) decision yyy, taken after. Stochastic programming minimizes the expected total cost under a known distribution of ξ\xiξ; robust optimization minimizes the worst-case cost over a support set. Distributional…

19 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Minimizing Finite Sums with the Stochastic Average Gradient: SAG with Step 1/(16L) Has E[g(x̄ᵏ)] − g(x*) ≤ (32n/k)C₀, and Rate (1 − min{μ/(16L), 1/(8n)})ᵏC₀ if g Is μ-Strongly ConvexResearch Paper

Many problems in statistics and machine learning minimize a finite sum: an average of nnn smooth convex losses, one per data point, often plus a strongly convex regularizer. The full gradient method costs nnn component gradients per iteration and converges at rate O(1/k)O(1/k)O(1/k), or linearly when the objective is strongly convex (Nesterov, 2004). The stochastic…

19 thms4 active usersReviewed
🏆Completed
Functional AnalysisNumerical AnalysisOptimization·Captain: mikedeng1

Projected Reflected Gradient Methods for Monotone Variational Inequalities 1: The Projected Reflected Gradient Method Converges Weakly to a SolutionResearch Paper

Many problems in optimization, game theory and mechanics come down to a variational inequality: find a point of a convex set at which a given vector field points "inward" against every feasible direction. Constrained convex minimization (where the field is a gradient), saddle-point problems (where it is the gradient of a convex–concave function with one…

12 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

K-Adaptability in Two-Stage Robust Binary Programming 2: The K-Adaptability Problem with Objective Uncertainty Is Equivalent to the MILP (5)Research Paper

Many planning problems are decided in two stages. A here-and-now decision xxx is taken before an uncertain parameter vector ξ\xiξ is observed, and a wait-and-see decision yyy is taken afterwards. When the wait-and-see decision is binary (which route to drive, which facility to open, which machine to schedule), the resulting two-stage robust binary program has no…

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

K-Adaptability in Two-Stage Robust Binary Programming 3: Under Constraint Uncertainty, Every K < |𝒴| Can Leave a Strict GapResearch Paper

Two-stage robust optimization models decisions taken in two steps around an uncertain parameter ξ\xiξ: a here-and-now decision xxx is fixed before ξ\xiξ is revealed, and a wait-and-see (recourse) decision yyy is chosen afterwards, against the worst case of ξ\xiξ in an uncertainty set Ξ\XiΞ. When the recourse is binary — routing, scheduling, facility opening, emergency…

7 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimal TransportOptimization+1·Captain: mikedeng1

A Short and General Duality Proof for Wasserstein Distributionally Robust Optimization IV: On a Polish Space, the Maximum-Transport-Cost Worst-Case Loss Equals E[sup{f(x) : c(X̂, x) ≤ ρ}]Research Paper

In Wasserstein distributionally robust optimization (DRO) a decision is evaluated against the worst distribution within an optimal-transport ball around a nominal distribution P^\widehat{\mathbb P}P. For a Wasserstein distance of finite order ppp, the ball constrains an average transport cost. The case p=∞p=\inftyp=∞ is different. The ∞\infty∞-Wasserstein distance …

16 thms4 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisOptimization·Captain: mikedeng1

Optimization-Based Algorithms for Tensor Decompositions: Canonical Polyadic Decomposition, Decomposition in Rank-(Lr, Lr, 1) Terms, and a New Generalization 2: The Cogradient Is ½(Ā·W − T̄·V)Research Paper

Tensor decompositions are a standard tool in signal processing, chemometrics, telecommunications and blind source separation. The canonical polyadic decomposition (CPD) writes a tensor as a sum of rank-one tensors; the rank-(Lr,Lr,1)(L_r,L_r,1)(Lr​,Lr​,1) block term decomposition (BTD) replaces each rank-one term by the outer product of a rank-LrL_rLr​ matrix and a vector. Sorber,…

9 thms4 active usersReviewed
🏆Completed
Algebraic TopologyCombinatoricsLinear algebra·Captain: mikedeng1

Isoperimetric Inequalities in Simplicial Complexes 2: The Mixing Lemma — for Disjoint A_0,…,A_d in a Complex with a Complete Skeleton, ||F(A_0,…,A_d)| − α|A_0|⋯|A_d|/n| ≤ ρ_α(|A_0|⋯|A_d|)^(d/(d+1))Research Paper

For a kkk-regular graph G=(V,E)G=(V,E)G=(V,E) on nnn vertices, the Expander Mixing Lemma (Alon–Chung 1988; see the survey of Hoory, Linial and Wigderson 2006) says that for any vertex sets A,BA,BA,B, the number of edges between them is close to its expected value: ∣∣E(A,B)∣−k∣A∣∣B∣/n∣≤ρ∣A∣∣B∣\bigl||E(A,B)|-k|A||B|/n\bigr|\le\rho\sqrt{|A||B|}​∣E(A,B)∣−k∣A∣∣B∣/n​≤ρ∣A∣∣B∣​, where ρ\rhoρ is the largest absolute value of a nontrivial…

16 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimal TransportOptimization+1·Captain: mikedeng1

Residuals-based distributionally robust optimization with covariate information 1: Wasserstein ER-DRO with the Enlarged Radius (10) Certifies Its Out-of-Sample Cost with Probability 1−αResearch Paper

Many operational decisions are made after observing covariates that carry information about the uncertainty: a retailer sets inventory after seeing weather and calendar features that predict demand, a grid operator commits generation after seeing a load forecast. The decision problem is a conditional stochastic program: choose z∈Zz\in\mathcal Zz∈Z to minimize …

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

Distributionally Robust Joint Chance Constraints with Second-Order Moment Information I: Worst-Case CVaR Is Exact for Individual Chance Constraints with Concave or Quadratic LossesResearch Paper

A chance constraint asks that an uncertain constraint hold with high probability: a decision is acceptable if the loss L(ξ~)L(\tilde\xi)L(ξ~​) it incurs is nonpositive with probability at least 1−ϵ1-\epsilon1−ϵ. Chance constraints appear in portfolio selection, power-system dispatch, inventory control and engineering design, wherever an occasional violation is tolerable but…

18 thms4 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

Optimality Conditions and Finite Convergence of Lasserre's Hierarchy I: Under Archimedeanness, the Classical Optimality Conditions at Every Global Minimizer Imply Finite ConvergenceResearch Paper

Polynomial optimization asks for the global minimum of a polynomial fff over a set K⊆RnK \subseteq \mathbb R^nK⊆Rn cut out by polynomial equations and inequalities. It contains nonconvex quadratic programming, max-cut, and many problems from control and engineering. Lasserre's hierarchy (Lasserre 2001) replaces this problem by a sequence of semidefinite programs…

12 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

A Modern Introduction to Online Learning VII: The Perceptron's Mistakes Exceed the Competitor's Hinge-Power Loss by at Most q²R²‖u‖²/2 + qR‖u‖√(q²R²‖u‖²/4 + L_q)Textbook

An online classifier must predict a label before learning the correct answer. Its errors matter directly: a low numerical loss is useful only if it controls the number of wrong predictions. Chapter 8 of Orabona's textbook examines this connection for linear classification, where a vector of weights produces a score by taking an inner product with the…

8 thms4 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraOptimization·Captain: mikedeng1

Phase Recovery, MaxCut and Complex Semidefinite Programming 2: If Weak PhaseLift Is C-Stable at x₀, Then PhaseCut Is (2C + 2√2 + 1)-Stable at x₀Research Paper

Phase recovery asks to reconstruct a complex signal x0∈Cpx_0 \in \mathbb{C}^px0​∈Cp from the moduli of linear measurements, b=∣Ax0∣∈Rnb = |Ax_0| \in \mathbb{R}^nb=∣Ax0​∣∈Rn, where A∈Cn×pA \in \mathbb{C}^{n\times p}A∈Cn×p is known. The problem arises in X-ray crystallography, diffraction imaging and microscopy, where detectors record intensities but not phases (Shechtman et al., 2015). Since the map …

10 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

A Modern Introduction to Online Learning III: Adaptive Online Subgradient Descent on s-Self-Bounded Losses Has Regret 4sD² + 2D√(s Σ_t ℓ_t(u))Textbook

In online convex optimization, a learner selects a point before seeing the current loss. A useful guarantee compares the learner's accumulated loss with that of a single fixed point chosen in hindsight. A step size chosen from a preannounced bound on all future gradients can be wasteful when the realized gradients are small. Chapter 4 of Orabona's online…

7 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationMachine Learning+1·Captain: mikedeng1

Fast Convergence of Regularized Learning in Games I: If Every Player Runs Optimistic FTRL with Step Size 1/(2(n−1)), the Sum of All Players' Regrets Is at Most 2n(n−1)RResearch Paper

When the players of a game repeatedly adjust their strategies with no-regret learning algorithms, the empirical distribution of play converges to a coarse correlated equilibrium, and in smooth games the average social welfare approaches the price-of-anarchy guarantee of the game (Roughgarden 2009). For generic no-regret algorithms such as Hedge the…

9 thms4 active usersReviewed
🏆Completed
Linear algebraMachine LearningNumerical Analysis+3·Captain: mikedeng1

An Introduction to Matrix Concentration Inequalities III: A Matrix Sampling Estimator Satisfies E‖R̄ₙ − B‖ ≤ √(2m₂(R)log(d₁ + d₂)/n) + 2L log(d₁ + d₂)/(3n)Textbook

Matrix approximation replaces a large or complicated matrix with a random matrix that is easier to store or compute. Averaging independent realizations improves accuracy while retaining the structure of each realization. Examples in Tropp's monograph include sparse approximations and randomized matrix products. The practical question is how the number of…

8 thms4 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability·Captain: mikedeng1

A Primal-Dual Learning Algorithm for Personalized Dynamic Pricing with an Inventory Constraint: The Primal-Dual Learning Algorithm Has Regret at Most C(log n)^(2+δ) n^(−1/2)Research Paper

A firm selling a fixed stock of a perishable product over a finite season must set prices without knowing how demand responds to them. Online retail and travel platforms often see a customer's segment before quoting a price, so they can price-discriminate across consumer types. Learning a separate demand curve for each type, however, seems to cost more…

21 thms4 active usersReviewed
🏆Completed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming 4: The Mini-Batch RSAG Method Bounds the Expected Gradient Mapping on Nonconvex Stochastic Composite ProblemsResearch Paper

Training a model by stochastic gradients on a constrained or regularized loss is a stochastic composite problem: a smooth expected loss, observed only through noisy gradients, plus a simple non-smooth term such as a constraint set or an ℓ1\ell_1ℓ1​ penalty. For convex losses, accelerated stochastic approximation methods attain the optimal rates (Lan 2012; Ghadimi…

22 thms4 active usersReviewed
PreviousPage 27 of 193Next

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