Saut de dualité

Modèle:Ébauche En théorie de l'optimisation, le saut de dualité est la différence entre les solutions primale et duale.

Définitions

On considère un problème d'optimisation

$\inf f(\mathrm{x}),\mathrm{x}\in X\subseteq {ℝ}^n$

Si Modèle:Math est la valeur optimale duale et Modèle:Math la valeur optimale primale alors le saut de dualité vaut Modèle:Math. Cette valeur est toujours positive (pour les problèmes de minimisation) et s'annule si et seulement si la dualité forte est vérifiée, sinon on parle de dualité faible.

En général, pour deux paires d'espaces localement convexes séparés $(X,X^{*})$ et $(Y,Y^{*})$, en posant $f:X\to ℝ\cup \{+\mathrm{\infty }\}$, on peut écrire le problème primal comme

$\underset{\mathrm{x}\in X}{\inf }f(x).$

Pour un problème sous contraintes, on peut corriger Modèle:Mvar par Modèle:Math avec Modèle:Mvar est la fonction indicatrice de l'espace des contraintes. Soit alors $F:X\times Y\to ℝ\cup \{+\mathrm{\infty }\}$ une fonction de perturbation telle que $F(\mathrm{x},0)=f(\mathrm{x})$. Le saut de dualité est alors donné par

$\underset{\mathrm{x}\in X}{\inf }[F(\mathrm{x},0)]-\underset{{\mathrm{y}}^{*}\in Y^{*}}{\sup }[-F^{*}(0,{\mathrm{y}}^{*})]$

avec Modèle:Math la fonction conjuguée selon les deux variablesModèle:,Modèle:,.

En optimisation calculatoire, un autre "saut de dualité" est souvent évoqué, qui est la différence de valeurs entre toute solution duale et la valeur d'un itéré réalisable mais sous-optimal du problème primal. Ce "saut de dualité" quantifie la discrépance entre la valeur d'un itéré courant réalisable mais sous-optimal du problème primal et la valeur du problème dual ; cette dernière est, sous des conditions de régularité, égale à la valeur de la relaxation convexe du problème primal : la relaxation convexe est le problème apparaissant en remplaçant un ensemble non convexe réalisable avec son enveloppe convexe fermée et une fonction non convexe par sa fermeture convexe, soit la fonction dont l'épigraphe est l'enveloppe convexe fermée de la fonction objectif primale originaleModèle:,Modèle:,Modèle:,Modèle:,Modèle:,Modèle:,Modèle:,Modèle:,.

Exemples

Programmation linéaire sur espace non convexe

On considère le problème de minimisation

$\underset{(x,y,z)\in X}{\min }f(x,y,z)=10-3x-2y-z,X=\{(x,y,z)\in \{0;1{\}}^3,2x+3y+4z\le 4\}.$

Le maximum est atteint en Modèle:Math. Par la méthode de la relaxation lagrangienne, on définit le lagrangien

$L(x,y,z,\mu )=f(x,y,z)+\mu (2x+3y+4z-4)=10-4\mu +(-3+2\mu )x+(-2+3\mu )y+(-1+4\mu )z.$

à partir duquel on construit le problème dual

$\inf (10-4\mu +(-3+2\mu )x+(-2+3\mu )y+(-1+4\mu )z).$