Article
Full entry |
PDF
(0.6 MB)
Feedback
PDF
(0.6 MB)
Feedback
Keywords:
global optimization; cardinality-constraint; quadratic optimization; branch-and-bound; best subset selection; portfolio optimization
global optimization; cardinality-constraint; quadratic optimization; branch-and-bound; best subset selection; portfolio optimization
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.
References:
[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.
[2] Beasley, J. E.: OR-Library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41 (1990), 11, 1069-1072. DOI
[3] Bertsimas, D., Shioda, R.: Algorithm for cardinality-constrained quadratic optimization. Comput. Optim. Appl. 43 (2009), 1, 1-22. DOI
[4] Bertsimas, D., King, A., Mazumder, R.: Best subset selection via a modern optimization lens. Ann. Statist. 44 (2015), 2, 813-852. DOI
[5] Bienstock, D.: Computational study of a family of mixed-integer quadratic programming problems. Math. Program. 74 (1996), 121-140. DOI
[6] Bixby, R. E.: Implementing the simplex method: the initial basis. ORSA J. Comput. 4 (1992), 3, 267-284. DOI
[7] Blumensath, T., Davies, M. E.: Iterative thresholding for sparse approximations. J. Fourier Anal. Appl. 14 (2008), 629-654. DOI
[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. DOI 10.1287/opre.1080.0599
[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. DOI
[10] Bühlmann, P., Geer, S. van de: Statistics for High-Dimensional Data: Methods, Theory and Applications. Springer-Verlag, Berlin 2011. DOI
[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. DOI
[12] Friedman, J., Hastie, T., Tibshirani, R.: Regularization paths for generalized linear models via coordinate descent. J. Stat. Softw. 33 (2010), 1, 1-22. DOI
[13] Fukunaga, K.: Introduction to Statistical Pattern Recognition. Second edition. Academic Press, Inc., San Diego 1990.
[14] Gao, J., Li, D.: Optimal cardinality constrained portfolio selection. Oper. Res. 61 (2013), 3, 745-761. DOI
[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. DOI
[16] Optimization, Gurobi, LLC: Gurobi optimizer reference manual. 2023.
[17] Eldon, H.: Global optimization using interval analysis—the multi-dimensional case. Numer. Math. 34 (1980), 3, 247-270. DOI 10.1007/BF01396702
[18] Hastie, T., Tibshirani, R., Tibshirani, R. J.: Extended comparisons of best subset selection, forward stepwise selection, and the lasso. (2017).
[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. DOI
[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. DOI
[21] Markowitz, H.: Portfolio Selection*. J. Finance 7 (1952), 1, 77-91. DOI
[22] Miller, A.: Subset Selection in Regression. Second edition. Chapman and Hall/CRC, New York 2002.
[23] Moore, R. E.: Interval Analysis. Prentice-Hall, Englewood Cliffs, New Jersey 1966.
[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. DOI
[25] Narendra, P. M., Fukunaga, K.: A branch and bound algorithm for feature subset selection. IEEE Trans. Comput. 26 (1977), 9, 917-922. DOI 10.1109/TC.1977.1674939
[26] Natarajan, B. K.: Sparse approximate solutions to linear systems. SIAM J. Comput. 24 (1995), 2, 227-234. DOI
[27] Ratschek, H., Rokne, J.: New Computer Methods for Global Optimization. Halsted Press, Chichester 1988.
[28] Çay, S. B.: Random Portfolio Dataset Generator. DOI
[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. DOI
[30] Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B. Stat. Methodol. 58 (1996), 1, 267-288. DOI
[31] Tillman, A. M., Bienstock, D., Lodi, A., Schwartz, A.: Cardinality minimization, constraints, and regularization: a survey. SIAM Rev. 66 (2024), 3, 403-477. DOI
[32] Watkins, D. S.: Fundamentals of Matrix Computations. Third edition. John Wiley and Sons, Hoboken, New Jersey 2010.
[33] Yu, B., Yuan, B.: A more efficient branch and bound algorithm for feature selection. Pattern Recognit. 26 (1993), 6, 883-889. DOI
[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. DOI
[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. DOI
[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. DOI
Search
Partner of
