{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,25]],"date-time":"2026-10-25T14:28:09Z","timestamp":1792938489158,"version":"4.5.0"},"reference-count":57,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We develop a fast and robust algorithm for solving large-scale convex composite optimization models with an emphasis on the $\\ell_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.<\/jats:p>","DOI":"10.1137\/16m1097572","type":"journal-article","created":{"date-parts":[[2018,2,13]],"date-time":"2018-02-13T14:14:48Z","timestamp":1518531288000},"page":"433-458","source":"Crossref","is-referenced-by-count":135,"title":["A Highly Efficient Semismooth Newton Augmented Lagrangian Method for Solving Lasso Problems"],"prefix":"10.1137","volume":"28","author":[{"given":"Xudong","family":"Li","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Defeng","family":"Sun","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kim-Chuan","family":"Toh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,2,13]]},"reference":[{"key":"atypb1","unstructured":"A. Y. Aravkin, J. V. Burke, D. Drusvyatskiy, M. P. Friedlander, and S. Roy,\n                      Level-set methods for convex optimization\n                      , preprint,arXiv:1602.01506, 2016."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/090756855"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/080714488"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/1462173.1462178"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0965-3"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0941-y"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961199"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596304010"},{"key":"atypb10","unstructured":"F. Clarke,\n                      Optimization and Nonsmooth Analysis\n                      , John Wiley and Sons, New York, 1983."},{"key":"atypb11","first-page":"65","author":"Dontchev A. L.","year":"1998","journal-title":"New York"},{"key":"atypb12","unstructured":"Y. Cui, D. F. Sun, and K.C. Toh,\n                      On the asymptotic superlinear convergence of the augmented Lagrangian method for semidefinite programming with multiple solutions\n                      , preprint,arXiv:1610.00875, 2016."},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"A. L. Dontchev and R. T. Rockafellar,\n                      Implicit Functions and Solution Mappings\n                      , Springer Monographs in Mathematics, Springer, New York, 2009.","DOI":"10.1007\/978-0-387-87821-8"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"F. Facchinei and J.S. Pang,\n                      Finite-Dimensional Variational Inequalities and Complementarity Problems\n                      , Springer, New York, 2003.","DOI":"10.1007\/b97543"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1093\/nsr\/nwt032"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2007.910281"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0364-4"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-013-0063-6"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(76)90003-1"},{"key":"atypb20","first-page":"41","volume":"9","author":"Glowinski R.","year":"1975","journal-title":"Inform. Rech. Op'erationelle"},{"key":"atypb21","first-page":"263","volume":"15","author":"Goebel R.","year":"2008","journal-title":"J. Convex Anal."},{"key":"atypb22","unstructured":"G. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , 3rd ed., Johns Hopkins University Press, Baltimore, MD, 1996."},{"key":"atypb23","first-page":"883","author":"Huang L.","year":"2010","journal-title":"Advances in Neural Information Processing Systems"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0586-z"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-014-0069-8"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2016.1138222"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050018"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"S. Kogan, D. Levin, B. R. Routledge, J. S. Sagi, and N. A. Smith,\n                      Predicting Risk from Financial Reports with Regression\n                      , NAACL-HLT 2009, Boulder, CO, 2009.","DOI":"10.3115\/1620754.1620794"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/130921428"},{"key":"atypb31","unstructured":"X. D. Li, D. F. Sun, and K.C. Toh,\n                      QSDPNAL: A Two-Phase Proximal Augmented Lagrangian Method for Convex Quadratic Semidefinite Programming\n                      , preprint,arXiv:1512.08872, 2015."},{"key":"atypb32","unstructured":"J. Liu, S. Ji, and J. Ye,\n                      SLEP: Sparse Learning with Efficient Projections\n                      , Arizona State University, 2009."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/0330025"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/0322019"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/0315061"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/120892167"},{"key":"atypb37","first-page":"372","volume":"27","author":"Nesterov Y.","year":"1983","journal-title":"Soviet Math. Dokl."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581275"},{"key":"atypb39","first-page":"206","author":"Robinson S. M.","year":"1981","journal-title":"Heidelberg"},{"key":"atypb40","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton University Press, Princeton, NJ, 1970."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/0314056"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1.2.97"},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"R. T. Rockafellar and R. J.B. Wets,\n                      Variational Analysis\n                      , Grundlehren Math. Wiss., Springer-Verlag, Berlin, 1998.","DOI":"10.1007\/978-3-642-02431-3"},{"key":"atypb44","unstructured":"M. Schmidt,\n                      Graphical Model Structure Learning with $\\ell_1$-Regularization\n                      , Ph.D. thesis, Department of Computer Science, The University of British Columbia, 2010."},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1287\/moor.27.1.150.342"},{"key":"atypb46","unstructured":"J. Sun,\n                      On Monotropic Piecewise Quadratic Programming\n                      , Ph.D. thesis, Department of Mathematics, University of Washington, 1986."},{"key":"atypb47","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/s10107-010-0394-2","volume":"125","author":"Tseng P.","year":"2010","journal-title":"Math. Program."},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1137\/090747695"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2009.2016892"},{"key":"atypb51","unstructured":"X. Xiao, Y. Li, Z. Wen, and L. Zhang,\n                      Semi-smooth second-order type methods for composite convex programs\n                      , preprint,arXiv:1603.07870, 2016."},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-015-0082-6"},{"key":"atypb53","unstructured":"M.C. Yue, Z. Zhou, and A. M.C. So,\n                      Inexact Regularized Proximal Newton Method: Provable Convergence Guarantees for Non-Smooth Convex Minimization without Strong Convexity\n                      , preprint,arXiv:1605.07522, 2016."},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1137\/080718206"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-010-9408-8"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1198\/016214506000000735"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9868.2005.00503.x"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1100-9"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1097572","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:15:21Z","timestamp":1787336121000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1097572"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1097572"],"URL":"https:\/\/doi.org\/10.1137\/16m1097572","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}