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

2676–2700 of 4812
Open1243Completed3569All4812
🏆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
Algorithmic Game TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

A General Framework for the Study of Decentralized Distribution Systems: A Core Allocation Rule Whose Nash Equilibrium Is First-BestResearch Paper

Retailers that sell the same product can raise their joint profit by pooling: stock left over at one location is shipped to meet unmet demand at another, and stock can be held in shared warehouses until demand is known (Eppen 1979; Eppen and Schrage 1981). When the retailers are independent firms, pooling creates two questions at once. After demand is…

10 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
🏆Completed
Dynamic ProgrammingOperations ResearchProbability+1·Captain: mikedeng1

Asymptotic Optimality of Tailored Base-Surge Policies in Dual-Sourcing Inventory Systems: Asymptotic Optimality of the Best TBS Policy for Long Lead TimesResearch Paper

Firms that can buy the same item from two suppliers, a cheap slow one and a fast expensive one, face the dual-sourcing inventory problem: how much to order from each source in every period when demand is random and unmet demand is backlogged. Global sourcing (offshore regular supply plus a near-shore express supply) is the standard example (Allon and Van…

20 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability+1·Captain: mikedeng1

Markovian Decision Processes with Uncertain Transition Probabilities II: Max-Max and Max-Min Optimal Returns Bound the Bayesian Optimal ReturnResearch Paper

A Markovian decision process (Howard, 1960) models a controller who, in each of finitely many states, picks a decision, earns a reward and moves to a random next state according to known transition probabilities. In applications (inventory control, equipment replacement, quality control) those probabilities are estimated, not known. Satia and Lave (Operation…

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

A Nonsmooth Version of Newton's Method I: local superlinear convergence of the generalized-Jacobian Newton method at a semismooth regular rootResearch Paper

Many problems in optimization and equilibrium modelling reduce to a system of equations F(x)=0F(x) = 0F(x)=0 whose map F:Rn→RnF : \mathbb R^n \to \mathbb R^nF:Rn→Rn is Lipschitz but not differentiable: reformulations of nonlinear complementarity problems through the componentwise minimum or the Fischer–Burmeister function, Karush–Kuhn–Tucker systems of constrained programs, and…

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

Shortest Connection Networks And Some Generalizations: Construction Principles P1 and P2 Yield a Shortest Spanning Subtree of Every Connected Labelled GraphResearch Paper

Connecting a set of terminals by a network of direct links of least total length is one of the oldest problems of combinatorial optimization. R. C. Prim's 1957 paper in the Bell System Technical Journal (DOI) was motivated by the rate structure for Bell System leased-line services, in which the charge for connecting a set of terminals depends on the length…

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

Updating Quasi-Newton Matrices with Limited Storage: The Limited-Storage BFGS Method Reaches the Minimizer of a Strictly Convex Quadratic in at Most n StepsResearch Paper

Quasi-Newton methods minimize a smooth function fff on Rn\mathbb{R}^nRn by moving along dk=−Hkgkd_k = -H_k g_kdk​=−Hk​gk​, where gkg_kgk​ is the gradient and HkH_kHk​ is an approximation of the inverse Hessian built from observed gradient differences. The BFGS update is the most widely used way of building HkH_kHk​, but it stores a dense n×nn \times nn×n matrix, which is prohibitive for large nnn.

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

Cubic Regularization of Newton Method and Its Global Performance I: Global Rate of Convergence to Second-Order Stationary PointsResearch Paper

Newton's method is the standard second-order algorithm for unconstrained minimization, but without safeguards it has no global guarantee: far from a minimizer the Newton step can increase the objective, and at a point where the Hessian is indefinite the step can head for a saddle point or a maximum. The usual repairs (line search, trust regions,…

16 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryProbability+1·Captain: mikedeng1

A Simple Parallel Algorithm for the Maximal Independent Set Problem II: The Round Bound of the Derandomized AlgorithmResearch Paper

A maximal independent set (MIS) of a graph is a set of pairwise non-adjacent vertices to which no further vertex can be added. Sequentially an MIS is found greedily in linear time, but the greedy scan is inherently serial. Whether an MIS can be computed by a fast parallel algorithm was a central question of parallel complexity in the early 1980s: Karp and…

16 thms3 active usersReviewed
🏆Completed
Graph TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

A Simple Parallel Algorithm for the Maximal Independent Set Problem I: One Round of Monte Carlo Algorithm A or B Removes an Expected Eighth of the EdgesResearch Paper

A maximal independent set (MIS) of a graph is a set of vertices, no two adjacent, to which no further vertex can be added. Sequentially an MIS is found greedily in linear time, but the greedy scan is inherently serial. Whether an MIS can be found fast in parallel was a central question of parallel complexity in the early 1980s: an MIS algorithm is a…

8 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: mikedeng1

Critical-Path Planning and Scheduling I: Critical Jobs Occur Only When the Completion Time Is the Earliest, and Then Form a Path from Origin to TerminusResearch Paper

The Critical-Path Method (CPM) was introduced by J. E. Kelley, Jr. (Remington Rand) and M. R. Walker (du Pont) in Critical-Path Planning and Scheduling (Proc. Eastern Joint Computer Conference, 1959, pp. 160–173, doi:10.1145/1460299.1460318). Together with PERT, developed at the same time for the Polaris programme, it became the standard way to plan and…

7 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research+1·Captain: mikedeng1

Markov-Renewal Programming. I: Formulation, Finite Return Models: Policy Iteration Finds an Optimal Stationary Policy for the Discounted Infinite-Horizon Markov-Renewal ProgramResearch Paper

Many operational systems move between a finite number of states at random times: a machine alternates between working and repair, a queue between occupancy levels, an inventory between stock positions. When the time spent in a state is not exponential and not a fixed period, neither discrete-time Markov decision processes nor continuous-time Markov chains…

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

Methods of Conjugate Gradients for Solving Linear Systems II: Each Conjugate Gradient Step Shortens the Error VectorResearch Paper

The conjugate gradient method (cg-method) of Hestenes and Stiefel is the standard iterative solver for linear systems Ax=kAx=kAx=k with a symmetric positive definite matrix AAA. It is used for the large sparse systems of finite-element and finite-difference discretizations, as the inner solver of Newton-type and interior-point methods in optimization, and as the…

9 thms3 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisOperations Research+1·Captain: mikedeng1

Methods of Conjugate Gradients for Solving Linear Systems I: Finite Termination of the Conjugate Gradient MethodResearch Paper

Solving a linear system Ax=kAx = kAx=k with a large symmetric positive definite matrix AAA is a basic task of scientific computing: it arises from discretized elliptic equations, least-squares problems and the Newton steps of optimization methods. In 1952 Magnus Hestenes and Eduard Stiefel published the conjugate gradient method (cg-method) (J. Res. Natl. Bur. Stand.…

11 thms3 active usersReviewed
PreviousPage 108 of 193Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5262500
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR38135708
5NINickrobbins953290156
6VEvebis25800
7FIfizzyinc321735
8SHshivm17520
9KMkmehltretter821009265
10SCShuze Chen9455327

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