Aller au contenu

Dualité (optimisation)

Un article de Wikipédia, l'encyclopédie libre.

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

[modifier | modifier le code]

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 vérifiant Ainsi, si existe, 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 avec Icontraintes une fonction convenable sur X qui atteint son minimum, égal à 0, quand les contraintes sont satisfaites, ce qui permet de prouver que . Cette dernière condition est trivialement, mais pas toujours de façon idéale, satisfaite pour la fonction indicatrice (i.e. Icontraintes(x) = 0 avec x satisfaisant les contraintes et Icontraintes(x) = +∞ sinon). On étend alors en une fonction de perturbation F : X × Y → ℝ ∪ {+∞} telle que [2].

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

F* est le conjugué convexe sur les deux variables et sup désigne le supremum (plus petit majorant)[2],[3],[4].

Saut de dualité

[modifier | modifier le code]

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

Cas linéaire

[modifier | modifier le code]

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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

dans le domaine non vide, le lagrangien est défini par

Les vecteurs λ et ν sont appelés variables duales ou vecteurs multiplicateurs de Lagrange associés au problème. La fonction duale de Lagrange est définie par :

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 :

.

Problèmes convexes

[modifier | modifier le code]

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

on peut utiliser plusieurs versions du problème dual :

Problème dual de Lagrange

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

Problème dual de Wolfe

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

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

f * et les g*
j
désignent les conjuguées de Fenchel-Legendre respectives de f et gj :

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.

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

  1. (en) Stephen P. Boyd et Lieven Vandenberghe, Convex Optimization, Cambridge University Press, , 716 p. (ISBN 978-0-521-83378-3, lire en ligne [PDF]), p. 216
  2. a et b (en) Radu Ioan Boţ, Gert Wanka et Sorin-Mihai Grad, Duality in Vector Optimization, Springer, (ISBN 978-3-642-02885-4)
  3. (en) Ernö Robert Csetnek, Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators, Logos Verlag Berlin GmbH, , 110 p. (ISBN 978-3-8325-2503-3, lire en ligne)
  4. (en) Constantin Zălinescu, Convex analysis in general vector spaces, River Edge, NJ, World Scientific PublishingCo.,Inc., , 106–113 p. (ISBN 981-238-067-1, MR 1921556), « J »
  5. (en) Jonathan Borwein et Qiji Zhu, Techniques of Variational Analysis, Springer, , 362 p. (ISBN 978-1-4419-2026-3)
  6. (en) Ravindra K. Ahuja, Thomas L. Magnanti et James B. Orlin, Network Flows : Theory, Algorithms and Applications, Englewood Cliffs (N. J.), Prentice Hall, , 846 p. (ISBN 0-13-617549-X)
  7. (en) Dimitri Bertsekas, Angelia Nedic et Asuman Ozdaglar, Convex Analysis and Optimization, Athena Scientific, (ISBN 1-886529-45-0)
  8. (en) Dimitri P. Bertsekas, Nonlinear Programming, Belmont, Mass., Athena Scientific, , 777 p. (ISBN 1-886529-00-0)
  9. (en) Dimitri P. Bertsekas, Convex Optimization Theory, Athena Scientific, , 246 p. (ISBN 978-1-886529-31-1)
  10. Jean-Frédéric Bonnans, Jean-Charles Gilbert, Claude Lemaréchal et Claudia A. Sagastizábal, Optimisation Numérique : Aspects théoriques et pratiques, Berlin, Springer-Verlag, , xiv+490 (ISBN 978-3-540-63183-5, DOI 10.1007/978-3-540-35447-5, MR 2265882, lire en ligne)
  11. (en) Jean-Baptiste Hiriart-Urruty et Claude Lemaréchal, Convex Analysis and Minimization Algorithms I : Fundamentals, vol. 305, Berlin, Springer-Verlag, , xviii+417 (ISBN 3-540-56850-6, MR 1261420, lire en ligne)
  12. (en) Jean-Baptiste Hiriart-Urruty et Claude Lemaréchal, Convex Analysis and Minimization Algorithms II : Advanced Theory and Bundle Methods, vol. 306, Berlin, Springer-Verlag, , xviii+346 (ISBN 3-540-56852-2, MR 1295240, lire en ligne)
  13. Leon S. Lasdon, Optimization theory for large systems, Mineola, New York, Dover Publications, Inc., (1re éd. Reprint of the 1970 Macmillan), xiii+523 (ISBN 978-0-486-41999-2, MR 1888251, lire en ligne)
  14. (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) », , 112–156 p. (ISBN 3-540-42877-1, DOI 10.1007/3-540-45586-8_4, MR 1900016), « Lagrangian relaxation »
  15. (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., , xxviii+489 (ISBN 0-471-90170-9, MR 868279)
  16. Jeremy F. Shapiro, Mathematical programming : Structures and algorithms, New York, Wiley-Interscience John Wiley & Sons, , xvi+388 (ISBN 0-471-77886-9, MR 544669)
  17. Arthur M. Geoffrion, « Duality in Nonlinear Programming: A Simplified Applications-Oriented Development », SIAM Review, vol. 13, no 1,‎ , p. 1–37 (DOI 10.1137/1013001, JSTOR 2028848)
  18. (en) A. Chambolle et T. Pock., « A first-order primal-dual splitting algorithm for convex problems with applications to imaging », Journal of Mathematical Imaging and Vision, vol. 1, no 40,‎ , p. 120–145

Références

[modifier | modifier le code]