Iterative reweighted minimization methods for l_p regularized unconstrained nonlinear programming

In this paper we study general \(l_p\) regularized unconstrained minimization problems. In particular, we derive lower bounds for nonzero entries of the 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\) ( \(\mathrm{IRL}_1\) ) and \(l_2\) ( \(\mathrm{IRL}_2\) ) minimization methods to solve these problems and propose 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 \(\Vert x\Vert ^p_p\) . Using this result, we develop new \(\mathrm{IRL}_1\) methods for the \(l_p\) minimization problems and show 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 \(\mathrm{IRL}_1\) method and the new variants generally outperform the existing \(\mathrm{IRL}_1\) methods (Chen and Zhou in 2012; Foucart and Lai in Appl Comput Harmon Anal 26:395–407, 2009).