Choisissez le fuseau horaire
Le fuseau horaire de votre profil:
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.