full
search.png

Search

close.png

Cancel

arrow
Volume 35, Issue 4
Linearly Convergent First-Order Algorithms for Semidefinite Programming

Cong D. Dang, Guanghui Lan & Zaiwen Wen

DOI: 10.4208/jcm.1612-m2016-0703

J. Comp. Math., 35 (2017), pp. 452-468.

Published online: 2017-08

Preview Purchase PDF 2119 31699

Cited by

google scholar semantic scholar
Export citation
  • Abstract

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'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.

  • Keywords

Semi-definite programming, Linear matrix inequalities, Error bounds, Linear convergence.

  • AMS Subject Headings

90C25, 90C06, 90C22, 49M37

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

congdd@ufl.edu (Cong D. Dang)

george.lan@isye.gatech.edu (Guanghui Lan)

wenzw@pku.edu.cn (Zaiwen Wen)

  • BibTex
  • RIS
  • TXT
@Article{JCM-35-452, author = {Dang , Cong D.Lan , Guanghui and Wen , Zaiwen}, title = {Linearly Convergent First-Order Algorithms for Semidefinite Programming}, journal = {Journal of Computational Mathematics}, year = {2017}, volume = {35}, number = {4}, pages = {452--468}, abstract = {

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'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.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1612-m2016-0703}, url = {http://global-sci.org/intro/article_detail/jcm/10026.html} }
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 -

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'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.

Dang , Cong D.Lan , Guanghui and Wen , Zaiwen. (2017). Linearly Convergent First-Order Algorithms for Semidefinite Programming. Journal of Computational Mathematics. 35 (4). 452-468. doi:10.4208/jcm.1612-m2016-0703
Copy to clipboard
BibteX RIS TXT
The citation has been copied to your clipboard