 |
Communication dans un congrès
Algorithme branch-and-bound pour l’optimisation exacte en norme L0
Ramzi Ben Mhenni
1
Sébastien Bourguignon
1
Jordan Ninin
2
Marcel Mongeau
3
Hervé Carfantan
4
2
Lab-STICC_ENSTAB_CID_PRASYS
Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
Ramzi Ben Mhenni 1
Auteur Etablissement employeur : Laboratoire des Sciences du Numérique de Nantes IdHAL : ramzi-ben-mhenni ORCID : https://orcid.org/0000-0002-3611-0119
Sébastien Bourguignon 1
Auteur IdHAL : sebastien-bourguignon ORCID : https://orcid.org/0000-0002-6660-2704
Jordan Ninin 2
Auteur IdHAL : jordan-ninin ORCID : https://orcid.org/0000-0002-7232-8246
Marcel Mongeau 3
Auteur Etablissement employeur : Ecole Nationale de l'Aviation Civile IdHAL : marcel-mongeau IdRef : https://www.idref.fr/076723291 ORCID : https://orcid.org/0000-0001-7667-1044 VIAF : https://viaf.org/viaf/105598818
Hervé Carfantan 4
Auteur IdHAL : herve-carfantan ORCID : https://orcid.org/0000-0001-7925-9426
1
LS2N - Laboratoire des Sciences du Numérique de Nantes (Université de Nantes – faculté des Sciences et Techniques (FST)
2 Chemin de la Houssinière
BP 92208, 44322 Nantes Cedex 3 - France)
- Université de Nantes - Faculté des Sciences et des Techniques (2, rue de la Houssinière - BP 92208 - 44322 Nantes cedex 3 - France)
- UN - Université de Nantes (1, quai de Tourville - BP 13522 - 44035 Nantes cedex 1 - France)
- ECN - École Centrale de Nantes (1 rue de la Noë - BP 92101 - 44321 Nantes cedex 3 - France)
- CNRS - Centre National de la Recherche Scientifique : UMR6004 (France)
- IMT Atlantique - IMT Atlantique Bretagne-Pays de la Loire (Campus Brest : Technopôle Brest-Iroise CS 8381829238 BREST Cedex 3 -
Campus Nantes : 4, rue Alfred Kastler- La chantrerie 44300 NANTES -
Campus Rennes : 2 Rue de la Châtaigneraie, 35510 CESSON SEVIGNE - France)
- IMT - Institut Mines-Télécom [Paris] (37-39 Rue Dareau, 75014 Paris - France)
2
Lab-STICC_ENSTAB_CID_PRASYS (ENSTA Bretagne, 2 rue François Verny, 29806 Brest cedex 9 - France)
- Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Technopole Brest Iroise CS 83818 29238 BREST cedex 3 - France)
- ENIB - École Nationale d'Ingénieurs de Brest (945 avenue du Technopole - 29280 Plouzané - France)
- UBS - Université de Bretagne Sud (BP 92116 - 56321 Lorient cedex - France)
- UBO - Université de Brest (Université de Bretagne Occidentale - 3 Rue des Archives 29238, Brest - France)
- ENSTA Bretagne - École Nationale Supérieure de Techniques Avancées Bretagne (2 rue François Verny, 29806 Brest cedex 9 - France)
- IMT - Institut Mines-Télécom [Paris] (37-39 Rue Dareau, 75014 Paris - France)
- CNRS - Centre National de la Recherche Scientifique : UMR6285 (France)
- UBL - Université Bretagne Loire (Cité Internationale, 1 place Paul Ricoeur - CS 54417 35044 RENNES CEDEX - France)
- IMT Atlantique - IMT Atlantique Bretagne-Pays de la Loire (Campus Brest : Technopôle Brest-Iroise CS 8381829238 BREST Cedex 3 -
Campus Nantes : 4, rue Alfred Kastler- La chantrerie 44300 NANTES -
Campus Rennes : 2 Rue de la Châtaigneraie, 35510 CESSON SEVIGNE - France)
- IMT - Institut Mines-Télécom [Paris] (37-39 Rue Dareau, 75014 Paris - France)
3
ENAC - Ecole Nationale de l'Aviation Civile (7 avenue Edouard Belin
CS 54005
31055 Toulouse cedex 4 - France)
4
IRAP - Institut de recherche en astrophysique et planétologie (9 avenue Colonel Roche 31028 Toulouse - France)
- CNRS - Centre National de la Recherche Scientifique : UMR5277 (France)
- OMP - Observatoire Midi-Pyrénées (14 avenue Edouard Belin, 31400 TOULOUSE - France)
- Météo France (Direction interrégionale - Sud-Est, 2 boulevard Château Double, Aix-en-Provence - France)
- CNES - Centre National d'Études Spatiales [Toulouse] (18 avenue Edouard Belin 31401 Toulouse - France)
- Université Fédérale Toulouse Midi-Pyrénées (41 Allée Jules Guesde, 31000 Toulouse - France)
- CNRS - Centre National de la Recherche Scientifique : UAR 831 (France)
- IRD - Institut de Recherche pour le Développement (Siège Le Sextant 44, bd de Dunkerque CS 90009 13572 Marseille cedex 02 - France)
- UT3 - Université Toulouse III - Paul Sabatier (118 route de Narbonne - 31062 Toulouse - France)
- Université Fédérale Toulouse Midi-Pyrénées (41 Allée Jules Guesde, 31000 Toulouse - France)
- INSU - CNRS - Institut national des sciences de l'Univers : UMR5277 (INSU-CNRS 3 rue Michel-Ange, 75794 Paris Cedex 16 - France)
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.
Type de document :
Communication dans un congrès
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
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
Collections
UNIV-BREST | UNIV-TLSE3 | EC-NANTES | OMP-IRAP | UNAM | ENIB | LAB-STICC | ENAC | LS2N | OMP | UNIV-NANTES | CNRS | INSU | OPTIM | ENSTA-BRETAGNE | ENSTA-BRETAGNE-STIC | LS2N-SIMS | INSTITUT-TELECOM | METEO
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⟩
Métriques
Consultations de la notice