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

726–750 of 4812
Open1285Completed3527All4812
🏆Completed
Operations ResearchOptimal TransportOptimization+1·Captain: mikedeng1

On a Problem of Optimal Transport Under Marginal Martingale Constraints 6: For c = −|y − x| and Continuous µ the Optimizer Is Unique and Lives on Two Monotone GraphsResearch Paper

A forward-start straddle pays ∣S2−S1∣|S_2 - S_1|∣S2​−S1​∣, the absolute change of an asset price between two future dates. A trader who knows the market prices of all vanilla options at both dates knows the laws μ\muμ of S1S_1S1​ and ν\nuν of S2S_2S2​, but not their joint law. Under a pricing measure the price is a martingale, so the admissible joint laws are exactly the martingale…

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

On a Problem of Optimal Transport Under Marginal Martingale Constraints 4: For c = h(y − x) with h′ Strictly Convex the Left-Curtain Coupling Is the Unique OptimizerResearch Paper

Martingale optimal transport asks for the cheapest way to couple two probability laws μ\muμ and ν\nuν on R\mathbb RR under the extra constraint that the coupling is the law of a one-step martingale. The problem arose in robust mathematical finance: when the prices of all call options at two maturities are observed, the marginal laws of the underlying asset at…

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

Distributionally Robust Chance-Constrained Programs with Right-Hand Side Uncertainty under Wasserstein Ambiguity: The Reduced Quantile-Strengthened MIP (20) Is an Exact Reformulation of DR-CCPResearch Paper

A chance-constrained program chooses a decision xxx so that a random vector ξ\xiξ falls outside a decision-dependent safety set S(x)\mathcal S(x)S(x) with probability at most ϵ\epsilonϵ. Chance constraints are a standard model for reliability requirements in power systems, supply chains and transportation, where a plan must survive random demand or supply with high…

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

Bootstrap Robust Prescriptive Analytics 2: The Entropic Robust Nadaraya-Watson Budget Equals inf{α : ν log Σ D·exp((L−α)w/ν) + rν ≤ 0}Research Paper

Data-driven decision making with side information ("prescriptive analytics") chooses a decision zzz after observing a context x=x0x = x_0x=x0​, using a training set of past pairs (x,y)(x, y)(x,y). A common recipe estimates the conditional expected cost E[L(z,y)∣x=x0]\mathbb E[L(z, y) \mid x = x_0]E[L(z,y)∣x=x0​] with a local learning method, such as Nadaraya–Watson kernel regression or nearest neighbours,…

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

Fast Convergence of Inertial Dynamics and Algorithms with Asymptotic Vanishing Viscosity 3: For α > 3 and Σ k‖g_k‖ < ∞, the Perturbed Inertial Forward-Backward Iterates Converge Weakly to a MinimizerResearch Paper

Many problems in signal processing, statistics and machine learning take the form min⁡xΦ(x)+Ψ(x)\min_x \Phi(x)+\Psi(x)minx​Φ(x)+Ψ(x), where Ψ\PsiΨ is smooth and Φ\PhiΦ is convex but nonsmooth (a norm, the indicator of a constraint set). The forward-backward method takes a gradient step on Ψ\PsiΨ followed by a proximal step on Φ\PhiΦ. Its accelerated, inertial version — FISTA of Beck and…

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

Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs 2: Sufficient Decrease, Multi-Step Relative Error and KL Give Finite Length and Linear RatesResearch Paper

Many first-order methods for nonconvex and nonsmooth optimization are analysed with the same template: a merit function decreases by a definite amount at every step, a subgradient of the merit function at the current point is bounded by the step length, and the Kurdyka–Łojasiewicz (KL) property of the merit function turns these two facts into a proof that…

14 thms4 active usersReviewed
🏆Completed
Information TheoryOperations ResearchProbability+1·Captain: mikedeng1

Bootstrap Robust Prescriptive Analytics 3: Any Distance Exceeding the Bootstrap Distance Near Some D Loses the Disappointment Rate −rResearch Paper

Data-driven decision making estimates the cost of a decision from training data and then optimizes that estimate. The optimized estimate is biased downwards: the decision that looks best on the training data tends to disappoint on fresh data. Distributionally robust optimization counters this by optimizing the worst case of the estimate over all…

9 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

Bootstrap Robust Prescriptive Analytics 1: The Entropic Robust Budget Is Broken on Bootstrap Data with Probability at Most Σⱼ exp(−n·max{r, rⱼⁿ})Research Paper

