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
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

Cones of Matrices and Set-Functions and 0–1 Optimization IV: Clique, Odd Hole, Odd Wheel and Odd Antihole Constraints Hold after One Round of N₊Research Paper

The stable set problem (find a largest, or maximum-weight, set of pairwise non-adjacent nodes in a graph) is NP-hard, and its linear programming relaxations have been studied since the 1970s as a test bed for polyhedral combinatorics. Lovász and Schrijver (SIAM J. Optim. 1991) introduced a general lift-and-project procedure for 0–1 programs: lift a…

8 thms2 active usersReviewed
🏆Completed
Control TheoryOperations ResearchOptimization·Captain: mikedeng1

Robust Solutions to Uncertain Semidefinite Programs II: An SDP Inner Approximation of the Robust Feasible Set under Structured PerturbationsResearch Paper

A semidefinite program (SDP) minimizes a linear objective cTxc^TxcTx subject to a linear matrix inequality F(x)=F0+∑i=1mxiFi⪰0F(x) = F_0 + \sum_{i=1}^m x_i F_i \succeq 0F(x)=F0​+∑i=1m​xi​Fi​⪰0. In engineering applications the coefficient matrices are rarely known exactly: they come from measurements, from a model of a physical plant, or from a finite-precision implementation. El Ghaoui, Oustry and Lebret…

5 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Validation of Subgradient Optimization I: The Core Problem Built from the Subgradient Iterates Solves the Dual Linear ProgramResearch Paper

Subgradient optimization maximizes a concave function that is not differentiable by stepping along an arbitrary subgradient with a prescribed sequence of step sizes. It became a standard tool of integer programming after Held and Karp used it to compute the Lagrangian 1-tree bound for the traveling-salesman problem (Held & Karp 1971). Held, Wolfe and…

7 thms2 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisOperations Research+1·Captain: mikedeng1

Robust Solutions to Least-Squares Problems with Uncertain Data II: Robust Least Squares as Tikhonov RegularizationResearch Paper

Least squares fits a linear model Ax≃bAx \simeq bAx≃b by minimizing ∥Ax−b∥\|Ax - b\|∥Ax−b∥, and its solution can be extremely sensitive to errors in the data (A,b)(A, b)(A,b) when AAA is ill-conditioned. The standard remedy is Tikhonov regularization (ridge regression): minimize ∥Ax−b∥2+μ∥x∥2\|Ax - b\|^2 + \mu\|x\|^2∥Ax−b∥2+μ∥x∥2, whose solution x=(A⊤A+μI)−1A⊤bx = (A^\top A + \mu I)^{-1}A^\top bx=(A⊤A+μI)−1A⊤b is stable but depends on a…

9 thms2 active usersReviewed
🏆Completed
Linear algebraOptimization·Captain: mikedeng1

A Singular Value Thresholding Algorithm for Matrix Completion 3: Convergence to the Minimum Nuclear Norm SolutionResearch Paper

Nuclear norm minimization is the standard convex surrogate for rank minimization: to recover a low-rank matrix from a few linear measurements, or from a subset of its entries, one minimizes the sum of the singular values subject to the data constraints. For matrix completion, Candès and Recht (Found. Comput. Math. 2009) showed that this convex program…

8 thms2 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisOptimization·Captain: mikedeng1

A Singular Value Thresholding Algorithm for Matrix Completion 2: Convergence of the SVT Iteration under General Convex ConstraintsResearch Paper

Singular value thresholding (SVT) is a first-order method introduced by Cai, Candès and Shen (SIAM J. Optim. 20 (2010)) for recovering a low-rank matrix from incomplete or indirect information. Its basic form, for matrix completion, alternates a soft-thresholding of singular values with a gradient step on a dual variable, and needs only one sparse singular…

9 thms2 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisOptimization·Captain: mikedeng1

A Singular Value Thresholding Algorithm for Matrix Completion 1: The SVT Iteration Converges to the Unique Solution of the Proximal ProblemResearch Paper

