Aller au contenu

Optimisation quadratique

Un article de Wikipédia, l'encyclopédie libre.

Optimisation quadratique dans un espace à deux dimensions

Voir l’image vierge

Optimisation quadratique dans un espace à deux dimensions (x1, x2) contraint dans un polygone convexe.

  • Gauche : l'ensemble admissible E contient le minimum absolu.
  • Droite : l'ensemble admissible E ne contient pas le minimum absolu.
  • Haut : vue en perspective.
  • Bas : vue plane, la valeur de y étant représentée par des courbes de niveau.

En optimisation mathématique, un problème d'optimisation quadratique est un problème d'optimisation dans lequel on minimise (ou maximise) une fonction quadratique sur un polyèdre convexe. Les contraintes peuvent donc être décrites par des fonctions linéaires (on devrait dire affines). L'optimisation quadratique est la discipline qui étudie ces problèmes. L'optimisation linéaire peut être vue comme un cas particulier de l'optimisation quadratique.

Ce problème est NP-difficile dans le cas général. Dans le cas particulier de la minimisation d'une fonction objectif convexe, le problème est polynomial et on parle d'optimisation quadratique convexe ; une discipline déjà très riche aux propriétés mieux connues.

Lorsque le critère et les contraintes du problème d'optimisation sont quadratiques, on parle d'optimisation tout quadratique (en). Cette classe de problèmes contient toute l'optimisation polynomiale et est donc beaucoup plus générale que l'optimisation quadratique.

Formulation du problème

[modifier | modifier le code]

Un problème d'optimisation quadratique consiste à minimiser une fonction quadratique , non nécessairement convexe, sur un polyèdre convexe.

Critère à minimiser

La fonction q est définie en par

Dans la première expression de q(x), l'expression sous forme matricielle, est un vecteur et est une matrice réelle symétrique (celle-ci est généralement supposée symétrique, car q ne voit pas la partie antisymétrique éventuelle de H). Il ne sert à rien de garder le terme constant dans q, car celui-ci n'affecte pas la solution du problème de minimisation.

Rappelons qu'une telle fonction quadratique q est

Contraintes

On impose également au vecteur recherché x d'appartenir à un polyèdre convexe, ce qui revient à dire que x doit vérifier un nombre fini de contraintes affines. Celles-ci peuvent prendre des formes variées comme

expressions dans lesquelles on a noté

  • lB et uB des vecteurs de pouvant donc prendre des valeurs infinies et vérifiant lB < uB,
  • une matrice réelle de type mI × n (AIx désigne le produit de la matrice AI par le vecteur x),
  • lI et uI des vecteurs de pouvant donc prendre des valeurs infinies et vérifiant lI < uI,
  • une matrice réelle de type mE × n,
  • un vecteur réel.

Il sera intéressant d'utiliser la notation compacte

et une définition similaire pour [lI , uI]. On note XQ l'ensemble admissible défini par toutes les contraintes ci-dessus, à savoir

Formulation compacte

De manière compacte, on peut donc écrire le problème d'optimisation quadratique de la manière suivante

On dit que ce problème est convexe si le critère q est convexe, ce qui est le cas si, et seulement si, H est semi-définie positive.

Analyse du problème

[modifier | modifier le code]

Existence de solution

[modifier | modifier le code]

Le résultat fondamental est dû à Frank et Wolfe (1956[1]). Il est du même type que celui connu en optimisation linéaire. Rappelons que

  • un problème d'optimisation est dit réalisable si son ensemble admissible est non vide (ce qui revient à dire que sa valeur optimale ne vaut pas +∞),
  • un problème d'optimisation réalisable est dit borné si sa valeur optimale ne vaut pas –∞ (on ne peut pas trouver une suite de points admissibles faisant tendre le critère vers –∞).

Existence de solution — Pour un problème d'optimisation quadratique (non nécessairement convexe), les propriétés suivantes sont équivalentes :

  1. le problème a une solution,
  2. le problème est réalisable et borné,
  3. la valeur optimale du problème est finie.

L'unicité de la solution aura certainement lieu si q est strictement convexe, mais pourra se produire sans cela. C'est le cas par exemple pour le problème à une unique variable inf{x: x ≥ 0}, dont le critère est linéaire (donc pas strictement convexe).

Voici une caractérisation du caractère borné (ou non borné) d'un problème quadratique convexe réalisable (c'est-à-dire dont l'ensemble admissible est non vide) en termes d'existence d'une direction qui a des intérêts théorique et numérique[2]. On y a noté X le cône asymptotique de l'ensemble X.

Bornitude d'un problème quadratique convexe — Pour un problème d'optimisation quadratique convexe réalisable, dont l'ensemble admissible polyédrique est noté X, les propriétés suivantes sont équivalentes :

  1. le problème est non borné,
  2. il existe une direction d telle que , et .

Le cône asymptotique de l'ensemble admissible XQ défini ci-dessus (supposé non vide) s'écrit

L'expression de [l , u] est donnée dans la page sur le cône asymptotique.

Méthodes de résolution

[modifier | modifier le code]

S'il n'y a que des contraintes d'égalité, le problème revient à résoudre un système linéaire. En présence de contraintes d'inégalité, le problème en général est NP-ardu et peut être résolu par les approches suivantes :

  1. Voir l'appendice (i) de l'article.
  2. Voir par exemple le lemme 2.2 dans l'article de Chiche et Gilbert (2014).
  3. Beaucoup de contributions sur ce sujet. L'article de Delbos et Gilbert (2005) en analyse la convergence linéaire globale lorsque le problème a une solution; celui de Chiche et Gilbert (2014) en analyse le comportement lorsque le problème n'est pas réalisable.

Articles connexes

[modifier | modifier le code]

Lien externe

[modifier | modifier le code]
  • Operations Research Models and Methods (Paul A. Jensen and Jonathan F. Bard) [1]

Bibliographie

[modifier | modifier le code]
  • (en) A. Chiche, J. Ch. Gilbert (2016). How the augmented Lagrangian algorithm can deal with an infeasible convex quadratic optimization problem. Journal of Convex Analysis, 23:2, 425-459.
  • (en) F. Delbos, J. Ch. Gilbert (2005). Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems. Journal of Convex Analysis, 12, 45–69. [2]
  • (en) M. Frank, P. Wolfe (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3, 95–110.