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.

3527 completed missions

Missions

626–650 of 3527
Open1285Completed3527All4812
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization II: If f = f₀ + Σf_k Is Quasiconvex and Hemivariate in Each Block, BCD Cluster Points Are Coordinatewise MinimaResearch Paper

Block coordinate descent (BCD), also called the nonlinear Gauss–Seidel method or alternating minimization, minimizes a function of several blocks of variables by exactly minimizing over one block at a time while the others are held fixed. It is used wherever the subproblem in a single block is cheap even though the joint problem is not: alternating least…

10 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Quantitative Stability in Stochastic Programming: The Method of Probability Metrics 1: Solution Sets Move by at Most Ψ of the Minimal Information DistanceResearch Paper

A stochastic program minimizes an expected cost under expected-value constraints, and the expectation is taken with respect to a probability distribution μ\muμ of the random data. In applications μ\muμ is rarely known: it is estimated from samples, replaced by a finite scenario tree, or chosen from a parametric family. Whether the optimal value and the optimal…

10 thms4 active usersReviewed
🏆Completed
Machine LearningOptimizationStatistics·Captain: mikedeng1

Additive Logistic Regression: A Statistical View of Boosting 1: The Exponential Criterion E[e^{−yF(x)}] Is Minimized at Half the Log-Odds ½ log[P(y=1|x)/P(y=−1|x)]Research Paper

AdaBoost (Freund and Schapire, 1996) combines many weak classifiers, such as small decision trees, into a single strong classifier by repeatedly reweighting the training data. In the late 1990s it was among the most accurate off-the-shelf classifiers, but why it worked was unclear. Friedman, Hastie and Tibshirani (Ann. Statist. 28 (2000) 337–407) gave a…

8 thms4 active usersReviewed
🏆Completed
Machine LearningOptimizationStatistics·Captain: mikedeng1

Additive Logistic Regression: A Statistical View of Boosting 5: J-Class LogitBoost Is the Base-Class-Averaged Diagonal Quasi-Newton Step on the Multinomial Log-LikelihoodResearch Paper

Boosting combines many weak classifiers into a strong one. Friedman, Hastie and Tibshirani (Ann. Statist. 28 (2000) 337–407) explained the two-class AdaBoost algorithms statistically: in the population, boosting fits an additive logistic regression model by stagewise optimization of a criterion on the log-odds scale. Section 5 of that paper carries the…

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

Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization I: On a Compact Level Set, Cluster Points of Essentially Cyclic BCD Are Stationary or Coordinatewise MinimaResearch Paper

Block coordinate descent (BCD), also called the nonlinear Gauss–Seidel method or alternating minimization, minimizes a function of several blocks of variables by minimizing over one block at a time with the others held fixed. It is used wherever the full problem is hard but each block subproblem is easy: proximal point methods, the Arimoto–Blahut algorithm…

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

Bounded Rationality in Newsvendor Models IV: Raising the Payoff Scale from λ₂ to λ₁ > λ₂ Strictly Raises the Expected Profit of a Logit Decision MakerResearch Paper

A standard way to coordinate a supply chain is to align incentives: contracts are written so that the retailer's profit is a fixed fraction λ\lambdaλ of the whole chain's profit. With buy-back terms b=(1−λ)pb=(1-\lambda)pb=(1−λ)p and wholesale price w=(1−λ)p+λcw=(1-\lambda)p+\lambda cw=(1−λ)p+λc, for instance, the retailer's profit is λπS(x)\lambda\pi_S(x)λπS​(x), where πS\pi_SπS​ is the chain's newsvendor profit.…

7 thms4 active users
🏆Completed
Convex OptimizationNumerical AnalysisOperations Research+1·Captain: mikedeng1

A Coordinate Gradient Descent Method for Nonsmooth Separable Minimization 3: The Local Lipschitzian Error Bound Holds for Polyhedral P with Quadratic or Composite f, and for Strongly Convex fResearch Paper

Many problems in statistics, signal processing and machine learning minimize the sum of a smooth function and a convex but nonsmooth one: ℓ1\ell_1ℓ1​-regularized least squares (the Lasso), bound-constrained problems, and group-sparse regression are standard examples. Tseng and Yun (Math. Program. Ser. B 117 (2009) 387–423) proposed the coordinate gradient…

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

An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm 2: τᵏ Stays Bounded Below If (LP) Has an Optimum, and Otherwise κᵏ Stays Bounded Below and τᵏ/θᵏ Is BoundedResearch Paper

Interior-point methods for linear programming are usually analysed under two assumptions: a strictly feasible starting point is known, and the problem has an optimal solution. In practice neither is known in advance. The homogeneous self-dual embedding of Ye, Todd and Mizuno (Math. Oper. Res. 19(1), 1994) removes both assumptions. It embeds a standard-form…

