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

1726–1750 of 4812
Open1269Completed3543All4812
AlgebraCombinatoricsDiscrete Geometry·Captain: mikedeng1

A Large Family of Maximum Scattered Linear Sets of PG(1, q^n) and Their Associated MRD Codes 1: For q Odd, t ≥ 3, h ∉ 𝔽_{q^t} and h^(q^t+1) = −1, ψ_{h,t} Is Scattered over 𝔽_{q^{2t}}Research Paper

A linear set of a projective space over a finite field is the set of points spanned by the nonzero vectors of a subspace over a subfield. They have been used to construct and characterize semifields, rank-metric codes, translation spreads, translation ovoids, two-intersection sets and the blocking sets for which Lunardon introduced them (Polverino 2010;…

13 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: mikedeng1

Distribution-Free Contextual Dynamic Pricing 2: Every Algorithm Has Expected Regret at Least C₀ C_p T₀ on Some Perturbed Linear Bandit with Perturbation C_pResearch Paper

Dynamic pricing asks a seller to post prices to a stream of customers and learn demand from purchase decisions alone. Luo, Sun and Liu study the contextual version in which a customer's valuation is linear in a covariate vector plus noise with an unknown distribution (arXiv:2109.07340v2; Mathematics of Operations Research, 2024). Their DIP policy estimates…

5 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

On the tightness of SDP relaxations of QCQPs 6: For Diagonal QCQPs the SOCP and SDP Relaxations Have the Same Projected Epigraph and Optimal ValueResearch Paper

Quadratically constrained quadratic programs (QCQPs) minimize a quadratic function subject to quadratic inequality and equality constraints. They model trust-region subproblems, robust least squares, max-cut and many problems in signal processing and control. They are NP-hard in general, so practice relies on convex relaxations, and the standard one is the S…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

On the tightness of SDP relaxations of QCQPs 2: Polyhedral Γ with 0 ∉ Proj_V(F){b(γ) : γ ∈ F} on Every Semidefinite Face Makes Every SDP Optimizer FeasibleResearch Paper

A quadratically constrained quadratic program (QCQP) minimizes a quadratic function subject to quadratic inequality and equality constraints. The class contains nonconvex problems such as max-cut, Boolean least squares, the trust-region subproblem and its generalizations, and robust least squares, and it is NP-hard in general. The standard convex approach…

15 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Product Price, Quality and Service Decisions under Consumer Choice Models I: Under MNL Demand, Optimal Service Durations Are Extreme, Qualities Are Set Product by Product, and Markups Are EqualResearch Paper

Manufacturers rarely sell a bare product. A laptop, a vacuum cleaner or a car comes with an ancillary service (a factory warranty, maintenance, technical support) whose length the firm chooses together with the price and the quality of the product. The three decisions interact: a longer warranty makes a product more attractive to consumers but costs the…

9 thms3 active usersReviewed
🏆Completed
Actuarial ScienceOperations ResearchProbability·Captain: mikedeng1

Inf-Convolution, Optimal Allocations, and Model Uncertainty for Tail Risk Measures I: The Inf-Convolution of Left and Right VaRs Is a VaR at the Summed Level, with an Explicit Optimal AllocationResearch Paper

Value-at-Risk (VaR) is the quantile-based capital requirement written into banking and insurance regulation (Basel, Solvency II). When several institutions, desks or subsidiaries each hold capital according to their own VaR, a natural question is how a total loss XXX should be split among them so that the aggregate capital is as small as possible. This is the …

9 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Product Price, Quality and Service Decisions under Consumer Choice Models V: A Dealer Optimally Offers a Markup-Ordered Assortment and Attaches Long Service to an Adjusted-Markup-Ordered SetResearch Paper

Car dealers, electronics retailers and office suppliers sell products whose prices and features are set upstream by manufacturers, and bundle each product with a service of their own: maintenance, repairs or a warranty. The dealer's short-term problem is then purely combinatorial. Which products should be carried, and which of them should come with a long…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Product Price, Quality and Service Decisions under Consumer Choice Models IV: Under the Two-Stage Nested Logit Model, Qualities Are Set Product by Product and Markups Are Nest-InvariantResearch Paper

A firm that sells durable products with an attached service (a warranty, a maintenance plan, a support contract) chooses three things for each product: its price, its quality, and how long the service lasts. Wang, Ke and Cui (SSRN 3766191, Manufacturing & Service Operations Management, 2022) study this joint decision when consumers choose among the products…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

On the tightness of SDP relaxations of QCQPs 1: Polyhedral Γ and Large Shared Zero Eigenspaces on Semidefinite Faces Give conv(D) = D_SDP and Opt = Opt_SDPResearch Paper

Quadratically constrained quadratic programs (QCQPs) minimize a quadratic function subject to quadratic inequality and equality constraints. They model facility location, pooling, max-cut, trust-region steps and robust optimization problems, and every {0,1}\{0,1\}{0,1} integer program can be written as one; in general they are NP-hard. The standard tractable approach…

16 thms3 active usersReviewed
🏆Completed
Convex OptimizationDynamical SystemsOptimization·Captain: mikedeng1

Understanding the Acceleration Phenomenon via High-Resolution Differential Equations IV: The High-Resolution Heavy-Ball ODE Satisfies f(X(t)) − f(x⋆) ≤ 7‖x₀ − x⋆‖² e^(−√μ t/4)/(2s)Research Paper

Polyak's heavy-ball method and Nesterov's accelerated gradient method for strongly convex functions (NAG-SC) are the two classical momentum methods of smooth convex optimization. With step size sss and momentum α=(1−μs)/(1+μs)\alpha=(1-\sqrt{\mu s})/(1+\sqrt{\mu s})α=(1−μs​)/(1+μs​) they differ only by a gradient-correction term, yet NAG-SC is accelerated for every μ\muμ-strongly convex, LLL-smo…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOptimization·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 6: Nesterov's Method Has ℒ_k ≤ ℒ₀·min{4L/(√γ₀k + 2√L)², (1 − √(min{γ₁, μ}/L))^k}Research Paper

Nesterov's accelerated gradient method minimises a smooth convex function fff to accuracy ε\varepsilonε in O(L/ε)O(\sqrt{L/\varepsilon})O(L/ε​) gradient evaluations, and a μ\muμ-strongly convex one in O(L/μ log⁡(1/ε))O(\sqrt{L/\mu}\,\log(1/\varepsilon))O(L/μ​log(1/ε)); both counts match the lower bounds for first-order methods. Nesterov's own analysis (Y. Nesterov, Introductory Lectures on Convex…

9 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

Douglas-Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results III: ADMM Is Douglas-Rachford Splitting on the Image-Function Problem, for Every RelaxationResearch Paper

The alternating direction method of multipliers (ADMM) solves linearly constrained problems

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOptimization·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 4: The Predictor–Corrector Scheme Has ℒ_k ≤ ℒ₀·min{4L/(√γ₀k + 2√L)², (1 + √(min{γ₀, μ}/L))^(−k)}Research Paper

Nesterov's accelerated gradient method minimises a smooth convex function fff to accuracy ε\varepsilonε in O(1/ε)O(1/\sqrt{\varepsilon})O(1/ε​) gradient evaluations, and a μ\muμ-strongly convex one in O(L/μlog⁡(1/ε))O(\sqrt{L/\mu}\log(1/\varepsilon))O(L/μ​log(1/ε)), which is optimal for first-order methods. The method's original derivation by estimate sequences gives little insight into why it…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOptimization·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 3: The Implicit Scheme Gives ℒ_{k+1} ≤ ℒ_k/(1 + α_k) for Every μ-Convex f and Every Step α_k > 0Research Paper

Accelerated first-order methods, beginning with Nesterov's 1983 scheme, reach the optimal iteration complexity among gradient methods for smooth convex minimization, but their classical derivations ("estimate sequences") give little insight into why acceleration works. A line of work started by Su, Boyd and Candès (arXiv:1503.01243) reads accelerated…

10 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOptimization·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 5: The Gradient-Corrected Scheme Contracts ℒ_k by 1/(1 + α_k) and Has the Rate of Theorem 5.1Research Paper

Nesterov's accelerated gradient method minimises a smooth convex function fff to accuracy ε\varepsilonε in O(1/ε)O(1/\sqrt{\varepsilon})O(1/ε​) gradient evaluations, against O(1/ε)O(1/\varepsilon)O(1/ε) for plain gradient descent, and this rate is optimal for first-order methods (Nesterov 2018). The method is usually presented through estimate sequences, which certify the rate but say…

10 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

Douglas-Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results V: The Image Function (Af) Is Smooth Under Relative Smoothness, Lipschitz Minimizers, or ConvexityResearch Paper

The alternating direction method of multipliers (ADMM) solves problems of the form min⁡{f(x)+g(z)∣Ax+Bz=b}\min\{f(x)+g(z)\mid Ax+Bz=b\}min{f(x)+g(z)∣Ax+Bz=b} and is a standard tool in signal processing, statistics and distributed optimization (Boyd et al., 2011). For convex problems ADMM is known to be the Douglas–Rachford splitting (DRS) applied to a dual problem. Themelis and Patrinos (arXiv:1709.057…

11 thms3 active usersReviewed
🏆Completed
Convex OptimizationDynamical SystemsNumerical Analysis+1·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 2: The NAG Flow Has a Unique C² Solution and Its Lyapunov Function Satisfies ℒ(t) ≤ e^(−t)ℒ(0)Research Paper

Accelerated first-order methods, above all Nesterov's accelerated gradient (NAG) method, minimize a convex function with an LLL-Lipschitz gradient to accuracy ε\varepsilonε in O(L/ε)O(\sqrt{L/\varepsilon})O(L/ε​) gradient evaluations, and a μ\muμ-strongly convex one in O(L/μlog⁡(1/ε))O(\sqrt{L/\mu}\log(1/\varepsilon))O(L/μ​log(1/ε)), against O(L/ε)O(L/\varepsilon)O(L/ε) and O((L/μ)log⁡(1/ε))O((L/\mu)\log(1/\varepsilon))O((L/μ)log(1/ε)) for gradient…

11 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

Douglas-Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results II: No Stepsize Above 1/L Guarantees a Vanishing DRS ResidualResearch Paper

Douglas–Rachford splitting (DRS) minimizes a sum φ1+φ2\varphi_1+\varphi_2φ1​+φ2​ by alternating between the proximal mappings of the two terms. It is one of the most used first-order methods in signal processing, statistics and control, and, through its dual interpretation, it is the engine behind the alternating direction method of multipliers (ADMM). For convex…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationDynamical SystemsOptimization·Captain: mikedeng1

Understanding the Acceleration Phenomenon via High-Resolution Differential Equations III: The High-Resolution ODE of NAG-SC Satisfies f(X(t)) − f(x⋆) ≤ 2‖x₀ − x⋆‖² e^(−√μ t/4)/sResearch Paper

Nesterov's accelerated gradient method for μ\muμ-strongly convex, LLL-smooth functions (NAG-SC) reaches accuracy ε\varepsilonε in O(L/μlog⁡(1/ε))O(\sqrt{L/\mu}\log(1/\varepsilon))O(L/μ​log(1/ε)) gradient steps, against O((L/μ)log⁡(1/ε))O((L/\mu)\log(1/\varepsilon))O((L/μ)log(1/ε)) for gradient descent (Nesterov, 1983; Nesterov, 2004). Polyak's heavy-ball method has the same accelerated behaviour on quadratics but not in…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

The Bayesian Prophet: A Low-Regret Framework for Online Decision Making: Constant Regret of the Fluid Bayes Selector for the Multi-Secretary ProblemResearch Paper

In online allocation, requests arrive one at a time and each must be accepted or rejected on arrival, using a limited budget of resources. Revenue management, ad allocation and hiring all fit this pattern. A natural benchmark for an online policy is the prophet, or Offline: the decision maker who sees the whole arrival sequence in advance and acts optimally…

9 thms3 active usersReviewed
🏆Completed
AnalysisOperations Research·Captain: mikedeng1

Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios IV: The Tight Ratio 1 − e^{−α⁽¹⁾} Exceeds (1 − 1/e)σ⁽¹⁾ and the Price-Continuum RatioResearch Paper

In online matching with multiple prices, a firm sells nnn items with limited inventories to customers who arrive one at a time; each item can be offered at any price from its own finite price set, and the firm must commit to an offer without knowing future customers. Ma and Simchi-Levi (arXiv:1905.04770, Oper. Res. 2020) show that the best possible competitive…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraNumerical Analysis+1·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 1: Gauss–Seidel Splitting of the HB and NAG Transforms Has ρ(E(α, G)) ≤ 1/√(1 + 2α) If 0 < α ≤ 2/√κ(A)Research Paper

Accelerated first-order methods, the heavy-ball method of Polyak and Nesterov's accelerated gradient (NAG) method, reach an error ε\varepsilonε on a μ\muμ-strongly convex, LLL-smooth problem in O(κlog⁡(1/ε))O(\sqrt{\kappa}\log(1/\varepsilon))O(κ​log(1/ε)) gradient steps, κ=L/μ\kappa=L/\muκ=L/μ, against O(κlog⁡(1/ε))O(\kappa\log(1/\varepsilon))O(κlog(1/ε)) for plain gradient descent. A long line of work has tried to explain…

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

Operator Splitting for a Homogeneous Embedding of the Linear Complementarity Problem: The Embedding Operator Q = F ∪ I of a Monotone LCP Is Maximal MonotoneResearch Paper

Many problems in optimization reduce to a linear complementarity problem over a cone: convex quadratic programs, linear and second-order cone programs, and more generally the KKT systems of convex quadratic cone programs (QCPs). First-order solvers for these problems, such as SCS (O'Donoghue–Chu–Parikh–Boyd 2016), must return either a solution or a…

10 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOptimization·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 8: Semi-AFB for min over Q of h + g Contracts ℒ_k by 1/(1 + α_k) and Has the Rate of Theorem 5.1Research Paper

Many convex problems in signal processing, statistics and control have the composite form "smooth loss plus nonsmooth regulariser, subject to a simple constraint": a least-squares or entropy term hhh, a sparsity or total-variation penalty ggg, and a feasible set QQQ such as a box, a simplex or a cone. Accelerated proximal gradient methods (FISTA, Beck and…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOperations Research+1·Captain: mikedeng1

Sinkhorn Distributionally Robust Optimization 2: Biased Stochastic Mirror Descent with SG or RT-MLMC Subgradient Estimators Reaches a δ-Optimal SolutionResearch Paper

Sinkhorn distributionally robust optimization (Wang, Gao and Xie, arXiv:2109.11926) hedges a learning or decision problem against distribution shift. It minimizes the worst-case expected loss over all distributions within an entropically regularized optimal-transport distance (the Sinkhorn distance) of a nominal distribution P^\widehat{\mathbb P}P. Strong…

10 thms3 active usersReviewed
PreviousPage 70 of 193Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5197499
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36595448
5NINickrobbins953288156
6VEvebis25800
7FIfizzyinc321715
8SHshivm17500
9SCShuze Chen9455324
10KMkmehltretter82925261

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