An Alternating Method for Cardinality-Constrained Optimization: A Computational Study for the Best Subset Selection and Sparse Portfolio Problems

Carina Moreira Costa (), Dennis Kreber () and Martin Schmidt ()
Additional contact information
Carina Moreira Costa: Department of Mathematics, Trier University, 54296 Trier, Germany
Dennis Kreber: Department of Mathematics, Trier University, 54296 Trier, Germany
Martin Schmidt: Department of Mathematics, Trier University, 54296 Trier, Germany

INFORMS Journal on Computing, 2022, vol. 34, issue 6, 2968-2988

Abstract: Cardinality-constrained optimization problems are notoriously hard to solve in both theory and practice. However, as famous examples, such as the sparse portfolio optimization and best subset selection problems, show, this class is extremely important in real-world applications. In this paper, we apply a penalty alternating direction method to these problems. The key idea is to split the problem along its discrete-continuous structure to obtain two subproblems that are much easier to solve than the original problem. In addition, the coupling between these subproblems is achieved via a classic penalty framework. The method can be seen as a primal heuristic for which convergence results are readily available from the literature. In our extensive computational study, we first show that the method is competitive to a commercial mixed-integer program solver for the portfolio optimization problem. On these instances, we also test a variant of our approach that uses a perspective reformulation of the problem. Regarding the best subset selection problem, it turns out that our method significantly outperforms commercial solvers and it is at least competitive to state-of-the-art methods from the literature.

Keywords: cardinality constraints; alternating direction methods; penalty methods; best subset selection; portfolio optimization (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1211 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:6:p:2968-2988

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().