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
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
Machine LearningOperations ResearchStatistics·Captain: Shuze Chen

Shape-Constrained Regression Using Sum of Squares Polynomials: Almost-sure consistency of convex sum-of-squares estimatorsResearch Paper

Regression estimates an unknown relationship between features and responses from noisy observations. In many applications, a qualitative property of that relationship is known before data are collected. A production response may exhibit convexity, or a response may have a known directional derivative bound. Enforcing such information throughout a continuous…

18 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
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Gradient-Based Algorithms for Convex Discrete Optimization via Simulation: Truncated Stochastic Subgradient Descent with Rounding Finds an (ε, δ)-Good Solution of Stochastic Submodular MinimizationResearch Paper

Many operations decisions are made over discrete, high-dimensional choices whose cost can only be estimated by simulation: how many bikes to place at each station, which subset of facilities to open, how to allocate servers in a queueing network. Each evaluation of a candidate decision is a noisy run of a simulator, and the goal is to select a decision…

15 thms4 active usersReviewed
🏆Completed
Functional AnalysisOperations ResearchOptimization·Captain: mikedeng1

On the Douglas–Rachford Algorithm for Solving Possibly Inconsistent Optimization Problems: The Primal Shadows Converge Weakly, and in Value, to a Solution of the Normal ProblemResearch Paper

The Douglas–Rachford algorithm is one of the most widely used splitting methods for minimizing a sum f+gf + gf+g of two convex functions, or more generally for finding a zero of a sum A+BA + BA+B of two maximally monotone operators. It touches each summand only through its proximal mapping (resolvent), which is why it underlies ADMM and a large share of first-order…

29 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Interior Point Algorithms I: The Central Path Converges to the Analytic Centers of the Optimal FacesTextbook

Primal–dual interior-point methods are the standard polynomial-time algorithms for linear programming. They do not walk along the vertices of the feasible polyhedron as the simplex method does. They follow a smooth curve through its interior, the central path, toward the optimal set. Every complexity bound for these methods is a statement about iterates…

7 thms4 active usersReviewed
🏆Completed
Discrete GeometryOperations ResearchOptimization·Captain: Shuze Chen

Lectures on Modern Convex Optimization IX: Ellipsoids Containing a Sum of Ellipsoids Within a Factor (π/2)^{n/2}Textbook

Ellipsoids are the simplest convex bodies that can approximate an arbitrary convex set to within a factor depending only on the dimension. They are used for exactly that in control (reachable sets of linear systems), robust optimization (uncertainty sets) and the ellipsoid method. A linear system x(t+1)=Ax(t)+Bu(t)x(t+1)=Ax(t)+Bu(t)x(t+1)=Ax(t)+Bu(t) with ∥u(t)∥2≤1\|u(t)\|_2\le1∥u(t)∥2​≤1 illustrates the need.…

18 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: Shuze Chen

Lectures on Modern Convex Optimization VI: Nesterov's π/2 Theorem for Semidefinite RelaxationsTextbook

Many combinatorial and nonconvex problems can be written as the maximization or minimization of a quadratic form under quadratic constraints. Such problems are NP-hard in general, but each has a semidefinite relaxation: a convex problem over positive semidefinite matrices, solvable to any accuracy in polynomial time, whose optimal value bounds the original…

19 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

A Soft Robust Model for Optimization Under Ambiguity: For Every δ > 0, Soft Robust Feasibility Is a Convex Risk Measure Constraint, and Every Normalized Convex Risk Measure Arises This WayResearch Paper

Optimization under uncertainty usually fixes one probability distribution P\mathbb PP for the uncertain data and optimizes an expected payoff, or fixes a set Q\mathcal QQ of distributions and protects against the worst one (robust optimization). The first is sensitive to a misspecified P\mathbb PP; the second can be very conservative, because it treats a barely…

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

Stochastic Dual Dynamic Integer Programming 3: The Convex Lower Envelope of a Function on {0,1}^n Is Piecewise Linear and Agrees with It at Every Binary PointResearch Paper

