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
Machine LearningOperations ResearchProbability+1·Captain: mikedeng1

A Distributional Interpretation of Robust Optimization II: Box-Robust Sample Average Optimization Is ConsistentResearch Paper

Many decision problems under uncertainty take the form of a stochastic program: choose a decision vvv from a feasible set F\mathcal FF to maximise the expected utility Ex∼μ[f(v,x)]\mathbb E_{x\sim\mu}[f(v,x)]Ex∼μ​[f(v,x)], where the distribution μ\muμ of the uncertain parameter x∈Rmx\in\mathbb R^mx∈Rm is known only through i.i.d. samples x1,…,xnx_1,\dots,x_nx1​,…,xn​. The standard remedy, sample average…

7 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability·Captain: mikedeng1

Robust solutions of Linear Programming problems contaminated with uncertain data: A Violation-Probability Bound for the Robust CounterpartResearch Paper

Linear programs solved in practice carry data that are measured, estimated or rounded. Ben-Tal and Nemirovski (Math. Program. 88, 2000) examined the NETLIB collection of real-world LPs and found that in 13 of them a relative perturbation of only 0.01% in the "ugly" coefficients of the inequality constraints can make the nominal optimal solution more than…

12 thms4 active usersReviewed
🏆Completed
Discrete GeometryLinear OptimizationNumber Theory+1·Captain: mikedeng1

Maximal Lattice-Free Convex Sets in Linear Subspaces I: Characterization of Maximal Lattice-Free Convex Sets in a SubspaceResearch Paper

Cutting planes for mixed-integer linear programs are often derived from convex sets that contain no integer point in their interior. Balas observed in 1971 that every such lattice-free convex set containing the current fractional LP solution in its interior yields a valid inequality, the intersection cut (Balas, Intersection cuts, Oper. Res. 19, 1971). The…

18 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningProbability+1·Captain: mikedeng1

Learnability, Stability and Uniform Convergence II: Tikhonov-Regularized ERM Learns Convex Lipschitz Stochastic Optimization in Hilbert Space with High ProbabilityResearch Paper

Statistical learning theory asks when a rule that sees only an i.i.d. sample z1,…,zmz_1,\dots,z_mz1​,…,zm​ from an unknown distribution DDD can return a hypothesis whose expected loss is close to the best possible. In supervised classification the classical answer is uniform convergence: learnability holds exactly when empirical risks converge to expected risks uniformly…

9 thms4 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingOperations Research·Captain: mikedeng1

Robust Control of Markov Decision Processes with Uncertain Transition Matrices 1: Perfect Duality and the Robust Dynamic Programming Recursion for Finite-Horizon MDPsResearch Paper