17 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: mikedeng1

On the Structure of Lost-Sales Inventory Models 2: The Optimal Lost-Sales Order Obeys the Karlin–Scarf–Morton Bounds z̄_t(v) ∈ Z(s̄) for All t ≤ TResearch Paper

In the periodic-review inventory system with lost sales and a positive lead time LLL, demand that cannot be met from stock is lost rather than backlogged. Unlike the backorder model, whose optimal policy is a base-stock policy depending only on the inventory position, the lost-sales model needs the whole pipeline of outstanding orders as its state, and its…

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

On the Relationship Between Inventory Costs and Variety Benefits in Retail Assortments II: Optimal Variety Rises with Price and Store Volume and Falls as the No-Purchase Preference VanishesResearch Paper

A retailer deciding how many variants of a product to carry (colours, sizes, flavours) faces a trade-off. A broader assortment captures customers whose favourite variant would otherwise be missing, but it splits demand into more, smaller streams, each of which needs its own safety stock. van Ryzin and Mahajan (Management Science 45(11), 1999) combine a…

9 thms4 active usersReviewed
🏆Completed
Machine LearningOperations ResearchTheoretical Computer Science·Captain: mikedeng1

The Weighted Majority Algorithm 9: With η Anomalies Every Randomized Learner Can Be Forced to ½ opt(F, 0) + η Expected MistakesResearch Paper

Prediction with expert advice asks a learner to predict a binary label on each of a sequence of trials, after seeing the predictions of a pool of candidate functions, and to make few more mistakes than the best member of the pool. Littlestone and Warmuth's The Weighted Majority Algorithm (Inform. and Comput. 108, 1994) gave the deterministic algorithm WM…

7 thms4 active usersReviewed
🏆Completed
AlgebraInformation TheoryTheoretical Computer Science·Captain: mikedeng1

Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data 3: Shingling plus PinSketch Gives an Average-Case Secure Sketch for Edit DistanceResearch Paper

Biometric readings, physical unclonable functions and typed passphrases share two defects as cryptographic keys: they are not uniformly distributed, and they are never reproduced exactly. Dodis, Ostrovsky, Reyzin and Smith (SIAM J. Comput. 38(1), 2008; preprint arXiv:cs/0602007v4) introduced the secure sketch to handle the second defect without destroying…

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

Monotone Comparative Statics III: f(x, t) + p·x Is Quasisupermodular with the Single Crossing Property for Every Price Vector p If and Only If f Is SupermodularResearch Paper

Monotone comparative statics asks when the optimal choice of an agent moves in a predictable direction as a parameter of the problem changes: does a firm hire more of every input when the output price rises, does a monopolist raise its price when its marginal cost rises? Topkis (1978) gave a cardinal answer: if the objective f(x,t)f(x,t)f(x,t) is supermodular in the…

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

Bounded Rationality in Newsvendor Models V: If σ_T ≤ Σσ_i and σ_T ≥ σ_i, Pooling Strictly Lowers the Expected Cost of Logit Newsvendors with Normal DemandsResearch Paper

Inventory pooling lets several locations serve their combined demand from one stock of goods. Classical newsvendor analysis predicts lower optimal cost when pooling reduces demand variation, but the reduction can vanish when demands are perfectly correlated. Xuanming Su asks whether that conclusion survives when managers make noisy stocking decisions rather…

9 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: mikedeng1

Negative Dynamic Programming II: With Non-Positive Rewards on Borel Spaces, the Optimal Return Satisfies the Optimality EquationResearch Paper

Negative dynamic programming is the study of infinite-horizon sequential decision problems in which every one-stage reward is non-positive and nothing is discounted. Equivalently, a non-negative cost accumulates forever and the controller minimizes its expected total. Stochastic shortest-path problems, optimal stopping with a cost per step, and inventory or…

22 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Understanding the Efficiency of Multi-Server Service Systems I: With Poisson Arrivals and Finitely Many Service-Time Values of Mean 1, the Number of Busy Servers in M/G/∞ Is Poisson(λ)Research Paper

Call centers, hospital wards, telephone exchanges and server farms all face the same staffing question: given an arrival rate λ\lambdaλ, how many servers sss are needed to keep congestion at a fixed level? A widely used answer is the square-root staffing rule

9 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

On Finding Optimal Policies in Discrete Dynamic Programming with No Discounting 2: f Maximizes Gain and Then Bias Exactly When Its Averaged Finite-Horizon Returns Dominate Every Stationary Policy'sResearch Paper

A Markov decision process with finitely many states and actions is usually run either with a discount factor β<1\beta<1β<1 or under the long-run average criterion. Without discounting, the total return over an infinite horizon is typically infinite, and the average return per period ignores everything that happens in any finite stretch of time: two policies with…

