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
Machine LearningProbabilityRandom Matrix Theory+1·Captain: mikedeng1

The Power of Convex Relaxation: Near-Optimal Matrix Completion I: Exact Nuclear-Norm Recovery with Quadratic Dependence on the RankResearch Paper

Matrix completion asks to recover a low-rank matrix from a small random subset of its entries. It models collaborative filtering (a ratings matrix with most entries missing), sensor-network localization from partial distance matrices, and system identification. The natural estimator, the matrix of least rank that agrees with the observations, is NP-hard to…

14 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
Machine LearningOptimizationProbability+1·Captain: Shuze Chen

Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in ℓp\ell_pℓp​ GeometriesResearch Paper

Stochastic convex optimization (SCO) asks for an approximate minimizer of a convex function that can only be probed through noisy subgradients. Two features of modern instances are not captured by the textbook Euclidean, bounded-variance setting. First, the natural geometry is often an ℓp norm with p>2p>2p>2: the feasible region is an ℓp ball and the Lipschitz…

15 thms1 active userReviewed
OptimizationQuantum InformationTheoretical Computer Science·Captain: Shuze Chen

Convex optimization on moment polytopes: Hadamard mirror descent and efficient algorithms for quantum functionals and other tensor parametersResearch Paper

Strassen's asymptotic spectrum of tensors governs the asymptotic rank and subrank of tensors, and with them questions such as the exponent of matrix multiplication. The quantum functionals of Christandl, Vrana and Zuiddam (CVZ23) were the first explicit family of universal spectral points for complex tensors of arbitrary order. They are defined as maxima of…

20 thms1 active userReviewed
Computational ComplexityMachine Learning·Captain: iris

Universal Hardness From Masking ChannelsResearch Paper

Given a class C\mathcal CC of predictors (Boolean circuits of bounded size, models of a fixed architecture), why is a labeling fff hard to approximate by members of C\mathcal CC? The hardcore lemma of complexity theory answers this for Boolean labels and the 0-1 loss: if every c∈Cc\in\mathcal Cc∈C errs on a δ\deltaδ-fraction of inputs, then there is a measure μ\muμ of…

31 thms1 active userReviewed
Machine LearningOperations Research·Captain: mikedeng1

Minimax Alternating Regret for the Experts Problem and Online Convex OptimizationResearch Paper

Alternating regret measures an online learner using both its action before a loss is revealed and its next action, chosen after seeing that loss. This timing arises when two players update their strategies alternately: one response is evaluated against two successive states of the opponent. Researchers studying online learning and game dynamics therefore…

17 thms1 active userReviewed
Linear OptimizationOptimizationTheoretical Computer Science·Captain: iris

Accelerated Parallel Algorithms for Packing Linear ProgrammingResearch Paper

A packing linear program asks for max⁡x≥0, Ax≤1⟨1,x⟩\max_{x\ge0,\ Ax\le\mathbf 1}\langle\mathbf 1,x\ranglemaxx≥0, Ax≤1​⟨1,x⟩ with A∈R≥0m×nA\in\mathbb R^{m\times n}_{\ge0}A∈R≥0m×n​. Packing LPs model resource allocation, fractional matching and fractional knapsack, and they are subroutines in approximation algorithms for scheduling and combinatorial auctions. The standard goal is low accuracy: a feasible x^\hat xx^…

25 thms1 active userReviewed
Functional AnalysisMachine LearningOptimization·Captain: iris

When Do Gradients Suffice? A Characterization of First-Order Convex OptimizationResearch Paper

First-order methods (gradient descent, Mirror Descent, their stochastic and accelerated variants) are the default tools of large-scale convex optimization, and their guarantees are usually stated in a Euclidean or ℓp\ell_pℓp​ geometry. A basic question underlies all of them: in which normed spaces can a convex Lipschitz function on the unit ball be minimized to…

66 thms1 active userReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: iris

Universal Acceleration: New Approaches to Heavy Ball DiscretizationResearch Paper

Two accelerated methods sit at the centre of first-order convex optimization. Nesterov's accelerated gradient descent (Nesterov 1983) minimizes an LLL-smooth, μ\muμ-strongly convex function in O(L/μlog⁡(1/ε))O(\sqrt{L/\mu}\log(1/\varepsilon))O(L/μ​log(1/ε)) gradient queries. Monteiro–Svaiter acceleration (Monteiro–Svaiter 2013) accelerates proximal-type steps, and Carmon et al. 2020 used it…

25 thms1 active userReviewed
PreviousPage 29 of 30Next

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