Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Convex Optimization

746 missions · 569 completed

Missions

Open177Completed569All746
🏆Completed
Linear OptimizationOperations ResearchOptimization·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
Operations ResearchOptimization·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
Operations ResearchOptimizationProbability·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
Discrete GeometryOperations ResearchOptimization·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
Functional AnalysisOperations Research·Captain: mikedeng1

On the Maximal Monotonicity of Subdifferential Mappings II: Subdifferentials Are Exactly the Maximal Cyclically Monotone Operators, Unique up to an Additive ConstantResearch Paper

A differentiable convex function on Rn\mathbb{R}^nRn is determined, up to an additive constant, by its gradient, and a vector field is a gradient of a convex function exactly when it satisfies a monotonicity condition along closed cycles. Convex analysis and optimization need the same statement for nonsmooth and extended-valued functions on infinite-dimensional…

16 thms5 active usersReviewed
🏆Completed
Functional AnalysisOperations ResearchOptimization+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
Machine LearningProbabilityRandom Matrix Theory+1·Captain: mikedeng1

The Power of Convex Relaxation: Near-Optimal Matrix Completion II: Exact Nuclear-Norm Recovery from Nearly Minimally Many EntriesResearch Paper

Many data sets are large matrices of which only a small fraction of the entries is observed, and of which the underlying object is believed to have low rank: user–item rating tables in collaborative filtering, distance matrices in sensor-network localization, and measurement matrices in structure-from-motion. Matrix completion asks when the missing entries…

22 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·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
Operations ResearchOptimization·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
Machine LearningOperations ResearchOptimization·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 ResearchOptimization·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
Machine LearningOperations ResearchOptimization·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
Machine LearningOperations ResearchOptimization+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
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: mikedeng1

First-Order and Stochastic Optimization Methods for Machine Learning II: Subgradient Descent, Mirror Descent and Accelerated Gradient DescentTextbook

Gradient descent's convergence rate for a general smooth convex problem is O(1/k)O(1/k)O(1/k) in the function-value gap; Nemirovski and Yudin (1983) proved that no first-order method can do better than O(1/k2)O(1/k^2)O(1/k2) is achievable, and Nesterov (1983, 1988, 2004) constructed the first method attaining it — the accelerated (or "fast") gradient method. For thirty years this…

14 thms5 active users
🏆Completed
Algorithmic Game TheoryLinear OptimizationMachine Learning+1·Captain: mikedeng1

Introduction to Online Convex Optimization VIII: Solving Zero-Sum Games and Linear Programs via Regret MinimizationTextbook

Two-player zero-sum games and linear programming are, on their surface, unrelated pieces of 20th-century mathematics: von Neumann's minimax theorem for games (1928) was proved with tools from topology, and linear programming duality (Dantzig, 1940s) with convexity and geometry. Yet the two are formally equivalent — Dantzig recounts von Neumann conjecturing…

8 thms5 active users
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Introduction to Stochastic Programming I: Convexity, Attainment and Optimality of the Two-Stage Recourse ProblemTextbook

Two-stage stochastic linear programming with recourse models a decision made before uncertainty resolves (the first-stage variables xxx) followed by a corrective decision made after (the second-stage, or recourse, variables yyy). Solving such a program means minimizing cTx+Q(x)c^{\mathsf T}x + Q(x)cTx+Q(x), where Q(x)Q(x)Q(x) is the expected cost of the best recourse action given xxx --…

17 thms5 active users
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Convex Optimization III: Conic Duality and the S-procedureTextbook

Two quadratic functions can be compared losslessly. The S-procedure says that, when the constraint is strictly feasible, the implication

17 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Convex Optimization I: Prékopa's TheoremTextbook

Log-concave functions are the meeting point of convex analysis and probability: densities of Gaussian, exponential, uniform and Wishart distributions are all log-concave, and countless facts of applied probability flow from one structural theorem — integrating out variables preserves log-concavity. This mission builds the convex-analysis spine of Boyd &…

