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.

3566 completed missions

Missions

2226–2250 of 3566
Open1246Completed3566All4812
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Competitive Paging Algorithms III: No Randomized Paging Algorithm Is Better than H_k-CompetitiveResearch Paper

Paging is the problem of managing a two-level memory: a cache holds kkk of the nnn pages a program uses, every request must find its page in the cache, and a request to a page outside the cache (a page fault) forces the algorithm to bring the page in and evict another. An on-line algorithm chooses what to evict without seeing future requests. Sleator and Tarjan…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Competitive Paging Algorithms II: Algorithm EATR Is 3/2-Competitive for Two ServersResearch Paper

Paging is the problem of managing a two-level memory: a fast cache holding kkk pages and a slow memory holding the rest. When a requested page is not in the cache (a page fault), it must be brought in and, if the cache is full, some page must be evicted. An on-line paging algorithm decides which page to evict without knowing future requests. Sleator and…

8 thms3 active usersReviewed
🏆Completed
Information TheoryOperations ResearchProbability·Captain: mikedeng1

Conditional and Dynamic Convex Risk Measures II: The Conditional Entropic Risk Measure and Conditional Relative EntropyResearch Paper

A risk measure assigns to a random financial position XXX a capital requirement ρ(X)\rho(X)ρ(X): the amount of cash that must be added to XXX to make it acceptable. The axiomatic theory of convex risk measures (Föllmer–Schied 2002; Frittelli–Rosazza Gianin 2002) treats this number as computed with no information beyond the model. In practice a regulator or a risk…

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

Optimizing Static Linear Feedback: Gradient Method III: Gradient Descent with the Hessian Step Size Converges Linearly on Strongly Convex FunctionsResearch Paper

Gradient descent needs a step size, and the classical choices each ask for something the user may not have. A constant step 1/L1/L1/L needs the Lipschitz constant LLL of the gradient, which is rarely known and often pessimistic. Backtracking needs repeated function evaluations. The exact line search needs a one-dimensional minimization at every iteration.…

6 thms3 active usersReviewed
🏆Completed
Control TheoryOperations ResearchOptimization·Captain: mikedeng1

Optimizing Static Linear Feedback: Gradient Method I: The Gradient Method Converges to a Stationary Point, and Linearly to the Optimal Gain under State FeedbackResearch Paper

The linear-quadratic regulator (LQR) is the basic problem of optimal control: steer a linear system x˙=Ax+Bu\dot x = Ax + Bux˙=Ax+Bu so as to minimize an integrated quadratic cost. When the full state is measured and the gain may be chosen freely, the optimal feedback is given by the algebraic Riccati equation (Kalman, 1960). In many applications only an output y=Cxy = Cxy=Cx is…

16 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOperations Research+1·Captain: mikedeng1

Projected Gradient Methods for Linearly Constrained Problems I: The Gradient Projection Method Drives the Projected Gradients to ZeroResearch Paper

The gradient projection method minimizes a continuously differentiable function over a closed convex set by alternating a gradient step with a projection back onto the set. It was proposed by Goldstein (1964) and by Levitin and Polyak (1966), and it is the basic step of many algorithms for bound constrained and linearly constrained optimization, including…

16 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma: ℓ1-Proximity of Integer and LP OptimaResearch Paper

Integer programs are routinely solved by first solving their linear programming (LP) relaxation and then searching for an integer optimum near the fractional one. How near an integer optimum must be is the subject of proximity theorems. They bound the search region of branch-and-bound and of dynamic programming, and they turn a fractional optimum into a…

12 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

An Analog of the Minimax Theorem for Vector Payoffs: A Closed Convex Set Is Approachable If and Only If It Meets Every T(q), and Is Otherwise ExcludableResearch Paper

Von Neumann's minimax theorem says that in a zero-sum game with real payoffs, Player I can guarantee an expected gain of at least the value vvv and Player II can hold it to at most vvv. In a long series of plays, the law of large numbers turns this into a statement about the average payoff: I can make it exceed v−εv-\varepsilonv−ε, II can keep it below v+εv+\varepsilonv+ε,…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsDynamic ProgrammingGraph Theory+1·Captain: mikedeng1

The Steiner Problem in Graphs: Algorithm A Computes the Length of the Steiner TreeResearch Paper

