| Title:
|
An algorithm for cardinality-constrained optimization with an application to the best subset selection and sparse portfolio problems (English) |
| Author:
|
Singh, Vikram |
| Author:
|
Sun, Min |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
62 |
| Issue:
|
3 |
| Year:
|
2026 |
| Pages:
|
373-399 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
global optimization |
| Keyword:
|
cardinality-constraint |
| Keyword:
|
quadratic optimization |
| Keyword:
|
branch-and-bound |
| Keyword:
|
best subset selection |
| Keyword:
|
portfolio optimization |
| MSC:
|
65K05 |
| MSC:
|
90C26 |
| MSC:
|
90C57 |
| DOI:
|
10.14736/kyb-2026-3-0373 |
| . |
| Date available:
|
2026-07-15T16:24:41Z |
| Last updated:
|
2026-07-15 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/153680 |
| . |
| Reference:
|
[1] d'Aspremont, A., Bach, F., Ghaoui, L. El: Optimal solutions for sparse principal component analysis..J. Mach. Learn. Res. 9 (2008), 7, 1269-1294. |
| Reference:
|
[2] Beasley, J. E.: OR-Library: distributing test problems by electronic mail..J. Oper. Res. Soc. 41 (1990), 11, 1069-1072. |
| Reference:
|
[3] Bertsimas, D., Shioda, R.: Algorithm for cardinality-constrained quadratic optimization..Comput. Optim. Appl. 43 (2009), 1, 1-22. |
| Reference:
|
[4] Bertsimas, D., King, A., Mazumder, R.: Best subset selection via a modern optimization lens..Ann. Statist. 44 (2015), 2, 813-852. |
| Reference:
|
[5] Bienstock, D.: Computational study of a family of mixed-integer quadratic programming problems..Math. Program. 74 (1996), 121-140. |
| Reference:
|
[6] Bixby, R. E.: Implementing the simplex method: the initial basis..ORSA J. Comput. 4 (1992), 3, 267-284. |
| Reference:
|
[7] Blumensath, T., Davies, M. E.: Iterative thresholding for sparse approximations..J. Fourier Anal. Appl. 14 (2008), 629-654. |
| Reference:
|
[8] Bonami, P., Lejeune, M. A.: An exact solution approach for portfolio optimization problems under stochastic and integer constraints..Oper. Res. 57 (2009), 3, 650-670. 10.1287/opre.1080.0599 |
| Reference:
|
[9] Branda, M., Bucher, M., Červinka, M., Schwartz, A.: 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. |
| Reference:
|
[10] Bühlmann, P., Geer, S. van de: Statistics for High-Dimensional Data: Methods, Theory and Applications..Springer-Verlag, Berlin 2011. |
| Reference:
|
[11] Moreira, C., Kreber, D., Schmidt, M.: 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. |
| Reference:
|
[12] Friedman, J., Hastie, T., Tibshirani, R.: Regularization paths for generalized linear models via coordinate descent..J. Stat. Softw. 33 (2010), 1, 1-22. |
| Reference:
|
[13] Fukunaga, K.: Introduction to Statistical Pattern Recognition. Second edition..Academic Press, Inc., San Diego 1990. |
| Reference:
|
[14] Gao, J., Li, D.: Optimal cardinality constrained portfolio selection..Oper. Res. 61 (2013), 3, 745-761. |
| Reference:
|
[15] Gatu, C., Kontoghiorghes, E. J.: Branch-and-bound algorithms for computing the best-subset regression models..J. Comput. Graph. Statist. 15 (2006), 1, 139-156. |
| Reference:
|
[16] Optimization, Gurobi, LLC: Gurobi optimizer reference manual..2023. |
| Reference:
|
[17] Eldon, H.: Global optimization using interval analysis—the multi-dimensional case..Numer. Math. 34 (1980), 3, 247-270. 10.1007/BF01396702 |
| Reference:
|
[18] Hastie, T., Tibshirani, R., Tibshirani, R. J.: Extended comparisons of best subset selection, forward stepwise selection, and the lasso. (2017). |
| Reference:
|
[19] Hirschberger, M., Qi, Y., Steuer, R. E.: Randomly generating portfolio-selection covariance matrices with specified distributional characteristics..European J. Oper. Res. 177 (2007), 3, 1610-1625. |
| Reference:
|
[20] Jin, Y., Qu, R., Atkin, J.: 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. |
| Reference:
|
[21] Markowitz, H.: Portfolio Selection*..J. Finance 7 (1952), 1, 77-91. |
| Reference:
|
[22] Miller, A.: Subset Selection in Regression. Second edition..Chapman and Hall/CRC, New York 2002. |
| Reference:
|
[23] Moore, R. E.: Interval Analysis..Prentice-Hall, Englewood Cliffs, New Jersey 1966. |
| Reference:
|
[24] Morrison, D. R., Jacobson, S. H., Sauppe, J. J., Sewell, E. C.: Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning..Discrete Optim. 19 (2016), 79-102. |
| Reference:
|
[25] Narendra, P. M., Fukunaga, K.: A branch and bound algorithm for feature subset selection..IEEE Trans. Comput. 26 (1977), 9, 917-922. 10.1109/TC.1977.1674939 |
| Reference:
|
[26] Natarajan, B. K.: Sparse approximate solutions to linear systems..SIAM J. Comput. 24 (1995), 2, 227-234. |
| Reference:
|
[27] Ratschek, H., Rokne, J.: New Computer Methods for Global Optimization..Halsted Press, Chichester 1988. |
| Reference:
|
[28] Çay, S. B.: Random Portfolio Dataset Generator.. |
| Reference:
|
[29] Somol, P., Pudil, P., Kittler, J.: Fast branch \& bound algorithms for optimal feature selection..IEEE Trans. Patt. Anal. Machine Intell. 26 (2004), 7, 900-912. |
| Reference:
|
[30] Tibshirani, R.: Regression shrinkage and selection via the lasso..J. R. Stat. Soc. Ser. B. Stat. Methodol. 58 (1996), 1, 267-288. |
| Reference:
|
[31] Tillman, A. M., Bienstock, D., Lodi, A., Schwartz, A.: Cardinality minimization, constraints, and regularization: a survey..SIAM Rev. 66 (2024), 3, 403-477. |
| Reference:
|
[32] Watkins, D. S.: Fundamentals of Matrix Computations. Third edition..John Wiley and Sons, Hoboken, New Jersey 2010. |
| Reference:
|
[33] Yu, B., Yuan, B.: A more efficient branch and bound algorithm for feature selection..Pattern Recognit. 26 (1993), 6, 883-889. |
| Reference:
|
[34] Zhao, Y., Huo, X.: A survey of numerical algorithms that can solve the Lasso problems..Wiley Interdiscip. Rev. Comput. Stat. 15 (2023), 4, e1602. |
| Reference:
|
[35] Zhu, J., Wen, C., Zhu, J., Zhang, H., Wang, X.: A polynomial algorithm for best-subset selection problem..Proc. Natl. Acad. Sci. USA 117 (2020), 52, 33117-33123. |
| Reference:
|
[36] Zhu, J., Wang, X., Hu, L., Huang, J., Jiang, K., Zhang, Y., Lin, S., Zhu, J.: abess: A fast best-subset selection library in python and R..J. Mach. Learn. Res. 23 (2022), 202, 1-7. |
| . |
