Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Algorithme branch-and-bound pour l’optimisation exacte en norme L0

Abstract : Nous proposons une approche d’optimisation globale de critères de moindres carrés pénalisés par la « norme » L0 , avec un algorithme de séparation et évaluation progressive (branch-and-bound). Nous construisons une procédure dédiée d’exploration de l’arbre de recherche combinatoire. Nous montrons que chaque nœud parcouru peut être évalué par l’optimisation de problèmes en norme L1 avec des contraintes de borne. Nous construisons alors un algorithme de type active-set pour les résoudre. Notre procédure permet de résoudre des problèmes de taille modérée mais difficiles, et s’avère notamment plus efficace que le solveur générique CPLEX s’appuyant sur une reformulation MIQP (Mixed- integer Quadratic Programming) du problème.
Liste complète des métadonnées

https://hal.archives-ouvertes.fr/hal-02583457
Contributeur : Sébastien Bourguignon <>
Soumis le : jeudi 14 mai 2020 - 22:24:40
Dernière modification le : mercredi 21 avril 2021 - 11:18:03

Identifiants

  • HAL Id : hal-02583457, version 1

Citation

Ramzi Ben Mhenni, Sébastien Bourguignon, Jordan Ninin, Marcel Mongeau, Hervé Carfantan. Algorithme branch-and-bound pour l’optimisation exacte en norme L0. GRETSI, XXVIIème Colloque francophone de traitement du signal et des images, Aug 2019, Lille, France. ⟨hal-02583457⟩

Partager

Métriques

Consultations de la notice

89