Primal-dual first-order methods with O(1/e){\mathcal {O}(1/\epsilon)} iteration-complexity for cone programming
| 详细信息 | 推荐本文 | |
- 作者：Guanghui Lan (1) glan@isye.gatech.edu
Zhaosong Lu (2) zhaosong@sfu.ca
Renato D. C. Monteiro (3) monteiro@isye.gatech.edu - 关键词：Cone programming – ; Primal ; dual first ; order methods – ; Smooth optimal method – ; Nonsmooth method – ; Prox ; method – ; Linear programming – ; Semidefinite programming
- 刊名：Mathematical Programming
- 出版时间：January 2011
- 出版年：2011
- 期刊代码：104_0025-5610
- 类别：cp
- 卷：126
- 期：1
- 页码：1-29
- 数据来源：sp
摘要
In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov’s optimal method (Nesterov in Doklady AN SSSR 269:543–547, 1983; Math Program 103:127–152, 2005), Nesterov’s smooth approximation scheme (Nesterov in Math Program 103:127–152, 2005), and Nemirovski’s prox-method (Nemirovski in SIAM J Opt 15:229–251, 2005), and propose a variant of Nesterov’s optimal method which has outperformed the latter one in our computational experiments. We also derive iteration-complexity bounds for these first-order methods applied to the proposed primal-dual reformulations of the cone programming problem. The performance of these methods is then compared using a set of randomly generated linear programming and semidefinite programming instances. We also compare the approach based on the variant of Nesterov’s optimal method with the low-rank method proposed by Burer and Monteiro (Math Program Ser B 95:329–357, 2003; Math Program 103:427–444, 2005) for solving a set of randomly generated SDP instances.