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

626–650 of 4812
Open1285Completed3527All4812
🏆Completed
Experimental DesignOperations ResearchProbability+1·Captain: mikedeng1

Pigeonhole Design: Balancing Sequential Experiments from an Online Matching Perspective 1: With T^η Uniform Pigeonholes on [0,1] the Expected Discrepancy Is O(T^(1/2−η/2) + T^(η/2)(log T)^(1/2))Research Paper

Online platforms run controlled experiments in which subjects (users, sessions, sellers) arrive one at a time and must be assigned to control or treatment on arrival, before later subjects are seen. A good design makes the two groups look alike in their observed covariates, because covariate imbalance inflates the variance of treatment-effect estimates.…

14 thms4 active usersReviewed
🏆Completed
EconomicsOperations ResearchOptimization·Captain: mikedeng1

Capturing the Benefits of Autonomous Vehicles in Ride-Hailing: The Role of Market Configuration 1: A Pure Human-Driver Market Has a Unique Maximal Stable Equilibrium, Increasing in Market SizeResearch Paper

Ride-hailing platforms match riders with drivers who choose for themselves whether to work. Autonomous vehicles (AVs) would replace part of this self-scheduling labor with capital whose fleet size the platform chooses. Lian and van Ryzin study when, and under which market configuration, the cost savings of AVs reach riders. Their comparison needs a…

18 thms4 active users
🏆Completed
EconomicsOperations ResearchOptimization·Captain: mikedeng1

The Bright Side of the GDPR: Welfare-Improving Privacy Management II: A Firm with Small Data-Based Revenue Earns More Profit After the GDPRResearch Paper

The European Union's General Data Protection Regulation (GDPR, 2018) requires a firm to obtain a consumer's explicit consent before it collects personal data. The common expectation, in policy debate and in much of the empirical literature, is that consent requirements cost firms money: they shrink the pool of consumer data that can be monetized through…

11 thms4 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Rank-Based Stochastic Differential Inclusions and Diffusion Limits for a Load-Balancing Model: Diffusion-Scaled Queue Lengths and Idle Times Converge to the Reflected Rank-Based DiffusionResearch Paper

Randomized load balancing assigns arriving jobs to one of several parallel servers using only partial information about queue lengths. The best-known example is the power-of-choice rule: sample ℓ\ellℓ of the NNN queues and join the shortest. Such rules are used in large server farms because the dispatcher communicates with only a few servers per job. The case…

22 thms4 active usersReviewed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: mikedeng1

Thompson Sampling with Information Relaxation Penalties I: For Natural Exponential Families the Suboptimality Gaps of TS, IRS.FH and IRS.V-Zero Are at Most 2√L[1/√ν + √(2 log T)(K/√ν + 2√(KT))]Research Paper

Thompson sampling (TS) is the most widely used heuristic for Bayesian multi-armed bandits: at each step it samples a parameter from the current posterior and plays the arm that is best for the sample. Its Bayesian regret has been analysed extensively (Russo and Van Roy, 2014; Bubeck and Liu, 2013). Min, Maglaras and Moallemi (arXiv:1902.04251) place TS…

9 thms4 active usersReviewed
🏆Completed
EconomicsOperations ResearchOptimization·Captain: mikedeng1

The Bright Side of the GDPR: Welfare-Improving Privacy Management I: The Equilibrium Price Is Higher After the GDPR for Every Opt-in Benefit and Data RevenueResearch Paper

