Please use this identifier to cite or link to this item:
Title: A highly efficient semismooth Newton augmented lagrangian method for solving lasso problems
Authors: Li, X
Sun, D 
Toh, KC
Keywords: Lasso
Sparse optimization
Augmented Lagrangian
Metric subregularity
Newton's method
Issue Date: 2018
Publisher: Society for Industrial and Applied Mathematics
Source: SIAM journal on optimization, 2018, v. 28, no. 1, p. 433-458 How to cite?
Journal: SIAM journal on optimization 
Abstract: We develop a fast and robust algorithm for solving large-scale convex composite optimization models with an emphasis on the l(1)-regularized least squares regression (lasso) problems. Despite the fact that there exist a large number of solvers in the literature for the lasso problems, we found that no solver can efficiently handle difficult large-scale regression problems with real data. By leveraging on available error bound results to realize the asymptotic superlinear convergence property of the augmented Lagrangian algorithm, and by exploiting the second order sparsity of the problem through the semismooth Newton method, we are able to propose an algorithm, called SSNAL, to efficiently solve the aforementioned difficult problems. Under very mild conditions, which hold automatically for lasso problems, both the primal and the dual iteration sequences generated by Ssnal possess a fast linear convergence rate, which can even be superlinear asymptotically. Numerical comparisons between our approach and a number of state-of-the-art solvers, on real data sets, are presented to demonstrate the high efficiency and robustness of our proposed algorithm in solving difficult large-scale lasso problems.
ISSN: 1052-6234
EISSN: 1095-7189
DOI: 10.1137/16M1097572
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Citations as of Sep 11, 2018


Citations as of Sep 19, 2018

Page view(s)

Citations as of Sep 18, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.