Optimisation convexe non-différentiable et méthodes de décomposition en recherche opérationnelle

Mots clé :

• dualité lagrangienne
• méthodes de faiceaux
• optimisation convexe non-différentiable
• recherche opérationnelle

Nous nous intéressons à la résolution de problèmes d'optimisation de grande taille, potentiellement non-linéaires et à variables mixtes ; tels les problèmes classiques de conception de réseaux, le problème de planification de production électrique d'EDF, ou encore le problème de réaffectation de machines de Google. Ces problèmes, hors de portée des méthodes de résolution frontales, ont une structure décomposable qui peut être exploitée. Cependant, leur résolution par les approches de décomposition classiques présente encore de nombreux défis. Dans cette thèse, nous adoptons un point de vue d'optimisation convexe non-différentiable sur les méthodes de décomposition pour en proposer de nouvelles variantes adaptées à ces problèmes difficiles. Plus précisément, nous présentons : (1) une accélération de la décomposition de Benders utilisant une stabilisation algorithmique ; (2) une régularisation de la décomposition lagrangienne dans le but d'améliorer la structure des solutions ; (3) un moyen de tirer parti d'informations faciles à obtenir mais de précision incontrôlée dans les algorithmes d'optimisation non-différentiable (souvent au cœur des approches de décomposition) ; (4) et enfin une nouvelle stratégie de décomposition pour le problème de réaffectation de machines, ainsi que des heuristiques efficaces pour la résolution des sous-problèmes engendrés.

Président:

Mr Anatoli Iouditski (Professeur - Université Joseph Fourier)

Directeurs:

• Mr Jérôme Malick (Chargé de Recherche - CNRS )
• Mr Bernard Brogliato (Directeur de Recherche - INRIA )

Raporteurs:

• Mr François Vanderbeck (Professeur - Université de Bordeaux )
• Mme Claudia Sagastizabal (Chercheur - IMPA - Brésil )

Examinateurs:

• Mr Wim van Ackrooil (Chercheur - EDF R&D Paris )
• Mr Anatoli Iouditski (Professeur - Université Joseph Fourier )