All-integer global optimization for high-dimensional sparse regression, with applications in financial and genomic data

OLS-regression fails to provide meaningful solutions under a large number of predictor variables due to the presence of multicollinearity. Sparse regression, or best subset selection, is used in such cases utilizing norm-0 control or norm-1 regularization. Mixed-integer optimization models resulting under norm-0 control, however, are computationally intractable although recent advances have been made for a moderate number of predictors. This paper contributes with a new efficient approach in very large dimensions under successive separable quadratic approximation of the mean squared error (MSE) function. At every iteration, given a current pivot solution, a separable form of the MSE function is minimized over a local hypercube trust region that is discretized to obtain an all-integer optimization subproblem employing norm-0 and norm-1 parametrization. Each subproblem is solved efficiently using the entropy-based constraint surrogation technique (ISCENT). The true MSE value associated with the subproblem optima is then used to specify a target MSE with specified tolerance, and the local trust region is enumerated to identify solutions that satisfy the target. With successively shrinking local hypercubes, along with corresponding subproblem optima and target enumeration, the method terminates with a high quality sparse predictive system. We test the method using two high-dimensional applications: financial index-tracking portfolio selection using 225 assets, and cancer prediction using genomic data having 906,600 predictors representing genetic variations for a sample of 704 humans. The proposed approach is shown to be more efficient and effective relative to the standard OLS or Lasso/Ridge models in providing accurate predictions.