Séminaire Modélisation, Optimisation, Dynamique

Global optimization for least squares problems with low cardinality

par Sébastien Bourguignon (École Centrale de Nantes)

Europe/Paris
XLIM Salle X.203

XLIM Salle X.203

FST-Université de Limoges, 123, Av. Albert Thomas.
Description
Finding solutions to least-squares problems with low cardinality has found many applications, including cardinality-constrained portfolio optimization, subset selection in Statistics, and 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 l_1-norm-based optimization problems. A dedicated algorithm is built, based on the homotopy continuation principle, which efficiently computes the relaxed solutions for the three problem classes.

The resulting algorithms are shown to equal or improve over the CPLEX MIP solver, especially for problems involving quadratic constraints. The proposed strategies are able to exactly solve problems involving 500 to 1000 unknowns in less than 1000 seconds, for which CPLEX usually fails.