Primal-dual first-order methods with $${\mathcal {O}(1/\epsilon)}$$ iteration-complexity for cone programming |
| |
Authors: | Guanghui Lan Zhaosong Lu Renato D C Monteiro |
| |
Institution: | (1) Faculty of Mathematics, University “Al.I.Cuza” Iaşi, 700506 Iaşi, Romania;(2) Romania and Institute of Mathematics Octav Mayer, Iaşi, Romania |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|