A constrained optimization reformulation and a feasible descent direction method for L1/2 regularization

• Published in: Computational optimization and applications 2014, Vol.59 (1-2), p.263-284
• Main Authors: Li, Dong-Hui, Wu, Lei, Sun, Zhe, Zhang, Xiong-ji
• Format: Article
• Language: English
• Subjects: Convex and Discrete Geometry; Management Science; Mathematics; Mathematics and Statistics; Operations Research; Operations Research/Decision Theory; Optimization; Statistics
• ISSN: 0926-6003; 1573-2894
• DOI: 10.1007/s10589-014-9683-7

In this paper, we first propose a constrained optimization reformulation to the L 1 / 2 regularization problem. The constrained problem is to minimize a smooth function subject to some quadratic constraints and nonnegative constraints. A good property of the constrained problem is that at any feasible point, the set of all feasible directions coincides with the set of all linearized feasible directions. Consequently, the KKT point always exists. Moreover, we will show that the KKT points are the same as the stationary points of the L 1 / 2 regularization problem. Based on the constrained optimization reformulation, we propose a feasible descent direction method called feasible steepest descent method for solving the unconstrained L 1 / 2 regularization problem. It is an extension of the steepest descent method for solving smooth unconstrained optimization problem. The feasible steepest descent direction has an explicit expression and the method is easy to implement. Under very mild conditions, we show that the proposed method is globally convergent. We apply the proposed method to solve some practical problems arising from compressed sensing. The results show its efficiency.