Techniques d'accélération d'une méthode de Branch-and-bound pour l'optimisation parcimonieuse - ENSTA Bretagne - École nationale supérieure de techniques avancées Bretagne Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

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

Résumé

Les 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.
Fichier principal
Vignette du fichier
gretsi2022_Samain_Bourguignon_Ninin_postreview.pdf (288.53 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03781318 , version 1 (20-09-2022)

Identifiants

  • HAL Id : hal-03781318 , version 1

Citer

Gwenaël Samain, Sébastien Bourguignon, Jordan Ninin. Techniques d'accélération d'une méthode de Branch-and-bound pour l'optimisation parcimonieuse. GRETSI'22 XXVIIIème Colloque Francophone de Traitement du Signal et des Images, Sep 2022, Nancy, France. ⟨hal-03781318⟩
67 Consultations
32 Téléchargements

Partager

Gmail Facebook X LinkedIn More