{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T10:14:02Z","timestamp":1773137642733,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T00:00:00Z","timestamp":1679443200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T00:00:00Z","timestamp":1679443200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004434","name":"Universit\u00e0 degli Studi di Firenze","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004434","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper provides a theoretical and numerical investigation of a penalty decomposition scheme for the solution of optimization problems with geometric constraints. In particular, we consider some situations where parts of the constraints are nonconvex and complicated, like cardinality constraints, disjunctive programs, or matrix problems involving rank constraints. By a variable duplication and decomposition strategy, the method presented here explicitly handles these difficult constraints, thus generating iterates which are feasible with respect to them, while the remaining (standard and supposingly simple) constraints are tackled by sequential penalization. Inexact optimization steps are proven sufficient for the resulting algorithm to work, so that it is employable even with difficult objective functions. The current work is therefore a significant generalization of existing papers on penalty decomposition methods. On the other hand, it is related to some recent publications which use an augmented Lagrangian idea to solve optimization problems with geometric constraints. Compared to these methods, the decomposition idea is shown to be numerically superior since it allows much more freedom in the choice of the subproblem solver, and since the number of certain (possibly expensive) projection steps is significantly less. Extensive numerical results on several highly complicated classes of optimization problems in vector and matrix spaces indicate that the current method is indeed very efficient to solve these problems.<\/jats:p>","DOI":"10.1007\/s10589-023-00475-2","type":"journal-article","created":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T05:02:39Z","timestamp":1679461359000},"page":"937-971","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Inexact penalty decomposition methods for optimization problems with geometric constraints"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2897-2509","authenticated-orcid":false,"given":"Christian","family":"Kanzow","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2488-5486","authenticated-orcid":false,"given":"Matteo","family":"Lapucci","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,3,22]]},"reference":[{"key":"475_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01870-z","author":"X Jia","year":"2022","unstructured":"Jia, X., Kanzow, C., Mehlitz, P., Wachsmuth, G.: An augmented lagrangian method for optimization problems with structured geometric constraints. Progr. Math. (2022). https:\/\/doi.org\/10.1007\/s10107-022-01870-z","journal-title":"Progr. Math."},{"issue":"1","key":"475_CR2","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s11228-020-00569-7","volume":"30","author":"M Benko","year":"2022","unstructured":"Benko, M., \u010cervinka, M., Hoheisel, T.: Sufficient conditions for metric subregularity of constraint systems with applications to disjunctive and ortho-disjunctive programs. Set-Val. Variat. Anal. 30(1), 143\u2013177 (2022)","journal-title":"Set-Val. Variat. Anal."},{"issue":"1","key":"475_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/02331934.2017.1387547","volume":"67","author":"M Benko","year":"2018","unstructured":"Benko, M., Gfrerer, H.: New verifiable stationarity concepts for a class of mathematical programs with disjunctive constraints. Optimization 67(1), 1\u201323 (2018)","journal-title":"Optimization"},{"issue":"2","key":"475_CR4","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s11228-006-0033-5","volume":"15","author":"ML Flegel","year":"2007","unstructured":"Flegel, M.L., Kanzow, C., Outrata, J.V.: Optimality conditions for disjunctive programs with application to mathematical programs with equilibrium constraints. Set-Val. Anal. 15(2), 139\u2013162 (2007)","journal-title":"Set-Val. Anal."},{"issue":"10","key":"475_CR5","doi-asserted-by":"publisher","first-page":"2241","DOI":"10.1080\/02331934.2019.1679811","volume":"69","author":"P Mehlitz","year":"2020","unstructured":"Mehlitz, P.: On the linear independence constraint qualification in disjunctive programming. Optimization 69(10), 2241\u20132277 (2020)","journal-title":"Optimization"},{"issue":"2","key":"475_CR6","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1137\/S1052623497321882","volume":"9","author":"J Ye","year":"1999","unstructured":"Ye, J.: Optimality conditions for optimization problems with complementarity constraints. SIAM J. Optimiz. 9(2), 374\u2013387 (1999)","journal-title":"SIAM J. Optimiz."},{"issue":"1","key":"475_CR7","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s10107-006-0083-3","volume":"114","author":"W Achtziger","year":"2008","unstructured":"Achtziger, W., Kanzow, C.: Mathematical programs with vanishing constraints: optimality conditions and constraint qualifications. Math. Progr. 114(1), 69\u201399 (2008)","journal-title":"Math. Progr."},{"issue":"1","key":"475_CR8","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s10107-019-01380-5","volume":"181","author":"P Mehlitz","year":"2020","unstructured":"Mehlitz, P.: Stationarity conditions and constraint qualifications for mathematical programs with switching constraints. Math. Progr. 181(1), 149\u2013186 (2020)","journal-title":"Math. Progr."},{"key":"475_CR9","unstructured":"Lapucci, M.: Theory and algorithms for sparsity constrained optimization problems. PhD thesis, University of Florence, Italy (2022)"},{"issue":"2","key":"475_CR10","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/s10957-020-01793-9","volume":"188","author":"M Lapucci","year":"2021","unstructured":"Lapucci, M., Levato, T., Sciandrone, M.: Convergent inexact penalty decomposition methods for cardinality-constrained problems. J. Optimiz. Theory Appl. 188(2), 473\u2013496 (2021)","journal-title":"J. Optimiz. Theory Appl."},{"issue":"11","key":"475_CR11","doi-asserted-by":"publisher","first-page":"2212","DOI":"10.1080\/03081087.2016.1267104","volume":"65","author":"N Kishore Kumar","year":"2017","unstructured":"Kishore Kumar, N., Schneider, J.: Literature survey on low rank approximation of matrices. Linear Multilin. Algebra 65(11), 2212\u20132244 (2017)","journal-title":"Linear Multilin. Algebra"},{"key":"475_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-2227-2","volume-title":"Low rank approximation: algorithms, implementation, applications","author":"I Markovsky","year":"2012","unstructured":"Markovsky, I.: Low rank approximation: algorithms, implementation, applications, 2nd edn. Springer, London, UK (2012)","edition":"2"},{"issue":"3","key":"475_CR13","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1080\/10556788.2019.1576177","volume":"35","author":"G Galvan","year":"2020","unstructured":"Galvan, G., Lapucci, M., Levato, T., Sciandrone, M.: An alternating augmented Lagrangian method for constrained nonconvex optimization. Optimiz. Method. Softw. 35(3), 502\u2013520 (2020)","journal-title":"Optimiz. Method. Softw."},{"issue":"4","key":"475_CR14","doi-asserted-by":"publisher","first-page":"2448","DOI":"10.1137\/100808071","volume":"23","author":"Z Lu","year":"2013","unstructured":"Lu, Z., Zhang, Y.: Sparse approximation via penalty decomposition methods. SIAM J. Optimiz. 23(4), 2448\u20132478 (2013)","journal-title":"SIAM J. Optimiz."},{"key":"475_CR15","unstructured":"Zhang, Y., Lu, Z.: Penalty decomposition methods for rank minimization. Adv. Neural Inf. Process. Sys. 24 (2011)"},{"issue":"2","key":"475_CR16","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF02592954","volume":"39","author":"M Guignard","year":"1987","unstructured":"Guignard, M., Kim, S.: Lagrangean decomposition: a model yielding stronger Lagrangean bounds. Math. Progr. 39(2), 215\u2013228 (1987)","journal-title":"Math. Progr."},{"key":"475_CR17","volume-title":"Variable splitting: a new Lagrangean relaxation approach to some mathematical programming models","author":"KO J\u00f6rnsten","year":"1985","unstructured":"J\u00f6rnsten, K.O., N\u00e4sberg, M., Smeds, P.A.: Variable splitting: a new Lagrangean relaxation approach to some mathematical programming models. Universitetet i Link\u00f6ping\/Tekniska H\u00f6gskolan i Link\u00f6ping, Department of Mathematics (1985)"},{"issue":"4","key":"475_CR18","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1080\/10556789908805730","volume":"10","author":"L Grippo","year":"1999","unstructured":"Grippo, L., Sciandrone, M.: Globally convergent block-coordinate techniques for unconstrained optimization. Optimiz. Meth. Softw. 10(4), 587\u2013637 (1999)","journal-title":"Optimiz. Meth. Softw."},{"issue":"4","key":"475_CR19","doi-asserted-by":"publisher","first-page":"1431","DOI":"10.1093\/imanum\/drq024","volume":"31","author":"S Bonettini","year":"2011","unstructured":"Bonettini, S.: Inexact block coordinate descent methods with application to non-negative matrix factorization. IMA J. Numer. Anal. 31(4), 1431\u20131452 (2011)","journal-title":"IMA J. Numer. Anal."},{"key":"475_CR20","doi-asserted-by":"publisher","unstructured":"Bauschke, H.H., Combettes, P.L.: Convex analysis and monotone operator theory in hilbert spaces, 1st edn. Springer, New York (2011). https:\/\/doi.org\/10.1007\/978-1-4419-9467-7","DOI":"10.1007\/978-1-4419-9467-7"},{"key":"475_CR21","doi-asserted-by":"publisher","unstructured":"Mordukhovich, B.S.: Variational analysis and applications, 1st edn. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-92775-6","DOI":"10.1007\/978-3-319-92775-6"},{"key":"475_CR22","doi-asserted-by":"crossref","unstructured":"Mehlitz, P.: Asymptotic stationarity and regularity for nonsmooth optimization problems. J Nonsmooth Anal. Optimiz. 1 (2020)","DOI":"10.46298\/jnsao-2020-6575"},{"issue":"5","key":"475_CR23","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1080\/02331930903578700","volume":"60","author":"R Andreani","year":"2011","unstructured":"Andreani, R., Haeser, G., Mart\u00ednez, J.M.: On sequential optimality conditions for smooth constrained optimization. Optimization 60(5), 627\u2013641 (2011)","journal-title":"Optimization"},{"issue":"1","key":"475_CR24","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/15M1008488","volume":"26","author":"R Andreani","year":"2016","unstructured":"Andreani, R., Martinez, J.M., Ramos, A., Silva, P.J.: A cone-continuity constraint qualification and algorithmic consequences. SIAM J. Optimiz. 26(1), 96\u2013110 (2016)","journal-title":"SIAM J. Optimiz."},{"issue":"3","key":"475_CR25","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1287\/moor.2017.0879","volume":"43","author":"R Andreani","year":"2018","unstructured":"Andreani, R., Martinez, J.M., Ramos, A., Silva, P.J.: Strict constraint qualifications and sequential optimality conditions for constrained optimization. Math. Operat. Res. 43(3), 693\u2013717 (2018)","journal-title":"Math. Operat. Res."},{"key":"475_CR26","doi-asserted-by":"publisher","unstructured":"Rockafellar, R.T., Wets, R.J.-B.: Variational analysis, 1st Edn. Springer, Heidelberg(2009) https:\/\/doi.org\/10.1007\/978-3-642-02431-3","DOI":"10.1007\/978-3-642-02431-3"},{"issue":"6","key":"475_CR27","doi-asserted-by":"publisher","first-page":"3694","DOI":"10.1137\/19M1240186","volume":"57","author":"E B\u00f6rgens","year":"2019","unstructured":"B\u00f6rgens, E., Kanzow, C., Steck, D.: Local and global analysis of multiplier methods for constrained optimization in Banach spaces. SIAM J. Contr. Optimiz. 57(6), 3694\u20133722 (2019)","journal-title":"SIAM J. Contr. Optimiz."},{"issue":"6","key":"475_CR28","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1016\/j.orl.2017.09.005","volume":"45","author":"C Kanzow","year":"2017","unstructured":"Kanzow, C., Steck, D.: An example comparing the standard and safeguarded augmented Lagrangian methods. Operat. Res. Lett. 45(6), 598\u2013603 (2017)","journal-title":"Operat. Res. Lett."},{"key":"475_CR29","volume-title":"Nonlinear programming","author":"D Bertsekas","year":"2016","unstructured":"Bertsekas, D.: Nonlinear programming, vol. 4, 2nd edn. Athena Scientific, Belmont (2016)","edition":"2"},{"issue":"3","key":"475_CR30","doi-asserted-by":"publisher","first-page":"1480","DOI":"10.1137\/120869778","volume":"23","author":"A Beck","year":"2013","unstructured":"Beck, A., Eldar, Y.C.: Sparsity constrained nonlinear optimization: optimality conditions and algorithms. SIAM J. Optimiz. 23(3), 1480\u20131509 (2013). https:\/\/doi.org\/10.1137\/120869778","journal-title":"SIAM J. Optimiz."},{"issue":"2","key":"475_CR31","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s10898-021-01070-7","volume":"82","author":"S L\u00e4mmel","year":"2022","unstructured":"L\u00e4mmel, S., Shikhman, V.: On nondegenerate M-stationary points for sparsity constrained nonlinear optimization. J. Global Optimiz. 82(2), 219\u2013242 (2022)","journal-title":"J. Global Optimiz."},{"key":"475_CR32","doi-asserted-by":"crossref","unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization: analysis, algorithms, and engineering applications, 1st edn. SIAM, Philadelphia (2001)","DOI":"10.1137\/1.9780898718829"},{"issue":"1","key":"475_CR33","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s10107-002-0356-4","volume":"94","author":"S Burer","year":"2002","unstructured":"Burer, S., Monteiro, R.D., Zhang, Y.: Maximum stable set formulations and heuristics based on continuous optimization. Math. Progr. 94(1), 137\u2013166 (2002)","journal-title":"Math. Progr."},{"issue":"6","key":"475_CR34","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","volume":"9","author":"EJ Cand\u00e8s","year":"2009","unstructured":"Cand\u00e8s, E.J., Recht, B.: Exact matrix completion via convex optimization. Foundat. Comp. Math. 9(6), 717\u2013772 (2009)","journal-title":"Foundat. Comp. Math."},{"issue":"3","key":"475_CR35","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/070697835","volume":"52","author":"B Recht","year":"2010","unstructured":"Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review 52(3), 471\u2013501 (2010)","journal-title":"SIAM Review"},{"key":"475_CR36","doi-asserted-by":"crossref","unstructured":"Hosseini, S., Luke, D.R., Uschmajew, A.: Tangent and normal cones for low-rank matrices. In: Nonsmooth optimization and its applications, pp. 45\u201353. Springer, Birkh\u00e4user, Cham (2019)","DOI":"10.1007\/978-3-030-11370-4_3"},{"issue":"1","key":"475_CR37","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1137\/140978077","volume":"26","author":"OP Burdakov","year":"2016","unstructured":"Burdakov, O.P., Kanzow, C., Schwartz, A.: Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method. SIAM J. Optimiz. 26(1), 397\u2013425 (2016)","journal-title":"SIAM J. Optimiz."},{"issue":"1","key":"475_CR38","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/BF01589116","volume":"45","author":"DC Liu","year":"1989","unstructured":"Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Math. Progr. 45(1), 503\u2013528 (1989)","journal-title":"Math. Progr."},{"issue":"3","key":"475_CR39","doi-asserted-by":"publisher","first-page":"1489","DOI":"10.1287\/ijoc.2021.1127","volume":"34","author":"D Bertsimas","year":"2022","unstructured":"Bertsimas, D., Cory-Wright, R.: A scalable algorithm for sparse portfolio selection. Informs J. Comput. 34(3), 1489\u20131511 (2022)","journal-title":"Informs J. Comput."},{"key":"475_CR40","unstructured":"Gurobi optimization, LLC: Gurobi optimizer reference manual (2022). https:\/\/www.gurobi.com"},{"issue":"2","key":"475_CR41","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E.D., Mor\u00e9, J.J.: Benchmarking optimization software with performance profiles. Math. Progr. 91(2), 201\u2013213 (2002)","journal-title":"Math. Progr."},{"issue":"3","key":"475_CR42","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s11590-019-01506-w","volume":"14","author":"G Cocchi","year":"2020","unstructured":"Cocchi, G., Levato, T., Liuzzi, G., Sciandrone, M.: A concave optimization-based approach for sparse multiobjective programming. Optimiz. Lett. 14(3), 535\u2013556 (2020)","journal-title":"Optimiz. Lett."},{"issue":"12","key":"475_CR43","doi-asserted-by":"publisher","first-page":"5586","DOI":"10.1109\/TKDE.2021.3070203","volume":"34","author":"Y Zhang","year":"2021","unstructured":"Zhang, Y., Yang, Q.: A survey on multi-task learning. IEEE Trans. Knowl. Data Eng. 34(12), 5586\u20135609 (2021)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"475_CR44","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-84858-7","volume-title":"The elements of statistical learning: data mining, inference, and prediction","author":"T Hastie","year":"2009","unstructured":"Hastie, T., Tibshirani, R., Friedman, J.: The elements of statistical learning: data mining, inference, and prediction, 2nd edn. Springer, New York (2009)","edition":"2"},{"issue":"1","key":"475_CR45","first-page":"35","volume":"8","author":"Y Xue","year":"2007","unstructured":"Xue, Y., Liao, X., Carin, L., Krishnapuram, B.: Multi-task learning for classification with Dirichlet process priors. J. Mach. Learn. Res. 8(1), 35\u201363 (2007)","journal-title":"J. Mach. Learn. Res."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00475-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-023-00475-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00475-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,4]],"date-time":"2023-07-04T16:53:41Z","timestamp":1688489621000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-023-00475-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,22]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["475"],"URL":"https:\/\/doi.org\/10.1007\/s10589-023-00475-2","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,22]]},"assertion":[{"value":"12 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}