Chapitre 5
QUELQUES SCHÉMAS DE DUALISATION
DANS DES PROBLÈMES D’OPTIMISATION
NON CONVEXES
"Dire que la plupart des fonctions sont non-convexes est
semblable à dire que la plupart des animaux de la jungle sont
des non-éléphants." S. Ulam (1909-1984)
"In the occupation with mathematical problems, a more
important role than generalization is played – I believe – by
specialization." K. Popper (1984)
Quand on a à traiter d’un problème d’optimisation non convexe, mais qui
a un peu de structure, il est possible de le "dualiser" d’une manière appropriée. Pour ce faire, on fait appel à des résultats et techniques qui, eux,
sont du monde de l’optimisation convexe. Dans ce chapitre, nous présentons
quelques schémas de dualisation de problèmes non convexes mais structurés.
Il s’agit de constructions qui ont fait leurs preuves, et bien établies à présent.
Points d’appui / Prérequis :
• Techniques de l’Analyse convexe (Chapitre 4), notamment les règles de
calcul sur la transformée de Legendre- Fenchel et le sous-différentiel.
Idée générale
Étant donné un problème d’optimisation (P), on lui associe, par des
méthodes de construction à définir, un autre problème d’optimisation (D),
qui sera appelé "dual" ou "adjoint" (ou encore autre appellation), possédant
les caractéristiques suivantes :
• (D) est a priori plus facile à traiter que le problème originel (P).
• La résolution de (D) (i.e. sa valeur optimale, ses solutions) aident à la
résolution de (P) (théoriquement comme numériquement).
• (Si possible) Il y a des règles de correspondance précises entre les
solutions (ou autres éléments d’intérêt comme les points critiques) de (P)
et de (D).
J.-B. Hiriart-Urruty, Bases, outils et principes pour l’analyse variationnelle,
117
Mathématiques et Applications 70, DOI: 10.1007/978-3-642-30735-5_5,
© Springer-Verlag Berlin Heidelberg 2013
QUELQUES SCHÉMAS DE DUALISATION
DANS DES PROBLÈMES D’OPTIMISATION
NON CONVEXES
"Dire que la plupart des fonctions sont non-convexes est
semblable à dire que la plupart des animaux de la jungle sont
des non-éléphants." S. Ulam (1909-1984)
"In the occupation with mathematical problems, a more
important role than generalization is played – I believe – by
specialization." K. Popper (1984)
Quand on a à traiter d’un problème d’optimisation non convexe, mais qui
a un peu de structure, il est possible de le "dualiser" d’une manière appropriée. Pour ce faire, on fait appel à des résultats et techniques qui, eux,
sont du monde de l’optimisation convexe. Dans ce chapitre, nous présentons
quelques schémas de dualisation de problèmes non convexes mais structurés.
Il s’agit de constructions qui ont fait leurs preuves, et bien établies à présent.
Points d’appui / Prérequis :
• Techniques de l’Analyse convexe (Chapitre 4), notamment les règles de
calcul sur la transformée de Legendre- Fenchel et le sous-différentiel.
Idée générale
Étant donné un problème d’optimisation (P), on lui associe, par des
méthodes de construction à définir, un autre problème d’optimisation (D),
qui sera appelé "dual" ou "adjoint" (ou encore autre appellation), possédant
les caractéristiques suivantes :
• (D) est a priori plus facile à traiter que le problème originel (P).
• La résolution de (D) (i.e. sa valeur optimale, ses solutions) aident à la
résolution de (P) (théoriquement comme numériquement).
• (Si possible) Il y a des règles de correspondance précises entre les
solutions (ou autres éléments d’intérêt comme les points critiques) de (P)
et de (D).
J.-B. Hiriart-Urruty, Bases, outils et principes pour l’analyse variationnelle,
117
Mathématiques et Applications 70, DOI: 10.1007/978-3-642-30735-5_5,
© Springer-Verlag Berlin Heidelberg 2013