LINEARLY CONVERGENT FIRST-ORDER ALGORITHMS FOR SEMIDEFINITE PROGRAMMING

• 来源期刊: 计算数学（英文版）
• 关键词: Semi-definite Programming Linear Matrix Inequalities Error Bounds Linear Convergence
• 年，卷（期）: 2017,（4）
• 页码范围: 452-468
• 页数: 17页
• 语种: 英文
• DOI: 10.4208/jcm.1612-m2016-0703

摘要

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.