Abstract
This paper describes an algorithm for cardinality-constrained quadratic optimization problems, which are convex quadratic programming problems with a limit on the number of non-zeros in the optimal solution. In particular, we consider problems of subset selection in regression and portfolio selection in asset management and propose branch-and-bound based algorithms that take advantage of the special structure of these problems. We compare our tailored methods against CPLEX’s quadratic mixed-integer solver and conclude that the proposed algorithms have practical advantages for the special class of problems we consider.
Similar content being viewed by others
References
Arthanari, T.S., Dodge, Y.: Mathematical Programming in Statistics. Wiley, New York (1993)
Beale, E.M.L., Kendall, M.G., Mann, D.W.: The discarding of variables in multivariate analysis. Biometrika 54(3/4), 357–366 (1967)
Bertsimas, D., Darnell, C., Soucy, R.: Portfolio construction through mixed-integer programming at Grantham, Mayo, Van Otterloo and Company. Interfaces 29(1), 49–66 (1999)
Bienstock, D.: Computational study on families of mixed-integer quadratic programming problems. Math. Program. 74, 121–140 (1996)
Blog, B., van der Hoek, G., Rinnooy Kan, A.H.G., Timmer, G.T.: Optimal selection of small portfolio. Manag. Sci. 29(7), 792–798 (1983)
Chang, T.J., Meade, N., Beasley, J.E., Sharaiha, Y.: Heuristics for cardinality constrained portfolio optimisation. Comput. Operat. Res. 27, 1271–1302 (2000)
Cottle, R.W., Pang, J., Stone, R.E.: The Linear Complementarity Problem. Academic, San Diego (1992)
ILOG CPLEX 8.1 User Manual. ILOG CPLEX Division, Incline Village, NV (2002)
Furnival, G.M., Wilson Jr., R.W.: Regression by leaps and bounds. Technometrics 16(4), 499–511 (1974)
Hockings, R.R., Leslie, R.N.: Selection of the best subset in regression analysis. Technometrics 9(4), 531–540 (1967)
Jacob, N.: A limited diversification portfolio selection model for the small investor. J. Finance 29(3), 847–856 (1974)
Jobst, N., Horniman, M., Lucas, C., Mitra, G.: Computational aspects of alternative portfolio selection models in the presence of discrete asset choice constraints. Quant. Finance 1(5), 489–501 (2001)
Lemke, C.E.: Bimatrix equilibrium points and mathematical programming. Manag. Sci. 11(7), 681–689 (1965)
Lemke, C.E., Howson, J.T. Jr.: Equilibrium points of bimatrix games. J. Soc. Ind. Appl. Math. 12(2), 413–423 (1964)
Konno, H., Wijayanayake, A.: Portfolio optimization problem under concave transaction costs and minimal transaction unit constraints. Math. Program. 89, 233–250 (2001)
Mansini, R., Speranza, M.G.: An exact approach for portfolio selection with transaction costs and rounds. IIE Trans. 37, 919–929 (2005)
Mansini, R., Speranza, M.G.: Heuristic algorithms for portfolio selection problem with minimum transaction lots. Eur. J. Operat. Res. 114(1), 219–233 (1999)
Miller, A.: Subset Selection in Regression. Monographs on Statistics and Applied Probability, vol. 40. Chapman and Hall, London (1990)
Narula, S., Wellington, J.: Selection of variables in linear regression using the minimum sum of weighted absolute errors criterion. Technometrics 21(3), 299–311 (1979)
Owens-Butera, G.: The solution of a class of limited diversification portfolio selection problems. Ph.D. thesis, Rice University, CRPC-TR97724-S (1997)
Patel, N., Subrahmanyam, M.: A simple algorithm for optimal portfolio selection with fixed transaction costs. Manag. Sci. 28(3), 303–314 (1982)
Press, W.H., Flannery, B., Teukolsky, S., Vetterling, W.: Numerical Recipes in C, 2nd edn. Cambridge University Press, Cambridge (1992). http://www.nr.com
Ryan, T.P.: Modern Regression Methods. Wiley Series in Probability and Statistics. Wiley, New York (1997)
Sharpe, W.: A linear programming algorithm for mutual fund portfolio selection. Manag. Sci. 13(7), 499–510 (1967)
Sharpe, W.: A linear programming approximation for the general portfolio analysis problem. J. Financ. Quant. Anal. 6(5), 1263–1275 (1971)
Author information
Authors and Affiliations
Corresponding author
Additional information
The research of D. Bertsimas was partially supported by the Singapore-MIT alliance.
The research of R. Shioda was partially supported by the Singapore-MIT alliance, the Discovery Grant from NSERC and a research grant from the Faculty of Mathematics, University of Waterloo.
Rights and permissions
About this article
Cite this article
Bertsimas, D., Shioda, R. Algorithm for cardinality-constrained quadratic optimization. Comput Optim Appl 43, 1–22 (2009). https://doi.org/10.1007/s10589-007-9126-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-007-9126-9