Relaxation lagrangienne

Cet article ne cite pas suffisamment ses sources (novembre 2023).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

La relaxation lagrangienne est une technique de relaxation mathématique 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

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

max		${\displaystyle c^{T}x}$
s.c.
		${\displaystyle Ax\leqslant b}$

Si on sépare les contraintes de ${\displaystyle A}$ en ${\displaystyle A_{1}\in \mathbb {R} ^{m_{1},n}}$, ${\displaystyle A_{2}\in \mathbb {R} ^{m_{2},n}}$ avec ${\displaystyle m_{1}}$ et ${\displaystyle m_{2}}$ tels que ${\displaystyle m_{1}+m_{2}=m}$ on peut réécrire le système sous la forme :

max		${\displaystyle c^{T}x}$
s.c.
(1)		${\displaystyle A_{1}x\leqslant b_{1}}$
(2)		${\displaystyle A_{2}x\leqslant b_{2}}$

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

max		${\displaystyle c^{T}x+\lambda ^{T}(b_{2}-A_{2}x)}$
s.t.
(1)		${\displaystyle A_{1}x\leqslant b_{1}}$

Si ${\displaystyle \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.

Notes et références

• Portail de l'analyse