Optimisation convexe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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-ardus (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.

Connaissances supposées : les bases de l'optimisation, les bases de l'analyse convexe, le calcul sous-différentiel.

Définitions du problème[modifier | modifier le code]

Formulation générale[modifier | modifier le code]

Soit \mathbb{E} un espace vectoriel. Un problème d'optimisation convexe consiste à minimiser une fonction convexe f:\mathbb{E}\to\bar{\R}:=\R\cup\{-\infty,+\infty\} sur \mathbb{E}, ce que l'on écrit d'une des manières suivantes :


\inf_{x\in\mathbb{E}}\,f(x)
\quad\mbox{ou}\quad
\inf\,\{f(x):x\in\mathbb{E}\}
\quad\mbox{ou}\quad
\inf\,f(\mathbb{E})
\quad\mbox{ou}\quad
\left\{\begin{array}{l}
\inf\,f(x)\\
x\in\mathbb{E}.
\end{array}\right.

Si on note


{\mathcal A}\equiv\operatorname{dom} f:=\{x\in\mathbb{E}:f(x)<+\infty\}

le domaine (effectif) de f, le problème est identique à celui de minimiser f sur {\mathcal A} :


\inf_{x\in{\mathcal A}}\,f(x).

Si {\mathcal A}=\varnothing, c'est-à-dire si f\equiv+\infty, cette expression est encore valable puisque, par convention, \inf f(\varnothing)=+\infty. L'intérêt d'avoir une fonction f pouvant prendre la valeur +\infty est donc d'introduire des contraintes dans le problème de minimisation (on oblige la solution du problème à être dans {\mathcal A}).

Solution[modifier | modifier le code]

Une solution (globale) du problème \inf\{f(x):x\in\mathbb{E}\} est un point \bar{x}\in\mathbb{E} tel que


\forall\,x\in\mathbb{E}:\quad
f(\bar{x})\leq f(x).

Clairement, si f prend la valeur -\infty, on a f(\bar{x})=-\infty ; et si f n'est pas identiquement égale à +\infty, on a f(\bar{x})<+\infty.

Si \mathbb{E} est un espace vectoriel topologique, \bar{x} est une solution locale du problème \inf\{f(x):x\in\mathbb{E}\} si


\exists\,V~\mbox{voisinage de}~\bar{x},\quad
\forall\,x\in V:\quad
f(\bar{x})\leq f(x).

En réalité une solution locale est une solution globale au sens précédent.

Solutions d'un problème d'optimisation convexe — 

  1. L'ensemble des solutions d'un problème d'optimisation convexe est convexe.
  2. Si f est strictement convexe, le problème d'optimisation convexe a au plus une solution.
  3. Si \mathbb{E} est un espace vectoriel topologique et si \bar{x} est une solution locale d'un problème d'optimisation convexe, alors \bar{x} est une solution globale du problème.

Contraintes fonctionnelles[modifier | modifier le code]

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


\left\{\begin{array}{l}
\inf\,f(x)\\
x\in C\\
Ax=b\\
c(x)\leqslant0,
\end{array}\right.

dans lequel on minimise une fonction f:x\in\mathbb{E}\mapsto f(x)\in\R à valeurs finies et l'inconnue x\in\mathbb{E} doit

  • appartenir à un ensemble convexe C de \mathbb{E},
  • vérifier une contrainte affine Ax=b (A:\mathbb{E}\to\mathbb{F} est une application linéaire entre \mathbb{E} et un autre espace vectoriel \mathbb{F} et b\in\mathbb{F}) et
  • vérifier un nombre fini de contraintes fonctionnelles convexes données par une fonction c:\mathbb{E}\to\R^m dont les m composantes sont convexes et l'inégalité vectorielle c(x)\leqslant0 doit se comprendre composante par composante (elle est équivalente aux m contraintes d'inégalité c_i(x)\leqslant0 pour i\in[\![1,m]\!]).

L'ensemble admissible de ce problème est convexe et s'écrit


X:=\{x\in\mathbb{E}:x\in C,~
Ax=b,~
c(x)\leqslant0\}.

Le problème est bien convexe puisqu'il s'agit de minimiser sur \mathbb{E} la fonction \tilde{f}:x\in\mathbb{E}\mapsto \tilde{f}(x)\in\bar{\R} définie par


\tilde{f}(x)=\left\{\begin{array}{ll}
f(x) & \mbox{si}~ x\in X\\
+\infty & \mbox{sinon},
\end{array}\right.

qui est une fonction convexe.

Conditions d'optimalité[modifier | modifier le code]

Condition générale[modifier | modifier le code]

La condition d'optimalité correspondant à la formulation générale du problème est le suivant. On note \partial f(x) le sous-différentiel de f en un point x tel que f(x)\in\R.

Condition d'optimalité générale — Si \bar{x}\in\mathbb{E} est tel que f(\bar{x})\in\R, alors \bar{x} est solution du problème convexe \inf\{f(x):x\in\mathbb{E}\} si, et seulement si, 0\in\partial f(\bar{x}).

Cas de contraintes fonctionnelles[modifier | modifier le code]

On s'intéresse ici à des conditions d'optimalité pour le problème exprimé au moyen de contraintes fonctionnelles.

Exemples de problèmes d'optimisation convexe[modifier | modifier le code]