Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Optimization

2,311 missions · 1,728 completed

Missions

Open583Completed1728All2311
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Optimal Starting Times for End-of-Season Sales and Optimal Stopping Times for Promotional Fares 2: Markup Is Optimal Once Time-to-Go Exceeds an Increasing Threshold z_nResearch Paper

An airline may offer a low promotional fare while seats remain available, then raise the fare as departure approaches. The choice is dynamic: a sale changes both the number of seats left and the benefit of waiting. The same decision appears for hotel rooms and theater seats. Feng and Gallego study a policy with two fixed prices and at most one price change,…

6 thms5 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: mikedeng1

METRIC: A Multi-Echelon Technique for Recoverable Item Control 1: The Marginal Conditions on the Convex Hull of Each Item's Decreasing Cost Function Determine a Unique Optimal AllocationResearch Paper

Service organizations keep repairable spare parts at a depot and at operating bases. Stock has a purchase or holding cost, while insufficient stock leaves backorders. Craig Sherbrooke's METRIC study describes how to evaluate such a system and distribute additional units among item types. Its fifth computational stage compares the reduction in expected…

22 thms5 active users
🏆Completed
Algorithmic Game TheoryTopology·Captain: mikedeng1

On General Minimax Theorems 1: For a Minimal Finite Y with Every f(·, y) Quasi-Concave and u.s.c. on Convex M, One μ₀ ∈ M Has f(μ₀, y) < c for All y ∈ YResearch Paper

A minimax theorem asserts that, for a function f(μ,ν)f(\mu, \nu)f(μ,ν) of two variables,

11 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations Research·Captain: mikedeng1

Revenue Management Under a General Discrete Choice Model of Consumer Behavior 1: The Optimal Policy Offers Only Nondominated Sets, a Larger One the More Capacity and the Less Time RemainResearch Paper

A seller with one limited inventory pool can choose which fare products to show in each selling period. When customers choose among the displayed products, showing another fare can both add sales and divert buyers from a more expensive fare. A fixed ranking of fares therefore does not by itself tell the seller which products to offer. Talluri and van…

10 thms5 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Optimal Pricing and Return Policies for Perishable Commodities II: Neither Unlimited Returns at Full Credit nor a No-Returns Policy Coordinates the ChannelResearch Paper

Manufacturers of perishable goods must decide how much inventory risk to leave with retailers. A retailer who pays for every ordered unit may order less than is best for the manufacturer and retailer together; a generous return policy changes that incentive. Pasternack studies this question in a single-period setting, with a fixed selling price, uncertain…

9 thms5 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchStochastic Systems·Captain: mikedeng1

Loss Networks 1: The Primal Problem Has a Unique Optimum x_r = ν_r ∏_j (1 − B_j)^{A_jr}; the Conditions on B Are Solvable, Uniquely if rank A = J, and Biject with Dual OptimaResearch Paper

A loss network carries calls that require capacity on one or more links. A call is accepted only when every required link has enough free circuits; otherwise it is lost. This makes the traffic on different links dependent even when calls on different routes arrive independently. Network operators need to know where capacity constraints bind and how offered…

11 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

A Linear Programming Approach to the Cutting Stock Problem—Part II 2: For a Linear-Fractional Objective, a Basic Feasible Solution with No Improving Edge Is a Global MinimumResearch Paper

In the cutting stock problem, stock rolls of length LLL are cut into pieces of lengths l1,…,lml_1,\dots,l_ml1​,…,lm​ to fill orders. Part I of Gilmore and Gomory's work (Opns. Res. 9 (1961)) solved its linear programming relaxation by the simplex method with column generation: the columns (cutting patterns) are too many to list, so each simplex iteration finds an improving…

8 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

A Linear Programming Approach to the Cutting-Stock Problem: If No Slack and No Knapsack Pattern Prices Out, the Current Basic Solution Is a Minimum of the Cutting-Stock LPResearch Paper

A cutting-stock shop receives orders for pieces of several lengths and cuts them from a limited menu of longer stock lengths. Each stock length has a cost. The shop can repeat any cutting pattern, so the central optimization question is which patterns meet the demand at least cost. The direct linear program has a variable for every possible pattern. Even a…

13 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationOperations Research·Captain: mikedeng1

A Probabilistic Production and Inventory Problem: The Optimal Discounted Cost Is the Greatest Point of the Constraint Set (9) and the Unique Optimum of the Linear Program (P2)Research Paper

