Dualité (optimisation)

En théorie de l'optimisation, la dualité ou principe de dualité désigne le principe selon lequel les problèmes d'optimisation peuvent être vus de deux perspectives, le problème primal ou le problème dual, et la solution du problème dual donne une borne inférieure à la solution du problème (de minimisation) primal. Cependant, en général les valeurs optimales des problèmes primal et dual ne sont pas forcément égales : cette différence est appelée saut de dualité. Pour les problèmes en optimisation convexe, ce saut est nul sous contraintes.

Problème dual

Le terme de problème dual renvoie généralement au problème dual de Lagrange mais d'autres existent – comme le problème dual de Wolfe ou de Fenchel. Le problème dual de Lagrange est obtenu en écrivant le Lagrangien d'un problème de minimisation avec des multiplicateurs de Lagrange positifs pour ajouter les contraintes à la fonction objectif puis en résolvant sur les variables primales qui minimisent la fonction objectif originale. Cette solution donne les variables primales comme fonctions des multiplicateurs de Lagrange, appelés variables duales, et le nouveau problème consiste à maximiser la fonction objectif sur les variables duales sous les contraintes dérivées sur ces variables duales (comptant au minimum les contraintes non négatives).

En général, avec deux paires d'espaces localement convexes séparés (X , X^*) et (Y , Y^*) et la fonction F : X → ℝ ∪ {+∞} , on peut définir le problème primal ainsi : déterminer ${\hat {x}}$ vérifiant $f({\hat {x}})=\inf _{x\in X}f(x).\,$ Ainsi, si ${\hat {x}}$ existe, $f({\hat {x}})$ est le minimum de la fonction f et l'infimum (plus grand minorant) de la fonction est atteint.

S'il y a des contraintes, on peut modifier la fonction objectif f en ${\tilde {f}}=f+I_{\mathrm {contraintes} }$ avec I_contraintes une fonction convenable sur X qui atteint son minimum, égal à 0, quand les contraintes sont satisfaites, ce qui permet de prouver que $\inf _{x\in X}{\tilde {f}}(x)=\inf _{x\ \mathrm {contraint} }f(x)$. Cette dernière condition est trivialement, mais pas toujours de façon idéale, satisfaite pour la fonction indicatrice (i.e. I_contraintes(x) = 0 avec x satisfaisant les contraintes et I_contraintes(x) = +∞ sinon). On étend alors ${\tilde {f}}$ en une fonction de perturbation F : X × Y → ℝ ∪ {+∞} telle que $F(x,0)={\tilde {f}}(x)$.

Le saut de dualité est la différence entre les deux terme de l'inégalité

$\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leq \inf _{x\in X}F(x,0),\,$

où F^* est le conjugué convexe sur les deux variables et sup désigne le supremum (plus petit majorant).

Saut de dualité

Le saut de dualité désigne la différence entre les valeurs prises par les problèmes primal et dual aux points solutions. Si d^* est la valeur optimale duale et p^* est la valeur primale optimale, le saut de dualité vaut p^* – d^*. Cette valeur est toujours positive ou nulle, et ne s'annule que si et seulement si les conditions de dualité forte sont vérifiées ; sinon, le saut est strictement positif et on parle de dualité faible.

En optimisation numérique, un autre saut de dualité est évoqué : la différence des valeurs entre une solution duale et la valeur d'une solution primale admissible mais sous-optimale. Ce saut alternatif quantifie la différence entre la valeur d'un itéré admissible mais sous-optimal pour le problème primal et la valeur du problème dual ; la valeur du problème dual est, sous conditions de régularité, égale à la valeur de relaxation convexe du problème primal : la relaxation convexe est le problème levé en remplaçant un ensemble admissible non convexe par son enveloppe convexe fermée et en remplaçant une fonction non convexe par sa fermeture convexe, ainsi la fonction a l'épigraphe qui est l'enveloppe convexe fermée de la fonction objectif primale d'origine.

Cas linéaire