Matrix completion asks to recover an n1×n2n_1\times n_2n1​×n2​ matrix MMM from a subset Ω\OmegaΩ of its entries. When MMM has low rank, a standard convex surrogate is to minimize the nuclear norm ∥X∥∗\|X\|_*∥X∥∗​ (the sum of the singular values) subject to agreeing with MMM on Ω\OmegaΩ; Candès and Recht showed that this recovers MMM exactly under incoherence and sampling conditions (Candès–…

12 thms2 active usersReviewed
🏆Completed
Functional AnalysisOperations ResearchOptimization·Captain: mikedeng1

A Three-Operator Splitting Scheme and its Optimization Applications 1: Weak and Strong Convergence of the Three-Operator Splitting IterationResearch Paper

Many problems in convex optimization, variational inequalities and signal processing reduce to a monotone inclusion: find a point xxx at which the sum of several monotone operators contains 000. When the sum has two terms, the classical operator-splitting methods (Douglas–Rachford, forward–backward, forward–backward–forward) solve it by iterating a fixed-point…

14 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

On Minimizing a Convex Function Subject to Linear Inequalities II: Optimality Conditions for the Sum of the Largest Linear FormsResearch Paper

In 1955 E. M. L. Beale showed how Dantzig's simplex method, which was built for linear objectives, can be carried over to certain nonlinear convex objectives that are minimized subject to linear inequalities (Beale 1955). Section 4 of that paper treats one such objective: the sum of the ttt largest of a set of ggg linear forms. Beale's motivation comes from the…

7 thms2 active usersReviewed
🏆Completed
Linear algebraLinear OptimizationOperations Research+1·Captain: mikedeng1

Path-Finding Methods for Linear Programming II: Properties of the Regularized D-Optimal-Design Weight FunctionResearch Paper

Interior point methods for a linear program min⁡{c⊤x:Ax≥b}\min\{c^\top x : Ax\ge b\}min{c⊤x:Ax≥b} with A∈Rm×nA\in\mathbb R^{m\times n}A∈Rm×n follow the central path of the logarithmic barrier −∑ilog⁡si-\sum_i\log s_i−∑i​logsi​, where s=Ax−bs=Ax-bs=Ax−b is the slack vector. Renegar's path-following analysis (1988) gives O(m L)O(\sqrt m\,L)O(m​L) iterations, and for decades this was the best bound for methods whose iterations cost a linear…

7 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Path-Finding Methods for Linear Programming I: Centering with Weights on the Weighted Central PathResearch Paper

Interior point methods solve a linear program by following a central path: a curve of minimizers of a penalized objective that trades off cost against distance from the boundary of the feasible region. The classical analysis of path following with the logarithmic barrier needs O(m L)O(\sqrt{m}\,L)O(m​L) iterations for a program with mmm constraints, where LLL is the bit…

6 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Nonmonotone Spectral Projected Gradient Methods on Convex Sets I: SPG2 Is Well Defined and Its Accumulation Points Are StationaryResearch Paper

Minimizing a smooth function over a closed convex set Ω⊆Rn\Omega\subseteq\mathbb R^nΩ⊆Rn on which projection is cheap (a box, a ball, a simplex) is a routine subproblem in large-scale optimization: box-constrained minimization is the inner solver of augmented Lagrangian methods, and bound-constrained least squares, image restoration and density estimation all have…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Robust Solutions of Optimization Problems Affected by Uncertain Probabilities II: A Self-Concordant Barrier for the Perspective ConstraintResearch Paper

Robust optimization protects a decision against every scenario in an uncertainty set. When the uncertain data are probabilities, a natural uncertainty set is a ball around a nominal distribution measured by a φ-divergence (Kullback–Leibler, Burg entropy, χ², Hellinger and others). Ben-Tal, den Hertog, De Waegenaere, Melenberg and Rennen (Management Science…

8 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Robust Solutions of Optimization Problems Affected by Uncertain Probabilities I: The Robust Counterpart of a Linear Constraint under φ-Divergence UncertaintyResearch Paper

Many decision problems contain a constraint whose coefficients are an expectation under a probability vector that is not known exactly: an expected cost under uncertain scenario probabilities, an expected payoff of an asset under an estimated distribution, the expected demand in a newsvendor model. The probabilities are usually estimated from data, and a…

12 thms2 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Introduction to Online Convex Optimization XI: Boosting via Online Convex OptimizationTextbook

A "rule of thumb" classifier — a single pixel's brightness distinguishing handwritten "0" from "1" — is trivial to produce and barely better than a coin flip. A rule that gets every example right is, in general, far harder. Boosting asks whether many weak, easy-to-produce rules can be combined into one strong, hard-to-produce rule, and Chapter 11 answers it…

3 thms2 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Introduction to Online Convex Optimization II: Convergence Rates for Well-Conditioned Convex OptimizationTextbook

Convex optimization — minimizing a convex function over a convex set — is the offline problem that online convex optimization (OCO) generalizes: an OCO algorithm run against a single, fixed cost function repeated every round is exactly an algorithm for this classical problem. Its convergence theory, developed over decades and surveyed comprehensively in…

9 thms2 active usersReviewed
🏆Completed
Optimization·Captain: wenxinzhang

Vector Space Methods XI: Generalized Kuhn–Tucker ConditionsTextbook

Luenberger's generalized Kuhn–Tucker theorem turns inequality-constrained optimization into an order-theoretic statement on normed vector spaces. Instead of listing scalar inequalities, it lets a convex cone P define positivity in a target space Z; one condition G x ≤ₚ 0 can therefore represent finite, infinite, or function-valued families of constraints.…

5 thms2 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: Minghui

A Field Guide to Federated Optimization: Convex FedAvg ConvergenceResearch Paper

Federated optimization studies learning when data and computation are spread across clients. Communicating after every stochastic gradient step can be costly, so clients often take several steps before averaging their models. The difficulty is that different clients can optimize different objective functions. Their models then move apart between…

5 thms1 active userReviewed
🏆Completed
Functional AnalysisOptimization·Captain: Shuze Chen

Vector Space Methods IV: Hahn–Banach and Minimum Norm DualityTextbook

Chapter 5 of Luenberger's Optimization by Vector Space Methods (Wiley, 1969) carries the minimum norm theory of Chapter 3 (Mission I of this series) from Hilbert space to arbitrary real normed spaces. The inner product is gone, so orthogonal projection is no longer available; its role is taken over by the Hahn–Banach theorem, in two classical forms. The…

17 thms1 active userReviewed
PreviousPage 23 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