TY - JOUR
T1 - Iterative reweighted minimization methods for lp regularized unconstrained nonlinear programming
AU - Lu, Zhaosong
N1 - Publisher Copyright:
© 2013, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.
Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.
PY - 2013/10
Y1 - 2013/10
N2 - In this paper we study general lp 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 lp minimization problems. We extend some existing iterative reweighted l1 (IRL1) and l2(IRL2) 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 ϵ-approximation to ‖x‖pp. Using this result, we develop new IRL1 methods for the lp 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 ϵ is below a computable threshold value. This is a remarkable result since all existing iterative reweighted minimization methods require that ϵ be dynamically updated and approach zero. Our computational results demonstrate that the new IRL1 method and the new variants generally outperform the existing IRL1 methods (Chen and Zhou in 2012; Foucart and Lai in Appl Comput Harmon Anal 26:395–407, 2009).
AB - In this paper we study general lp 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 lp minimization problems. We extend some existing iterative reweighted l1 (IRL1) and l2(IRL2) 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 ϵ-approximation to ‖x‖pp. Using this result, we develop new IRL1 methods for the lp 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 ϵ is below a computable threshold value. This is a remarkable result since all existing iterative reweighted minimization methods require that ϵ be dynamically updated and approach zero. Our computational results demonstrate that the new IRL1 method and the new variants generally outperform the existing IRL1 methods (Chen and Zhou in 2012; Foucart and Lai in Appl Comput Harmon Anal 26:395–407, 2009).
KW - Iterative reweighted l1 minimization
KW - Iterative reweighted l2 minimization
KW - lp Minimization
UR - http://www.scopus.com/inward/record.url?scp=84920707992&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84920707992&partnerID=8YFLogxK
U2 - 10.1007/s10107-013-0722-4
DO - 10.1007/s10107-013-0722-4
M3 - Article
AN - SCOPUS:84920707992
VL - 147
SP - 277
EP - 307
JO - Mathematical Programming
JF - Mathematical Programming
SN - 0025-5610
IS - 1-2
ER -