Multistage stochastic integer programs model sequential decisions under uncertainty in which some decisions are discrete: unit commitment in power systems, capacity expansion, production planning with setups. The standard decomposition methods for multistage stochastic linear programs, nested Benders decomposition and stochastic dual dynamic programming…

9 thms4 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Shortest Paths in Graphs of Convex Sets II: For Compact 𝒳 the Set-Based Relaxation 𝒮′ of Z = xyᵀ Is Exact at Every Extreme Point of a Polytope 𝒴Research Paper

The shortest-path problem in a graph of convex sets (SPP in GCS), introduced by Marcucci, Umenberger, Parrilo and Tedrake (arXiv:2101.11565, SIAM J. Optim. 2024), asks for a path through a directed graph whose vertices carry convex sets, together with a point in each visited set, minimizing a sum of convex edge lengths. It models motion planning around…

12 thms4 active usersReviewed
🏆Completed
Control TheoryLinear algebraOptimization·Captain: mikedeng1

Quadratic Matrix Inequalities with Applications to Data-Based Control IV: Noisy Data Are Informative for Quadratic Stabilization iff an LMI in (P, L, β) Is FeasibleResearch Paper

Data-driven control asks for a controller computed directly from measured trajectories of an unknown system, without first identifying a model. When the measurements are corrupted by unknown process noise, many systems explain the same data, and a controller designed from the data alone is only trustworthy if it stabilizes every one of them. Van Waarde,…

17 thms4 active usersReviewed
🏆Completed
Control TheoryLinear algebraOptimization·Captain: mikedeng1

Quadratic Matrix Inequalities with Applications to Data-Based Control I: Nonemptiness, Convexity, Boundedness and Interior of QMI Solution SetsResearch Paper

Quadratic matrix inequalities (QMIs) describe sets of matrices rather than sets of vectors. They appear whenever an unknown matrix is constrained by a quadratic bound: in robust control, where an uncertain block of a system is only known to lie in a norm ball or a sector, and in data-driven control, where the system matrices (A,B)(A, B)(A,B) of a linear system …

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

On the tightness of SDP relaxations of QCQPs 3: Quadratic Eigenvalue Multiplicity k ≥ m + 2 Gives conv(D) = D_SDP Without PolyhedralityResearch Paper

A quadratically constrained quadratic program (QCQP) minimizes a quadratic function subject to quadratic inequality and equality constraints. The class contains nonconvex problems such as binary programs, max-cut, the trust-region subproblem and many problems in signal processing and control. A standard convex approximation is the Shor semidefinite…

11 thms4 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Understanding the Acceleration Phenomenon via High-Resolution Differential Equations II: NAG-C Minimizes the Squared Gradient Norm at the Inverse Cubic Rate 8568‖x₀ − x⋆‖²/(s²(k + 1)³)Research Paper

Nesterov's accelerated gradient method for smooth convex objectives, here called NAG-C, reaches function-value accuracy O(L∥x0−x⋆∥2/k2)O(L\|x_0-x^\star\|^2/k^2)O(L∥x0​−x⋆∥2/k2) after kkk gradient evaluations, which is optimal among first-order methods (Nesterov 1983; Nesterov 2004). In many uses the quantity of interest is not the function gap but the squared gradient norm …

16 thms4 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Understanding the Acceleration Phenomenon via High-Resolution Differential Equations I: NAG-SC with Step Size 1/(4L) Satisfies f(xₖ) − f(x⋆) ≤ 5L‖x₀ − x⋆‖²/(1 + √(μ/L)/12)ᵏResearch Paper

Nesterov's accelerated gradient method is the standard example of a first-order method that is provably faster than gradient descent. On a μ\muμ-strongly convex function with LLL-Lipschitz gradient, gradient descent reduces the objective gap by a factor 1−O(μ/L)1-O(\mu/L)1−O(μ/L) per step, while the accelerated method achieves 1−O(μ/L)1-O(\sqrt{\mu/L})1−O(μ/L​), the best possible rate for…

11 thms4 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 7: Semi-APGM for min h + g Contracts ℒ_k by 1/(1 + α_k) and Has the Rate of Theorem 5.1Research Paper

