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.

3528 completed missions

Missions

1876–1900 of 3528
Open1284Completed3528All4812
🏆Completed
Convex OptimizationMachine LearningOptimization+1·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity XVI: Random Coordinate Descent RCD(γ) on a Strongly Convex Coordinate-Smooth Function Has Rate (1 − 1/κ_γ)^tTextbook

When a problem has millions of variables, even one full gradient can be too expensive to compute, while a single partial derivative ∂f/∂xi\partial f/\partial x_i∂f/∂xi​ is often cheap: in regularized regression, support vector machines and many structured problems, updating one coordinate costs a small fraction of a full gradient step. Coordinate descent methods exploit…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization+1·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity XIV: Stochastic Mirror Descent on a β-Smooth Function with Noise σ Has Rate Rσ√(2/t) + βR²/tTextbook

Many optimization problems in statistics and machine learning ask to minimize an expected loss f(x)=Eξ ℓ(x,ξ)f(x)=\mathbb E_\xi\,\ell(x,\xi)f(x)=Eξ​ℓ(x,ξ), or an average f(x)=1m∑i=1mfi(x)f(x)=\frac1m\sum_{i=1}^m f_i(x)f(x)=m1​∑i=1m​fi​(x) over a large data set. Exact gradients of such an fff are unavailable or too expensive, but unbiased random estimates are cheap: the gradient of the loss at one sample, or of one randomly…

6 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity XII: Mirror Prox on a Convex β-Smooth Function Has Rate βR²/(ρt)Textbook

First-order methods for constrained convex optimization are usually analysed in the Euclidean norm, where gradient descent and its projected and accelerated variants have well-understood rates. Many constraint sets of practical interest, such as the probability simplex, the ℓ1\ell_1ℓ1​ ball and the spectrahedron, are poorly adapted to the Euclidean geometry: the…

8 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Online Primal-Dual Algorithms for Covering and Packing 1: The Online Fractional Packing Scheme Is B-Competitive and Violates Each Packing Constraint by at Most 2 log(1 + n·a_i(max)/a_i(min))/BResearch Paper

Many resource-allocation problems arrive one request at a time and must be answered immediately: a bandwidth request is admitted or refused when it appears, an advertiser's budget is charged when a query arrives, a job is accepted before later jobs are seen. Their linear-programming relaxations are packing problems: maximize a total profit subject to…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity XI: Mirror Descent with a ρ-Strongly Convex Mirror Map Has Rate RL√(2/(ρt))Textbook

The projected subgradient method of Chapter 3 measures distances in the Euclidean norm, and its rate RL/tRL/\sqrt tRL/t​ depends on the geometry only through a Euclidean radius RRR and a Euclidean bound LLL on the subgradients. For many constraint sets that occur in practice this is the wrong geometry. On the probability simplex Δn\Delta_nΔn​ with subgradients bounded in …

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity X: Nesterov's Accelerated Gradient Descent on a β-Smooth α-Strongly Convex Function Has Rate ((α + β)/2)‖x₁ − x*‖² exp(−(t − 1)/√κ)Textbook

First-order methods, which query only function values and gradients, are the workhorse of large-scale optimization in machine learning, signal processing and operations research, because each step costs little more than one gradient evaluation. For a function that is both strongly convex and smooth, plain gradient descent converges geometrically, but the…

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

Convex Optimization: Algorithms and Complexity IX: Nesterov's Accelerated Gradient Descent on a Convex β-Smooth Function Has Rate 2β‖x₁ − x*‖²/t²Textbook

Minimizing a convex function f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R whose gradient is Lipschitz is the basic problem of first-order optimization, and it is the regime in which most large-scale methods of machine learning, signal processing and operations research are analysed. The natural method, gradient descent, reaches accuracy ε\varepsilonε after O(1/ε)O(1/\varepsilon)O(1/ε) gradi…

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

Convex Optimization: Algorithms and Complexity VIII: No Black-Box Method Beats 3β‖x₁ − x*‖²/(32(t + 1)²) on β-Smooth Convex FunctionsTextbook

Upper bounds for an optimization method say how fast it converges; oracle complexity lower bounds say how fast any method of a given kind can possibly converge. Chapter 3 of S. Bubeck, Convex Optimization: Algorithms and Complexity (Foundations and Trends in Machine Learning 8(3–4), 2015, arXiv:1405.4980) proves upper bounds for subgradient descent on…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimal TransportOptimization+1·Captain: mikedeng1

Quantifying Distributional Model Risk via Optimal Transport 1: Strong Duality — the Worst-Case Expectation over an Optimal-Transport Ball on a Polish Space Equals Its Dual over (λ, φ)Research Paper

