Optimisation quadratique

Modèle:Début d'illustration Modèle:Fin d'illustration

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'Modèle:Lien. 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

Un problème d'optimisation quadratique consiste à minimiser une fonction quadratique $q:{ℝ}^n\to ℝ$, non nécessairement convexe, sur un polyèdre convexe.

Critère à minimiser

La fonction Modèle:Mvar est définie en $x=(x_1,\dots ,x_n)\in {ℝ}^n$ par

$q(x)=g^{𝖳}x+\frac{1}{2}{x}^{𝖳}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 Modèle:Math, l'expression sous forme matricielle, $g\in {ℝ}^n$ est un vecteur et $H\in {ℝ}^{n\times n}$ est une matrice réelle symétrique (celle-ci est généralement supposée symétrique, car Modèle:Mvar ne voit pas la partie antisymétrique éventuelle de Modèle:Mvar). Il ne sert à rien de garder le terme constant dans Modèle:Mvar, car celui-ci n'affecte pas la solution du problème de minimisation.

Rappelons qu'une telle fonction quadratique Modèle:Mvar est

• convexe si, et seulement si, la matrice Modèle:Mvar est semi-définie positive,
• strictement convexe si, et seulement si, la matrice Modèle:Mvar est définie positive.

Contraintes

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

$\begin{array}{cc}{l}_B⩽x⩽u_B& \text{(contraintes de borne)}\\ l_I⩽A_{I}x⩽u_I& \text{(contraintes d'inégalité affines)}\\ A_{E}x=b_E& \text{(contraintes d'égalité affines),}\end{array}$

expressions dans lesquelles on a noté

• Modèle:Mvar et Modèle:Mvar des vecteurs de ${\overline{ℝ}}^n$ pouvant donc prendre des valeurs infinies et vérifiant Modèle:Math,
• $A_I\in {ℝ}^{m_I\times n}$ une matrice réelle de type Modèle:Math (Modèle:Mvar désigne le produit de la matrice Modèle:Mvar par le vecteur Modèle:Mvar),
• Modèle:Mvar et Modèle:Mvar des vecteurs de ${\overline{ℝ}}^{m_I}$ pouvant donc prendre des valeurs infinies et vérifiant Modèle:Math,
• $A_E\in {ℝ}^{m_E\times n}$ une matrice réelle de type Modèle:Math,
• $b_E\in {ℝ}^{m_E}$ un vecteur réel.

Il sera intéressant d'utiliser la notation compacte

$[l_B,u_B]:=\{x\in {ℝ}^n:l_B⩽x⩽u_B\}$

et une définition similaire pour Modèle:Math. On note Modèle:Mvar l'ensemble admissible défini par toutes les contraintes ci-dessus, à savoir

$X_Q:=\{x\in {ℝ}^n:x\in [l_B,u_B],A_{I}x\in [l_I,u_I],A_{E}x=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)\underset{x\in X_Q}{\inf }q(x).$

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

Analyse du problème

Existence de solution

Le résultat fondamental est dû à Frank et Wolfe (1956). 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 Modèle:Math),
• un problème d'optimisation réalisable est dit borné si sa valeur optimale ne vaut pas Modèle:Math (on ne peut pas trouver une suite de points admissibles faisant tendre le critère vers Modèle:Math).

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

Bornitude

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. On y a noté Modèle:Math le cône asymptotique de l'ensemble Modèle:Mvar.

Le cône asymptotique de l'ensemble admissible Modèle:Mvar défini ci-dessus (supposé non vide) s'écrit

$X_Q^{\mathrm{\infty }}=\{d\in {ℝ}^n:d\in [l_B,u_B{]}^{\mathrm{\infty }},A_{I}d\in [l_I,u_I{]}^{\mathrm{\infty }},A_{E}d=0\}.$

L'expression de Modèle:Math est donnée dans la page sur le cône asymptotique.

Méthodes de résolution

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 :

• Algorithme d'activation,
• Algorithme du gradient conjugué (des extensions),
• Algorithme du gradient projeté,
• Algorithme du lagrangien augmenté,
• Méthode de Nelder-Mead (des extensions).
• Algorithmes de points intérieurs (pour problème convexe).

Annexes

Articles connexes

• Conditions de Kuhn-Tucker
• Multiplicateur de Lagrange
• Optimisation linéaire

Lien externe

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

Bibliographie

• Modèle: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.
• Modèle: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]
• Modèle:En M. Frank, P. Wolfe (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3, 95–110.