Les problèmes d'ajustement de modèles de faible cardinalité ont trouvé de nombreuses applications en statistique, en optimisation de portefeuille et en traitement du signal. Parmi ces problèmes, nous nous intéressons à la résolution d'un problème structuré, dans lequel la pénalité de faible cardinalité l0 porte sur des groupes de composantes et non sur les composantes individuelles, et l'ajustement au modèle se fait par moindres carrés.
Ce problème, plus général que son équivalent non structuré, ne possède pas à notre connaissance de méthode dédiée pour trouver son optimum global de manière garantie. Nous proposons dans cette communication d'utiliser une méthode de branch-and-bound, et de calculer les bornes inférieures de chaque nœud via une relaxation l1 du problème originel permettant à la fois de gérer des cas de groupes se chevauchant et de réutiliser des algorithmes et techniques d'accélérations spécifiques aux problèmes l1 standard.
Nous intégrons cette approche dans une extension du solveur open-source Mimosa pour résoudre exactement ce problème structuré.