Subset Selection by Local Convex Approximation

This paper concerns selection of the optimal subset of variables in a lenear regression setting. The posed problem is combinatiorial and the globally best subset can only be found in exponential time. We define a cost function for the subset selection problem by adding the penalty term to the usual least squares criterion. We propose an optimization technique for the posed probelm based on a modified version of the Newton-Raphson iterations, combined with a backward elimination type algorithm. THe Newton-Raphson modification concerns iterative approximations to the non-convex cost function of the subset selection problem so as to guarantee positive definiteness of the Hessian term, hence avoiding numerical instability. The backward Elemination type algorithm attempts to improve the results upon termination of the modified Newton-Raphson search by sing the current solution as an initial guess. The efficiency of the method is illustrated by a numerical example with highly correlated explanatory variables for which the commonly used techiques such as forward selection/backward elimination perform poorly.