A Markov decision process (MDP) is solved by dynamic programming once its transition probabilities are known. In practice they are estimated from data, and the optimal policy of an MDP can be sensitive to estimation error: a policy computed from point estimates may perform much worse under the true transition matrices. Nilim and El Ghaoui (Oper. Res. 53(5),…

11 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningStatistics·Captain: mikedeng1

A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers: Error Bounds under Decomposability and Restricted Strong ConvexityResearch Paper

High-dimensional statistics studies estimation when the number of parameters ppp is comparable to, or larger than, the number of observations nnn. The standard estimators in this regime are regularized M-estimators: minimise an empirical loss plus a penalty that encodes structure, such as the Lasso (ℓ1\ell_1ℓ1​ penalty, sparse vectors), the group Lasso (block norms,…

5 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research·Captain: Shuze Chen

Disjunctive Programming XVI: Unions of Upper Monotone Polytopes and PolymatroidsTextbook

This mission is the sixteenth and last of the Disjunctive Programming series, and its goal theorem is the book's own closing result. The chapter's arc closes a loop opened at the very start of the book: Theorem 2.1 (02a-convex-hull) gave the convex hull of a union of polyhedra in the same space via lifting; this chapter's Theorem 13.13 (not drafted in this…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research·Captain: Shuze Chen

Disjunctive Programming XV: Dominants of Polytopes and Upper SeparationTextbook

Many real-world disjunctive models are not unions of polyhedra in a single shared space, but unions of polyhedra in different spaces linked by a logical implication: some action affecting one set of entities has consequences for another. Balas's treatment of such models (§17 of the book, following [17]) reduces to understanding a single auxiliary object…

8 thms4 active users
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Disjunctive Programming XIV: Disjunctive Cuts from the V-Polyhedral RepresentationTextbook

The lift-and-project cut-generating LP (CGLP) is the workhorse of the book's cutting-plane machinery, but its number of variables grows with qqq, the number of terms in the disjunction — a real computational cost for disjunctions with many terms. An alternative representation of the same disjunctive hull, built from vertices and extreme rays rather than from…

7 thms4 active users
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Disjunctive Programming XIII: Monoidal Cut Strengthening and the Gomory Mixed-Integer CutTextbook

The Gomory mixed-integer (GMI) cut is the single most widely deployed cutting plane in practical mixed-integer programming: every commercial solver generates it, from a simplex tableau row, essentially for free. Yet the GMI cut is not the strongest cut derivable from the same row: once a subset of the variables is known to be integer-constrained, that…

8 thms4 active users
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Disjunctive Programming XI: The Cut-Generating LP Under a Ray NormalizationTextbook

Lift-and-project (L&P) cuts strengthen the linear relaxation of a mixed 0-1 program by separating a fractional point from the convex hull of a disjunction such as xk≤0∨xk≥1x_k \le 0 \lor x_k \ge 1xk​≤0∨xk​≥1. Generating an optimal L&P cut means solving the cut-generating linear program (CGLP), a linear program lifted to a space with one new pair of variables per constraint of…

8 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Disjunctive Programming X: Solving the Cut-Generating LP on the Simplex TableauTextbook

Chapter 8 established an exact correspondence between lift-and-project cuts and simple disjunctive cuts, but its practical payoff is what this chapter develops: the cut-generating LP (CGLP)_k never needs to be formulated or solved on its own. Every pivot of (CGLP)_k can instead be mimicked directly on the much smaller simplex tableau of the original LP…

9 thms4 active usersReviewed
Linear OptimizationOperations Research·Captain: Shuze Chen

Disjunctive Programming IX: The Correspondence Between Lift-and-Project Cuts and Simple Disjunctive CutsTextbook

Chapter 6 built lift-and-project (L&P) cuts from a cut-generating LP, and Chapter 7 surveyed alternative nonlinear constructions reaching the same integer hull. This chapter asks a sharper question: how do L&P cuts relate, coefficient for coefficient, to older, more classical cutting planes — simple disjunctive cuts and mixed integer Gomory cuts, derived…

14 thms4 active users
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Disjunctive Programming VIII: Nonlinear Higher-Dimensional RepresentationsTextbook

Chapter 2's convex-hull machinery gives an exact, finitely-generated linear description of a disjunctive set's convex hull, but for a mixed 0-1 program with ppp binary variables that description lives in a space with roughly pnpnpn auxiliary variables — one full lift per disjunction. This chapter surveys the alternative nonlinear higher-dimensional constructions…

16 thms4 active users
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Disjunctive Programming VII: Lift-and-Project Cuts for Mixed 0-1 ProgramsTextbook

A mixed 0-1 program's feasible region is a disjunctive set built from the split disjunctions xj≤0∨xj≥1x_j \le 0 \lor x_j \ge 1xj​≤0∨xj​≥1, one per binary variable — a special case general enough that Chapter 2's convex-hull machinery applies directly, yet structured enough to produce closed-form cutting planes efficiently. The resulting lift-and-project (L&P) cuts, generated…

8 thms4 active users
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

A Branch and Bound Algorithm for the Generalized Assignment Problem: The Knapsack Penalty Bound Equals the Lagrangean Bound at Second-Smallest CostsResearch Paper

The generalized assignment problem (GAP) asks for the cheapest way to give each of nnn tasks to exactly one of mmm agents when every agent has a limited amount of a resource and different agents consume different amounts of it for the same task. It models assigning jobs to machines or computers, software tasks to programmers, commercials to time slots, and…

10 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Disjunctive Programming II: The Convex Hull of a Disjunctive Set via Lifting and ProjectionTextbook

Convexity is what makes optimization tractable: a linear program's feasible region is convex, and this single fact underwrites the simplex method, LP duality, and everything built on top of them. Integer and disjunctive programs have no such luck — their feasible regions are unions of polyhedra, and a union of convex sets is generally not convex. If the conv…

8 thms4 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Strategic Capacity Rationing to Induce Early Purchases: Rationing Is Optimal When the Valuation Bound Reaches U_c, Low-Price-Only OtherwiseResearch Paper

Retailers of seasonal goods sell at a full price first and mark down later. Customers who know this can wait for the markdown, and a firm that always has stock left for the markdown teaches them to wait. One remedy is to stock less than the low-price market would absorb, so that a customer who waits risks not getting the good at all. Liu and van Ryzin (Manag…

9 thms4 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Advance Demand Information, Price Discrimination, and Preorder Strategies: When Preorder Profit Increases with Demand CorrelationResearch Paper

Firms that sell new products (consoles, books, films) often take preorders before release. A preorder serves two purposes at once. It lets the firm charge early adopters a different price from later buyers, a form of price discrimination, and the number of preorders is advance demand information: an early signal of how large regular-season demand will be.…

10 thms4 active usersReviewed
🏆Completed
Numerical AnalysisOperations Research·Captain: mikedeng1

Pattern Search Algorithms for Bound Constrained Minimization: Generalized Pattern Search Drives the Projected Stationarity Measure to ZeroResearch Paper

Pattern search methods minimize a function f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R by comparing values of fff at points of a structured set of trial points, without evaluating or approximating derivatives. Coordinate search and the method of Hooke and Jeeves (Hooke–Jeeves 1961) are the classical members of the family. Such methods remain in use when derivatives are…

21 thms4 active users
🏆Completed
Information TheoryOperations ResearchProbability·Captain: mikedeng1

Worst-Case Value-At-Risk and Robust Portfolio Optimization: A Conic Programming Approach 2: Closed Form of the Entropy-Constrained Worst-Case VaRResearch Paper

Value-at-Risk (VaR) is the loss level that a portfolio exceeds with probability at most ε\varepsilonε. It is the standard risk measure of banking regulation, and its classical computation assumes Gaussian returns: for a Gaussian return vector with mean x^\hat xx^ and covariance Γ\GammaΓ it equals −Φ−1(ε)w⊤Γw−x^⊤w-\Phi^{-1}(\varepsilon)\sqrt{w^\top\Gamma w} - \hat x^\top w−Φ−1(ε)w⊤Γw​−x^⊤w, where …

9 thms4 active usersReviewed
🏆Completed
Convex OptimizationFunctional Analysis·Captain: mikedeng1

Strong Convergence of a Proximal-Type Algorithm in a Banach Space: The Algorithm Converges Strongly to the Generalized Projection of x0 onto the Zeros of a Maximal Monotone OperatorResearch Paper

Many problems in optimization and variational analysis reduce to finding a zero of a maximal monotone operator TTT: minimizers of a proper convex lower semicontinuous function are the zeros of its subdifferential, and saddle points and solutions of variational inequalities are zeros of associated monotone operators. The classical tool is Rockafellar's proximal…

13 thms4 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraOperations Research·Captain: mikedeng1

Robust Solutions to Uncertain Semidefinite Programs III: Quadratic Growth and Uniqueness of the Robust SDP SolutionResearch Paper

A semidefinite program (SDP) minimizes a linear objective cTxc^TxcTx subject to a linear matrix inequality F(x)=F0+∑ixiFi⪰0F(x) = F_0 + \sum_i x_i F_i \succeq 0F(x)=F0​+∑i​xi​Fi​⪰0. When the data FiF_iFi​ are uncertain, El Ghaoui, Oustry and Lebret (SIAM J. Optim. 9(1), 1998) proposed to optimize against the worst case over a norm-bounded family of perturbations: the robust SDP. Their Theorem 3.1 shows…

10 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations Research·Captain: mikedeng1

Integrating Replenishment Decisions with Advance Demand Information I: The Myopic Order-Up-To Level Is Optimal When Observed Demand Beyond the Protection Period Is LargeResearch Paper

Many firms learn part of future demand before it has to be served: customers place orders days or weeks ahead of the date they need the goods, or commit to delivery dates in contracts. Advance demand information of this kind reduces the uncertainty the inventory manager has to protect against, and the question is how replenishment decisions should use it.…

15 thms4 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraNumerical Analysis+1·Captain: mikedeng1

Robust Solutions to Least-Squares Problems with Uncertain Data III: Structured Robust Least Squares Is Solved Exactly by a Semidefinite ProgramResearch Paper

Least squares fits a model Ax≈bAx \approx bAx≈b as if the data (A,b)(A, b)(A,b) were exact. In practice they are measured, rounded or estimated, and the least-squares solution can be very sensitive to such errors. El Ghaoui and Lebret (SIAM J. Matrix Anal. Appl. 18(4), 1997) proposed to treat the errors as deterministic, unknown but bounded, and to choose xxx minimizing the wor…

14 thms4 active users
PreviousPage 20 of 93Next

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