Techniques d'accélération d'une méthode de Branch-and-bound pour l'optimisation parcimonieuse

International audienceLes problèmes d'ajustement de modèles de faible cardinalité ont trouvé de nombreuses applications en statistique, en finance et en traitement du signal. Au sein de ces problèmes, nous nous intéressons au problème de l'ajustement par moindres carrés, pénalisé par la cardinalité de la solution. Nous utilisons un algorithme branch-and-bound pour trouver l'optimum global de ce problème NP-complet. Au sein de cet algorithme, les bornes inférieures évaluées à chaque noeud sont calculées par la résolution de problèmes en norme 1, qui disposent d'une large panoplie de méthodes dédiées. Dans cette communication, nous exposons deux techniques exploitant la dualité convexe pour, d'une part, éviter de résoudre certains problèmes de relaxation jusqu'à l'optimalité, permettant d'accélérer le calcul des bornes inférieures, et d'autre part réduire la dimension de ces problèmes par une stratégie de screening. Une étude expérimentale valide la pertinence de ces techniques pour réduire le temps de calcul