Optimization Online


Iterative Hard Thresholding Methods for $l_0$ Regularized Convex Cone Programming

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

Abstract: In this paper we consider $l_0$ regularized convex cone programming problems. In particular, we first propose an iterative hard thresholding (IHT) method and its variant for solving $l_0$ regularized box constrained convex programming. We show that the sequence generated by these methods converges to a local minimizer. Also, we establish the iteration complexity of the IHT method for finding an $\epsilon$-local-optimal solution. We then propose a method for solving $l_0$ regularized convex cone programming by applying the IHT method to its quadratic penalty relaxation and establish its iteration complexity for finding an $\epsilon$-approximate local minimizer. Finally, we propose a variant of this method in which the associated penalty parameter is dynamically updated, and show that every accumulation point is a local minimizer of the problem.

Keywords: Sparse approximation, iterative hard thresholding method, $l_0$ regularization, box constrained convex programming, convex cone programming

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Combinatorial Optimization

Citation: Manuscript, Department of Mathematics, Simon Fraser University, Canada

Download: [PDF]

Entry Submitted: 10/30/2012
Entry Accepted: 10/31/2012
Entry Last Modified: 11/01/2012

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 Optimization Society