The Steiner problem in graphs asks for the cheapest way to connect a prescribed set of nodes of a network, where intermediate nodes may be used freely. It is the network version of the classical Euclidean Steiner tree problem surveyed by Gilbert and Pollak (SIAM J. Appl. Math. 16, 1968), and it arises wherever a few sites must be joined through an existing…

10 thms3 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingOperations Research+1·Captain: mikedeng1

Monotone Mappings with Application in Dynamic Programming II: Convergence of the DP Algorithm under Uniform DecreaseResearch Paper

Infinite-horizon sequential decision problems (deterministic optimal control, Markov decision processes, minimax control) share one computational question: does the dynamic programming (DP) algorithm, which starts from a terminal cost and repeatedly applies the Bellman operator, converge to the optimal cost? For discounted problems with bounded costs the…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOperations Research+1·Captain: mikedeng1

A Three-Operator Splitting Scheme and its Optimization Applications 3: Accelerated Convergence under Strong MonotonicityResearch Paper

Many problems in convex optimization, variational inequalities and signal processing reduce to finding a zero of a sum of three monotone operators, one of which is single-valued and smooth. Davis and Yin (Set-Valued Var. Anal. 25, 2017) introduced a splitting scheme that evaluates each of the three operators separately: the two set-valued ones through their…

11 thms3 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOperations Research+1·Captain: mikedeng1

A Three-Operator Splitting Scheme and its Optimization Applications 2: The Objective Rate of the Weighted Ergodic IterateResearch Paper

Many problems in signal processing, statistics and machine learning minimise a sum of three convex terms: a smooth data-fit term and two nonsmooth regularisers or constraints, each of which is easy to handle on its own (through its proximal map) but not in combination. Examples are constrained sparse regression, matrix completion with a nuclear-norm penalty…

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

On Polyhedral Approximations of the Second-Order Cone III: Closeness of the Relaxed Feasible SetResearch Paper

Conic quadratic problems (also called second-order cone programs) arise directly in applications such as contact problems with Coulomb friction, and a wide range of nonlinear convex problems can be rewritten in this form (Lobo, Vandenberghe, Boyd and Lebret 1998). Interior-point methods solve them in polynomial time, but around 2000 the available software…

7 thms3 active usersReviewed
🏆Completed
AnalysisOperations ResearchOptimization·Captain: mikedeng1

Generalized Gradients and Applications I: The Generalized Gradient of a Max FunctionResearch Paper

Many objective functions in optimization are pointwise maxima: the worst case of a loss over an uncertainty set, the value of a minimax problem as a function of the outer variable, a penalty max⁡igi(x)\max_i g_i(x)maxi​gi​(x) for a system of constraints, or the largest eigenvalue of a symmetric matrix. Such a function

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

On Minimizing a Convex Function Subject to Linear Inequalities III: The Expected Cost of a Linear Program with Random Coefficients Is ConvexResearch Paper

A linear program is solved with known data, but in planning problems the data are often only known in distribution when the main decision is taken: demands, yields and requirements are revealed later, and a corrective action is taken after they are. E. M. L. Beale's 1955 paper On Minimizing a Convex Function Subject to Linear Inequalities formulates this…

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

Scheduling Subject to Resource Constraints: Classification and Complexity III: The Two-Machine Algorithm for Q2 with One Resource and Unit-Time Jobs Is OptimalResearch Paper

Many production and computing systems run jobs on parallel machines that also draw on a shared, limited resource: tools, workers, memory, power. Adding such a resource to a scheduling problem can change its complexity entirely. Błażewicz, Lenstra and Rinnooy Kan (DAM 1983) extended the three-field classification α∣β∣γ\alpha\mid\beta\mid\gammaα∣β∣γ of Graham, Lawler,…

10 thms3 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisProbability+1·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix I: Sample Bound for the Gaussian Trace EstimatorResearch Paper

Many computations in scientific computing, statistics and machine learning need the trace of a matrix AAA that is never formed explicitly: AAA may be f(B)f(B)f(B) for a large sparse BBB, an inverse B−1B^{-1}B−1, or a product of operators, and the only access to it is the ability to compute products AzAzAz for chosen vectors zzz. Examples are log-determinant estimation in Gaussian…

9 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization+1·Captain: mikedeng1

Optimal Pricing of Seasonal Products in the Presence of Forward-Looking Consumers 2: A Threshold Nash Equilibrium under Announced Fixed-Discount PricingResearch Paper

