In this paper, we study a gradient based method for general cone programming (CP) problems. In particular, we first consider four natural primal-dual convex smooth minimization reformulations for them, and then discuss a variant of Nesterov’s smooth (VNS) method recently proposed by Tseng  for solving these reformulations. The associated worst-case major arithmetic operations costs of the VNS method for them are estimated and compared. We show that for a class of CP problems, the VNS method based on the last reformulation generally outperforms that applied to the others. Finally, we discuss the application of the VNS method  to some large-scale CP problems arising in compressed sensing, which are highly challenging to simplex and/or interior point (IP) methods. The performance of this method is compared with the IP method  that is specially implemented for these problems. Our computational results demonstrate that for these CP problems, the VNS method  applied to the mostly suitable reformulation mentioned above substantially outperforms the IP method .
Manuscript, Department of Mathematics, Simon Fraser University, Burnaby, BC V5A 1S6, Canada, September 2008.