13 thms4 active usersReviewed
🏆Completed
AnalysisOperations ResearchStochastic Systems·Captain: mikedeng1

The G/GI/N Queue in the Halfin–Whitt Regime 1: The Regulator Equation z(t) = x(t) + ∫₀ᵗ (z(t−s)+a)⁺ dB(s) Has a Unique Càdlàg Solution, Lipschitz on Bounded Intervals and Measurable in xResearch Paper

The G/GI/NG/GI/NG/GI/N queue has NNN identical servers, a general arrival process, and independent service times with a common distribution FFF. In the Halfin–Whitt regime the number of servers and the offered load grow together, so that the fraction of delayed customers stays strictly between 000 and 111. This is the standard asymptotic model of large call centers and service…

13 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

Optimal Ordering and Rationing Policies in a Nonstationary Dynamic Inventory Model with n Demand Classes IV: Critical-Level Ordering at Nondecreasing Myopic Levels ȳₘ Is OptimalResearch Paper

A firm with one product may face several customer classes in each selling interval. When stock is scarce, it must decide which outstanding demands to satisfy and how much inventory to carry into later intervals. When new stock can be bought at several dates, the rationing choice also changes the value of future purchasing opportunities. Topkis studied these…

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

Fast Approximation Algorithms for Fractional Packing and Covering Problems 2: An ε-Relaxed Decision Procedure for Fractional Covering Using O(m + ρ log² m + ε⁻²ρ log(m/ε)) Oracle CallsResearch Paper

Many linear programs that arise in combinatorial optimization ask only whether a convex set contains a point satisfying a family of nonnegative linear constraints. In the fractional covering problem the constraints have the form Ax≥bAx\ge bAx≥b with A≥0A\ge 0A≥0: the fractional relaxation of set cover, the Held–Karp lower bound for the travelling salesman problem, and…

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

A Dual Approach to Solving Nonlinear Programming Problems by Unconstrained Optimization 2: For a Normal Convex Program and Any Dual Optimal ȳ, x̄ Is Optimal iff x̄ Minimizes L_r(·, ȳ)Research Paper

Lagrangian duality turns a constrained minimization problem into the maximization of a dual function over multipliers. For convex programs the duality is clean: under mild conditions the dual optimal value equals the primal one, and an optimal multiplier vector yˉ\bar yyˉ​ exists. Computationally, however, the ordinary Lagrangian has a well-known defect. Knowing…

8 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces XI: The Random Assignment Problem — Fluctuations of the Optimal Cost of Order (log N)²/(√N log log N)Textbook

The assignment problem asks for a one-to-one matching of NNN agents to NNN tasks that minimizes the total cost. It is one of the basic problems of combinatorial optimization and is solved in polynomial time by the Hungarian method. Its random version, in which the N2N^2N2 costs are independent random variables, is a standard model for the typical behavior of…

7 thms4 active usersReviewed
🏆Completed
CombinatoricsNumber TheoryProbability+1·Captain: mikedeng1

A New Class of Random Number Generators 2: For Prime m = bʳ − bˢ + 1, Every Nontrivial Subtract-with-Borrow Sequence Is Periodic After r Steps, with Period the Order of b mod mResearch Paper

A pseudorandom number generator replaces repeated random sampling with a deterministic update of a small state. Its useful lifetime depends on the length and structure of the resulting orbit. In Marsaglia and Zaman’s 1991 paper, the subtract-with-borrow generators use only digit subtraction and a one-bit borrow while attaining cycles that can be almost as…

17 thms4 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Empirical Bernstein Bounds and Sample Variance Penalization: Sample Variance Penalization Has Excess Risk at Most √(32V(f*,μ)ln(3M(n)/δ)/n) + 22ln(3M(n)/δ)/(n−1) (Theorem 15)Research Paper

Confidence bounds for the mean of a bounded random variable are the basic tool for certifying learned hypotheses, stopping sampling procedures and running bandit algorithms. Hoeffding's inequality gives an interval of width of order 1/n\sqrt{1/n}1/n​ whatever the variance. Bennett's and Bernstein's inequalities do better for low-variance variables, with width of…

21 thms4 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryFunctional Analysis+1·Captain: mikedeng1

The Geometry of Graphs and Some of Its Algorithmic Applications 2: Euclidean Distortion ≤ c iff Σ_{q>0} q·d² + c²·Σ_{q<0} q·d² ≤ 0 for Every PSD Q with Q·1 = 0Research Paper

Many algorithms for graphs and finite metric spaces begin by placing the points in a geometric space and then working with the geometry. Euclidean space is the most convenient target: distances there are controlled by inner products, so the question "where should the points go?" becomes a question about matrices. Linial, London and Rabinovich (Combinatorica…

6 thms4 active usersReviewed
PreviousPage 26 of 142Next

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