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
Operations ResearchOptimization·Captain: mikedeng1

A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization: The Framework Returns an ε-Near-Stationary Point Within an Explicit Number of IterationsResearch Paper

Many problems in robust optimization, adversarial learning, distributionally robust learning and min-max games have the max-structured form

10 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Approximate Parametric Computation of Minimum-Cost Flows with Convex Costs: Linear Splines of the Marginal Costs with Bounded Step Sizes Give an (α, β)-Approximate Minimum-Cost Flow FunctionResearch Paper

Flow networks model the movement of material, traffic, electricity, or gas through connected systems. In many such models, the required net flow at each vertex varies with a parameter, so the object of interest is a whole family of optimal flows rather than one solution. When edge costs are nonlinear, solving a new optimization problem for every parameter…

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

A Study of Convex Convex-Composite Functions via Infimal Convolution with Applications: Under a Slater-Type Condition the Conjugate of g∘F Is an Attained Minimum over the Negative Polar ConeResearch Paper

Convex optimization often minimizes a function obtained by applying one convex function to the output of another map. The inner map may be vector valued, and its components need not be linear. To understand sensitivity, optimality conditions, and dual formulations for such a convex composite, one needs its Fenchel conjugate. Standard formulas for an affine…

9 thms2 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

Aggregating Distributed Energy Resources: Efficiency and Market Power I: A Profit-Seeking Aggregator with Two-Part Pricing Attains the Benchmark Welfare, Dispatch and PricesResearch Paper

Distributed energy resources (DERs) — rooftop solar, home batteries, electric vehicles — turn electricity consumers into prosumers who can both buy and sell power. Their individual capacities are far too small to bid in a wholesale electricity market directly, so regulators have opened these markets to DER aggregators, intermediaries that pool many small…

9 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOptimization·Captain: mikedeng1

Infinite-Dimensional Fisher Markets and Tractable Fair Division 2: For Linear Valuations on [0,1] the Feasible Utility Set Is a Projection of Linear and Parabolic ConstraintsResearch Paper

A Fisher market divides a supply of goods among buyers with different values and budgets. In many fair division models, the goods form a continuum: pieces of time, land, or a divisible resource can be allocated in arbitrarily small amounts. A direct description of all possible buyer utilities then appears to require one allocation function for every buyer.…

9 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryProbability·Captain: mikedeng1

Persuading Risk-Conscious Agents: A Geometric Approach I: The Sender's Persuasion Problem Is Solved by a Convex Program over Conv(P_a ∪ {0})Research Paper

Bayesian persuasion studies a sender who observes a state of the world and commits in advance to a randomized disclosure rule, in order to influence the action of a receiver who updates her belief by Bayes' rule. Since Kamenica and Gentzkow (2011) the model has been applied to platform design, recommendation systems, queue information and rating systems.…

7 thms2 active usersReviewed
🏆Completed
Graph TheoryOptimization·Captain: mikedeng1

Shortest Paths in Graphs of Convex Sets I: The Perspective Mixed-Integer Convex Program (5.5) Has the Same Optimal Value as the Shortest-Path Problem in a Graph of Convex SetsResearch Paper

