Optimization Online


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

Guanghui Lan (glan***at***isye.gatech.edu)
Zhaosong Lu (zhaosong***at***sfu.ca)
Renato D.C. Monteiro (monteiro***at***isye.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society