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
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
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Disjunctive Programming XII: Intersection Cuts, Generalized Intersection Cuts, and Lift-and-Project CutsTextbook

Intersection cuts (Balas, 1971) are the founding construction of cutting-plane theory for mixed 0-1 and mixed-integer programs: given a fractional LP solution xˉ\bar xxˉ and a convex region SSS around it known to contain no feasible integer point, the hyperplane through the points where SSS's boundary meets the extreme rays of the LP cone at xˉ\bar xxˉ cuts off xˉ\bar xxˉ w…

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

Disjunctive Programming V: Moving Between Conjunctive and Disjunctive Normal FormsTextbook

Chapter 2 gives a compact lifted description of the closed convex hull of a disjunctive set once it is written as a union of polyhedra (its disjunctive normal form, DNF). But most discrete optimization problems present their feasible region the opposite way: as a conjunction of many small disjunctions (the conjunctive normal form, CNF) — "linear…

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

Disjunctive Programming IV: Sequential Convexification of Disjunctive SetsTextbook

Computing the convex hull of a disjunctive set — a union of finitely many polyhedra — is generally hard in direct proportion to how many polyhedra are in the union: Chapter 2's Theorem 2.1 gives a compact lifted description, but working with it still means reasoning about all the disjunctions of the program simultaneously. A natural question, with obvious…

6 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Disjunctive Programming III: Projecting Polyhedra and the Convex Hull via PolarityTextbook

Theorem 2.1 (the previous mission in this series) shows that the closed convex hull of a union of polyhedra has a compact description after lifting to a higher-dimensional space. That description comes in two dual flavors: a primal one, as the projection of an explicit lifted polyhedron, and a polar one, characterizing the hull's facets directly via a cone…

20 thms5 active users
🏆Completed
Complexity TheoryLinear algebraOperations Research·Captain: mikedeng1

Some NP-Complete Problems in Quadratic and Nonlinear Programming: Copositivity Testing Is NP-Hard via Subset SumResearch Paper

Nonlinear programming algorithms are routinely advertised as finding a local minimum. Most of them only certify first-order conditions (a KKT point), and the natural next question is whether a given feasible point is in fact a local minimum. For smooth problems where the Hessian is nonsingular this is a second-order test, but in the degenerate case the test…

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

Worst-Case Value-At-Risk and Robust Portfolio Optimization: A Conic Programming Approach 1: Exact Worst-Case VaR under Known Mean and Covariance and Its SDP RepresentationsResearch Paper

Value-at-Risk (VaR) is the standard regulatory measure of downside risk of a portfolio: the loss level that is exceeded only with a prescribed small probability ε\varepsilonε. Computing it requires the full distribution of asset returns, which is rarely known. In practice one estimates a mean vector and a covariance matrix and then assumes a Gaussian…

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

An Application of Simultaneous Diophantine Approximation in Combinatorial Optimization: A Small Integral Objective with the Same Optimal Solutions and Dual BasesResearch Paper

An algorithm for linear programming is strongly polynomial if the number of arithmetic operations it performs is bounded by a polynomial in the dimension of the problem alone (the number of variables and constraints), independently of the bit lengths of the numbers in the input. Many combinatorial optimization problems are linear programs over polyhedra of…

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

The Generalized Quasi-Variational Inequality Problem II: Existence via Projection and the Brouwer Fixed Point TheoremResearch Paper

A variational inequality asks for a point xxx of a set K⊆RnK\subseteq\mathbb R^nK⊆Rn at which a vector field fff makes a non-obtuse angle with every feasible direction: (x′−x)Tf(x)≥0(x'-x)^T f(x)\ge 0(x′−x)Tf(x)≥0 for all x′∈Kx'\in Kx′∈K. It is the common form of the first-order optimality condition of a constrained optimization problem, of complementarity problems in mathematical programming, and of…

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

On Properties of Stochastic Inventory Systems I: Using the EOQ Order Quantity in the Stochastic (Q, r) Model Raises Costs by at Most 1/8Research Paper

The economic order quantity (EOQ) is the most widely used formula in inventory management. It assumes that demand is a deterministic constant stream. Real demand is random, and the model that accounts for this, the continuous-review (Q,r)(Q, r)(Q,r) policy with stochastic demand, has no closed-form optimum: for decades its optimal parameters were computed…

18 thms5 active usersReviewed
🏆Completed
AnalysisOperations Research·Captain: mikedeng1

Robust Mean-Covariance Solutions for Stochastic Optimization II: An Inverse S-Shaped Derivative with Finite Limits Gives the Two-Point Support PropertyResearch Paper

In stochastic optimization the law of a random return rrr is rarely known exactly, while its mean and variance can be estimated. A robust mean-covariance decision maker therefore evaluates a utility uuu by its worst case

10 thms5 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOperations Research·Captain: mikedeng1

Logarithmic Regret Algorithms for Online Convex Optimization 1: Logarithmic Regret of Online Gradient DescentResearch Paper

Online convex optimization is a repeated game between a learner and an adversary. In each round t=1,…,Tt=1,\dots,Tt=1,…,T the learner commits to a point xtx_txt​ of a convex set P⊆Rn\mathcal P\subseteq\mathbb R^nP⊆Rn; only then is a convex cost function ftf_tft​ revealed, and the learner pays ft(xt)f_t(x_t)ft​(xt​). The learner is judged by its regret: its total cost minus the total cost of the best…

5 thms5 active usersReviewed
🏆Completed
Machine LearningOperations ResearchStatistics·Captain: mikedeng1

Generalization Bounds in the Predict-then-Optimize Framework I: Natarajan-Dimension Generalization Bound for Polyhedral Feasible RegionsResearch Paper

In many operational problems (shortest paths, assignment, planning) the decision solves a linear program whose cost vector is unknown at decision time and is predicted from contextual features. The predict-then-optimize pipeline fits a model fff that maps a feature vector xxx to a predicted cost vector c^=f(x)\hat c=f(x)c^=f(x), and then acts on the decision that is optimal…

9 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchProbability·Captain: naimengye

Multi-armed Bandit Allocation Indices III: Superprocesses, Condition D and the Index Theorem for a SFASTextbook

The index theorem says that among several Markov reward processes, of which one may be advanced at each decision time, the right one to advance is the one of greatest Gittins index. Chapter 4 of Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/9780470980033), asks how far this extends when the constituents are not…

