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

Cong D. Dang, Guanghui Lan & Zaiwen Wen

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

Published online: 2017-08

Preview Full PDF 2 554
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)

  • References
  • Hide All
    View All

@Article{JCM-35-452, author = {Dang , Cong D. and 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} }
Copy to clipboard
The citation has been copied to your clipboard