Les problèmes d'optimisation linéaire sont des problèmes d'optimisation dans lesquels la fonction objectif et les contraintes sont toutes linéaires. Dans le problème primal, la fonction objectif est une combinaison linéaire de n variables. Il y a m contraintes, qui chacune place une majoration sur une combinaison linéaire des n variables. Le but est de maximiser la valeur de la fonction objectif soumise aux contraintes. Une solution sera alors un vecteur de n valeurs qui atteint le maximum possible pour la fonction objectif.

Dans le problème dual, la fonction objectif est une combinaison linéaire des m valeurs qui sont limites sur les m contraintes pour le problème primal. Il y a donc n contraintes duales, chacune plaçant une minoration sur une combinaison linéaire des m variables duales.

Relation entre les problèmes primal et dual

Dans le cas linéaire, pour le problème primal, pour chaque point sous-optimal satisfaisant toutes les contraintes, il y a une direction ou sous-espace de directions à déplacer qui augmente la valeur de la fonction objectif. Déplacer dans une de ces directions est supposé supprimer une erreur entre la solution candidate et une ou plusieurs contraintes. Une valeur non admissible de la solution candidate provoque un excès sur une ou plusieurs contraintes.

Dans le problème dual, le vecteur dual multiplie les contraintes qui déterminent les positions des contraintes dans le primal. Faire varier le vecteur dual dans le problème dual est équivalent à revoir les majorants du problème primal. Le plus petit majorant est recherché. Ainsi, le vecteur dual est minimisé de façon à diminuer la marge entre les positions candidates des contraintes et le véritable optimum. Une valeur non admissible du vecteur dual est une qui serait trop basse. Elle place les positions candidates d'une ou plusieurs contraintes dans une position qui exclut l'optimum recherché.

Cas non linéaire

En optimisation non linéaire, les contraintes ne sont pas nécessairement linéaires. Certaines idées directrices restent applicables.

Pour assurer que le maximum global d'un problème non linéaire soit facilement identifié, la formulation du problème demande souvent que les fonctions soient convexes et des ensembles faiblement compacts.

C'est ce qu'on retrouve à travers les conditions de Karush-Kuhn-Tucker. Elles donnent des conditions nécessaires pour identifier des optima locaux de problèmes d'optimisation non linéaire. Il y a des conditions supplémentaires (qualifications de contrainte) qui sont nécessaires de sorte qu'il sera possible de définir la direction vers une solution optimale. Cette solution optimale sera un optimum local, pas forcément global.

Principe de Lagrange fort : dualité de Lagrange

Soit un problème d'optimisation non linéaire dans sa forme standard

${\begin{aligned}{\text{minimiser }}&f(x)\\{\text{avec }}&g_{i}(x)\leq 0,\ i\in \left\{1,\dots ,m\right\}\\&h_{j}(x)=0,\ j\in \left\{1,\dots ,p\right\}\end{aligned}}$

dans le domaine ${\mathcal {D}}\subset \mathbb {R} ^{n}$ non vide, le lagrangien ${\mathcal {L}}:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ est défini par

${\mathcal {L}}(x,\lambda ,\nu )=f(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)+\sum _{j=1}^{p}\nu _{j}h_{j}(x).$

Les vecteurs λ et ν sont appelés variables duales ou vecteurs multiplicateurs de Lagrange associés au problème. La fonction duale de Lagrange $g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ est définie par :

$g(\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}{\mathcal {L}}(x,\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}\left(f(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)+\sum _{j=1}^{p}\nu _{j}h_{j}(x)\right).$

La fonction duale g est concave, même si le problème initial n'est pas convexe, car c'est l'infimum ponctuel de fonctions affines. La fonction duale a des bornes inférieures sur la valeur optimale p^* du problème initial ; pour tout λ ≥ 0 et tout ν, on a g(λ , ν) ≤ p^*.

Si une contrainte telle que la condition de Slater est vérifiée et que le problème original est convexe, on a alors une dualité forte :

$d^{*}=\max _{\lambda \geq 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}$.

Problèmes convexes

Pour un problème de minimisation convexe avec contraintes d'inégalité,

${\begin{aligned}&{\underset {x\in {\mathcal {D}}}{\min }}&&f(x)\\&\operatorname {avec} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\end{aligned}}$

