Global Optimization for Sparse Solution of Least Squares Problems

Finding solutions to least-squares problems with low cardinality has found many applications, including cardinality-constrained portfolio optimization, subset selection in Statistics, and many sparsity-enhancing inverse problems in signal processing. In general, this problem is NP-hard, and most works from a global optimization perspective consider a mixed integer programming (MIP) reformulation with binary variables, whose resolution is performed via branch-and-bound methods. We propose dedicated branch-and-bound algorithms for three possible formulations: cardinality-constrained and cardinality-penalized least-squares, and cardinality minimization under quadratic constraints. We show that the continuous relaxation problems involved at each node of the search tree are L1-norm-based optimization problems. A dedicated algorithm is built, based on the homotopy continuation principle , which efficiently computes the relaxed solutions for the three kinds of problems. The performance of the resulting global optimization procedure is then shown to compete with or improve over the CPLEX MIP solvers, especially for problems involving quadratic constraints. The proposed strategies are able to exactly solve some problems involving 500 to 1 000 unknowns in less than 1 000 seconds, for which CPLEX mostly fails.