Optimisation quadratique

600px|Optimisation quadratique dans un espace à deux dimensions

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'. 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 , non nécessairement convexe, sur un polyèdre convexe.

Critère à minimiser

La fonction est définie en par

Dans la première expression de , 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 ne voit pas la partie antisymétrique éventuelle de ). Il ne sert à rien de garder le terme constant dans , car celui-ci n'affecte pas la solution du problème de minimisation.

Rappelons qu'une telle fonction quadratique est convexe si, et seulement si, la matrice est semi-définie positive, strictement convexe si, et seulement si, la matrice est définie positive.

Contraintes

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

expressions dans lesquelles on a noté et des vecteurs de pouvant donc prendre des valeurs infinies et vérifiant , une matrice réelle de type ( désigne le produit de la matrice par le vecteur ), et des vecteurs de pouvant donc prendre des valeurs infinies et vérifiant , une matrice réelle de type , un vecteur réel.

Il sera intéressant d'utiliser la notation compacte

et une définition similaire pour . On note 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 est convexe, ce qui est le cas si, et seulement si, est semi-définie positive.

Analyse du problème

Existence de solution

Le résultat fondamental est dû à Frank et Wolfe (1956Voir l'appendice (i) de l'article.). 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 ).

L'unicité de la solution aura certainement lieu si est strictement convexe, mais pourra se produire sans cela. C'est le cas par exemple pour le problème à une unique variable , 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ériqueVoir par exemple le lemme 2.2 dans l'article de Chiche et Gilbert (2014).. On y a noté le cône asymptotique de l'ensemble .

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

L'expression de 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é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., Méthode de Nelder-Mead (des extensions). Algorithmes de points intérieurs (pour problème convexe).

Annexes

Note

Optimisation quadratique

Źródło i licencja