Retailers of fashion and seasonal goods sell at a premium price early in the season and mark down later. When customers anticipate the markdown, some of them wait, and the seller's pricing problem becomes a game between the seller and a population of forward-looking (strategic) customers. Aviv and Pazgal (MSOM 10(3), 2008) study this game in a model with…

5 thms3 active usersReviewed
🏆Completed
Machine LearningOptimizationProbability+1·Captain: mikedeng1

Simultaneous Analysis of Lasso and Dantzig Selector III: A Sparsity Oracle Inequality for the LassoResearch Paper

In high-dimensional regression the number of candidate predictors MMM can far exceed the number of observations nnn. A regression function can then be estimated only if it is well approximated by a combination of a few elements of a large dictionary. The Lasso is the most widely used estimator in this regime. The question this mission formalizes is how well the…

9 thms3 active usersReviewed
🏆Completed
Linear algebraMachine LearningOptimization+1·Captain: mikedeng1

Simultaneous Analysis of Lasso and Dantzig Selector I: Sparse Eigenvalue and Correlation Conditions Imply the Restricted Eigenvalue ConditionResearch Paper

In high-dimensional linear regression one observes y=Xβ∗+w∈Rny = X\beta^* + w \in \mathbb R^ny=Xβ∗+w∈Rn with a design matrix X∈Rn×MX\in\mathbb R^{n\times M}X∈Rn×M whose number of columns MMM may far exceed the sample size nnn. The two standard estimators of a sparse β∗\beta^*β∗, the Lasso (Tibshirani, 1996) and the Dantzig selector (Candès and Tao, 2007), both come with error bounds of order …

11 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningProbability·Captain: mikedeng1

Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits I: The Regret Bound of ILOVETOCONBANDITSResearch Paper

In a contextual bandit problem a learner repeatedly observes a context (a user, a patient, a query), chooses one of KKK actions, and observes the reward of the chosen action only. It competes with the best policy of a fixed class Π\PiΠ of maps from contexts to actions. This is the standard model for news and advertisement recommendation, adaptive clinical…

12 thms3 active usersReviewed
🏆Completed
AnalysisNumerical AnalysisOperations Research+1·Captain: mikedeng1

Analysis of Generalized Pattern Searches: Nonnegative Clarke Derivatives at Limits of Refining SubsequencesResearch Paper

Generalized pattern search (GPS) is a class of derivative-free methods for minimizing a function that can only be evaluated, not differentiated. Such objectives arise in engineering design, where one evaluation is an expensive simulation that may fail and return no value at all. The helicopter rotor design problem of Booker et al. is one example: no value…

13 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+2·Captain: mikedeng1

Maximizing Non-Monotone Submodular Functions II: A Nonadaptive Algorithm Achieves 1/3 of the OptimumResearch Paper

Maximizing a submodular set function without constraints contains Max Cut, Max Directed Cut, maximum facility location and several graph and hypergraph cut problems as special cases, and it appears in operations research wherever a value exhibits diminishing returns but is not monotone (profit that combines coverage with a cost, for example). These problems…

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

On Properties of Stochastic Inventory Systems IV: The (Q, r) Cost Is Flatter in the Order Quantity than the EOQ CostResearch Paper

The continuous-review (Q,r)(Q, r)(Q,r) policy is the standard replenishment rule of inventory theory: whenever the inventory position (stock on hand plus on order minus backorders) drops to the reorder point rrr, order a fixed order quantity QQQ. It is used in practice and taught in every operations management course, usually after the deterministic economic order…

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

On Properties of Stochastic Inventory Systems II: The Optimal Order Quantity of the Stochastic (Q, r) Model Exceeds the EOQ by a Bounded GapResearch Paper

The continuous-review (Q,r)(Q, r)(Q,r) policy is the standard control rule for a single stocked item with random demand: whenever the inventory position falls to the reorder point rrr, an order of fixed size QQQ is placed. It is implemented in a large share of commercial inventory systems. Choosing the two parameters jointly has traditionally required numerical search…

10 thms3 active usersReviewed
PreviousPage 90 of 143Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5259500
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36775496
5NINickrobbins953290156
6VEvebis25800
7FIfizzyinc321735
8SHshivm17520
9KMkmehltretter82999263
10SCShuze Chen9455326

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