Optimisation quadratique

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

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 (OQ) est la discipline qui étudie ces problèmes. L'optimisation linéaire peut être vue comme un cas particulier de l'optimisation quadratique, obtenue lorsque les monômes de degré 2 du critère ont leurs coefficients nuls (une manière compliquée de dire que le critère est linéaire).

Ce problème d'apparence simple est pourtant NP-ardu lorsque la fonction à minimiser q n'est pas convexe. Lorsque le critère quadratique est convexe et que l'on minimise celui-ci, 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. 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 q:\R^n\to\R, non nécessairement convexe, sur un polyèdre convexe.

Le critère à minimiser

La fonction q est définie en x=(x_1,\ldots,x_n)\in\R^n par


q(x)
=g^{\!\top}x+\frac{1}{2}\, x^{\!\top}Hx
=\sum_{i=1}^{n}g_i x_i+\frac{1}{2}\,\sum_{i=1}^{n}\sum_{j=1}^{n}H_{ij}x_i x_j.

Dans la première expression de q(x), l'expression sous forme matricielle, g\in\R^n est un vecteur et H\in\R^{n\times n} 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

Les 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


\begin{array}{ll}
l_B\leqslant x\leqslant l_B & \mbox{(contraintes de borne)}\\
l_I\leqslant A_Ix\leqslant l_I & \mbox{(contraintes d'inégalité affines)}\\
A_Ex = b_E & \mbox{(contraintes d'égalité affines),}
\end{array}

expressions dans lesquelles on a noté

  • l_B et u_B des vecteurs de \bar{\R}^n pouvant donc prendre des valeurs infinies et vérifiant l_B<u_B,
  • A_I\in\R^{m_I\times n} une matrice réelle de type m_I\times n (A_Ix désigne le produit de la matrice A_I par le vecteur x),
  • l_I et u_I des vecteurs de \bar{\R}^{m_I} pouvant donc prendre des valeurs infinies et vérifiant l_I<u_I,
  • A_E\in\R^{m_E\times n} une matrice réelle de type m_E\times n,
  • b_E\in\R^{m_E} un vecteur réel.

Il sera intéressant d'utiliser la notation compacte


[l_B,u_B]:=\{x\in\R^n:l_B\leqslant x\leqslant l_B\}

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


X_Q:=\{x\in\R^n:x\in[l_B,u_B],~A_Ix\in[l_I,u_I],~A_Ex = b_E\}.

Formulation compacte

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


(P_Q)\quad
\inf_{x\in X_Q}\,q(x).

On dit que ce problème est convexe si le critère q est convexe.

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 +\infty),
  • un problème d'optimisation réalisable est dit borné si sa valeur optimale ne vaut pas -\infty (on ne peut pas trouver une suite de points admissibles faisant tendre le critère vers -\infty).

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\geqslant0\}, dont le critère est linéaire (donc pas strictement convexe).

Bornitude[modifier | modifier le code]

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^\infty 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 g^\top d<0, Hd=0 et d\in X^\infty.

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


X_Q^\infty=\{d\in\R^n:d\in[l_B,u_B]^\infty,~A_Id\in[l_I,u_I]^\infty,~A_Ed=0\}.

L'expression de [l,u]^\infty 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 :

Annexes[modifier | modifier le code]

Note[modifier | modifier le code]

  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]

Liens externes[modifier | modifier le code]

  • Operations Research Models and Methods (Paul A. Jensen and Jonathan F. Bard) [1]
  • Une courte présentation du problème [2]

Bibliographie[modifier | modifier le code]

  • (en) A. Chiche, J. Ch. Gilbert (2014). How the augmented Lagrangian algorithm deals with an infeasible convex quadratic optimization problem. Research Report 8583, INRIA, BP 105, 78153 Le Chesnay, France. [3]
  • (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. [4]
  • (en) M. Frank, P. Wolfe (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3, 95–110.