Optimisation quadratique

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

En optimisation, qui est une branche des mathématiques, un problème d'optimisation quadratique est un problème d'optimisation dans lequel on minimise 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.

Formulation[modifier | modifier le code]

Soit x \in \mathbb{R}^{n}. Il s'agit de minimiser une fonction objectif de la forme suivante :


f(x_1,\ldots,x_n)=\frac{1}{2}\,\sum_{i=1}^{n}\sum_{j=1}^{n}H_{ij}x_i x_j +\sum_{j=1}^{n}g_j x_j,

sous les contraintes


\sum_{j=1}^{n}A_{ij}x_j-b_i\le 0 \qquad \forall i\in \{1,\ldots, m\}.

Ce problème s'exprime sous forme matricielle :

f(x) = \frac{1}{2}\, x^{\!\top}Hx + g^{\!\top}x

sous les contraintes


Ax \le b,

avec

x= [x_i]_{i = 1,\ldots, n\ },
H= [H_{ij}]_{i= 1,\ldots, n;j = 1,\ldots, n\ },
A= [A_{ij}]_{i = 1,\ldots, m;j = 1,\ldots, n}.

La matrice H est généralement supposée symétrique, car f ne voit pas la partie antisymétrique éventuelle de H. La fonction f est convexe si, et seulement si, la matrice H est semi-définie positive. La fonction f est strictement convexe si, et seulement si, la matrice H est définie positive ; dans ce cas, le problème a au plus une solution (et il en a une s'il existe un point admissible).

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

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]