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.

Sommaire

Formulation

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

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

  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

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

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”