Optimization Online


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

Zhaosong Lu (zhaosong***at***sfu.ca)

Abstract: 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].

Keywords: Cone programming, variant of Nesterovís smooth method, compressed sensing

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Applications -- Science and Engineering (Statistics )

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

Download: [PDF]

Entry Submitted: 09/03/2008
Entry Accepted: 09/03/2008
Entry Last Modified: 09/17/2008

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