Many planning problems combine a discrete choice with a continuous one. A robot moving through a cluttered room chooses which free regions to traverse and where exactly to cross between them; a vehicle chooses a sequence of operating modes and a trajectory within each mode. Marcucci, Umenberger, Parrilo and Tedrake (arXiv:2101.11565, SIAM J. Optim. 2024, doi…

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

On the tightness of SDP relaxations of QCQPs 5: The Multiplicity Bound k ≥ aff dim{b(γ) : γ ∈ F} + 1 Cannot Be Lowered by OneResearch Paper

A quadratically constrained quadratic program (QCQP) minimizes a quadratic function subject to quadratic inequality and equality constraints. QCQPs contain max-cut, binary programming, the trust-region subproblem and many problems from signal processing and control, and are NP-hard in general. The standard convex approach is the Shor semidefinite relaxation,…

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

On the tightness of SDP relaxations of QCQPs 4: Quadratic Eigenvalue Multiplicity k ≥ m + 1 Gives conv(D ∩ H) = D_SDP ∩ H and Opt = Opt_SDPResearch Paper

A quadratically constrained quadratic program (QCQP) minimizes a quadratic function subject to quadratic inequality and equality constraints. QCQPs model trust-region subproblems, max-cut and other binary programs, phase retrieval, and many problems in signal processing and control; in general they are NP-hard. The standard tool for bounding and solving…

10 thms2 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Bridging Bayesian and Minimax Mean Square Error Estimation via Wasserstein Distributionally Robust Optimization 2: The Fully Adaptive Frank-Wolfe Algorithm Converges LinearlyResearch Paper

The Frank-Wolfe algorithm (also called the conditional gradient method) minimizes a smooth convex function over a compact convex set using only a linear minimization oracle in place of a projection. Each step solves a linearized problem over the feasible set and moves toward its solution. This makes it the method of choice when projections are expensive but…

11 thms2 active usersReviewed
🏆Completed
Dynamical SystemsOptimization·Captain: mikedeng1

Understanding the Acceleration Phenomenon via High-Resolution Differential Equations V: Along the High-Resolution ODE of NAG-C, inf ‖∇f(X(u))‖² ≤ (12 + 9sL)‖x₀ − x⋆‖²/(2√s(t³ − t₀³))Research Paper

Nesterov's accelerated gradient method for smooth convex functions, called NAG-C in the source paper, minimizes an LLL-smooth convex function fff with function values decreasing at the rate O(L/k2)O(L/k^2)O(L/k2). That rate is optimal among first-order methods (Nesterov, 1983). A line of work starting with Su, Boyd & Candès (2016) studies such methods through ordinary…

9 thms2 active usersReviewed
🏆Completed
Control TheoryOptimization·Captain: mikedeng1

Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints I: A Feasible LMI and a ρ-Hard IQC Certify the Linear Rate ‖ξₖ − ξ⋆‖ ≤ √cond(P) ρᵏ ‖ξ₀ − ξ⋆‖Research Paper

First-order methods such as the gradient method, Nesterov's accelerated method and the Heavy-ball method are usually analysed one at a time, each with its own hand-built potential function. Lessard, Recht and Packard (SIAM J. Optim. 26(1), 2016; read here in arXiv:1408.3595v7) observed that such a method is a linear dynamical system in feedback with the…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Distributionally Robust Convex Optimization I: Under the Nesting Condition, a Worst-Case Expectation Constraint over a Standardized Ambiguity Set Is Equivalent to a Finite Conic SystemResearch Paper

A constraint E[v(x,z~)]≤w\mathbb E[v(x,\tilde z)] \le wE[v(x,z~)]≤w on a decision xxx requires the distribution of the random vector z~\tilde zz~. In practice that distribution is known only partially: its support, a few moments, or the probability mass of some regions estimated from data. Distributionally robust optimization asks that the constraint hold for every distribution…

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

A Modern Introduction to Online Learning XII: Coordinate-Wise Krichevsky–Trofimov Betting Has Parameter-Free Regret ‖u‖₁L∞√(2T ln(1 + e‖u‖∞T/ε)) + dεL∞Textbook

In online convex optimization, a learner makes a prediction before seeing the next loss. A standard regret guarantee often depends on a learning rate chosen using the size of the comparator that will be assessed later. That comparator is unknown during play. Chapter 13 of Orabona's textbook uses coin betting to obtain a bound that adapts to every comparator…

7 thms2 active usersReviewed
🏆Completed
Machine LearningOptimizationProbability·Captain: mikedeng1

Stochastic Model-Based Minimization of Weakly Convex Functions 5: Under μ-Strong Convexity, Model-Based Minimization with β_t = μ(t+1)/2 Reaches Expected Function Gap O(1/(μT))Research Paper

Many problems in statistical learning and signal processing minimize an expectation f(x)=Eξ[F(x,ξ)]f(x)=\mathbb E_\xi[F(x,\xi)]f(x)=Eξ​[F(x,ξ)] plus a regularizer or constraint r(x)r(x)r(x), with access to fff only through samples ξ∼P\xi\sim Pξ∼P. The standard tool is the stochastic (proximal) subgradient method, which replaces fff at the current point by a random linear function. Two other methods use…

6 thms2 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness III: Adaptive Restarts Take at Most ⌈2C(q+2)/(αβ)⌉ Inner Steps and Converge Linearly on Sharp ProblemsResearch Paper

First order primal–dual algorithms are used when a linear program is too large for a direct factorization or when matrix operations are cheaper than solving a sequence of linear systems. Their basic guarantees often bound an averaged duality gap by a quantity proportional to 1/t1/t1/t after ttt steps. A restart discards the current inner iteration history and…

8 thms2 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness II: Fixed-Frequency Restarts Shrink the Distance to the Solution Set by β per Restart on Sharp ProblemsResearch Paper

Linear programs at very large scale are increasingly solved by first-order primal-dual methods, which use only matrix-vector products instead of matrix factorizations. Such methods parallelize well and have a small memory footprint, but on their own they are slow to reach moderate or high accuracy. Applegate, Hinder, Lu and Lubin (arXiv:2105.12715, Math.…

8 thms2 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness I: The LP Saddle-Point Problem Is 1/(H(K)√(1+4R²))-Sharp on Every Ball W_R(0)Research Paper

First-order primal-dual methods (PDHG, extragradient, ADMM) are the engine of a new generation of large-scale linear programming solvers, such as PDLP, because they need only matrix–vector products with the constraint matrix. Their textbook guarantees for convex–concave saddle-point problems are sublinear, O(1/t)O(1/t)O(1/t) for the averaged iterate, while in practice…

7 thms2 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization+1·Captain: mikedeng1

Incremental Proximal Methods for Large Scale Convex Optimization II: With a Randomized Order and a Diminishing Stepsize, Incremental Subgradient-Proximal Methods Converge Almost Surely to an OptimumResearch Paper

Many problems in statistical learning, signal processing and distributed optimization minimize a sum of a large number mmm of convex components over a convex set: a data-fit term per sample plus a regularizer or constraint per sample. When mmm is large, a method that processes one component per iteration is often far cheaper per step than one that evaluates the…

7 thms2 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions V: Relaxed PRS on Squared Distances Converges Linearly Under Bounded Linear RegularityResearch Paper

The convex feasibility problem asks for a point in the intersection of closed convex sets. It underlies signal and image reconstruction, phase retrieval relaxations, and the constraint handling inside larger optimization methods. The workhorse algorithms are projection methods: the method of alternating projections (MAP), going back to von Neumann for…

15 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: mikedeng1

Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization 2: When √(λ0/λ2) > M the Perspective Relaxation Is at Least as Strong as the Big-M and PR(∞) RelaxationsResearch Paper

Best subset selection with ridge shrinkage asks for a coefficient vector β∈Rp\beta\in\mathbb R^pβ∈Rp that fits a response y∈Rny\in\mathbb R^ny∈Rn through a design matrix X∈Rn×pX\in\mathbb R^{n\times p}X∈Rn×p while using few nonzero coefficients:

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: mikedeng1

Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization 1: The Perspective Interval Relaxation Is a Least Squares Problem with a Separable Reverse-Huber or ℓ1 PenaltyResearch Paper

Best subset selection with ridge shrinkage asks for a sparse linear model: given a design matrix X∈Rn×pX\in\mathbb R^{n\times p}X∈Rn×p and responses y∈Rny\in\mathbb R^ny∈Rn, minimize

6 thms2 active usersReviewed
🏆Completed
Dynamical SystemsOptimization·Captain: mikedeng1

Fast Convergence of Inertial Dynamics and Algorithms with Asymptotic Vanishing Viscosity 2: For Strongly Convex Φ and α > 3, Φ(x(t)) − min Φ, ‖x(t) − x*‖² and ‖ẋ(t)‖² Are O(t^(−2α/3))Research Paper

Nesterov's accelerated gradient method minimizes a smooth convex function at the rate O(k−2)\mathcal O(k^{-2})O(k−2) in the number of iterations kkk, against O(k−1)\mathcal O(k^{-1})O(k−1) for plain gradient descent. Su, Boyd and Candès (arXiv:1503.01243) observed that, as the step size tends to zero, Nesterov's scheme becomes the second-order differential equation

9 thms2 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods II: Dual Strict Complementarity and Firm Convexity of the Components Give the Error Bound for f(Ax) + g(x)Research Paper

Proximal gradient methods are used to minimize an objective with one smooth part and one convex part whose proximal map can be evaluated. A small proximal gradient step is a practical stopping signal, but it indicates proximity to an optimizer only when the objective has an appropriate error bound. Section 4 of Drusvyatskiy and Lewis gives conditions for…

10 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

From Error Bounds to the Complexity of First-Order Descent Methods for Convex Functions 3: ISTA for ℓ1-Regularized Least Squares Satisfies f(x_k) − min f ≤ (f(x_0) − min f)/q^k with q = 1 + 2aγ_R/b²Research Paper

The ℓ1-regularized least squares problem (the Lasso, or basis pursuit denoising) is the model problem of compressed sensing and sparse inverse problems: given a matrix A∈Rm×nA\in\mathbb R^{m\times n}A∈Rm×n, data d∈Rmd\in\mathbb R^md∈Rm and a weight μ>0\mu>0μ>0, one seeks a vector xxx that fits Ax≈dAx\approx dAx≈d while having few nonzero entries. The standard first-order method for it is the i…

14 thms2 active usersReviewed
PreviousPage 19 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