Optimisation quadratique
- Optimisation quadratique
-
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
Soit . Il s'agit de minimiser une fonction objectif de la forme suivante :
sous les contraintes
Ce problème s'exprime sous forme matricielle :
sous les contraintes
avec
,
,
.
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
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
Note
- ↑ 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
Liens externes
- Operations Research Models and Methods (Paul A. Jensen and Jonathan F. Bard) [1]
- Une courte présentation du problème [2]
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Optimisation quadratique de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Optimisation (mathématiques) — L optimisation est une branche des mathématiques, cherchant à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à déterminer le meilleur élément d un ensemble, au sens d un critère quantitatif donné. Ce mot vient … Wikipédia en Français
Optimisation (mathematiques) — Optimisation (mathématiques) En mathématiques, l optimisation est l’étude des problèmes qui sont de la forme : Étant donné : une fonction d’un ensemble A dans l ensemble des nombre réels Rechercher : un élément x0 de A tel que pour … Wikipédia en Français
OPTIMISATION ET CONTRÔLE — L’avènement du calcul différentiel, au XVIIe siècle, a permis de caractériser le minimum d’une fonction f par l’équation f (x ) = 0. On résolvait ainsi d’un coup une foule de problèmes pratiques, tout en soulevant de grandes questions théoriques … Encyclopédie Universelle
Optimisation difficile — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation … Wikipédia en Français
Optimisation débit-distorsion — L optimisation débit distorsion ou RDO pour (en) Rate distortion optimization est une méthode utilisée dans la compression vidéo afin d augmenter la qualité de la vidéo. Le nom se réfère à un calcul d optimisation entre le niveau de distorsion… … Wikipédia en Français
Crible quadratique — L algorithme du crible quadratique est un algorithme de factorisation fondé sur l arithmétique modulaire. C est en pratique le plus rapide après le crible généralisé sur les corps de nombres, lequel est cependant bien plus compliqué, et n est… … Wikipédia en Français
Algorithme proximal (optimisation) — En analyse numérique et plus précisément en optimisation mathématique, l algorithme proximal (ou algorithme du point proximal) est un algorithme itératif de calcul d un minimum d une fonction convexe semi continue inférieurement propre. Si la… … Wikipédia en Français
Programmation quadratique — Les problèmes de programmation quadratique sont des problèmes d optimisation où la fonction objectif est quadratique et les contraintes sont linéaires. On inclut parfois le cas où les contraintes sont quadratiques. Formalisme Soit . Il s agit de… … Wikipédia en Français
Conditions d'optimalité (dimension finie) — En optimisation mathématique, les conditions d optimalité sont un ensemble d équations, d inéquations (i.e., des inégalités) et d expressions diverses (e.g., la semi définie positivité de matrices sur des cônes) vérifiées par une solution d un… … Wikipédia en Français
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français