10 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchProbability·Captain: naimengye

Multi-armed Bandit Allocation Indices II: Jobs, Parallel Machines, Search and Bandit-Dependent DiscountingTextbook

Chapter 3 of Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/9780470980033), asks which of the assumptions behind the index theorem can be dropped and which cannot, using the simplest bandit processes there are: jobs, which pay a single reward when they complete. Along the way it settles three questions that matter…

8 thms5 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: naimengye

Multistage Stochastic Optimization III: Distortion Risk Functionals and Their Dual RepresentationTextbook

A decision maker who does not want to be judged by expected loss alone needs a functional that weighs the bad outcomes more heavily than the good ones and still behaves well under optimization: monotone, convex, unchanged by shifting the loss, and scaling with it. Kusuoka's theorem (mission II) says every such law-invariant functional on an atomless space…

11 thms5 active usersReviewed
Control TheoryOperations ResearchStochastic Systems·Captain: mikedeng1

Resource Allocation and Cross-Layer Control in Wireless Networks IV: The Energy-Constrained Control AlgorithmTextbook

Battery-powered and energy-harvesting wireless devices cannot treat transmission power as free: a control algorithm that maximizes throughput without regard to energy will drain a device long before the network's other resources are exhausted. Chapter 6 of Georgiadis, Neely & Tassiulas's survey Resource Allocation and Cross-Layer Control in Wireless Networks…

15 thms5 active users
🏆Completed
Machine LearningOperations ResearchProbability·Captain: mikedeng1

Wasserstein Distributionally Robust Optimization I: Kantorovich Duality and Strong Duality for the Worst-Case RiskTextbook

Every data-driven decision problem faces the same trap. A decision-maker estimates a risk functional R(P,ℓ)=EP[ℓ(ξ)]R(P,\ell) = \mathbb{E}_P[\ell(\xi)]R(P,ℓ)=EP​[ℓ(ξ)] from a nominal distribution P^N\hat P_NP^N​ built from NNN training samples, then optimizes a loss function ℓ\ellℓ against P^N\hat P_NP^N​ instead of the unknown true distribution PPP. Because the optimizer adapts to the noise in P^N\hat P_NP^N​,…

23 thms5 active users
🏆Completed
Operations Research·Captain: mikedeng1

Supermodularity and Complementarity IV: Monotone Optimal Policies in Markov Decision ProcessesTextbook

A Markov decision process (MDP) chooses a decision in every period of a dynamic system whose state evolves stochastically in response to the decision, so as to maximize expected discounted return. Firms use this model for inventory, pricing, and advertising decisions that respond to a randomly evolving demand state; engineers use it for maintaining or…

11 thms5 active users
🏆Completed
Convex OptimizationMachine LearningOperations Research·Captain: mikedeng1

First-Order and Stochastic Optimization Methods for Machine Learning VI: The Classic Conditional Gradient MethodTextbook

Every method in Chapters 2-4 of this series solves a projection or proximal subproblem at every step — a Euclidean projection, or a Bregman-divergence prox-mapping — which can itself be as hard as the original problem when XXX is a complicated feasible set (a spectrahedron, a flow polytope, a matroid base polytope). The conditional gradient method (Frank &…

4 thms5 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOperations Research·Captain: mikedeng1

First-Order and Stochastic Optimization Methods for Machine Learning V: Nonconvex Stochastic Mirror DescentTextbook

Most machine learning training objectives — deep network losses, matrix factorization, regularized empirical risk with a nonconvex loss — are not convex, yet the great majority of convergence theory available before Ghadimi and Lan's 2013 work applied only to convex problems or gave no non-asymptotic rate at all. Ghadimi and Lan (2013) established the first…

10 thms5 active users
🏆Completed
Convex OptimizationMachine LearningOperations Research+1·Captain: mikedeng1

First-Order and Stochastic Optimization Methods for Machine Learning IV: Variance-Reduced Mirror Descent for Finite-Sum ProblemsTextbook

Empirical-risk-minimization objectives in machine learning are finite sums: Ψ(x)=1m∑i=1mfi(x)+h(x)\Psi(x) = \frac{1}{m}\sum_{i=1}^m f_i(x) + h(x)Ψ(x)=m1​∑i=1m​fi​(x)+h(x), one smooth term fif_ifi​ per training example (or per worker, in a distributed setting), plus a simple nonsmooth regularizer hhh. Chapter 4's basic stochastic mirror descent handles this by sampling a single random component gradient …

10 thms5 active users
PreviousPage 7 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