Techniques d'accélération d'une méthode de Branch-and-bound pour l'optimisation parcimonieuse - Archive ouverte HAL Access content directly
Conference Papers Year :

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

(1) , (1) , (2, 3)
1
2
3

Abstract

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
Origin : Files produced by the author(s)

Dates and versions

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

Identifiers

  • HAL Id : hal-03781318 , version 1

Cite

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⟩
15 View
5 Download

Share

Gmail Facebook Twitter LinkedIn More