LINEARLY CONVERGENT FIRST-ORDER ALGORITHMS FOR SEMIDEFINITE PROGRAMMING  

作　　者：Cong D. Dang Guanghui Lan Zaiwen Wen 

机构地区：[1]Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611 [2]H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology,Atlanta, GA 30332, USA [3]Beijing International Center for Mathematical Research, Peking University, Beijing 100871, China

出　　处：《Journal of Computational Mathematics》2017年第4期452-468,共17页计算数学（英文）

摘　　要：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.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.

关 键 词：Semi-definite Programming Linear Matrix Inequalities Error Bounds Linear Convergence 

分 类 号：O[理学]