TY - JOUR
T1 - Linearly Convergent First-Order Algorithms for Semidefinite Programming
AU - Dang , Cong D.
AU - Lan , Guanghui
AU - Wen , Zaiwen
JO - Journal of Computational Mathematics
VL - 4
SP - 452
EP - 468
PY - 2017
DA - 2017/08
SN - 35
DO - http://doi.org/10.4208/jcm.1612-m2016-0703
UR - https://global-sci.org/intro/article_detail/jcm/10026.html
KW - Semi-definite programming, Linear matrix inequalities, Error bounds, Linear convergence.
AB - <p style="text-align: justify;">In this paper, we consider two different formulations (one is smooth and the other one is nonsmooth) for solving linear matrix inequalities (LMIs), an important class of semidefinite programming (SDP), under a certain Slater constraint qualification assumption. We then propose two first-order methods, one based on subgradient method and the other based on Nesterov&#39;s optimal method, and show that they converge linearly for solving these formulations. Moreover, we introduce an accelerated prox-level method which converges linearly uniformly for both smooth and non-smooth problems without requiring the input of any problem parameters. Finally, we consider a special case of LMIs, i.e., linear system of inequalities, and show that a linearly convergent algorithm can be obtained under a much weaker assumption.</p>