Prescriptive analytics chooses a decision zzz from data after observing a context x0x_0x0​: a retailer sets an order quantity after seeing the weather forecast, a hospital schedules staff after seeing the day of the week. A common recipe estimates the expected cost of each decision from the training observations closest to x0x_0x0​ (nearest neighbours, or a…

12 thms4 active usersReviewed
🏆Completed
AlgebraComplexity TheoryTheoretical Computer Science·Captain: mikedeng1

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs II: BLP+Affine Solves PCSP(A, B) Exactly When Pol(A, B) Has Block-Symmetric Polymorphisms of Arbitrarily High WidthResearch Paper

A promise constraint satisfaction problem PCSP(A,B)\mathrm{PCSP}(\mathbf A,\mathbf B)PCSP(A,B) asks to distinguish instances that are satisfiable in a structure A\mathbf AA from instances that are not even satisfiable in a weaker structure B\mathbf BB. Approximate graph colouring (tell 3-colourable graphs from graphs that are not 5-colourable) and …

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

From Error Bounds to the Complexity of First-Order Descent Methods for Convex Functions 1: Subgradient Descent Sequences of Convex KL Functions Obey f(x_k) ≤ ψ(α_k) for a 1-D Worst-Case Prox SequenceResearch Paper

Many first-order methods for convex minimization — the forward–backward (proximal gradient) method, alternating minimization, trust-region and majorization–minimization schemes — produce sequences that decrease the objective by an amount proportional to the squared step and whose step controls a subgradient at the new point. Luo and Tseng (Ann. Oper. Res.…

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

Optimal Transport-Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes 1: Mahalanobis-Transport Worst-Case Loss Equals inf over λ ≥ 0 of E_P0[ℓ_rob(β, λ; X)]Research Paper

Distributionally robust optimization chooses a decision against a range of plausible probability laws instead of a single fitted law. Here the decision is a linear rule evaluated through a loss function. The range of laws is specified by how much probability mass may be transported away from a baseline law. A conventional transport cost depends only on the…

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

Constrained Assortment Optimization for the Nested Logit Model 4: Under Space Constraints, O(n²) Rounded Knapsack-Relaxation Assortments Include a min{2, 1/(1−ε)}-Approximate Solution for Every u ≥ 0Research Paper

A retailer choosing which products to display faces a physical limit: different products consume different amounts of shelf space. Under a nested logit choice model, the value of an assortment also depends on how customers substitute among products within a nest and on whether they leave without buying. Gallego and Topaloglu study this combination of choice…

10 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Generation and Properties of Snarks 3: A Snark on 26 Vertices All of Whose 2-Factors Consist of Odd Cycles Refutes the Abreu–Labbate–Sheehan ConjectureResearch Paper

A cubic graph has chromatic index 3 or 4 (Vizing). Cubic graphs of chromatic index 4 — the uncolourable ones — are where most of the open problems on cubic graphs live: a minimal counterexample to the cycle double cover conjecture or to Tutte's 5-flow conjecture would be among them. Uncolourable graphs with small edge cuts or short cycles reduce to smaller…

12 thms4 active usersReviewed
🏆Completed
Complexity TheoryLinear OptimizationTheoretical Computer Science·Captain: mikedeng1

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs I: BLP+Affine Correctly Solves Every PCSP with Symmetric Polymorphisms of Arbitrarily Large AritiesResearch Paper

A constraint satisfaction problem (CSP) asks whether variables can be assigned values from a finite domain so that every constraint, drawn from a fixed list of allowed relations, is satisfied. A promise CSP (PCSP) relaxes the question: given two templates A\mathbf AA and B\mathbf BB with a homomorphism A→B\mathbf A\to\mathbf BA→B, distinguish instances satisfiable in …

11 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOperations Research+2·Captain: mikedeng1

On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games 2: Randomized Inexact Best Response Reaches an ϵ-NE in Explicitly Bounded Expected SG StepsResearch Paper

Many noncooperative problems in communication networks, power markets and supply chains are stochastic Nash games. Each player minimizes an expected cost that depends on its own decision and on the decisions of its rivals, and the expectation can only be sampled, not evaluated. A natural distributed way to compute an equilibrium is the best-response scheme:…

21 thms4 active usersReviewed
Algorithmic Game TheoryConvex OptimizationOperations Research+2·Captain: mikedeng1

On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games 3: Asynchronous Inexact Best Response with Delays Reaches an ϵ-NE in Explicitly Bounded SG StepsResearch Paper

Many equilibrium problems in operations research have the form of a stochastic Nash game: each of NNN players minimizes an expected cost that depends on the strategies of the others, and the expectation can only be sampled. The paper's introduction lists applications in generation-capacity and power markets and in communication networks (Abada, de Maere…

19 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Generation and Properties of Snarks 2: A Cyclically 5-Edge-Connected Permutation Snark on 34 Vertices Refutes Zhang's Conjecture That Only the Petersen Graph Is OneResearch Paper

A snark is a cubic graph that cannot be properly edge-coloured with three colours and that does not reduce to a smaller such graph. Snarks are the smallest possible counterexamples to several central conjectures about cubic graphs, among them the cycle double cover conjecture, Tutte's 5-flow conjecture and the Berge–Fulkerson conjecture, so structural…

15 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOperations Research+2·Captain: mikedeng1

On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games 1: Synchronous Inexact Best Response Reaches an ϵ-NE in Explicitly Bounded Projected SG StepsResearch Paper

Many equilibrium problems in operations research, such as networked Cournot competition, power markets and communication networks, are stochastic Nash games: each player minimizes an expected cost fi(xi,x−i)=E[ψi(xi,x−i;ξ)]f_i(x_i,x_{-i})=\mathbb E[\psi_i(x_i,x_{-i};\xi)]fi​(xi​,x−i​)=E[ψi​(xi​,x−i​;ξ)] that depends on the rivals' strategies and on a random vector ξ\xiξ whose law is accessible only through samples. B…

13 thms4 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics+1·Captain: mikedeng1

A Learning Theory Approach to Non-Interactive Database Privacy 1: The Net Mechanism Is (α, δ)-Useful for Every Class of Counting Queries with Error Governed by Its VC-DimensionResearch Paper

A data curator holds a database of nnn individual records and wants to publish something from which many statistics can be computed, while guaranteeing differential privacy: no single record should noticeably change what is published (Dwork, McSherry, Nissim, Smith 2006). Interactive mechanisms answer queries one at a time and add noise to each answer, so…

16 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Online Learning and Online Convex Optimization 2: Normalized Exponentiated Gradient Has Regret at Most log(d)/η + η Σₜ Σᵢ wₜ[i]zₜ[i]² When ηzₜ[i] ≥ −1Research Paper

Learning with expert advice and online linear optimization over the probability simplex are the basic models behind boosting, multiplicative-weights methods for linear programming and zero-sum games, and adversarial bandit algorithms. The algorithm that solves them, under the names Weighted Majority, Hedge and Exponentiated Gradient (EG), keeps a…

6 thms4 active usersReviewed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Self-Scaled Barriers and Interior-Point Methods for Convex Programming III: An Affine Potential-Reduction Step Lowers the Potential by at Least 1 − ln 2, and by (‖p‖²/|p|²)(1 − ln 2) When µ ≥ 2νResearch Paper

Potential-reduction methods solve a linear or conic program by driving down a single merit function that combines the objective gap with a barrier for the constraint cone. For linear programming the primal version goes back to Karmarkar (1984) and, without Karmarkar's special problem form, to Gonzaga (1990, Math. Programming 49, 7–21), whose method reduces…

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

Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization 1: SGD with α-Suffix Averaging Attains E[F(w̄ᵅ_T)] − F(w*) ≤ (2 + 2.5 log(1/(1−α)))G²/(αλT)Research Paper

Stochastic gradient descent (SGD) is the default method for minimizing an expected loss F(w)=Ez[ℓ(w,z)]F(w)=\mathbb E_z[\ell(w,z)]F(w)=Ez​[ℓ(w,z)] when only noisy gradients are available, which is the situation of nearly every large-scale learning problem. When FFF is strongly convex (for instance, any convex loss with an ℓ2\ell_2ℓ2​ regularizer), information-theoretic lower bounds show that no…

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

A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets 1: SAG with Step Size 1/(2nL) Converges Linearly at Rate (1 − μ/(8Ln))ᵏResearch Paper

Many problems in machine learning and statistics minimize an average of nnn smooth losses, one per training example: regularized least squares, logistic regression, and other forms of empirical risk minimization. Two classical families of methods attack such finite sums. The full gradient method evaluates all nnn component gradients per iteration and converges…

14 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability+1·Captain: mikedeng1

Matroid Prophet Inequalities 1: Against Any Online Weight-Adaptive Adversary, the 2-Balanced Threshold Algorithm Earns at Least Half the Expected Max-Weight BasisResearch Paper

The prophet inequality of optimal stopping compares a gambler, who sees independent non-negative random values X1,…,XnX_1, \dots, X_nX1​,…,Xn​ one at a time and must accept or reject each on arrival, with a prophet who sees them all in advance. Krengel, Sucheston and Garling showed that the gambler can secure E[Xτ]≥12 E[max⁡iXi]\mathbb E[X_\tau] \ge \tfrac12\,\mathbb E[\max_i X_i]E[Xτ​]≥21​E[maxi​Xi​], and…

16 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? 2: Random-Hyperplane Rounding Approximates Balanced MAX-2SAT within β ≈ 0.943Research Paper

MAX-2SAT asks for an assignment of Boolean variables that maximizes the total weight of satisfied clauses, each clause being a disjunction of two literals. It is one of the basic constraint satisfaction problems of approximation theory, and its approximability has been studied alongside MAX-CUT since semidefinite programming entered the field.

9 thms4 active usersReviewed
PreviousPage 30 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