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

Carina Moreira Costa(costauni-trier.de)
Dennis Kreber(kreberduni-trier.de)
Martin Schmidt(martin.schmidtuni-trier.de)

Abstract: Cardinality-constrained optimization problems are notoriously hard to solve both in theory and practice. However, as famous examples such as the cardinality-constrained portfolio optimization and the best subset selection problem show, this class is extremely important in practice. 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 classical 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 MIP solver for the portfolio optimization problem. Regarding the best subset selection problem, it turns out that our method significantly outperforms commercial solvers and that it is at least competitive to state-of-the-art heuristics from the literature.

Keywords: Cardinalty Constraints, Alternating Direction Methods, Penalty Methods, Best Subset Selection, Portfolio Optimization

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Applications -- Science and Engineering (Statistics )

Category 3: Applications -- OR and Management Sciences (Finance and Economics )

Citation:

Download: [PDF]

Entry Submitted: 11/20/2020
Entry Accepted: 11/20/2020
Entry Last Modified: 11/20/2020

Modify/Update this entry