Gradient based method for cone programming with application to large-scale compressed sensing

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 [30] 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 [30] 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 [4] that is specially implemented for these problems. Our computational results demonstrate that for these CP problems, the VNS method [30] applied to the mostly suitable reformulation mentioned above substantially outperforms the IP method [4].

Citation

Manuscript, Department of Mathematics, Simon Fraser University, Burnaby, BC V5A 1S6, Canada, September 2008.

Article

Download

View Gradient based method for cone programming with application to large-scale compressed sensing