Linearly Convergent First-Order Algorithms for Semi-definite Programming

2013/09/09 by Cong D. Dang, Guanghui Lan, Dang, Cong D. +1
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #math.OC

paper · pdf · doi:10.48550/arxiv.1309.2251

arxiv created 2013/09/09 · openalex publication_date 2013/09/09 · arxiv updated 2013/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we consider two formulations for Linear Matrix Inequalities (LMIs) under Slater type constraint qualification assumption, namely, SDP smooth and non-smooth formulations. We also propose two first-order linearly convergent algorithms for solving these formulations. Moreover, we introduce a bundle-level method which converges linearly uniformly for both smooth and non-smooth problems and does not require any smoothness information. The convergence properties of these algorithms are also discussed. Finally, we consider a special case of LMIs, linear system of inequalities, and show that a linearly convergent algorithm can be obtained under a weaker assumption.

Citations

• Smooth minimization of non-smooth functions
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning

Related

• Efficient First-Order Methods for Linear Programming and Semidefinite Programming
• Instance-specific linear relaxations of semidefinite optimization problems
• A First Order Method for Linear Programming Parameterized by Circuit Imbalance
• On the convergence of iterative schemes for solving a piecewise linear system of equations
• A sequential semidefinite programming method and an application in passive reduced-order modeling