Optimisation convexe

sous-discipline de l'optimisation mathématique

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).

Optimisation convexe dans un espace en deux dimensions dans un espace contraint

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

modifier

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

modifier

Formulation générale

modifier

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

modifier

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 — 

  1. L'ensemble des solutions d'un problème d'optimisation convexe est convexe.
  2. Si   est strictement convexe, le problème d'optimisation convexe a au plus une solution.
  3. 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

modifier

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é

modifier

Condition générale

modifier

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

modifier

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

Notes et références

modifier
  1. a et b Stephen Boyd et Lieven Vandenberghe, Convex Optimization, Cambridge University Press, (lire en ligne).