The European Union's General Data Protection Regulation (GDPR, in force since 2018) requires a firm to obtain a consumer's explicit opt-in consent before it collects her personal data. Most of the economic literature reads such consent rules as a cost to data-driven firms. Choe, Matsushima and Shekhar (ISER Discussion Paper No. 1246, Osaka University, June…

10 thms4 active usersReviewed
🏆Completed
EconomicsOperations ResearchOptimization·Captain: mikedeng1

Asset Pricing with Costly Short Sales 2: With One Risky Asset the Equilibrium Shorting Cost and Lending Yield Are Explicit, Increasing and Convex in the Belief GapResearch Paper

Short selling is never free. To sell a share short, an investor borrows it from a holder and pays that holder a lending fee, and the size of these fees has been documented empirically for decades (D'Avolio 2002; Duffie, Gârleanu and Pedersen 2002). Most equilibrium models of asset pricing either forbid short sales or take the fee as exogenous. Evgeniou,…

9 thms4 active usersReviewed
🏆Completed
EconomicsOperations ResearchOptimization·Captain: mikedeng1

Advance Selling and Upgrading in Priority Queues: With Only Online Customers, Upgrading Raises the Optimal Revenue Exactly When Bₛ − Bₐ > α(p(λₕ) − p(λₗ))Research Paper

Amusement parks and similar attractions sell two kinds of ticket for the same ride: a regular ticket, which joins a first-come-first-served queue, and a fast-track ticket, which joins a separate queue served with non-preemptive priority. Increasingly these tickets are sold online in advance, before the customer knows whether the park will be crowded on the…

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

A Soft Robust Model for Optimization Under Ambiguity: For Every δ > 0, Soft Robust Feasibility Is a Convex Risk Measure Constraint, and Every Normalized Convex Risk Measure Arises This WayResearch Paper

Optimization under uncertainty usually fixes one probability distribution P\mathbb PP for the uncertain data and optimizes an expected payoff, or fixes a set Q\mathcal QQ of distributions and protects against the worst one (robust optimization). The first is sensitive to a misspecified P\mathbb PP; the second can be very conservative, because it treats a barely…

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

Stochastic Dual Dynamic Integer Programming 3: The Convex Lower Envelope of a Function on {0,1}^n Is Piecewise Linear and Agrees with It at Every Binary PointResearch Paper

Multistage stochastic integer programs model sequential decisions under uncertainty in which some decisions are discrete: unit commitment in power systems, capacity expansion, production planning with setups. The standard decomposition methods for multistage stochastic linear programs, nested Benders decomposition and stochastic dual dynamic programming…

9 thms4 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability+1·Captain: mikedeng1

Learning Unknown Service Rates in Queues 3: In Heavy Traffic Every α-Consistent Scheduling Policy Has Average Queue-Regret at Least D(μ)(K−1) log t / (4 log log t) Up to Time (K−1)D(μ)/(4ε)Research Paper

A switch network is a set of UUU queues served by K≥UK\ge UK≥U servers. In every time slot each server can serve at most one queue, so a scheduler must pick a matching of queues to servers. Such systems model input-queued packet switches, crowdsourcing platforms that route job types to worker types, and wireless links with unknown channel quality. When the success…

10 thms4 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability+1·Captain: mikedeng1

Learning Unknown Service Rates in Queues 1: Every α-Consistent Scheduling Policy Has Average Queue-Regret at Least λ_min D(μ)(1−α)(K−1)/(8t) for Infinitely Many tResearch Paper

Many service systems must route work to servers whose quality is not known in advance: crowdsourcing platforms matching job types to worker types, wireless schedulers assigning users to channels, call centers routing request classes to agent pools. Learning the unknown service rates is a multi-armed bandit problem, but the cost of a bad decision is not a…

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

Shortest Paths in Graphs of Convex Sets II: For Compact 𝒳 the Set-Based Relaxation 𝒮′ of Z = xyᵀ Is Exact at Every Extreme Point of a Polytope 𝒴Research Paper

The shortest-path problem in a graph of convex sets (SPP in GCS), introduced by Marcucci, Umenberger, Parrilo and Tedrake (arXiv:2101.11565, SIAM J. Optim. 2024), asks for a path through a directed graph whose vertices carry convex sets, together with a point in each visited set, minimizing a sum of convex edge lengths. It models motion planning around…

12 thms4 active usersReviewed
🏆Completed
Control TheoryConvex OptimizationLinear algebra+1·Captain: mikedeng1

Quadratic Matrix Inequalities with Applications to Data-Based Control IV: Noisy Data Are Informative for Quadratic Stabilization iff an LMI in (P, L, β) Is FeasibleResearch Paper

Data-driven control asks for a controller computed directly from measured trajectories of an unknown system, without first identifying a model. When the measurements are corrupted by unknown process noise, many systems explain the same data, and a controller designed from the data alone is only trustworthy if it stabilizes every one of them. Van Waarde,…

17 thms4 active usersReviewed
🏆Completed
Convex OptimizationDynamic ProgrammingOperations Research+1·Captain: mikedeng1

On the Convergence of Decomposition Methods for Multistage Stochastic Convex Programs 1: Deterministic Cutting-Plane Bellman Approximations Become Exact Along the Generated TrajectoriesResearch Paper

Multistage stochastic programs model sequential decisions under uncertainty: hydro-thermal scheduling, inventory and capacity planning, portfolio management. The dominant solution methods, Stochastic Dual Dynamic Programming (SDDP, Pereira and Pinto 1991) and its relatives CUPPS and DOASA, never compute the Bellman (future-cost) functions of the problem.…

12 thms4 active usersReviewed
🏆Completed
Control TheoryConvex OptimizationLinear algebra+1·Captain: mikedeng1

Quadratic Matrix Inequalities with Applications to Data-Based Control I: Nonemptiness, Convexity, Boundedness and Interior of QMI Solution SetsResearch Paper

Quadratic matrix inequalities (QMIs) describe sets of matrices rather than sets of vectors. They appear whenever an unknown matrix is constrained by a quadratic bound: in robust control, where an uncertain block of a system is only known to lie in a norm ball or a sector, and in data-driven control, where the system matrices (A,B)(A, B)(A,B) of a linear system …

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

On the tightness of SDP relaxations of QCQPs 3: Quadratic Eigenvalue Multiplicity k ≥ m + 2 Gives conv(D) = D_SDP Without PolyhedralityResearch 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 binary programs, max-cut, the trust-region subproblem and many problems in signal processing and control. A standard convex approximation is the Shor semidefinite…

11 thms4 active usersReviewed
🏆Completed
Dynamical SystemsLinear algebra·Captain: mikedeng1

Sub/Super-Stochastic Matrix with Applications to Bipartite Tracking Control over Signed Networks 2: Chains to the Rows of Sum ≥ 1 of a Super-Stochastic F Give ρ(F) < 1 under Condition (2.5)Research Paper

Discrete-time linear iterations x(k+1)=Fx(k)x(k+1)=Fx(k)x(k+1)=Fx(k) with entrywise nonnegative FFF appear wherever a quantity is redistributed along the edges of a network: consensus and tracking protocols for multi-agent systems, positive switched systems, and Markov-type averaging schemes. Such an iteration converges to zero exactly when the spectral radius ρ(F)\rho(F)ρ(F), the largest…

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

Understanding the Acceleration Phenomenon via High-Resolution Differential Equations II: NAG-C Minimizes the Squared Gradient Norm at the Inverse Cubic Rate 8568‖x₀ − x⋆‖²/(s²(k + 1)³)Research Paper

Nesterov's accelerated gradient method for smooth convex objectives, here called NAG-C, reaches function-value accuracy O(L∥x0−x⋆∥2/k2)O(L\|x_0-x^\star\|^2/k^2)O(L∥x0​−x⋆∥2/k2) after kkk gradient evaluations, which is optimal among first-order methods (Nesterov 1983; Nesterov 2004). In many uses the quantity of interest is not the function gap but the squared gradient norm …

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

Understanding the Acceleration Phenomenon via High-Resolution Differential Equations I: NAG-SC with Step Size 1/(4L) Satisfies f(xₖ) − f(x⋆) ≤ 5L‖x₀ − x⋆‖²/(1 + √(μ/L)/12)ᵏResearch Paper

Nesterov's accelerated gradient method is the standard example of a first-order method that is provably faster than gradient descent. On a μ\muμ-strongly convex function with LLL-Lipschitz gradient, gradient descent reduces the objective gap by a factor 1−O(μ/L)1-O(\mu/L)1−O(μ/L) per step, while the accelerated method achieves 1−O(μ/L)1-O(\sqrt{\mu/L})1−O(μ/L​), the best possible rate for…

11 thms4 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOptimization·Captain: mikedeng1

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

Many problems in signal processing, statistics and control are posed as composite convex minimisation: minimise f=h+gf = h + gf=h+g, where hhh is smooth and ggg is convex but possibly nonsmooth or extended-valued (an ℓ1\ell^1ℓ1 penalty, a nuclear norm, the indicator of a constraint set). Proximal gradient methods handle ggg through its proximal operator and hhh through its…

10 thms4 active usersReviewed
🏆Completed
Linear algebra·Captain: mikedeng1

Sub/Super-Stochastic Matrix with Applications to Bipartite Tracking Control over Signed Networks 1: Chains to the Unit Rows of a Sub-Stochastic F Give ρ(F) ≤ (1 − (1 − α₁)α₂^|C*|)^(1/(|C*|+1)) < 1Research Paper

In distributed control, many convergence questions come down to one test: is the spectral radius of a nonnegative iteration matrix strictly below one? Consensus and tracking protocols for multi-agent systems (MASs) produce such matrices. The agents that hear the leader directly give rows whose sum is below one, and the agents that only average their…

8 thms4 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization: With Small Stepsizes the Smoothed Proximal ADMM Iterates Approach the KKT SetResearch Paper

The alternating direction method of multipliers (ADMM) and the closely related augmented Lagrangian method are workhorses for linearly constrained optimization: they split a problem into cheap primal steps and a dual (multiplier) update, and they scale to large and distributed instances (Boyd et al., 2011). For convex objectives their convergence theory is…

18 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability+1·Captain: mikedeng1

Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios II: In the Deterministic Case Multi-price Ranking Is minᵢ F(𝒫ᵢ)-CompetitiveResearch Paper

Online matching models a platform that must commit resources to requests as they arrive, without knowing the future. In revenue management the resources are items in limited supply and the requests are customers, and the firm also chooses the price. Ma and Simchi-Levi (arXiv:1905.04770, Oper. Res. 2020, DOI 10.1287/opre.2019.1957) give algorithms whose…

9 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization+1·Captain: mikedeng1

Distributed Stochastic Gradient Tracking Methods II: With Stepsizes θ/(m+k), DSGT's Mean-Square Error Is at Most 2θ²σ²/(n(θμ−1)(m+k)) Plus Higher-Order TermsResearch Paper

Many learning and estimation problems are solved by a group of computing agents that each hold part of the data and can talk only to their neighbours in a communication network. Each agent iii has a private cost fif_ifi​, and the group wants a minimizer of the average f=1n∑ifif=\frac1n\sum_i f_if=n1​∑i​fi​ without a central coordinator. In machine learning the agents usually cannot…

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