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
Complexity TheoryTheoretical Computer Science·Captain: Shuze Chen

Tetris is Hard, Even to Approximate: Inapproximability of cleared rowsResearch Paper

Knowing every future piece removes uncertainty from Tetris, but it does not remove the computational difficulty of choosing placements. Offline Tetris asks a player to plan against an entire finite piece sequence revealed in advance. The initial board can already contain occupied cells, and its dimensions are part of the input. Demaine, Hohenberger and…

62 thms11 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation I: a saddle point of the Lagrangian of a convex program solves both the primal and the dual problemTextbook

Kall and Mayer's Stochastic Linear Programming: Models, Theory, and Computation (Kluwer/Springer, 2005) reduces most stochastic models to deterministic optimization problems. Chance-constrained problems become nonlinear programs with convex constraint functions, and the regularized decomposition methods for recourse problems solve a quadratic master program…

27 thms10 active usersReviewed
🏆Completed
Machine LearningOperations ResearchProbability·Captain: mikedeng1

A Nonparametric Asymptotic Analysis of Inventory Planning with Censored Demand 1: AIM's Average Expected Cost Is Within O(1/√T) of the Newsvendor Cost, Perishable and Non-PerishableResearch Paper

A retailer who restocks a product every period must choose an order-up-to level without knowing the demand distribution, and in most retail settings it observes only sales, the minimum of demand and stock. Demand above the stock is lost and never recorded. This is censored demand: the data needed to estimate the distribution are truncated exactly at the…

17 thms8 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation VIII: under complete fixed recourse the expected recourse is finite, convex and LipschitzTextbook

A two-stage stochastic linear program models a decision taken before uncertain data are revealed, followed by a corrective (recourse) decision taken afterwards. Production planning under uncertain demand, capacity expansion under uncertain loads and network design under uncertain traffic all have this form. The first-stage decision xxx is chosen now; once the…

21 thms7 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

A First-Order Approach to Accelerated Value Iteration 1: For a Reversible Policy Chain, Accelerated Value Computation Converges at Rate 1 − √((1−λ)/(1+λ)) + η for Every η > 0Research Paper

Value iteration is the standard method for solving a discounted Markov decision process (MDP), and its policy-evaluation variant, value computation (VC), computes the value of a fixed policy by iterating an affine contraction. Both converge geometrically at rate λ\lambdaλ, the discount factor. When λ\lambdaλ is close to one, as in long-horizon…

18 thms7 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

On the Optimality of Affine Policies for Budgeted Uncertainty Sets 2: For Disjoint Constrained Budgeted Sets, Affine Policies Approximate the Adjustable Robust Problem within O(log² n / log log n)Research Paper

Two-stage adjustable robust optimization models decisions taken in two steps around an uncertain demand: a first-stage decision is fixed now, the demand is revealed, and a second-stage (recourse) decision reacts to it. The objective is the worst-case total cost over a set of possible demands. Computing the optimal adjustable solution is intractable in…

32 thms7 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Fast Approximation Algorithms for Fractional Packing and Covering Problems 3: An ε-Relaxed Decision Procedure for the General Problem Ax ≤ b, x ∈ P Using O(ρ²ε⁻² log(mρ/ε)) Oracle CallsResearch Paper

Many linear programs that arise in combinatorial optimization have a few "complicating" constraints Ax≤bAx \le bAx≤b on top of a set PPP over which linear optimization is easy: multicommodity flow, where PPP is a product of single-commodity flow polytopes; scheduling and the Held–Karp bound, where PPP is a polytope of assignments or trees. Plotkin, Shmoys and Tardos…

16 thms7 active users
🏆Completed
Computational GeometryConvex Optimization·Captain: mikedeng1

Rounding of Polytopes in the Real Number Model of Computation: Barycentric Coordinate Descent Finds a (1+ε)n-Rounding Ellipsoid of m Points in O(n(1/ε + ln n + ln ln m)) IterationsResearch Paper

Many algorithms for convex bodies need the body to be well rounded: sandwiched between two concentric ellipsoids whose size ratio is controlled by the dimension. The ellipsoid method, volume and integration algorithms, and preconditioning for linear programming use such roundings. For a polytope given by its vertices a1,…,am∈Rna_1,\dots,a_m \in \mathbb{R}^na1​,…,am​∈Rn, John's…

