Qu'est-ce que la programmation quadratique?
La programmation quadratique
est une méthode utilisée pour optimiser une fonction quadratique multivariable qui peut ou non être linéairement limitée. De nombreux problèmes réels, 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 faisable peut exister et peut être résolue par des algorithmes connus tels que l'algorithme simplex élargi. Des méthodes existent pour résoudre certaines fonctions quadratiques non convexes, mais elles sont compliquées et pas facilement disponibles. Les techniques d'optimisation mathématique
sont utilisées dans la programmation quadratique pour minimiser une fonction objectif. La fonction objectif est composée d'un certain nombre de variables de décision qui peuvent être bordées ou non. Les variables de décision ont des pouvoirs 0, 1 ou 2. La fonction objectif peut être soumise à un certain nombre de contraintes linéaires d'égalité et d'inégalité concernant les variables de décision. Un exemple de programmation quadratique est:Minimiser f (x, y) = x
2 + 3y 2 - 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 les problèmes du monde réel. Par exemple, en utilisant la théorie du portefeuille moderne, un analyste financier tentera d'optimiser le portefeuille d'une entreprise en choisissant la proportion d'actifs qui minimisent le risque associé à un rendement attendu donné. Une équation quadratique composée de poids d'actifs et 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 les 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 importantesNS dans la résolution d'un programme quadratique est la convexité de l'équation objective. La convexité d'une fonction quadratique est déterminée par la Hesse ou la matrice de ses seconds dérivés. La fonction est appelée convexe si la matrice de Hesse est une semi-définie positive ou positive, c'est-à-dire si toutes les valeurs propres sont respectivement positives ou non négatives. Si le Hesse est positif et une solution réalisable existe, alors le minimum local est unique et est un minimum global. Si la Hesse est semi-positive, une solution réalisable peut ne pas être unique. Les fonctions quadratiques non convexes peuvent avoir des minimums locaux ou globaux, mais ils 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 simplex. Certaines autres méthodes incluent le point intérieur ou la méthode de barrière, la méthode de l'ensemble actif et la méthode du gradient de conjugué. Ces méthodes sont intégrées dans CERdes programmes Tain tels que Mathematica® et Matlab® et ils sont disponibles dans les bibliothèques pour de nombreux langages de programmation.