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

1901–1925 of 3528
Open1284Completed3528All4812
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons 1: A Fixed Price Earns at Least 1 − 1/(2√min{n, λ*t}) of the Optimal Expected RevenueResearch Paper

A firm holds a fixed stock of a perishable or seasonal product: airline seats, hotel rooms, fashion goods, tickets. It must sell the stock over a finite season, and whatever is left at the end is worth nothing. The firm can change its price at any time, and demand responds to the price at random. Should it adjust its price continually as sales occur and…

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

Computational Issues in an Infinite-Horizon, Multiechelon Inventory Model 3: A Closed Form for the Induced Penalty Cost under Normal DemandResearch Paper

Multiechelon inventory theory studies supply systems in which stock is held at several levels: here, a depot that orders from an outside supplier and a retail outlet that is replenished from the depot and faces random customer demand. The question is how much to order and ship in each period so as to minimize expected holding, shortage and ordering costs…

17 thms3 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingMarkov Chain+1·Captain: mikedeng1

Optimal Control of Markov Processes with Incomplete State Information 1: Reduction to Complete State Information on the Conditional State Distributions, with the Same Optimal LawResearch Paper

A controller often cannot see the state of the system it steers. It sees only measurements that are noisy functions of that state. In operations research this happens in machine maintenance and inspection, in queues observed only partially, and in inventory systems with inexact stock records. In control engineering it is the usual case. The question is what…

10 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Contraction Mappings in the Theory Underlying Dynamic Programming 1: Under the Contraction and Monotonicity Assumptions the Solution of the Functional Equation Is the Optimal ReturnResearch Paper

Dynamic programming often replaces a search over whole plans with an equation for a value function. That replacement is useful only when solving the equation recovers the value actually available through policies. In his 1967 paper, Eric Denardo isolated conditions on an abstract return function that make this identification possible, without committing to…

6 thms3 active usersReviewed
🏆Completed
Machine LearningOptimizationReinforcement Learning·Captain: mikedeng1

On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift 1: Projected Gradient Ascent on the Simplex Is ε-Optimal After 64γ|S||A|D∞²/((1−γ)⁶ε²) IterationsResearch Paper

Policy gradient methods optimize a parameterized policy of a Markov decision process by gradient ascent on its expected discounted return. They are among the most widely used methods in reinforcement learning, from REINFORCE (Williams 1992) and the policy gradient theorem to natural policy gradient and trust-region methods. The objective is not concave in…

18 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Simultaneously Learning and Optimizing Using Controlled Variance Pricing 2: Certainty Equivalent Pricing Fails to Converge to the Optimal Price with Positive ProbabilityResearch Paper

A seller who does not know how demand responds to price has to learn the demand curve from its own sales while it is selling. The most natural policy is certainty equivalent pricing (also called myopic pricing or passive learning): after every period, estimate the unknown demand parameters from all data collected so far, and charge the price that would be…

15 thms3 active usersReviewed
🏆Completed
Machine LearningOptimal TransportOptimization+1·Captain: mikedeng1

Robust Wasserstein Profile Inference and Applications to Machine Learning 1: Square-Root LASSO Is Wasserstein DRO — the Worst-Case Squared Loss over D_c(P, P_n) ≤ δ Equals (√MSE_n(β) + √δ‖β‖_p)²Research Paper

Regularized least squares is the standard tool of high-dimensional linear regression. The square-root LASSO of Belloni, Chernozhukov and Wang (Biometrika, 2011) minimizes MSEn(β)+λ∥β∥1\sqrt{\mathrm{MSE}_n(\beta)} + \lambda\|\beta\|_1MSEn​(β)​+λ∥β∥1​. Unlike the LASSO, its optimal regularization parameter does not depend on the unknown noise level. Regularization is usually justified…

14 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOperations Research+1·Captain: mikedeng1

Oracle-Based Robust Optimization via Online Learning 1: The Dual-Subgradient Meta-Algorithm Returns a 2ε-Approximate Robust Solution or Certifies Infeasibility within ⌈G²D²/ε²⌉ Oracle CallsResearch Paper

Robust optimization protects a decision against every realization of uncertain data in a prescribed uncertainty set. The standard approach replaces the uncertain constraints by a deterministic robust counterpart and solves that counterpart directly (Ben-Tal, El Ghaoui, Nemirovski, Robust Optimization, 2009). The counterpart is often a harder problem than…

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

Rademacher and Gaussian Complexities: Risk Bounds and Structural Results 4: A Fixed Boolean Combination of k Classes Has Gaussian Complexity at Most 2 Σ_j G_n(F_j)Research Paper