24 thms7 active users
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Adaptive Subgradient Methods for Online Learning and Stochastic Optimization 1: Diagonal AdaGrad's Regret Is Bounded by the Per-Coordinate Gradient Norms Σᵢ‖g_{1:T,i}‖₂Research Paper

Stochastic and online subgradient methods are the workhorse of large-scale learning: each step touches one example, costs time linear in the dimension, and needs no line search. Their weak point is the step size. A single global step size treats every coordinate alike, while in high-dimensional, sparse problems (text, click-through data, bag-of-words…

22 thms7 active users
🏆Completed
Complexity TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources IX: Deciding Feasibility with Cumulative Resources Is NP-Complete Even for Acyclic Project NetworksTextbook

Project scheduling with cumulative resources models production and logistics projects in which activities fill and empty storage: an activity withdraws material from an inventory when it starts and deposits its output when it completes, and every inventory must stay between a safety stock and a storage capacity. Neumann, Schwindt and Zimmermann treat this…

29 thms7 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research·Captain: Shuze Chen

Discrete Convex Analysis XXVIII: The Conjugacy TheoremTextbook

Chapter 8 is where discrete convex analysis explains why it needed two separate notions — M-convexity (exchangeability) and L-convexity (submodularity) — rather than one. The answer is conjugacy: under the classical Legendre-Fenchel transform, the two classes turn out to be exactly dual to each other, the discrete analogue of the fact that convex analysis's…

84 thms7 active usersReviewed
🏆Completed
CombinatoricsConvex OptimizationOperations Research·Captain: mikedeng1

Convexity and Steinitz's Exchange Property III: Fenchel-Type Min-Max Duality with Primal and Dual Integrality for M-Concave and M-Convex FunctionsResearch Paper

Several classical min-max theorems of combinatorial optimization say that a discrete maximization problem and a continuous minimization problem have the same optimal value, and that both have integral optimal solutions when the data are integral. Edmonds' polymatroid intersection theorem (1970), Fujishige's Fenchel-type duality for submodular functions…

21 thms7 active usersReviewed
🏆Completed
CombinatoricsConvex OptimizationOperations Research·Captain: mikedeng1

Convexity and Steinitz's Exchange Property II: The Local Supermodularity Theorem for the Concave ConjugateResearch Paper

Matroids and their integral generalizations, integral base polytopes, are the combinatorial structures on which the greedy algorithm is exact. Edmonds' theory relates them to submodular and supermodular set functions: a polytope is a base polytope exactly when its support function, restricted to 0/10/10/1 vectors, is supermodular and the greedy formula evaluates…

18 thms7 active usersReviewed
🏆Completed
CombinatoricsConvex OptimizationOperations Research·Captain: mikedeng1

Convexity and Steinitz's Exchange Property I: The Extension Theorem — M-Concavity Is Concave Extendability with Integral Base Polytope MaximizersResearch Paper

Linear optimization over the bases of a matroid, over the integer points of a polymatroid, or over the flows of a network is well understood: the greedy algorithm is exact, the feasible sets are the integer points of polytopes described by submodular functions, and min-max theorems of Edmonds and Frank hold with integrality. Nonlinear objectives on the same…

24 thms7 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Disjunctive Programming I: Intersection Cuts and Duality for Disjunctive ProgramsTextbook

Linear programming duality is one of the load-bearing facts of optimization: every feasible linear program has a dual whose value matches the primal's, and this correspondence drives the simplex method's stopping criterion, sensitivity analysis, and most complexity results for polyhedral problems. Integer and mixed-integer programs have no such duality…

11 thms7 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: naimengye

Robust Optimization X: Globalized Robust Counterparts of Uncertain Conic Problems (retired)Textbook

A robust counterpart draws a hard line. Inside the uncertainty set the constraint must hold; outside it, nothing is promised — and in a real problem the perturbation does sometimes land outside. Chapter 3 answered this for linear problems with the globalized robust counterpart: keep the constraint exactly on the normal range Z\mathcal{Z}Z, and let it degrade…

10 thms7 active users
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: iris

Distributionally Robust Search: The Power of Information and the Limits of MomentsResearch Paper

Searching an ordered list for a target drawn from a probability distribution is one of the oldest problems in algorithms: when the distribution ppp is known, an optimal or near-optimal comparison strategy (an optimal binary search tree, or median search Mehlhorn 1975) costs O(OPT(p))O(\mathrm{OPT}(p))O(OPT(p)) queries in expectation, which can be far below the …

62 thms6 active usersReviewed
🏆Completed
Mathematical LogicTheoretical Computer Science·Captain: Shuze Chen

Horn Maximum Satisfiability: Reductions, Algorithms and Applications: SAT reduces to Horn MaxSAT by dual-rail encodingResearch Paper

Boolean satisfiability asks whether a collection of logical requirements can hold simultaneously. Maximum satisfiability instead asks how many requirements can hold, while sometimes retaining a separate collection that must hold. Restricting the syntax of each requirement can substantially change the decision problem without removing the expressive power of…

19 thms6 active usersReviewed
🏆Completed
Operations ResearchOptimal TransportProbability·Captain: Shuze Chen

Technical Note—Data-Driven Chance Constrained Programs over Wasserstein Balls: Exact deterministic reformulation of chance constraintsResearch Paper

A decision can be inexpensive on average yet fail too often to be acceptable. A chance constraint addresses this by bounding the probability of an unsafe outcome. When the distribution of uncertainty is itself unknown, enforcing the constraint only under observed frequencies can overlook outcomes absent from the data. A distributionally robust chance…

16 thms6 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchStochastic Systems·Captain: Shuze Chen

Stochastic Networks XII: Implied Costs and Sensitivity in Loss NetworksTextbook

An accepted call earns revenue but occupies circuits that could serve later calls. In a network, those consequences extend beyond the links used by the original call: a change in blocking on one link changes the traffic reaching other links. Network planning therefore needs a marginal value that accounts for these indirect effects. Chapter 4 of Kelly and…

9 thms6 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: Shuze Chen

Stochastic Networks XI: Gaussian Limits for Large Loss NetworksTextbook

A loss network accepts a request only when all resources needed by that request are available. An accepted telephone call, for example, occupies circuits on several links at once. A blocked request leaves immediately. Resource sharing makes route occupancies dependent, even when the arrival streams are independent. For a large network, its exact equilibrium…

15 thms6 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: Shuze Chen

Robust Optimization VI: The Matrix Cube Bound for Robust Least SquaresTextbook

A least-squares constraint limits the Euclidean length of a residual. When the coefficients of that residual are uncertain, checking the constraint at nominal data does not ensure that it holds for the data that actually occur. A robust constraint requires the same decision to satisfy the bound for every allowed perturbation. Such constraints arise…

10 thms6 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: Shuze Chen

Robust Optimization VIII: Rank-Sensitive Approximation of Robust LMIsTextbook

A linear matrix inequality requires a symmetric matrix, whose entries depend affinely on design variables, to be positive semidefinite. Such constraints express many optimization and control requirements. When coefficients are uncertain, a design must satisfy a whole family of matrix inequalities. Checking each possible perturbation separately is generally…

12 thms6 active usersReviewed
🏆Completed
Linear algebraOperations Research·Captain: mikedeng1

Numeraire-Invariant Quadratic Hedging and Mean–Variance Portfolio Allocation: Explicit Oblique-Projection Formulas for the Optimal Adjustment Process and Pure HedgeResearch Paper

Quadratic hedging chooses a self-financing trading strategy that minimizes the expected squared difference between its terminal value and a payoff HHH; with HHH constant it becomes mean–variance portfolio selection. The classical theory works in discounted prices: one asset is a risk-free numeraire, and optimal strategies are written in terms of the remaining…

15 thms6 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchProbability·Captain: Shuze Chen

Interior Point Algorithms VIII: The Semidefinite Relaxation Bounds Quadratic Programs within π/2Textbook

Many problems in combinatorial optimization, control and signal processing reduce to minimizing a nonconvex quadratic form over a box. Max-cut and other boolean quadratic programs are special cases. Computing the global minimum of such a program is NP-hard in general, so the practical question is how well a tractable convex problem can bound it. The semidefi…

16 thms6 active usersReviewed
PreviousPage 1 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