Relaxation lagrangienne

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 ces contraintes ne sont pas respectées.

Description mathématique[modifier | modifier le code]

É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 c^T x
s.c.
Ax \leqslant b

Si on sépare les contraintes de A en A_1\in \mathbb{R}^{m_1,n}, A_2\in \mathbb{R}^{m_2,n} avec m_1 et m_2 tels que m_1+m_2=m on peut réécrire le système sous la forme :

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

Supposons que les contraintes (2) soient difficiles, on les introduit dans la fonction objectif:

max c^T x+\lambda^T(b_2-A_2x)
s.t.
(1) A_1 x \leqslant b_1

Si \lambda=(\lambda_1,\ldots,\lambda_{m_2}) sont des pénalités positives, on est pénalisé si la contrainte (2) est violée. D'un autre côté, si on veut garder une fonction objectif linéaire, on est récompensé si on suit strictement la fonction objectif. Le système ci-dessus est appelé la relaxation lagrangienne du problème.

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