Primal-dual first-order methods with ${\cal O}(1/\epsilon)$ iteration-complexity for cone programming

Guanghui Lan (glanisye.gatech.edu)
Zhaosong Lu (zhaosongsfu.ca)
Renato D.C. Monteiro (monteiroisye.gatech.edu)

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 \cite{Nest83-1,Nest05-1}, Nesterov's smooth approximation scheme \cite{Nest05-1}, and Nemirovski's prox-method \cite{Nem05-1}, 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 (SDP) 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 \cite{BuMo03-1,BuMo05-1} for solving a set of randomly generated SDP instances.

Keywords: Cone programming, primal-dual first-order methods, smooth optimal method, non-smooth method, prox-method, linear programming,semidefinite programming

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization

Citation: Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205 USA, December 2006.

Download: [Postscript][PDF]

Entry Submitted: 12/05/2006
Entry Accepted: 12/05/2006
Entry Last Modified: 12/26/2006

Modify/Update this entry