Linearly convergent first-order algorithms for semidefinite programming

DOI10.4208/JCM.1612-M2016-0703zbMATH Open1413.90196arXiv1309.2251OpenAlexW2964123585MaRDI QIDQ4688142FDOQ4688142

Authors: Cong D. Dang, Guanghui Lan, Zaiwen Wen 

Publication date: 22 October 2018

Published in: Journal of Computational Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1309.2251

Recommendations

• First- and second-order methods for semidefinite programming
• Regularization methods for semidefinite programming
• Large-scale semidefinite programming via a saddle point mirror-prox algorithm
• scientific article; zbMATH DE number 1345926
• A novel approach for solving semidefinite programs

zbMATH Keywords

error boundslinear matrix inequalitiessemi-definite programminglinear convergence

Mathematics Subject Classification ID

Semidefinite programming (90C22)

Cited In (1)

• Accelerated first-order methods for hyperbolic programming

This page was built for publication: Linearly convergent first-order algorithms for semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4688142)