on peut utiliser plusieurs versions du problème dual :

Problème dual de Lagrange

${\begin{aligned}&{\underset {\lambda \in \mathbb {R} ^{m}}{\sup }}&&\inf _{x}\left(f(x)+\sum _{j=1}^{m}\lambda _{j}g_{j}(x)\right)\\&\operatorname {avec} &&\lambda _{i}\geq 0,\quad i=1,\dots ,m\end{aligned}}$

où la fonction objectif est la fonction duale de Lagrange. Sachant que les fonctions f et g₁, ..., g_m sont continûment dérivables, l'infimum est le point où le gradient s'annule.

Problème dual de Wolfe

${\begin{aligned}&{\underset {x,\lambda }{\sup }}&&f(x)+\sum _{j=1}^{m}\lambda _{j}g_{j}(x)\\&\operatorname {avec} &&\nabla f(x)+\sum _{j=1}^{m}\lambda _{j}\nabla g_{j}(x)=0\\&&&\lambda _{i}\geq 0,\quad i=1,\dots ,m\end{aligned}}$

Ce problème peut être difficile à résoudre numériquement car la fonction objectif n'est pas concave en tout point (u,x). De même, la contrainte d'égalité $\nabla f(x)+\sum _{j=1}^{m}\lambda _{j}\nabla g_{j}(x)$ est non linéaire en général, ainsi le problème dual de Wolfe est typiquement un problème d'optimisation non convexe. Dans tous les cas, on a une dualité faible.

Problème dual de Fenchel

Pour un problème de minimisation

${\underset {x\in {\mathcal {D}}}{\inf }}\left(f(x)+\sum _{j=1}^{m}g_{j}(x)\right)$

le problème dual de Fenchel s'écrit :

${\underset {\phi \in X}{\sup }}\left(-f^{*}(\phi )-\sum _{j=1}^{m}g_{j}^{*}(-\phi )\right)\quad {\textrm {ou}}\quad -{\underset {\phi \in X}{\inf }}\left(f^{*}(\phi )+\sum _{j=1}^{m}g_{j}^{*}(-\phi )\right)$

où f ^* et les g*
j désignent les conjuguées de Fenchel-Legendre respectives de f et g_j :

$\forall \phi \in \mathbb {R} ^{n},\,f^{*}(\phi )=\sup _{x\in \mathbb {R} ^{n}}\left(\langle \phi ,x\rangle -f(x)\right).$

Cette approche est notamment utilisée dans les algorithmes de lissage pour le traitement du signal et le traitement d'image.

Dans la littérature, il en est régulièrement fait mention sous le nom de dualité de Fenchel-Rockafellar. Pour plus de détails, voir la page Wikipédia anglaise : Fenchel's duality theorem.

Histoire

Selon George Dantzig, le théorème de dualité pour l'optimisation linéaire a été conjecturé par John von Neumann immédiatement après que Dantzig a présenté les problèmes d'optimisation linéaire. Von Neumann note qu'il utilise l'information de sa théorie des jeux, et suppose qu'un jeu matriciel à deux personnes à somme nulle est équivalent à un problème d'optimisation linéaire. Des preuves rigoureuses ont d'abord été publiés en 1948 par Albert W. Tucker et son groupe (préambule de Dantzig à Nering et Tucker, 1993).

Voir aussi

• Dualité
• Relaxation lagrangienne

Notes

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Duality (optimization) » (voir la liste des auteurs).

Références

Ouvrages

