Linearly convergent first-order algorithms for semidefinite programming

DOI10.4208/JCM.1612-M2016-0703MaRDI QIDQ4688142zbMATH OpenOpenAlexFDO

Authors Cong D. Dang, Guanghui Lan, Zaiwen Wen

Publication date 22 October 2018

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

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

zbMATH Keywords

error boundslinear matrix inequalitiessemi-definite programminglinear convergence

Mathematics Subject Classification ID

Semidefinite programming (90C22)

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.

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

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)