In this manuscript, we consider the problem of minimizing a smooth function with cardinality constraint, i.e., the constraint requiring that the [InlineEquation not available: see fulltext.]-norm of the vector of variables cannot exceed a given threshold value. A well-known approach of the literature is represented by the class of penalty decomposition methods, where a sequence of penalty subproblems, depending on the original variables and new variables, are inexactly solved by a two-block decomposition method. The inner iterates of the decomposition method require to perform exact minimizations with respect to the two blocks of variables. The computation of the global minimum with respect to the original variables may be prohibitive in the case of nonconvex objective function. In order to overcome this nontrivial issue, we propose a modified penalty decomposition method, where the exact minimizations with respect to the original variables are replaced by suitable line searches along gradient-related directions. We also present a derivative-free penalty decomposition algorithm for black-box optimization. We state convergence results of the proposed methods, and we report the results of preliminary computational experiments.

Convergent Inexact Penalty Decomposition Methods for Cardinality-Constrained Problems / Lapucci, M.; Levato, T.; Sciandrone, M.. - In: JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS. - ISSN 0022-3239. - 188:2(2021), pp. 473-496. [10.1007/s10957-020-01793-9]

Convergent Inexact Penalty Decomposition Methods for Cardinality-Constrained Problems

Sciandrone M.
2021

Abstract

In this manuscript, we consider the problem of minimizing a smooth function with cardinality constraint, i.e., the constraint requiring that the [InlineEquation not available: see fulltext.]-norm of the vector of variables cannot exceed a given threshold value. A well-known approach of the literature is represented by the class of penalty decomposition methods, where a sequence of penalty subproblems, depending on the original variables and new variables, are inexactly solved by a two-block decomposition method. The inner iterates of the decomposition method require to perform exact minimizations with respect to the two blocks of variables. The computation of the global minimum with respect to the original variables may be prohibitive in the case of nonconvex objective function. In order to overcome this nontrivial issue, we propose a modified penalty decomposition method, where the exact minimizations with respect to the original variables are replaced by suitable line searches along gradient-related directions. We also present a derivative-free penalty decomposition algorithm for black-box optimization. We state convergence results of the proposed methods, and we report the results of preliminary computational experiments.
2021
Cardinality constraint; Derivative-free optimization; Global convergence; Nonconvex optimization; Penalty decomposition method
01 Pubblicazione su rivista::01a Articolo in rivista
Convergent Inexact Penalty Decomposition Methods for Cardinality-Constrained Problems / Lapucci, M.; Levato, T.; Sciandrone, M.. - In: JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS. - ISSN 0022-3239. - 188:2(2021), pp. 473-496. [10.1007/s10957-020-01793-9]
File allegati a questo prodotto
File Dimensione Formato  
Lapucci_Convergent_2021.pdf

accesso aperto

Note: https://link.springer.com/article/10.1007/s10957-020-01793-9
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 455.28 kB
Formato Adobe PDF
455.28 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1625413
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 4
social impact