A Markov decision process with finitely many states and actions and a discounted cost criterion can be solved in three classical ways: policy iteration, value iteration, and linear programming. The third goes back to F. d'Epenoux's paper A Probabilistic Production and Inventory Problem (Management Science 10(1), 1963, partly redrafted from a translation of…

10 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

Coordinating Inventory Control and Pricing Strategies with Random Demand and Fixed Ordering Cost: The Finite Horizon Case 1: Additive Demand: k-Concave Profit-to-Go, Optimal (s, S, p) PolicyResearch Paper

A retailer that sets both its replenishment quantities and its prices over a finite selling season faces a coupled decision: the price shapes the demand that the inventory must serve, and the inventory position shapes which price is worth charging. With a fixed cost per order, the classical inventory answer is the (s, S) policy of Scarf (1960): when the…

11 thms5 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningProbability·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity XV: SVRG with η = 1/(10β) and k = 20κ Contracts the Expected Optimality Gap by 0.9 per EpochTextbook

Many optimization problems in machine learning minimize an average of losses, one loss for each observation. A full gradient step examines every observation, while a stochastic gradient step examines one. The latter is cheaper per step, but its sampled gradient can remain noisy even near the optimum. Section 6.3 of Bubeck's monograph studies stochastic…

14 thms5 active usersReviewed
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity III: Projected Subgradient Descent with η = R/(L√t) Satisfies f(average) − f(x*) ≤ RL/√tTextbook

Many convex optimization problems in machine learning and statistics have objectives that are convex but not differentiable: hinge losses, ℓ1\ell_1ℓ1​ penalties, maxima of finitely many affine functions, and the dual functions of Lagrangian relaxations. Methods that rely on gradients do not apply to them directly, while cutting-plane methods such as the…

15 thms5 active users
🏆Completed
Convex OptimizationOperations Research·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity II: For t ≥ 2n² log(R/r) the Ellipsoid Method Satisfies f(x_t) − min f ≤ (2BR/r)·exp(−t/(2n²))Textbook

The ellipsoid method is the cutting-plane algorithm that settled the polynomial-time solvability of linear programming and, more generally, of convex optimization over any set that comes with an efficient separation oracle. It was introduced for convex minimization by Shor and by Yudin and Nemirovski in the 1970s, and Khachiyan used it in 1979 to give the…

11 thms5 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Asymptotic Optimality of Order-up-to Policies in Lost Sales Inventory Systems: Ordering Up to the Newsvendor Level for Penalty b + τh Is Asymptotically Optimal as b → ∞Research Paper

Periodic-review inventory systems face a simple choice each period: how much to order before the next demand is known. When unmet demand is lost, the order can affect the stock available several periods later without preserving a backlog that records earlier shortages. This makes the optimal policy difficult to describe when replenishment takes time. An orde…

16 thms5 active usersReviewed
🏆Completed
Discrete GeometryLinear OptimizationOperations Research·Captain: mikedeng1

Sensitivity Theorems in Integer Linear Programming: Every Integral m×n Matrix Has Chvátal Rank at Most 2^(n³+1)·n^(5n)·Δ(A)^(n+1)Research Paper

An integer linear program max⁡{wx:Ax≤b, x integral}\max\{wx : Ax \le b,\ x \text{ integral}\}max{wx:Ax≤b, x integral} is usually attacked through its linear programming relaxation max⁡{wx:Ax≤b}\max\{wx : Ax \le b\}max{wx:Ax≤b}, which drops the integrality constraint. Two questions follow at once. How far can an optimal solution of the relaxation be from an optimal integer solution? And how many rounds of rounding-based cutting…

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

Understanding and Using Linear Programming IV: The Duality Theorem and Three Proofs of the Farkas LemmaTextbook

Every linear program comes with a second linear program, its dual, whose feasible solutions certify bounds on the optimum of the first. The duality theorem of linear programming says that these certificates are perfect: when both programs are feasible, the best bound equals the optimum. The theorem underlies the analysis of the simplex method, sensitivity…

14 thms5 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingLinear algebra+2·Captain: mikedeng1

Bellman's Dynamic Programming IX: Markovian Decision Processes and the Maximal Perron RootTextbook

Chapter XI of Richard Bellman's Dynamic Programming (Princeton University Press, 1957; DOI 10.2307/j.ctv1nxcw0f) studies decision processes whose state is a vector of nonnegative quantities, for example the probabilities that a system is in each of NNN states, or the stocks of NNN commodities, and whose transitions are linear maps chosen stage by stage by a…

13 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchTheoretical Computer Science·Captain: mikedeng1

A Dynamic Near-Optimal Algorithm for Online Linear Programming I: The Competitive Ratio of the Dynamic Learning AlgorithmResearch Paper

Many resource-allocation problems are decided one request at a time: a seller of airline seats or hotel nights, an ad platform allocating advertiser budgets, a network operator admitting bandwidth requests. Each request asks for a bundle of resources and offers a price. It must be accepted or rejected on arrival, before the later requests are seen. The onlin…

13 thms5 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: mikedeng1

Minimization Methods for Non-Differentiable Functions III: Convergence of the Normalized Subgradient Method with Divergent-Series StepsizesTextbook

Many optimization problems of operations research have objectives that are convex but not differentiable: Lagrangian duals of integer and combinatorial programs, maxima of finitely many affine or smooth functions, penalty functions for systems of inequalities, and the value functions produced by decomposition. For such functions the gradient method and…

10 thms5 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchProbability·Captain: mikedeng1

Introduction to the Scenario Approach I: The Violation Distribution of the Scenario SolutionTextbook

Many design problems in control, finance and operations research are convex programs with uncertain constraints: a decision θ\thetaθ must satisfy θ∈Θδ\theta\in\Theta_\deltaθ∈Θδ​ for a parameter δ\deltaδ that is not known in advance. Enforcing the constraint for every possible δ\deltaδ (robust optimization) is often intractable or too conservative, and a chance-constrained…

16 thms5 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research·Captain: mikedeng1

An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem II: Geometric Grouping with Residual LP RoundingResearch Paper

One-dimensional bin packing asks for the fewest unit-capacity bins that hold a given list of items with sizes in (0,1)(0,1)(0,1). Deciding whether two bins suffice is NP-hard (it contains the partition problem), so no polynomial-time algorithm guarantees a ratio below 3/23/23/2 unless P = NP. The natural question is therefore asymptotic: how small can the additive error …

21 thms5 active usersReviewed
🏆Completed
Discrete GeometryLinear OptimizationOperations Research·Captain: mikedeng1

Selected Topics in Column Generation I: Discretization — Every Integer Point of a Rational Polyhedron Is a Generating Integer Point Plus an Integer Combination of Integer RaysResearch Paper

Dantzig–Wolfe decomposition and column generation solve large integer programs by replacing a set of "easy" constraints with a description of its feasible points, and then pricing out the points one at a time. For linear programs this rests on the Minkowski–Weyl representation: every point of a polyhedron is a convex combination of its extreme points plus a…

5 thms5 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research·Captain: Shuze Chen

Discrete Convex Analysis XXV: L-Convex Functions via Minimizer PolyhedraTextbook

Chapter 5 characterized L-convex sets — sublattice-closed, translation-periodic subsets of ZV\mathbb Z^VZV — and showed they interact cleanly with integral convexity. Chapter 7 asks the functional analogue: which functions on the integer lattice deserve to be called convex in the "L" sense, and how do they relate back to L-convex sets? This mission (continuing…

41 thms5 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOperations Research+1·Captain: mikedeng1

Dual Stochastic Dominance and Related Mean-Risk Models 2: Mean–Gini Optimal Portfolios Exist and Are SSD-EfficientResearch Paper

Portfolio selection and other decisions under risk are routinely solved as mean–risk models: maximize the expected outcome minus a multiple of a risk measure over the feasible set. Such a model is computationally convenient, but it is only defensible if its answers agree with the preferences of risk-averse decision makers. The standard formal expression of…

13 thms5 active usersReviewed
🏆Completed
AnalysisControl TheoryDynamical Systems+1·Captain: mikedeng1

Generalized Gradients and Applications II: Flow-Invariant Sets of Lipschitz Differential InclusionsResearch Paper

A closed set F⊆RnF\subseteq\mathbb R^nF⊆Rn is flow-invariant for a dynamical system when every trajectory that starts in FFF stays in FFF. Invariance of sets underlies state constraints in optimal control, safety certificates for controlled systems, comparison and maximum principles for differential equations, and the positivity of solutions of kinetic and population…

17 thms5 active usersReviewed
PreviousPage 5 of 70Next

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