Relaxation lagrangienne

Relaxation lagrangienne

La relaxation lagrangienne est une technique de relaxation qui consiste à supprimer des contraintes difficiles en les intégrant dans la fonction objectif en la pénalisant si cette contrainte n'est pas respectée.

Description Mathématique

Étant donné un problème d'optimisation linéaire x\in \mathbb{R}^n et A\in \mathbb{R}^{m,n} sous la forme suivante :

max cTx
s.c.
Ax \leqslant b

Si on sépare les contraintes de A tel que A_1\in \mathbb{R}^{m_1,n}, A_2\in \mathbb{R}^{m_2,n} et m1 + m2 = m nous pouvons écrire le système comme:

max cTx
s.c.
(1) A_1 x \leqslant b_1
(2) A_2 x \leqslant b_2

Supposons que les contraintes (2) sont difficiles, nous les introduisons dans la fonction objectif:

max cTx + λT(b2 − A2x)
s.t.
(1) A_1 x \leqslant b_1

Si \lambda=(\lambda_1,\ldots,\lambda_{m_2}) sont des pénalités positives, nous sommes pénalisés si nous violons la contrainte (2), et d'un autre côté si nous voulons garder une fonction objectif linéaire nous voyons que nous sommes récompensés par le fait de suivre strictement la fonction objectif. Le système ci-dessus est appelé la relaxation lagrangienne du problème.

On va ensuite chercher à résoudre le dual de cette relaxation par différentes méthodes comme la méthode des faisceaux, la génération de colonnes et la plus utilisée : la descente de sous-gradient et ses variations.


Wikimedia Foundation. 2010.

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

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Relaxation — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Relaxation », sur le Wiktionnaire (dictionnaire universel) Le terme de relaxation peut renvoyer à… …   Wikipédia en Français

  • Technique de relaxation (Mathematique) — Technique de relaxation (Mathématique) Une technique de relaxation est une méthode en optimisation mathématique qui consiste à remplacer une contrainte stricte en contrainte moins stricte, voire à la supprimer. Les techniques de relaxation sont… …   Wikipédia en Français

  • Technique de relaxation (Mathématique) — Une technique de relaxation est une méthode en optimisation mathématique qui consiste à remplacer une contrainte stricte en contrainte moins stricte, voire à la supprimer. Les techniques de relaxation sont largement utilisées dans les méthodes de …   Wikipédia en Français

  • Technique de relaxation (mathématique) — Une technique de relaxation est une méthode en optimisation mathématique qui consiste à remplacer une contrainte stricte en contrainte moins stricte, voire à la supprimer. Les techniques de relaxation sont largement utilisées dans les méthodes de …   Wikipédia en Français

  • Technique de relaxation (mathématiques) —  Ne pas confondre avec les techniques de relaxation en psychologie. En mathématiques, une technique de relaxation est une méthode d optimisation qui consiste à remplacer une contrainte stricte en contrainte moins stricte, voire à la… …   Wikipédia en Français

  • Optimisation linéaire — En optimisation, qui est une branche des mathématiques, un problème d optimisation linéaire est un problème d optimisation dans lequel on minimise une fonction linéaire sur un polyèdre convexe. La fonction coût et les contraintes peuvent donc… …   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

  • 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

  • Branch and bound — Séparation et évaluation Un algorithme par séparation et évaluation, également appelé selon le terme anglo saxon branch and bound, est une méthode générique de résolution de problèmes d optimisation, et plus particulièrement d optimisation… …   Wikipédia en Français

  • Separation et evaluation — Séparation et évaluation Un algorithme par séparation et évaluation, également appelé selon le terme anglo saxon branch and bound, est une méthode générique de résolution de problèmes d optimisation, et plus particulièrement d optimisation… …   Wikipédia en Français

Share the article and excerpts

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