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

References

• Aktürk MS, Atamtürk A, Gürel S (2009) A strong conic quadratic reformulation for machine-job assignment with controllable processing times. Oper. Res. Lett. 37(3):187–191.Crossref, Google Scholar
• Atamtürk A, Gómez A (2018) Strong formulations for quadratic optimization with M-matrices and indicator variables. Math. Programming 170(1):141–176.Crossref, Google Scholar
• Atamtürk A, Gómez A (2020) Safe screening rules for l0-regression from perspective relaxations. Daumé H III, Singh A, eds. Proc. 37th Internat. Conf. Machine Learn., vol. 119, 421–430.Google Scholar
• Beasley JE (1990) OR-library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11):1069–1072.Crossref, Google Scholar
• Belotti P, Bonami P, Fischetti M, Lodi A, Monaci M, Nogales-Gómez A, Salvagnin D (2016) On handling indicator constraints in mixed integer programming. Comput. Optim. Appl. 65(3):545–566.Crossref, Google Scholar
• Bertsimas D, Copenhaver MS (2018) Characterization of the equivalence of robustification and regularization in linear and matrix regression. Eur. J. Oper. Res. 270(3):931–942.Crossref, Google Scholar
• Bertsimas D, Cory-Wright R (2018) A scalable algorithm for sparse portfolio selection. Preprint, submitted October 31, https://arxiv.org/abs/1811.00138.Google Scholar
• Bertsimas D, Digalakis V Jr (2020) The backbone method for ultra-high dimensional sparse machine learning. Preprint, submitted June 11, https://arxiv.org/abs/2006.06592.Google Scholar
• Bertsimas D, van Parys B (2020) Sparse high-dimensional regression: Exact scalable algorithms and phase transitions. Ann. Statist. 48(1):300–323.Crossref, Google Scholar
• Bertsimas D, Shioda R (2009) Algorithm for cardinality-constrained quadratic optimization. Comput. Optim. Appl. 43(1):1–22.Crossref, Google Scholar
• Bertsimas D, Copenhaver MS, Mazumder R (2017) The trimmed Lasso: Sparsity and robustness. Preprint, submitted August 15, https://arxiv.org/abs/1708.04527.Google Scholar
• Bertsimas D, Cory-Wright R, Pauphilet J (2019) A unified approach to mixed-integer optimization problems with logical constraints. Preprint, submitted July 3, https://arxiv.org/abs/1907.02109.Google Scholar
• Bertsimas D, Cory-Wright R, Pauphilet J (2020) Solving large-scale sparse PCA to certifiable (near) optimality. Preprint, submitted May 11, https://arxiv.org/abs/2005.05195.Google Scholar
• Bertsimas D, Darnell C, Soucy R (1999) Portfolio construction through mixed-integer programming at Grantham, Mayo, Van Otterloo and Company. INFORMS J. Appl. Anal. 29(1):49–66.Google Scholar
• Bertsimas D, King A, Mazumder R (2016) Best subset selection via a modern optimization lens. Ann. Statist. 44(2):813–852.Crossref, Google Scholar
• Bienstock D (1996) Computational study of a family of mixed-integer quadratic programming problems. Math. Programming 74:121–140.Crossref, Google Scholar
• Bienstock D (2010) Eigenvalue techniques for convex objective, nonconvex optimization problems. Eisenbrand F, Shepherd FB, eds. Internat. Conf. Integer Programming Combinatorial Optim. (Springer, Berlin, Heidelberg), 29–42.Google Scholar
• Bonami P, Lejeune MA (2009) An exact solution approach for portfolio optimization problems under stochastic and integer constraints. Oper. Res. 57(3):650–670.Link, Google Scholar
• Bonami P, Lodi A, Tramontani A, Wiese S (2015) On mathematical programming with indicator constraints. Math. Programming 151(1):191–223.Crossref, Google Scholar
• Bühlmann P, van de Geer S (2011) Statistics for High-Dimensional Data: Methods, Theory and Applications (Springer).Crossref, Google Scholar
• Burdakov OP, Kanzow C, Schwartz A (2016) Mathematical programs with cardinality constraints: Reformulation by complementarity-type conditions and a regularization method. SIAM J. Optim. 26(1):397–425.Crossref, Google Scholar
• Burer S, Monteiro RDC (2003) A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Programming 95:329–357.Crossref, Google Scholar
• Burgard JP, Costa CM, Schmidt M (2022) Decomposition methods for robustified k-means clustering problems: If less conservative does not mean less bad. Ann. Oper. Res. Forthcoming.Google Scholar
• Candes E, Tao T (2005) Decoding by linear programming. IEEE Trans. Inform. Theory 51(12):4203–4215.Crossref, Google Scholar
• Çay SB (2016) Random portfolio data set generator. Initial release of dataset. Zenodo. Accessed July 11, 2022, https://doi.org/10.5281/zenodo.53204.Google Scholar
• Chang T, Meade N, Beasley J, Sharaiha Y (2000) Heuristics for cardinality constrained portfolio optimisation. Comput. Oper. Res. 27(13):1271–1302.Crossref, Google Scholar
• Cui X, Zheng X, Zhu S, Sun X (2013) Convex relaxations and MIQCQP reformulations for a class of cardinality-constrained portfolio selection problems. J. Global Optim. 56(4):1409–1423.Crossref, Google Scholar
• Dedieu A, Hazimeh H, Mazumder R (2020) Learning sparse classifiers: Continuous and mixed integer optimization perspectives. Preprint, submitted January 17, https://arxiv.org/abs/2001.06471.Google Scholar
• Dey SS, Mazumder R, Molinaro M, Wang G (2017) Sparse principal component analysis and its l1-relaxation. Preprint, submitted December 3, https://arxiv.org/abs/1712.00800.Google Scholar
• Dobriban E, Fan J (2016) Regularity properties for sparse regression. Comm. Math. Statist. 4(1):1–19.Crossref, Google Scholar
• Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming91(2):201–213.Crossref, Google Scholar
• Dong H, Chen K, Linderoth J (2015) Regularization vs. relaxation: A conic optimization perspective of statistical variable selection. Preprint, submitted October 20, https://arxiv.org/abs/1510.06083.Google Scholar
• Efron B, Hastie T, Johnstone I, Tibshirani R (2004) Least angle regression. Ann. Statist. 32(2):407–499.Crossref, Google Scholar
• Frangioni A, Gentile C (2006) Perspective cuts for a class of convex 0-1 mixed integer programs. Math. Programming 106(2):225–236.Crossref, Google Scholar
• Frangioni A, Gentile C (2007) SDP diagonalizations and perspective cuts for a class of nonseparable MIQP. Oper. Res. Lett. 35(2):181–185.Crossref, Google Scholar
• Frangioni A, Gentile C (2009) A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes. Oper. Res. Lett. 37(3):206–210.Crossref, Google Scholar
• Frangioni A, Furini F, Gentile C (2016) Approximated perspective relaxations: A project and lift approach. Comput. Optim. Appl. 63(3):705–735.Crossref, Google Scholar
• Frangioni A, Furini F, Gentile C (2017) Improving the approximated projected perspective reformulation by dual information. Oper. Res. Lett. 45(5):519–524.Crossref, Google Scholar
• Friedman J, Hastie T, Höfling H, Tibshirani R (2007) Pathwise coordinate optimization. Ann. Appl. Statist. 1(2):302–332.Crossref, Google Scholar
• Gao J, Li D (2013) Optimal cardinality constrained portfolio selection. Oper. Res. 61(3):745–761.Link, Google Scholar
• Ge J, Li X, Jiang H, Liu H, Zhang T, Wang M, Zhao T (2019) Picasso: A sparse learning library for high dimensional data analysis in R and Python. J. Machine Learn. Res. 20(44):1–5.Google Scholar
• Geißler B, Morsi A, Schewe L, Schmidt M (2015) Solving power-constrained gas transportation problems using an MIP-based alternating direction method. Comput. Chemical Engrg. 82:303–317.Crossref, Google Scholar
• Geißler B, Morsi A, Schewe L, Schmidt M (2017) Penalty alternating direction methods for mixed-integer optimization: A new view on feasibility pumps. SIAM J. Optim. 27(3):1611–1636.Crossref, Google Scholar
• Geißler B, Morsi A, Schewe L, Schmidt M (2018) Solving highly detailed gas transport MINLPS: Block separability and penalty alternating direction methods. INFORMS J. Comput. 30(2):309–323.Link, Google Scholar
• Gorski J, Pfeuffer F, Klamroth K (2007) Biconvex sets and optimization with biconvex functions: A survey and extensions. Math. Methods Oper. Res. 66(3):373–407.Crossref, Google Scholar
• Günlük O, Linderoth J (2010) Perspective reformulations of mixed integer nonlinear programs with indicator variables. Math. Programming 124(1–2):183–205.Crossref, Google Scholar
• Hastie T, Tibshirani R, Tibshirani R (2020) Best subset, forward stepwise or Lasso? Analysis and recommendations based on extensive comparisons. Statist. Sci. 35(4):579–592.Google Scholar
• Hastie T, Mazumder R, Lee JD, Zadeh R (2015) Matrix completion and low-rank SVD via fast alternating least squares. J. Machine Learn. Res. 16(104):3367–3402.Google Scholar
• Hazimeh H, Mazumder R (2020) Fast best subset selection: Coordinate descent and local combinatorial optimization algorithms. Oper. Res. 68(5):1517–1537.Link, Google Scholar
• Hirschberger M, Qi Y, Steuer RE (2007) Randomly generating portfolio-selection covariance matrices with specified distributional characteristics. Eur. J. Oper. Res. 177(3):1610–1625.Crossref, Google Scholar
• Jin Y, Qu R, Atkin J (2016) Constrained portfolio optimisation: The state-of-the-art Markowitz models. Proc. Fifth Internat. Conf. Oper. Res. Enterprise Systems, 388–395.Google Scholar
• Kleinert T, Schmidt M (2019) Computing feasible points of bilevel problems with a penalty alternating direction method. INFORMS J. Comput. 33(1):198–215.Link, Google Scholar
• Kreber D (2019) Cardinality-constrained discrete optimization for regression. Unpublished doctoral thesis, Universität Trier, Germany.Google Scholar
• Li Y, Xie W (2020) Exact and approximation algorithms for sparse PCA. Preprint, submitted August 28, https://arxiv.org/abs/2008.12438.Google Scholar
• Markowitz H (1952) Portfolio selection. J. Finance 7(1):77–91.Google Scholar
• Mazumder R, Friedman JH, Hastie T (2011) SparseNet: Coordinate descent with nonconvex penalties. J. Amer. Statist. Assoc. 106(495):1125–1138.Crossref, Google Scholar
• Mencarelli L, D’Ambrosio C (2019) Complex portfolio selection via convex mixed-integer quadratic programming: A survey. Internat. Trans. Oper. Res. 26(2):389–414.Crossref, Google Scholar
• Miller A (1990) Subset Selection in Regression (Chapman and Hall, Melbourne, Australia).Crossref, Google Scholar
• Natarajan BK (1995) Sparse approximate solutions to linear systems. SIAM J. Comput. 24(2):227–234.Crossref, Google Scholar
• Oxley JG (2011) Matroid Theory (Oxford University Press, New York).Crossref, Google Scholar
• Schewe L, Schmidt M, Weninger D (2020) A decomposition heuristic for mixed-integer supply chain problems. Oper. Res. Lett. 48(3):225–232.Crossref, Google Scholar
• Tawarmalani M, Sahinidis N (2001) Semidefinite relaxations of fractional programs via novel convexification techniques. J. Global Optim. 20:133–154.Crossref, Google Scholar
• Teng Y, Yang L, Yu B, Song X (2017) A penalty PALM method for sparse portfolio selection problems. Optim. Methods Software 32(1):126–147.Crossref, Google Scholar
• Tibshirani R (1996) Regression shrinkage and selection via the Lasso. J. Roy. Statist. Soc. B 58(1):267–288.Crossref, Google Scholar
• Tibshirani RJ (2013) The lasso problem and uniqueness. Electronic J. Statist. 7(1):1456–1490.Google Scholar
• Tillmann AM, Pfetsch ME (2014) The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing. IEEE Trans. Inform. Theory 60(2):1248–1259.Crossref, Google Scholar
• van de Geer S (2007) The Deterministic Lasso. Seminar für Statistik, Eidgenössische Technische Hochschule Zürich, 140.Google Scholar
• Vielma JP, Ahmed S, Nemhauser GL (2008) A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs. INFORMS J. Comput. 20(3):438–450.Link, Google Scholar
• Wendell RE, Hurter AP (1976) Minimization of a non-separable objective function subject to disjoint constraints. Oper. Res. 24(4):643–657.Link, Google Scholar
• Zhang C-H (2010) Nearly unbiased variable selection under minimax concave penalty. Ann. Statist. 38(2):894–942.Crossref, Google Scholar
• Zheng X, Sun X, Li D (2014) Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: A semidefinite program approach. INFORMS J. Comput. 26(4):690–703.Link, Google Scholar
• Zou H, Hastie T (2005) Regularization and variable selection via the elastic net. J. Roy. Stat. Soc. Ser. B Statist. Methodology 67(2):301–320.Crossref, Google Scholar