A probability model μ\muμ for a random element XXX is rarely known exactly. Distributionally robust performance analysis replaces the single expectation Eμ[f(X)]E_\mu[f(X)]Eμ​[f(X)] by its worst case over all models within a prescribed distance of μ\muμ. When the distance is an optimal-transport cost, the neighbourhood contains models whose support differs from that of μ\muμ. That…

19 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

A Robust Optimization Approach to Inventory Theory: The Optimal Robust Policy Is the Optimal Nominal Policy for an Explicit Modified Demand, at Extra Cost (2ph/(p+h))·ΣA_kResearch Paper

Classical inventory theory chooses order quantities against a probability distribution of demand. The resulting dynamic programs are optimal in expectation but need the distribution, and they become intractable once several installations, capacities or fixed costs interact. Robust optimization replaces the distribution by an uncertainty set and asks for the…

12 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Airline Seat Allocation with Multiple Nested Fare Classes 2: With Integer-Valued Demands an Optimal Integer Protection-Level Policy ExistsResearch Paper

Airlines sell the seats of one flight leg at several prices. Cheaper fare classes tend to book earlier, so the seller must decide, as low-fare requests arrive, how many seats to hold back for later and more valuable passengers. The standard control is nested protection levels: a number pkp_kpk​ of seats is reserved for the kkk most expensive classes together, and…

70 thms3 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Rademacher and Gaussian Complexities: Risk Bounds and Structural Results 6: The Expected Maximum Discrepancy Lies Between R_n(F)/2 − 2√(2/n) and R_n(F) + 4√(2/n)Research Paper

