Skip to Main content Skip to Navigation
New interface
Conference papers

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.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03781318
Contributor : Gwenaël Samain Connect in order to contact the contributor
Submitted on : Tuesday, September 20, 2022 - 11:43:07 AM
Last modification on : Wednesday, September 28, 2022 - 5:41:50 AM

File

gretsi2022_Samain_Bourguignon_...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03781318, version 1

Citation

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⟩

Share

Metrics

Record views

15

Files downloads

5