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 $x \in \mathbb{R}^{n}$ . Il s'agit de minimiser une fonction objectif de la forme suivante:

$f(x_1,\cdots,x_n)=\sum_{i=1}^{n}\sum_{j=1}^{n}q_{ij}x_i x_j +\sum_{j=1}^{n}c_j x_j$

sous les contraintes:

$g_i(\mathbf{x})=\sum_{j=1}^{n}a_{ij}x_j-b_i\le 0 \qquad i\in 1,\ldots, m$

Ce problème s'exprime sous forme matricielle:

$f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T Q\mathbf{x} + \mathbf{c}^T \mathbf{x}$

$g_i(\mathbf{x})= A\mathbf{x} \le b \qquad i\in 1,\ldots, m$

Q est une matrice symétrique. Dans le cas où elle est semi-définie positive, la fonction $f$ est convexe et le problème a au moins une solution (s'il existe un point satisfaisant les contraintes). Si Q est définie positive, $f$ est strictement convexe et il existe une unique solution.

voir aussi

liens externes

Operations Research Models and Methods (Paul A. Jensen and Jonathan F. Bard) [1]
Une courte présentation du problème [2]

Portail des mathématiques

Ce document provient de « Programmation quadratique ».

Catégorie : Optimisation

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Programmation quadratique de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

Programmation mathématique — 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
Programmation non linéaire — 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
Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants … Wikipédia en Français
Minimisation — 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
Minimisation d'une fonction — 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
Minimum d'une fonction — 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 (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
Liste De Problèmes NP-Complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive … Wikipédia en Français
Liste de problemes NP-complets — Liste de problèmes NP complets Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets,… … Wikipédia en Français
Liste de problèmes np-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Programmation quadratique