Dualité (optimisation)

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[5].

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[6] - [7] - [8] - [9] - [10] - [11] - [12] - [13] - [14] - [15] - [16].

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é.

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

${\displaystyle {\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 ${\displaystyle {\mathcal {D}}\subset \mathbb {R} ^{n}}$ non vide, le lagrangien ${\displaystyle {\mathcal {L}}:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} }$ est défini par

${\displaystyle {\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 ${\displaystyle g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} }$ est définie par :

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

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

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

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

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

${\displaystyle {\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é ${\displaystyle \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[17].

Problème dual de Fenchel

Pour un problème de minimisation

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

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

${\displaystyle \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[18].

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.

• (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)

• 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