{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T15:49:07Z","timestamp":1783093747196,"version":"3.54.6"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,8,27]],"date-time":"2022-08-27T00:00:00Z","timestamp":1661558400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,27]],"date-time":"2022-08-27T00:00:00Z","timestamp":1661558400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universit\u00e0 degli Studi di Roma La Sapienza"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>\u2113<\/mml:mi><mml:mn>1<\/mml:mn><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-ball is a nicely structured feasible set that is widely used in many fields (e.g., machine learning, statistics and signal analysis) to enforce some sparsity in the model solutions. In this paper, we devise an active-set strategy for efficiently dealing with minimization problems over the<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>\u2113<\/mml:mi><mml:mn>1<\/mml:mn><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-ball and embed it into a tailored algorithmic scheme that makes use of a non-monotone first-order approach to explore the given subspace at each iteration. We prove global convergence to stationary points. Finally, we report numerical experiments, on two different classes of instances, showing the effectiveness of the algorithm.<\/jats:p>","DOI":"10.1007\/s10589-022-00407-6","type":"journal-article","created":{"date-parts":[[2022,8,27]],"date-time":"2022-08-27T04:02:27Z","timestamp":1661572947000},"page":"693-721","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Minimization over the $$\\ell _1$$-ball using an active-set non-monotone projected gradient"],"prefix":"10.1007","volume":"83","author":[{"given":"Andrea","family":"Cristofari","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1189-5917","authenticated-orcid":false,"given":"Marianna","family":"De Santis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefano","family":"Lucidi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francesco","family":"Rinaldi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,8,27]]},"reference":[{"key":"407_CR1","unstructured":"LIBSVM data: classification, regression, and multi-label. https:\/\/www.csie.ntu.edu.tw\/~cjlin\/libsvmtools\/datasets\/"},{"issue":"2","key":"407_CR2","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s10589-009-9240-y","volume":"45","author":"R Andreani","year":"2010","unstructured":"Andreani, R., Birgin, E.G., Mart\u00ednez, J.M., Schuverdt, M.L.: Second-order negative-curvature methods for box-constrained and general constrained optimization. Comput. Optim. Appl. 45(2), 209\u2013236 (2010)","journal-title":"Comput. Optim. Appl."},{"issue":"2","key":"407_CR3","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0320018","volume":"20","author":"DP Bertsekas","year":"1982","unstructured":"Bertsekas, D.P.: Projected Newton methods for optimization problems with simple constraints. SIAM J. Control. Optim. 20(2), 221\u2013246 (1982)","journal-title":"SIAM J. Control. Optim."},{"issue":"1","key":"407_CR4","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1023\/A:1019928808826","volume":"23","author":"EG Birgin","year":"2002","unstructured":"Birgin, E.G., Mart\u00ednez, J.M.: Large-scale active-set box-constrained optimization method with spectral projected gradients. Comput. Optim. Appl. 23(1), 101\u2013125 (2002)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"407_CR5","doi-asserted-by":"publisher","first-page":"2211","DOI":"10.1137\/18M1206953","volume":"29","author":"IM Bomze","year":"2019","unstructured":"Bomze, I.M., Rinaldi, F., Bulo, S.R.: First-order methods for the impatient: support identification in finite time with convergent Frank\u2013Wolfe variants. SIAM J. Optim. 29(3), 2211\u20132226 (2019)","journal-title":"SIAM J. Optim."},{"key":"407_CR6","doi-asserted-by":"crossref","unstructured":"Bomze, I.M., Rinaldi, F., Zeffiro, D.: Active set complexity of the Away-step Frank\u2013Wolfe Algorithm. arXiv preprint arXiv:1912.11492 (2019)","DOI":"10.1137\/19M1309419"},{"key":"407_CR7","first-page":"36","volume":"294","author":"CP Br\u00e1s","year":"2017","unstructured":"Br\u00e1s, C.P., Fischer, A., J\u00fadice, J.J., Sch\u00f6nefeld, K., Seifert, S.: A block active set algorithm with spectral choice line search for the symmetric eigenvalue complementarity problem. Appl. Math. Comput. 294, 36\u201348 (2017)","journal-title":"Appl. Math. Comput."},{"issue":"1","key":"407_CR8","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/s10107-015-0946-6","volume":"158","author":"L Condat","year":"2016","unstructured":"Condat, L.: Fast projection onto the simplex and the $$\\ell _1$$ ball. Math. Program. 158(1), 575\u2013585 (2016)","journal-title":"Math. Program."},{"issue":"2","key":"407_CR9","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s10957-016-1024-9","volume":"172","author":"A Cristofari","year":"2017","unstructured":"Cristofari, A., De Santis, M., Lucidi, S., Rinaldi, F.: A two-stage active-set algorithm for bound-constrained optimization. J. Optim. Theory Appl. 172(2), 369\u2013401 (2017)","journal-title":"J. Optim. Theory Appl."},{"issue":"1","key":"407_CR10","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s10589-020-00195-x","volume":"77","author":"A Cristofari","year":"2020","unstructured":"Cristofari, A., De Santis, M., Lucidi, S., Rinaldi, F.: An active-set algorithmic framework for non-convex optimization problems over the simplex. Comput. Optim. Appl. 77(1), 57\u201389 (2020)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"407_CR11","doi-asserted-by":"publisher","first-page":"1392","DOI":"10.1137\/19M1270446","volume":"80","author":"A Cristofari","year":"2020","unstructured":"Cristofari, A., Rinaldi, F., Tudisco, F.: Total variation based community detection using a nonlinear optimization approach. SIAM J. Appl. Math. 80(3), 1392\u20131419 (2020)","journal-title":"SIAM J. Appl. Math."},{"issue":"1","key":"407_CR12","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/141000737","volume":"26","author":"M De Santis","year":"2016","unstructured":"De Santis, M., Lucidi, S., Rinaldi, F.: A fast active set block coordinate descent algorithm for $$\\ell _1$$-regularized least squares. SIAM J. Optim. 26(1), 781\u2013809 (2016)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"407_CR13","doi-asserted-by":"publisher","first-page":"2809","DOI":"10.1137\/17M1128538","volume":"28","author":"D Di Serafino","year":"2018","unstructured":"Di Serafino, D., Toraldo, G., Viola, M., Barlow, J.: A two-phase gradient method for quadratic programming problems with a single linear constraint and bounds on the variables. SIAM J. Optim. 28(4), 2809\u20132838 (2018)","journal-title":"SIAM J. Optim."},{"key":"407_CR14","unstructured":"Dua, D., Graff, C.: UCI machine learning repository (2017). http:\/\/archive.ics.uci.edu\/ml"},{"key":"407_CR15","unstructured":"Duchi, J., Gould, S., Koller, D.: Projected subgradient methods for learning sparse gaussians. arXiv preprint arXiv:1206.3249 (2012)"},{"key":"407_CR16","doi-asserted-by":"crossref","unstructured":"Duchi, J., Shalev-Shwartz, S., Singer, Y., Chandra, T.: Efficient projections onto the l 1-ball for learning in high dimensions. In: Proceedings of the 25th International Conference on Machine learning, pp. 272\u2013279 (2008)","DOI":"10.1145\/1390156.1390191"},{"issue":"2","key":"407_CR17","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1214\/009053604000000067","volume":"32","author":"B Efron","year":"2004","unstructured":"Efron, B., Hastie, T., Johnstone, I., Tibshirani, R.: Least angle regression. Ann. Stat. 32(2), 407\u2013499 (2004)","journal-title":"Ann. Stat."},{"issue":"1","key":"407_CR18","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1137\/S1052623496305882","volume":"9","author":"F Facchinei","year":"1998","unstructured":"Facchinei, F., Fischer, A., Kanzow, C.: On the accurate identification of active constraints. SIAM J. Optim. 9(1), 14\u201332 (1998)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"407_CR19","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1137\/S1052623493253991","volume":"8","author":"F Facchinei","year":"1998","unstructured":"Facchinei, F., J\u00fadice, J., Soares, J.: An active set Newton algorithm for large-scale nonlinear programs with box constraints. SIAM J. Optim. 8(1), 158\u2013186 (1998)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"407_CR20","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1137\/0723046","volume":"23","author":"L Grippo","year":"1986","unstructured":"Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton\u2019s method. SIAM J. Numer. Anal. 23(4), 707\u2013716 (1986)","journal-title":"SIAM J. Numer. Anal."},{"key":"407_CR21","unstructured":"Guyon, I., Gunn, S.R., Ben-Hur, A., Dror, G.: Result analysis of the NIPS 2003 feature selection challenge. In: NIPS, vol.\u00a04, pp. 545\u2013552 (2004)"},{"issue":"2","key":"407_CR22","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1137\/050635225","volume":"17","author":"WW Hager","year":"2006","unstructured":"Hager, W.W., Zhang, H.: A new active set algorithm for box constrained optimization. SIAM J. Optim. 17(2), 526\u2013557 (2006)","journal-title":"SIAM J. Optim."},{"issue":"8","key":"407_CR23","doi-asserted-by":"publisher","first-page":"1525","DOI":"10.1007\/s11425-016-0300-6","volume":"59","author":"WW Hager","year":"2016","unstructured":"Hager, W.W., Zhang, H.: An active set algorithm for nonlinear optimization with polyhedral constraints. Sci. China Math. 59(8), 1525\u20131542 (2016)","journal-title":"Sci. China Math."},{"issue":"3","key":"407_CR24","doi-asserted-by":"publisher","first-page":"1773","DOI":"10.1137\/15M102825X","volume":"26","author":"WW Hager","year":"2016","unstructured":"Hager, W.W., Zhang, H.: Projection onto a polyhedron that exploits sparsity. SIAM J. Optim. 26(3), 1773\u20131798 (2016)","journal-title":"SIAM J. Optim."},{"key":"407_CR25","unstructured":"Jaggi, M.: Revisiting Frank\u2013Wolfe: projection-free sparse convex optimization. In: International Conference on Machine Learning, pp. 427\u2013435. PMLR (2013)"},{"key":"407_CR26","unstructured":"Lacoste-Julien, S., Jaggi, M.: On the global linear convergence of Frank\u2013Wolfe optimization variants. In: NIPS 2015\u2014Advances in Neural Information Processing Systems (2015)"},{"key":"407_CR27","first-page":"361","volume":"5","author":"DD Lewis","year":"2004","unstructured":"Lewis, D.D., Yang, Y., Russell-Rose, T., Li, F.: Rcv1: a new benchmark collection for text categorization research. J. Mach Learn. Res. 5, 361\u2013397 (2004)","journal-title":"J. Mach Learn. Res."},{"issue":"4","key":"407_CR28","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/BF01396045","volume":"55","author":"JJ Mor\u00e9","year":"1989","unstructured":"Mor\u00e9, J.J., Toraldo, G.: Algorithms for bound constrained quadratic programming problems. Numer. Math. 55(4), 377\u2013400 (1989)","journal-title":"Numer. Math."},{"key":"407_CR29","volume-title":"Introductory lectures on convex optimization: a basic course","author":"Y Nesterov","year":"2013","unstructured":"Nesterov, Y.: Introductory lectures on convex optimization: a basic course, vol. 87. Springer, Berlin (2013)"},{"key":"407_CR30","unstructured":"Schmidt, M., Berg, E., Friedlander, M., Murphy, K.: Optimizing costly functions with simple constraints: a limited-memory projected quasi-newton algorithm. In: Artificial Intelligence and Statistics, pp. 456\u2013463. PMLR (2009)"},{"key":"407_CR31","doi-asserted-by":"crossref","unstructured":"Schmidt, M., Murphy, K., Fung, G., Rosales, R.: Structure learning in random fields for heart motion abnormality detection. In: 2008 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1\u20138. IEEE (2008)","DOI":"10.1109\/CVPR.2008.4587367"},{"issue":"1","key":"407_CR32","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","volume":"58","author":"R Tibshirani","year":"1996","unstructured":"Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc.: Ser. B (Methodol.) 58(1), 267\u2013288 (1996)","journal-title":"J. R. Stat. Soc.: Ser. B (Methodol.)"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00407-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-022-00407-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00407-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,2]],"date-time":"2024-10-02T17:47:44Z","timestamp":1727891264000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-022-00407-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,27]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["407"],"URL":"https:\/\/doi.org\/10.1007\/s10589-022-00407-6","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,27]]},"assertion":[{"value":"30 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}