La programmation quadratique est une méthode utilisée pour optimiser une fonction quadratique multivariée qui peut ou non être contrainte linéairement. De nombreux problèmes du monde réel, tels que l’optimisation du portefeuille d’une entreprise ou la réduction des coûts d’un fabricant, peuvent être décrits à l’aide d’un programme quadratique. Si la fonction objectif est convexe, une solution réalisable peut exister et peut être résolue par des algorithmes connus tels que l’algorithme du simplexe étendu. Des méthodes existent pour résoudre certaines fonctions quadratiques non convexes, mais elles sont compliquées et difficilement disponibles.
Les techniques d’optimisation mathématique sont utilisées en programmation quadratique pour minimiser une fonction objectif. La fonction objectif est composée d’un certain nombre de variables de décision qui peuvent ou non être bornées. Les variables de décision ont des puissances 0, 1 ou 2. La fonction objectif peut être soumise à un certain nombre de contraintes d’égalité et d’inégalité linéaires concernant les variables de décision. Un exemple de programmation quadratique est : minimiser f(x,y) = x2 + 3y2 – 12y + 12 où x + y = 6 et x > 0 et y ≥ 0.
Il est souvent intéressant d’utiliser des fonctions quadratiques multivariées pour décrire des problèmes du monde réel. Par exemple, en utilisant la théorie moderne du portefeuille, un analyste financier essaiera d’optimiser le portefeuille d’une entreprise en choisissant la proportion d’actifs qui minimise le risque associé à un rendement attendu donné. Une équation quadratique composée des pondérations des actifs et de la corrélation entre les actifs décrit la variance du portefeuille qui peut être minimisée à l’aide de la programmation quadratique. Un autre exemple pourrait être un fabricant qui utilise une équation quadratique pour décrire la relation entre différents composants de qualité et le coût d’un produit. Le fabricant peut minimiser les coûts tout en maintenant certaines normes en ajoutant des contraintes linéaires au programme quadratique.
L’une des conditions les plus importantes pour résoudre un programme quadratique est la convexité de l’équation objective. La convexité d’une fonction quadratique est déterminée par la Hessienne ou la matrice de ses dérivées secondes. La fonction est dite convexe si la matrice hessienne est définie positive ou semi-définie positive, c’est-à-dire si toutes les valeurs propres sont respectivement positives ou non négatives. Si la Hessienne est positive et qu’une solution réalisable existe, alors ce minimum local est unique et est un minimum global. Si le Hessian est semi-positif, une solution réalisable peut ne pas être unique. Les fonctions quadratiques non convexes peuvent avoir des minimums locaux ou globaux, mais elles sont plus difficiles à déterminer.
Il existe de nombreuses approches pour résoudre une fonction quadratique convexe en utilisant la programmation quadratique. L’approche la plus courante est une expansion de l’algorithme du simplexe. Certaines autres méthodes incluent la méthode du point intérieur ou de la barrière, la méthode des ensembles actifs et la méthode du gradient conjugué. Ces méthodes sont intégrées dans certains programmes tels que Mathematica® et Matlab® et elles sont disponibles dans des bibliothèques pour de nombreux langages de programmation.