New bounds for subset selection from conic relaxations

Abstract New bounds are proposed for the subset selection problem which consists in minimizing the residual sum of squares subject to a cardinality constraint on the maximum number of non-zero variables. They rely on new convex relaxations providing both upper and lower bounds that are compared with others present in the literature. The performance of these methods is illustrated through computational experiments.