Nonmonotone Spectral Gradient Method for l_1-regularized Least Squares

In the paper, we investigate a linear constraint optimization reformulation to a more general form of the l_1 regularization problem and give some good properties of it. We first show that the equivalence between the linear constraint optimization problem and the l_1 regularization problem. Second, the KKT point of the linear constraint problem always exists since the constraints are linear; we show that the half constraints must be active at any KKT point. In addition, we show that the KKT points of the linear constraint problem are the same as the stationary points of the l_1 regularization problem. Based on the linear constraint optimization problem, we propose a nonomotone spectral gradient method and establish its global convergence. Numerical experiments with compressive sense problems show that our approach is competitive with several known methods for standard l_2-l_1 problem.