Data-dependent risk bounds in statistical learning replace combinatorial quantities such as the VC dimension with averages of how well a function class can fit random noise on the observed sample. Bartlett and Mendelson's article (JMLR 3, 2002) established these averages, the Rademacher and Gaussian complexities, as a general tool: a risk bound (their…

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

Optimization with Stochastic Dominance Constraints: Lagrange Multipliers of a Second-Order Dominance Constraint Are Concave Nondecreasing Utility FunctionsResearch Paper

A decision maker choosing a random outcome XXX (a portfolio return, a policy's cost savings, a schedule's throughput) often has a reference outcome YYY, the result of a benchmark policy, and wants the new outcome to be preferable to it for every risk-averse decision maker, not just on average. Expected-utility theory (von Neumann and Morgenstern) makes this…

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

Uniformly Bounded Regret in the Multi-Secretary Problem 2: When (f₁+ε)n ≤ k ≤ (1−fₘ−ε)n, Every Non-Adaptive Policy Has Regret at Least M√nResearch Paper

The multi-secretary problem is the basic model of selecting under a budget from a stream of offers. Hiring a fixed number of candidates, accepting a fixed number of requests for a perishable resource, and admitting customers into a capacity-limited service all have this structure. Each item must be accepted or rejected on arrival, and the comparison point…

11 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

Uniformly Bounded Regret in the Multi-Secretary Problem 1: The Budget-Ratio Policy Has Regret at Most a₁M(ε), Uniformly in the Number of Candidates n and the Budget kResearch Paper