Many problems in signal processing, statistics and control are posed as composite convex minimisation: minimise f=h+gf = h + gf=h+g, where hhh is smooth and ggg is convex but possibly nonsmooth or extended-valued (an ℓ1\ell^1ℓ1 penalty, a nuclear norm, the indicator of a constraint set). Proximal gradient methods handle ggg through its proximal operator and hhh through its…

10 thms4 active usersReviewed
🏆Completed
Machine LearningOptimizationProbability·Captain: mikedeng1

Distributed Stochastic Gradient Tracking Methods II: With Stepsizes θ/(m+k), DSGT's Mean-Square Error Is at Most 2θ²σ²/(n(θμ−1)(m+k)) Plus Higher-Order TermsResearch Paper

Many learning and estimation problems are solved by a group of computing agents that each hold part of the data and can talk only to their neighbours in a communication network. Each agent iii has a private cost fif_ifi​, and the group wants a minimizer of the average f=1n∑ifif=\frac1n\sum_i f_if=n1​∑i​fi​ without a central coordinator. In machine learning the agents usually cannot…

9 thms4 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Linear Convergence of First Order Methods for Non-Strongly Convex Optimization V: Fast Gradient on Quasi-Strongly Convex f Has f(x^k) − f* ≤ 2(1 − √μ)^k (f(x^0) − f*) if All y^k Share One ProjectionResearch Paper

Many convex problems met in practice — least squares with a rank-deficient matrix, dual problems of linearly constrained programs, min⁡xg(Ax)\min_x g(Ax)minx​g(Ax) with a strongly convex ggg and a wide matrix AAA — are not strongly convex: their optimal set is a whole affine piece rather than a point. The classical linear-rate theory of first order methods assumes strong…

10 thms4 active usersReviewed
🏆Completed
Control TheoryGraph TheoryOptimization·Captain: mikedeng1

Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs 1: DIGing Converges R-Linearly over Time-Varying Undirected Graphs for Every Step Size Below 1.5(1−δ)²/(μ̄J₁)Research Paper

In distributed optimization, nnn agents each hold a private function fi:Rp→Rf_i:\mathbb R^p\to\mathbb Rfi​:Rp→R and must jointly solve

11 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryDynamical Systems·Captain: mikedeng1

Learning in Games via Reinforcement and Regularization 1: Under Regularized Reinforcement Learning, Every Iteratively Dominated Strategy Becomes ExtinctResearch Paper

A basic test of any model of learning in games is whether it respects strict dominance: a strategy that does worse than another against every behaviour of the opponents should eventually be abandoned, and, after it is gone, so should every strategy that becomes dominated in what remains. For the replicator dynamics of evolutionary game theory this is…

13 thms4 active usersReviewed
Operations ResearchOptimal TransportOptimization·Captain: mikedeng1

Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls 1: Copositive Programs (28) Are Exact under Complete Recourse and Converge to (1) as δ ↓ 0Research Paper

Two-stage decision problems split decisions into a here-and-now decision xxx, taken before an uncertain parameter ξ\xiξ is observed, and a wait-and-see (recourse) decision yyy, taken after. Stochastic programming minimizes the expected total cost under a known distribution of ξ\xiξ; robust optimization minimizes the worst-case cost over a support set. Distributional…

19 thms4 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Minimizing Finite Sums with the Stochastic Average Gradient: SAG with Step 1/(16L) Has E[g(x̄ᵏ)] − g(x*) ≤ (32n/k)C₀, and Rate (1 − min{μ/(16L), 1/(8n)})ᵏC₀ if g Is μ-Strongly ConvexResearch Paper

Many problems in statistics and machine learning minimize a finite sum: an average of nnn smooth convex losses, one per data point, often plus a strongly convex regularizer. The full gradient method costs nnn component gradients per iteration and converges at rate O(1/k)O(1/k)O(1/k), or linearly when the objective is strongly convex (Nesterov, 2004). The stochastic…

19 thms4 active usersReviewed
PreviousPage 5 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