Optimisation convexe
L'optimisation convexe est une sous-discipline de l'optimisation mathĂ©matique, dans laquelle le critĂšre Ă minimiser est convexe et l'ensemble admissible est convexe. Ces problĂšmes sont plus simples Ă analyser et Ă rĂ©soudre que les problĂšmes d'optimisation non convexes, bien qu'ils puissent ĂȘtre NP-difficile (c'est le cas de l'optimisation copositive).
La théorie permettant d'analyser ces problÚmes ne requiert pas la différentiabilité des fonctions. Cette généralité est motivée par le fait que certaines méthodes de construction de problÚmes d'optimisation convexe conduisent à des problÚmes non différentiables (fonction marginale, dualisation de contraintes, etc). Si cette généralité est un atout, permettant de prendre en compte davantage de problÚmes, l'abord de la théorie est également plus difficile.
L'optimisation convexe repose sur l'analyse convexe.
Contexte et introduction
L'optimisation convexe est un type d'optimisation mathématique, c'est-à -dire une discipline qui étudie des problÚmes du type : optimiser une fonction donnée dans un espace donné. Elle généralise l'optimisation linéaire et l'optimisation semi-définie positive[1], mais aussi l'optimisation conique et l'optimisation copositive.
DĂ©finitions du problĂšme
Formulation générale
Soit un espace vectoriel. Un problĂšme d'optimisation convexe[1] consiste Ă minimiser une fonction convexe sur , ce que l'on Ă©crit d'une des maniĂšres suivantes :
Si on note
le domaine (effectif) de , le problĂšme est identique Ă celui de minimiser sur :
Si , c'est-Ă -dire si , cette expression est encore valable puisque, par convention, . L'intĂ©rĂȘt d'avoir une fonction pouvant prendre la valeur est donc d'introduire des contraintes dans le problĂšme de minimisation (on oblige la solution du problĂšme Ă ĂȘtre dans ).
Solution
Une solution (globale) du problĂšme est un point tel que
Clairement, si prend la valeur , on a ; et si n'est pas identiquement Ă©gale Ă , on a .
Si est un espace vectoriel topologique, est une solution locale du problĂšme si
En réalité une solution locale est une solution globale au sens précédent.
Solutions d'un problĂšme d'optimisation convexe â
- L'ensemble des solutions d'un problĂšme d'optimisation convexe est convexe.
- Si est strictement convexe, le problĂšme d'optimisation convexe a au plus une solution.
- Si est un espace vectoriel topologique et si est une solution locale d'un problĂšme d'optimisation convexe, alors est une solution globale du problĂšme.
Contraintes fonctionnelles
Au lieu de donner la valeur infinie au critÚre en dehors de l'ensemble admissible, on peut spécifier explicitement les contraintes à réaliser. Le problÚme s'écrit par exemple comme suit
dans lequel on minimise une fonction Ă valeurs finies et l'inconnue doit
- appartenir Ă un ensemble convexe de ,
- vérifier une contrainte affine ( est une application linéaire entre et un autre espace vectoriel et ) et
- vérifier un nombre fini de contraintes fonctionnelles convexes données par une fonction dont les composantes sont convexes et l'inégalité vectorielle doit se comprendre composante par composante (elle est équivalente aux contraintes d'inégalité pour ).
L'ensemble admissible de ce problĂšme est convexe et s'Ă©crit
Le problÚme est bien convexe puisqu'il s'agit de minimiser sur la fonction définie par
qui est une fonction convexe.
Conditions d'optimalité
Condition générale
La condition d'optimalité correspondant à la formulation générale du problÚme est la suivante. On note le sous-différentiel de en un point tel que .
Condition d'optimalitĂ© gĂ©nĂ©rale â Si est tel que , alors est solution du problĂšme convexe si, et seulement si, .
Cas de contraintes fonctionnelles
On s'intéresse ici à des conditions d'optimalité pour le problÚme exprimé au moyen de contraintes fonctionnelles.
Notes et références
- Stephen Boyd et Lieven Vandenberghe, Convex Optimization, Cambridge University Press, (lire en ligne).