Kybernetika 62 no. 3, 373-399, 2026

An algorithm for cardinality-constrained optimization with an application to the best subset selection and sparse portfolio problems

Vikram Singh and Min SunDOI: 10.14736/kyb-2026-3-0373

Abstract:

A lot of problems, from fields like sparse signal processing, statistics, portfolio selection, and machine learning, can be formulated as a cardinality-constrained optimization problem. The cardinality-constraint gives the problem a discrete nature, making it computationally challenging to solve as the dimension of the problem increases. In this work, we present an algorithm for solving the cardinality-constrained quadratic optimization problem, inspired by the interval branch-and-bound framework. The proposed method is guaranteed to find the global optimal solution and is capable of solving problems of a wide range of dimensions. In particular, we solve the classical best subset selection problem in regression and the cardinality-constrained portfolio optimization problem. The numerical results show that our algorithm is competitive with the state-of-the-art solvers to solve the best subset selection problem and is capable of solving the cardinality-constraint portfolio optimization problem in a practical amount of time.

Keywords:

portfolio optimization, global optimization, cardinality-constraint, quadratic optimization, branch-and-bound, best subset selection

Classification:

90C26, 90C57, 65K05

paper.pdf

References:

  1. A. d'Aspremont, F. Bach and L. El Ghaoui: Optimal solutions for sparse principal component analysis. J. Mach. Learn. Res. 9 (2008), 7, 1269-1294.   CrossRef
  2. J. E. Beasley: OR-Library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41 (1990), 11, 1069-1072.   DOI:10.1057/jors.1990.166
  3. D. Bertsimas and R. Shioda: Algorithm for cardinality-constrained quadratic optimization. Comput. Optim. Appl. 43 (2009), 1, 1-22.   DOI:10.1007/s10589-007-9126-9
  4. D. Bertsimas, A. King and R. Mazumder: Best subset selection via a modern optimization lens. Ann. Statist. 44 (2015), 2, 813-852.   DOI:10.1214/15-AOS1388
  5. D. Bienstock: Computational study of a family of mixed-integer quadratic programming problems. Math. Program. 74 (1996), 121-140.   DOI:10.1007/BF02592208
  6. R. E. Bixby: Implementing the simplex method: the initial basis. ORSA J. Comput. 4 (1992), 3, 267-284.   DOI:10.1287/ijoc.4.3.267
  7. T. Blumensath and M. E. Davies: Iterative thresholding for sparse approximations. J. Fourier Anal. Appl. 14 (2008), 629-654.   DOI:10.1007/s00041-008-9035-z
  8. P. Bonami and M. A. Lejeune: An exact solution approach for portfolio optimization problems under stochastic and integer constraints. Oper. Res. 57 (2009), 3, 650-670.   CrossRef
  9. M. Branda, M. Bucher, M. Červinka and A. Schwartz: Convergence of a Scholtes-type regularization method for cardinality-constrained optimization problems with an application in sparse robust portfolio optimization. Comput. Optim. Appl. 70 (2018), 2, 503-530.   DOI:10.1007/s10589-018-9985-2
  10. P. Bühlmann and S. van de Geer: Statistics for High-Dimensional Data: Methods, Theory and Applications. Springer-Verlag, Berlin 2011.   DOI:10.1007/978-3-642-20192-9
  11. C. Moreira, D. Kreber and M. Schmidt: An alternating method for cardinality-constrained optimization: a computational study for the best subset selection and sparse portfolio problems. INFORMS J. Comput. 34 (2022), 6, 2968-2988.   DOI:10.1287/ijoc.2022.1211
  12. J. Friedman, T. Hastie and R. Tibshirani: Regularization paths for generalized linear models via coordinate descent. J. Stat. Softw. 33 (2010), 1, 1-22.   DOI:10.18637/jss.v033.i01
  13. K. Fukunaga: Introduction to Statistical Pattern Recognition. Second edition. Academic Press, Inc., San Diego 1990.   CrossRef
  14. J. Gao and D. Li: Optimal cardinality constrained portfolio selection. Oper. Res. 61 (2013), 3, 745-761.   DOI:10.1287/opre.2013.1170
  15. C. Gatu and E. J. Kontoghiorghes: Branch-and-bound algorithms for computing the best-subset regression models. J. Comput. Graph. Statist. 15 (2006), 1, 139-156.   DOI:10.1198/106186006X100290
  16. Gurobi Optimization and LLC: Gurobi optimizer reference manual. 2023.   CrossRef
  17. H. Eldon: Global optimization using interval analysis—the multi-dimensional case. Numer. Math. 34 (1980), 3, 247-270.   CrossRef
  18. T. Hastie, R. Tibshirani and R. J. Tibshirani: Extended comparisons of best subset selection, forward stepwise selection, and the lasso. (2017)    CrossRef
  19. M. Hirschberger, Y. Qi and R. E. Steuer: Randomly generating portfolio-selection covariance matrices with specified distributional characteristics. European J. Oper. Res. 177 (2007), 3, 1610-1625.   DOI:10.1016/j.ejor.2005.10.014
  20. Y. Jin, R. Qu and J. Atkin: Constrained portfolio optimisation: the state-of-the-art Markowitz models. In: Proc. 5th International Conference on Operations Research and Enterprise Systems - ICORES (2016), pp. 388-395.   DOI:10.5220/0005758303880395
  21. H. Markowitz: Portfolio Selection*. J. Finance 7 (1952), 1, 77-91.   DOI:10.1111/j.1540-6261.1952.tb01525.x
  22. A. Miller: Subset Selection in Regression. Second edition. Chapman and Hall/CRC, New York 2002.   CrossRef
  23. R. E. Moore: Interval Analysis. Prentice-Hall, Englewood Cliffs, New Jersey 1966.   CrossRef
  24. D. R. Morrison, S. H. Jacobson, J. J. Sauppe and E. C. Sewell: Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optim. 19 (2016), 79-102.   DOI:10.1016/j.disopt.2016.01.005
  25. P. M. Narendra and K. Fukunaga: A branch and bound algorithm for feature subset selection. IEEE Trans. Comput. 26 (1977), 9, 917-922.   CrossRef
  26. B. K. Natarajan: Sparse approximate solutions to linear systems. SIAM J. Comput. 24 (1995), 2, 227-234.   DOI:10.1137/S0097539792240406
  27. H. Ratschek and J. Rokne: New Computer Methods for Global Optimization. Halsted Press, Chichester 1988.   CrossRef
  28. S. B. Çay: Random Portfolio Dataset Generator.    DOI:10.5281/zenodo.53204
  29. P. Somol, P. Pudil and J. Kittler: Fast branch \& bound algorithms for optimal feature selection. IEEE Trans. Patt. Anal. Machine Intell. 26 (2004), 7, 900-912.   DOI:10.1109/tpami.2004.28
  30. R. Tibshirani: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B. Stat. Methodol. 58 (1996), 1, 267-288.   DOI:10.1111/j.2517-6161.1996.tb02080.x
  31. A. M. Tillman, D. Bienstock, A. Lodi and A. Schwartz: Cardinality minimization, constraints, and regularization: a survey. SIAM Rev. 66 (2024), 3, 403-477.   DOI:10.1137/21M142770X
  32. D. S. Watkins: Fundamentals of Matrix Computations. Third edition. John Wiley and Sons, Hoboken, New Jersey 2010.   CrossRef
  33. B. Yu and B. Yuan: A more efficient branch and bound algorithm for feature selection. Pattern Recognit. 26 (1993), 6, 883-889.   DOI:10.1016/0031-3203(93)90054-Z
  34. Y. Zhao and X. Huo: A survey of numerical algorithms that can solve the Lasso problems. Wiley Interdiscip. Rev. Comput. Stat. 15 (2023), 4, e1602.   DOI:10.1002/wics.1602
  35. J. Zhu, C. Wen, J. Zhu, H. Zhang and X. Wang: A polynomial algorithm for best-subset selection problem. Proc. Natl. Acad. Sci. USA 117 (2020), 52, 33117-33123.   DOI:10.1073/pnas.2014241117
  36. J. Zhu, X. Wang, L. Hu, J. Huang, K. Jiang, Y. Zhang, S. Lin and J. Zhu: abess: A fast best-subset selection library in python and R. J. Mach. Learn. Res. 23 (2022), 202, 1-7.   DOI:10.32614/cran.package.abess