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.

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.

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

Si on note

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

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

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

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

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

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

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 ${\displaystyle f:x\in \mathbb {E} \mapsto f(x)\in \mathbb {R} }$ à valeurs finies et l'inconnue ${\displaystyle x\in \mathbb {E} }$ doit

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

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 ${\displaystyle \mathbb {E} }$ la fonction ${\displaystyle {\tilde {f}}:x\in \mathbb {E} \mapsto {\tilde {f}}(x)\in {\bar {\mathbb {R} }}}$ définie par

qui est une fonction convexe.

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

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

v · m Optimisation: théorie et algorithmes
Non linéaire	Méthode du nombre d'or Recherche linéaire Méthode de Nelder-Mead Critères de Wolfe Méthode de Broyden-Fletcher-Goldfarb-Shanno Algorithme à régions de confiance Pénalisation Algorithme du gradient Algorithme du gradient stochastique Méthode de Newton Algorithme de Gauss-Newton Algorithme de Levenberg-Marquardt Algorithme du lagrangien augmenté
Convexe	Optimisation complètement positive Optimisation copositive Optimisation SDP Méthode des plans sécants Algorithme de Frank-Wolfe Méthode de l'ellipsoïde Linéaire Optimisation conique Algorithme du simplexe Méthodes de points intérieurs Décomposition de Benders Génération de colonnes Quadratique Optimisation quadratique successive
Combinatoire	Algorithme d'approximation Programmation dynamique Algorithme glouton Optimisation linéaire en nombres entiers
Métaheuristique	Stratégie d'évolution Algorithme génétique Essaims Forêts aléatoires Boosting

• Portail des mathématiques
• Portail de l'informatique théorique