Data-dependent risk bounds in statistical learning theory control the gap between the expected loss of a learned function and its empirical loss by a complexity penalty that is computed from the training data. The first such penalties were the maximum discrepancy of a function class (Bartlett, Boucheron and Lugosi, Model selection and error estimation,…

10 thms3 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Rademacher and Gaussian Complexities: Risk Bounds and Structural Results 5: Kernel Expansions with α′Kα ≤ B² Have Rademacher and Gaussian Complexity at Most 2B√(E k(X,X)/n)Research Paper

Kernel methods, such as support vector machines, predict with functions of the form x↦∑iαik(x,xi)x \mapsto \sum_i \alpha_i k(x, x_i)x↦∑i​αi​k(x,xi​): finite expansions of a fixed similarity function kkk centred at data points. Their statistical behaviour is governed by the size of the class of such expansions that the method searches. Bartlett and Mendelson, in Rademacher and Gaussian…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey 4: Under Sennott's Conditions an Average-Cost Optimal Stationary Policy ExistsResearch Paper

Many controlled queueing, inventory and maintenance systems are modelled as controlled Markov processes (CMPs) on a countable state space whose one-stage cost grows without bound: the holding cost of a queue grows with its length. For such systems the natural performance measure is the long-run average cost, and the basic question is whether some simple…

11 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchProbability+1·Captain: mikedeng1

Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms III: With One Unknown Parameter, Staged Re-estimation Has Regret O((log log n)(log n)^{1/2}/n^{1/2})Research Paper

A seller with a fixed stock of a single product and a finite selling season must post prices without knowing how demand responds to price. Revenue management treats this as a constrained stochastic control problem; with the demand curve known, the problem was solved by Gallego and van Ryzin (Management Science, 1994). When the curve is unknown, every price…

15 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

On the Approximability of Single-Machine Scheduling with Precedence Constraints 1: A k-Fold Realizer of Size t Yields a Vertex Cover of Expected Weight at Most (2 − 2/(t/k)) Times OptimalResearch Paper

Single-machine scheduling with precedence constraints, written 1∣prec∣∑wjCj1|\mathrm{prec}|\sum w_jC_j1∣prec∣∑wj​Cj​ in the notation of Graham et al., asks for an order of nnn weighted jobs on one machine that respects a given partial order and minimizes the weighted sum of completion times. The problem is strongly NP-hard (Lawler 1978; Lenstra and Rinnooy Kan 1978), and closing its…

10 thms3 active usersReviewed
🏆Completed
Algebraic GeometryComplexity TheoryLinear Optimization+2·Captain: mikedeng1

Log-Barrier Interior Point Methods Are Not Strongly Polynomial 1: Every Polygonal Curve in the Wide Neighborhood of the Central Path of LW_r(t) from μ̄ ≤ 1 to μ̄ ≥ t² Has at Least 2^(r−1) SegmentsResearch Paper

Interior point methods solve linear programs in a number of arithmetic operations polynomial in the bit length of the input (Karmarkar 1984). Whether linear programming admits a strongly polynomial algorithm, one whose number of arithmetic operations is bounded by a polynomial in the number of variables and constraints alone, is open; it is the ninth of…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchProbability+1·Captain: mikedeng1

Data-Driven Robust Optimization V: The Order-Statistic Box U^M Built from Marginal Samples Dominates Value at Risk with Probability at Least 1 − αResearch Paper

Robust optimization replaces an uncertain constraint f(u~,x)≤0f(\tilde{\mathbf u},\mathbf x)\le 0f(u~,x)≤0 by the requirement that it hold for every u\mathbf uu in an uncertainty set U⊆Rd\mathcal U\subseteq\mathbb R^dU⊆Rd. The resulting problems are tractable for many sets, but the choice of U\mathcal UU decides whether the solution means anything probabilistically. Bertsimas, Gupta and…

11 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

On the Power and Limitations of Affine Policies in Two-Stage Adaptive Optimization V: The Optimal First Stage over a Dominating Simplex Is a 4√m-ApproximationResearch Paper

Two-stage adaptive optimization models decisions taken in two steps: a first-stage decision xxx is fixed before an uncertain right-hand side bbb is revealed, and a second-stage decision y(b)y(b)y(b) is chosen afterwards, with the worst case over an uncertainty set U\mathcal UU to be minimized. Problems of this form arise in capacity planning, network design and inventory…

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

Constructing Uncertainty Sets for Robust Linear Optimization 3: The Largest Centrally Symmetric Distortion Inner Approximation of a Polytope Solves a Linear ProgramResearch Paper

A robust linear constraint a′x≥ba'x \ge ba′x≥b for all a∈Ua \in \mathcal Ua∈U protects a decision xxx against every realization of the data aaa in an uncertainty set U\mathcal UU. Robust optimization took this form in the work of Ben-Tal and Nemirovski (Math. Oper. Res. 1998; Oper. Res. Lett. 1999), where U\mathcal UU is chosen by the modeller. Bertsimas and Brown (Oper. Res. 2009)…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons 3: With a Discrete Price Set the Two-Price Stopping-Time Heuristic Is Asymptotically OptimalResearch Paper

Airlines, hotels and cruise lines rarely change prices continuously. They sell a fixed product (seats on one flight, rooms on one night) over a finite selling season, and they sell it at a small set of fares, opening and closing fare classes as the season unfolds. Gallego and van Ryzin, in Optimal Dynamic Pricing of Inventories with Stochastic Demand over…

11 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear algebraOperations Research·Captain: mikedeng1

On the Abstract Properties of Linear Dependence 4: Orthogonal Subspaces Have Dual MatroidsResearch Paper

Hassler Whitney introduced matroids in On the Abstract Properties of Linear Dependence (Amer. J. Math. 57, 1935, doi:10.2307/2371182) to capture what linear dependence among the columns of a matrix and the circuit structure of a graph have in common. One of the central constructions of the paper is duality. For graphs, duality exists only for planar graphs…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research·Captain: mikedeng1

Robust Solutions of Uncertain Linear Programs II: With Ellipsoidal Uncertainty the Robust Counterpart Is Equivalent to a Conic Quadratic ProgramResearch Paper

The data of a linear program are often not known exactly: they are measured or estimated, or they are forecasts. The robust counterpart approach, going back to Soyster (1973), asks for a solution that is feasible for every data matrix in a prescribed uncertainty set and is best among such solutions. Ben-Tal and Nemirovski's 1999 paper [1] showed that the…

9 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability·Captain: mikedeng1

Constructing Uncertainty Sets for Robust Linear Optimization 1: A Distortion Risk Constraint Equals a Robust Constraint over a Permutohull and an Explicit Linear SystemResearch Paper

Robust linear optimization replaces an uncertain constraint a~′x≥b\tilde a'x \ge ba~′x≥b by the requirement that a′x≥ba'x \ge ba′x≥b hold for every aaa in an uncertainty set U\mathcal UU (Ben-Tal and Nemirovski 1999). The method leaves open where U\mathcal UU should come from. Risk theory answers a related question from the other side: a decision maker's attitude to an uncertain…

11 thms3 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research·Captain: mikedeng1

Constructing Uncertainty Sets for Robust Linear Optimization 2: The Distortion Risk Measures with Centrally Symmetric Permutohulls Are the Mixtures of ⌊N/2⌋+1 GeneratorsResearch Paper

A linear decision made with uncertain coefficients can be protected by requiring the constraint to hold for every coefficient vector in an uncertainty set. Choosing that set determines how conservative the decision is. Bertsimas and Brown connect this choice to a risk measure: a functional that assigns a cost to the random reward left by a decision. Their…

6 thms3 active usersReviewed
PreviousPage 76 of 142Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5162497
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36595448
5NINickrobbins953286155
6VEvebis25800
7FIfizzyinc321725
8SHshivm17490
9SCShuze Chen9455324
10KMkmehltretter82896261

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