The multi-secretary problem is the simplest model of capacity allocation under uncertainty: a decision maker sees nnn candidates one at a time and may hire at most kkk of them, with every decision final. The same structure underlies single-resource revenue management (accepting or rejecting booking requests against a fixed inventory; see Talluri and van Ryzin, T…

14 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Assortment Optimization under Variants of the Nested Logit Model 4: With Dissimilarity Parameters at Most One, the Knapsack-Relaxation and Singleton LP Optimum Scaled by 2 Is Feasible for the Full LPResearch Paper

Assortment optimization asks which set of products a firm should offer when customers choose among the offered products according to a discrete choice model; it underlies shelf-space planning in retail and fare-class control in airline revenue management (Talluri and van Ryzin, 2004). Under the nested logit model products are grouped into nests, and a…

20 thms3 active users
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Assortment Optimization under Variants of the Nested Logit Model 2: With Dissimilarity Parameters at Most One and Fully-Captured Nests, a Nested-by-Revenue Assortment in Every Nest Is OptimalResearch Paper

A retailer choosing which products to display, or an airline choosing which fare classes to open, solves an assortment optimization problem: pick the set of offered products that maximizes expected revenue when customers choose among what is offered according to a discrete choice model. Under the multinomial logit model the answer has a simple form: an…

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

On the Power and Limitations of Affine Policies in Two-Stage Adaptive Optimization IV: When A ≥ 0 the Best Affine Policy Costs at Most 3√m Times the Fully Adaptable OptimumResearch 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 after it, as a function of bbb. The objective protects against the worst bbb in an uncertainty set U\mathcal UU. Computing an optimal fully adaptable solution is…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsNumber Theory·Captain: mikedeng1

Explicit Expanders of Every Degree and Size 1: For Distinct Primes q₁, q₂, Every Large n Has an LPS Vertex Count Q(q₁, q₂, s, t) Between n and n + o(n)Research Paper

An (n,d,λ)(n,d,\lambda)(n,d,λ)-graph is a ddd-regular graph on nnn vertices in which every eigenvalue of the adjacency matrix other than the top eigenvalue ddd has absolute value at most λ\lambdaλ. Graphs of this kind with λ\lambdaλ small compared with ddd are expanders. They are used in derandomization, error-correcting codes, sorting networks and many other constructions in…

6 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchStatistics·Captain: mikedeng1

Conditional Logit Analysis of Qualitative Choice Behavior 3: The Conditional Logit Likelihood Has a Maximum Exactly When No Direction Makes Every Observed Choice Weakly BestResearch Paper

The conditional logit model is the workhorse of discrete choice analysis in transportation, marketing, labour and industrial organization. McFadden's 1974 chapter derived it from a theory of population choice behaviour and showed how to estimate it by maximum likelihood; this line of work was recognized by his 2000 Nobel Prize in Economic Sciences, awarded…

12 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: mikedeng1

Reversibility and Stochastic Networks IX: Partial Balance — Equivalent Characterizations via Truncation, Rate Changes and Time ReversalTextbook

Equilibrium distributions of Markov models of networks are rarely computed by solving the full equilibrium equations directly. In the classical product-form results (migration processes, Jackson and Kelly networks, loss networks, clustering processes) the equilibrium distribution satisfies a stronger, local family of equations, and that is what makes it…

18 thms3 active users
🏆Completed
Convex OptimizationFunctional AnalysisOptimization·Captain: mikedeng1

A Primal–Dual Splitting Method for Convex Optimization Involving Lipschitzian, Proximable and Linear Composite Terms I: Iterates Converge Weakly to a Primal–Dual Solution When 1/τ − σ‖L‖² ≥ β/2Research Paper

Many convex optimization models combine a smooth loss, a nonsmooth penalty whose proximity operator is easy to compute, and a second penalty applied after a linear map. Imaging models, for example, often place a data-fitting term on the image and a regularizer on its transformed coefficients. The resulting objective has the form F(x)+G(x)+H(Lx)F(x)+G(x)+H(Lx)F(x)+G(x)+H(Lx). Condat's…

15 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Conditional Logit Analysis of Qualitative Choice Behavior 2: Random Utility Maximizers Choose by Logit Exactly When Taste Shocks Are Extreme-Value DistributedResearch Paper

The conditional logit model assigns to an alternative iii in a finite choice set the probability eVi/∑jeVje^{V_i}/\sum_j e^{V_j}eVi​/∑j​eVj​, where VjV_jVj​ is a "representative utility" built from observed attributes of the alternative and the decision maker. It is the workhorse of discrete choice econometrics, transportation demand forecasting, marketing and revenue management,…

8 thms3 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization+1·Captain: mikedeng1

Twice Regularized MDPs and the Equivalence Between Robustness and Regularization 2: The Greedy Policy of the R2 Optimal Value Is the Unique Optimal R2 PolicyResearch Paper

A robust Markov decision process (robust MDP) evaluates a policy against the worst transition kernel and reward in an uncertainty set around a nominal model (P0,r0)(P_0, r_0)(P0​,r0​). It is the standard model for planning when the dynamics are estimated from data (Iyengar 2005; Nilim and El Ghaoui 2005; Wiesemann, Kuhn and Rustem 2013). Its Bellman update contains an…

9 thms3 active usersReviewed
🏆Completed
Graph TheoryMarkov ChainOperations Research+3·Captain: mikedeng1

Reversibility and Stochastic Networks VIII: Markov Fields — A Positive Random Field Is Markov iff It Factorizes over the Simplices of the GraphTextbook

Many systems consist of a finite number of sites whose states influence one another only locally: fruit trees in an orchard that are diseased or healthy, power sources that are working or broken, individuals holding one of several views. Chapter 9 of F. P. Kelly, Reversibility and Stochastic Networks (Wiley, 1979) asks which joint distributions such systems…

8 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchOptimization+2·Captain: mikedeng1

Reversibility and Stochastic Networks V: Optimal Capacity Allocation in a Network of QueuesTextbook

Chapter 4 of F. P. Kelly's Reversibility and Stochastic Networks (Wiley, 1979) applies the product-form theory of Chapter 3 to concrete systems. Two of its results have numbered statements, and they answer two practical questions.

8 thms3 active usersReviewed
🏆Completed
AnalysisDifferential GeometryOptimization·Captain: mikedeng1

Projection-like Retractions on Matrix Manifolds II: The Metric Projection onto a C^k Submanifold Is Locally Unique and C^(k−1), so Projecting a Tangent Step Is a RetractionResearch Paper

Many optimization problems in statistics, signal processing and control are posed over sets of matrices with a constraint that makes them curved: matrices of fixed rank, matrices with orthonormal columns, symmetric matrices with a prescribed spectrum. Algorithms on such sets ("optimization on manifolds") compute a step in the tangent space at the current…

8 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: mikedeng1

Reversibility and Stochastic Networks III: Open Networks of Queues with General Customer Routes Have Product-Form EquilibriumTextbook

Networks of queues model systems in which jobs visit a sequence of service stations: items in a manufacturing job-shop, packets in a communication network, patients moving between hospital departments. The open migration process of Chapter 2 of F. P. Kelly, Reversibility and Stochastic Networks (Wiley, 1979), and the job-shop networks of Jackson (Jackson…

10 thms3 active usersReviewed
PreviousPage 77 of 142Next

Top contributors

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

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