29 thms5 active usersReviewed
🏆Completed
Algorithmic Game TheoryBandit AlgorithmsMachine Learning·Captain: iris

Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism: One-Bit Feedback Achieves O(T3/5log⁡5T)O(T^{3/5}\log^{5}T)O(T3/5log5T) Regret for Independent Regular ValuationsResearch Paper

A broker stands between a seller and a buyer. It posts a price to each, and the trade happens only if both accept. Posted prices are the standard mechanism when the parties cannot be asked to report their values: they are simple, strategy-proof and individually rational. When the trade repeats, the broker must learn profitable prices while observing only…

27 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryBandit AlgorithmsMachine Learning·Captain: iris

Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism: One-Bit Feedback Achieves O(Tlog⁡5/2T)O(\sqrt{T}\log^{5/2}T)O(T​log5/2T) Regret for Independent MHR ValuationsResearch Paper

A broker stands between a seller who owns one item and a buyer who may want it. In every round t=1,…,Tt=1,\dots,Tt=1,…,T a fresh pair of private valuations (st,bt)∈[0,1]2(s_t,b_t)\in[0,1]^2(st​,bt​)∈[0,1]2 arrives, and the broker posts a price ptp_tpt​ to the seller and a price qtq_tqt​ to the buyer. Trade happens when both accept (st≤pts_t\le p_tst​≤pt​ and qt≤btq_t\le b_tqt​≤bt​), and the broker earns qt−ptq_t-p_tqt​−pt​. The broker sees only…

21 thms4 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: iris

Dynamic Data-Driven Estimation of Non-Parametric Choice Models: With Primal-Oracle Steps, the Weighted Average Has Primal Optimality Gap at Most the Dual Regret Plus the Two Data-Error TermsResearch Paper

A non-parametric choice model describes customers by a probability distribution over rankings of nnn products: a customer offered a subset of products buys the one ranked highest among them. Revenue management and assortment planning use such models because they impose no functional form on substitution behaviour (Farias, Jagabathula and Shah, 2013; van Ryzin…

16 thms4 active usersReviewed
🏆Completed
Optimization·Captain: Shuze Chen

Theory and Applications of Robust Optimization: Tightness of the semidefinite approximation for affine adaptabilityResearch Paper

In a two-stage robust optimization problem, a decision maker commits to some variables before observing uncertain data and chooses the remaining variables after observing it. Requiring every decision to be fixed at the outset can lose the benefit of this information. Allowing an arbitrary response, however, can produce a problem with infinitely many…

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

Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis: Sparsity Theorem, the Closed-Form Minimizer of a Symmetric Gauge over Sparse Weak MajorantsResearch Paper

Many problems in statistics and signal processing ask for a vector that is both small in some norm and sparse, with at most KKK nonzero entries. The best-known example is sparse principal component analysis (sparse PCA), whose feasible set is the set of unit vectors in the Euclidean norm with at most KKK nonzero entries (d'Aspremont et al. 2007). Cardinality…

13 thms4 active usersReviewed
🏆Completed
Functional AnalysisOperations ResearchOptimization+1·Captain: Shuze Chen

Modeling, Measuring and Managing Risk II: Dual Representation of Acceptability FunctionalsTextbook

Risk functionals assign a number to an uncertain profit and are used as objectives and constraints in portfolio selection, insurance and energy planning. Since the axiomatization of coherent risk measures by Artzner, Delbaen, Eber and Heath (Math. Finance 1999), the standard way to understand such a functional is through a dual representation: the…

9 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Robust Optimization VII: Exact Robust LMIs with Norm-Bounded UncertaintyTextbook

A design constraint may require a symmetric matrix to remain positive semidefinite even when some of its coefficients are uncertain. Such constraints arise in the structural design problems discussed in Chapter 8 of Ben-Tal, El Ghaoui and Nemirovski, Robust Optimization. A design that satisfies a constraint at the nominal data can fail after a perturbation.…

3 thms4 active usersReviewed
PreviousPage 3 of 23Next

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