Optimization Online


Iterative Reweighted Minimization Methods for $l_p$ Regularized Unconstrained Nonlinear Programming

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

Abstract: In this paper we study general $l_p$ regularized unconstrained minimization problems. In particular, we derive lower bounds for nonzero entries of first- and second-order stationary points, and hence also of local minimizers of the $l_p$ minimization problems. We extend some existing iterative reweighted $l_1$ (IRL1) and $l_2$ (IRL2) minimization methods to solve these problems and proposed new variants for them in which each subproblem has a closed form solution. Also, we provide a unified convergence analysis for these methods. In addition, we propose a novel Lipschitz continuous $\epsilon$-approximation to $\|x\|^p_p$. Using this result, we develop new IRL1 methods for the $l_p$ minimization problems and showed that any accumulation point of the sequence generated by these methods is a first-order stationary point, provided that the approximation parameter $\epsilon$ is below a computable threshold value. This is a remarkable result since all existing iterative reweighted minimization methods require that $\epsilon$ be dynamically updated and approach zero. Our computational results demonstrate that the new IRL1 method is generally more stable than the existing IRL1 methods [21,18] in terms of objective function value and CPU time.

Keywords: $l_p$ minimization, iterative reweighted $l_1$ minimization, iterative reweighted $l_2$ minimization

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Citation: Manuscript, Department of Mathematics, Simon Fraser University, September 2012.

Download: [PDF]

Entry Submitted: 09/28/2012
Entry Accepted: 09/28/2012
Entry Last Modified: 10/06/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