- 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/2006Entry Accepted: 12/05/2006Entry Last Modified: 12/26/2006Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.