• (en) Ahuja, Ravindra K.; Magnanti, Thomas L.; and Orlin, James B., Network Flows : Theory, Algorithms and Applications, Englewood Cliffs (N. J.), Prentice Hall, 1993, 846 p. (ISBN 0-13-617549-X)
• Dimitri Bertsekas, Angelia Nedic et Asuman Ozdaglar, Convex Analysis and Optimization, Athena Scientific, 2003 (ISBN 1-886529-45-0)
• (en) Dimitri P. Bertsekas, Nonlinear Programming, Belmont, Mass., Athena Scientific, 1999, 2nd éd., 777 p. (ISBN 1-886529-00-0)
• Dimitri P. Bertsekas, Convex Optimization Theory, Athena Scientific, 2009, 246 p. (ISBN 978-1-886529-31-1)
• J. Frédéric Bonnans, J. Charles Gilbert, Claude Lemaréchal et Claudia A. Sagastizábal, Numerical optimization: Theoretical and practical aspects, Berlin, Springer-Verlag, coll. « Universitext », 2006, xiv+490 (ISBN 3-540-35445-X, DOI 10.1007/978-3-540-35447-5, MR 2265882, lire en ligne)
• (en) William J. Cook, William H. Cunningham, William R. Pulleyblank et Alexander Schrijver, Combinatorial Optimization, New York/Chichester/Weinheim etc., John Wiley & Sons, 12 novembre 1997, 1st éd., 355 p. (ISBN 0-471-55894-X)
• George B. Dantzig, Linear Programming and Extensions, Princeton, NJ, Princeton University Press, 1963
• (en) Jean-Baptiste Hiriart-Urruty et Claude Lemaréchal, Convex analysis and minimization algorithms, Volume I: Fundamentals, vol. 305, Berlin, Springer-Verlag, coll. « Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] », 1993, xviii+417 (ISBN 3-540-56850-6, MR 1261420, lire en ligne)
• (en) Jean-Baptiste Hiriart-Urruty et Claude Lemaréchal, Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods, vol. 306, Berlin, Springer-Verlag, coll. « Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] », 1993, xviii+346 (ISBN 3-540-56852-2, MR 1295240, lire en ligne), « 14 Duality for Practitioners »
• Leon S. Lasdon, Optimization theory for large systems, Mineola, New York, Dover Publications, Inc., 2002 (1^re éd. Reprint of the 1970 Macmillan), xiii+523 (ISBN 978-0-486-41999-2, MR 1888251, lire en ligne)
• (en) Eugene Lawler, Combinatorial Optimization : Networks and Matroids, Mineola (N.Y.), Dover, 2001, 117–120 p. (ISBN 0-486-41453-1, lire en ligne), « 4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem »
• (en) Claude Lemaréchal, Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000, vol. 2241, Berlin, Springer-Verlag, coll. « Lecture Notes in Computer Science (LNCS) », 2001, 112–156 p. (ISBN 3-540-42877-1, DOI 10.1007/3-540-45586-8_4, MR 1900016), « Lagrangian relaxation »
• (en) Michel Minoux (Egon Balas (forward); Steven Vajda (trans) from the (1983 Paris: Dunod) French), Mathematical programming : Theory and algorithms, Chichester, A Wiley-Interscience Publication. John Wiley & Sons, Ltd., 1986, xxviii+489 (ISBN 0-471-90170-9, MR 868279)
• Evar D. Nering et Albert W. Tucker, Linear Programming and Related Problems, Boston, MA, Academic Press, 1993, 584 p. (ISBN 978-0-12-515440-6, lire en ligne)
• (en) Christos H. Papadimitriou et Kenneth Steiglitz, Combinatorial Optimization : Algorithms and Complexity, Mineola (N.Y.), Dover, juillet 1998, Unabridged éd., 496 p. (ISBN 0-486-40258-4, lire en ligne)
• Andrzej Ruszczyński, Nonlinear Optimization, Princeton, NJ, Princeton University Press, 2006, xii+454 (ISBN 978-0-691-11915-1, MR 2199043, lire en ligne)

Articles

• Hugh, III Everett, « Generalized Lagrange multiplier method for solving problems of optimum allocation of resources », Operations Research, vol. 11, n^o 3,‎ 1963, p. 399–417 (DOI 10.1287/opre.11.3.39, JSTOR 168028, MR 152360, lire en ligne [archive du 24 juillet 2011])
• Krzysztof C. Kiwiel, Torbjörn Larsson et P. O. Lindberg, « Lagrangian relaxation via ballstep subgradient methods », Mathematics of Operations Research, vol. 32, n^o 3,‎ août 2007, p. 669–686 (DOI 10.1287/moor.1070.0261, MR 2348241, lire en ligne)
• Duality in Linear Programming Gary D. Knott