Les premières formes de la dualité convexe
Extrait d'une note rédigée le 5 Mai 1998 au Courant Institute of Mathematical Sciences - New York University.
Théorème de séparation et principe minimax de Von Neumann
L'un des personnages clé de l'évolution que nous souhaitons décrire est John Von Neumann. Dans un article publié en 1937 [VN 1961], il sait voir dans les travaux de T. Bonnesen et W. Fenchel [BF 1934] de premiers résultats généraux de dualité convexe qu'il met en oeuvre pour une fonction jauge (dite de Minkowski): il introduit la fonction jauge "conjuguée" et obtient de manière très élégante une série d'inégalités sur l'espace des matrices hermitiennes.
Parallèlement Von Neumann s'intéresse à la théorie des jeux et propose avec O. Morgenstern en 1944 [VNM 1944] une approche "physico-géométrique" de la convexité: comme en physique où l'on étudie la dynamique du barycentre d'un solide (ou d'un ensemble de solides), il est pratique d'introduire en économie mathématique "la combinaison d'évènements incertains" comme le barycentre de ces évènements pondérés par leurs probabilités de réalisation. Dans ce contexte la dualité s'introduit également "naturellement" : elle devient un outil pour tester l'appartenance d'un évènement donné à un ensemble de combinaisons (convexes) d'évènements de référence. Les auteurs donnent alors un énoncé et une démonstration très clairs du théorème de séparation d'un point et d'un convexe fermé de RN [VNM 1944, p. 134] (généralisation proprement dite du lemme de Minkovski- Farkas qui se limite au cas où le convexe est polyédrique; ce cas particulier est appelé théorème d'alternative par Von Neumann).
Dans le même ouvrage, Von Neumann fait aussi le lien explicite entre la dualité convexe et l'existence d'un point selle d'une fonction bilinéaire définie sur un convexe de RN x RN . En utilisant le théorème du point fixe de Brouwer [VNM 1944, p.154]. La dualité va alors se faire connaître en économie mathématique sous le terme de "principe minimax de Von Neuman".
Dans les années 50, H. W. Kuhn et A. W. Tucker participent à la vulgarisation du principe minimax en éditant une série de quatre volumes consacrés à la théorie des jeux (1950-1959); la géométrie convexe y occupe une place importante. Dans le même temps ils mettent en évidence le lien entre la dualité minimax et la méthode de Lagrange utilisée en calcul des variations [KT 1951]. En 1956 ils éditent un recueil d'articles intitulé Linear Inequalities and Related Systems [KT 1956]; le volume présente les succès de la recherche opérationnelle et met en scène quelques grands noms de l'optimisation numérique. Entre autres, G. B. Dantzig y présente une version primale-duale du célèbre algorithme du simplexe et P. Wolfe étudie le saut de dualité d'un programme linéaire. Ky Fan participe également à l'ouvrage : il y présente plusieurs applications du théorème de séparation et en particulier un résultat de dualité sur le cône des matrices hermitiennes semidéfinies positives.
Quelques années plus tard, il ré-expose ce résultat avec R. Bellman dans [BF 1963] qui s'adresse à la communauté des automaticiens. Richard Bellman et Ky Fan y considèrent des inégalités affines d'un type particulier : les inégalités de Lyapunov. C'est véritablement la naissance de l'outil qui sera nommé "Linear Matrix Inequalities" (LMI) en automatique [BEFB1994] puis "Programmation Semidéfine" (Semidefinite Programming - SDP) par la communauté de l'optimisation numérique.
Dans le même temps les outils de l'analyse convexe continuent de se développer notamment avec les travaux de Terry Rockafellar [R1970] et dans la lignée de ces travaux l'optimisation, avec en particulier les travaux de Claude Lemaréchal et Jean-Baptiste Hiriart-Urruty [HUL1993] en retire de nouveaux "certificats de convergence numérique": on sépare des approximations du sous-différentiel de l'origine, on mesure la distance à une solution encore inconnue grâce à la dualité et on démontre la convergence globale des algorithmes d'optimisation convexe.
Pour renforcer ces certificats de convergence, D. Yudin et Arkadi Nemirovski vont produire en 1979 une théorie de la complexité en optimisation convexe. Ils montrent alors comment la convexité permet de quantifier l'effort de calcul à réaliser pour atteindre une précision souhaitée. Ils adaptent également les notions de polynomialité algorithmique à l'optimisation convexe et exposent l'algorithme de l’ellipsoïde: une méthode qui capture la solution dans un ellipsoïde dont le volume décroit à une vitesse géométrique. L'algorithme est utilisé par Khachian la même année pour démontrer la polynomialité de la programmation linéaire qui va alors donné l'impulsion aux méthodes de points intérieurs. Avec l'algorithme de Kamarkar (1984) apparaissent des fonctions convexes qui semblent particulièrement bien adaptées au schéma de Newton. Ce sont ce que Nesterov et Nemirovski [NN1994]vont appeler les fonctions auto-concordantes : des fonctions lisses pour lesquelles on peut donner une estimation a priori de la taille du bassin d'attraction de convergence quadratique de la méthode de Newton. Ils introduisent également une "fonction barrière universelle" d'un convexe fermé de RN d'intérieur non vide : une fonction auto-concordante qui mesure la distance entre un point intérieur et la frontière du convexe. La construction de cette fonction universelle repose encore une fois sur la dualité convexe (en particulier sur la fonction jauge de Minkowksi et le volume du polaire centré en un point intérieur). De telles fonctions admettent des formes explicitent simples pour les cônes les plus courants (orthant, cônes du second-ordre ou de Lorentz, cône des matrices semi-définies positives).
Références
[BEFB1994] Stephen Boyd, Laurent El Ghaoui, E. Feron, and V. Balakrishnan. Linear Matrix Inequalities in System and Control Theory. Volume 15 of Studies in Applied Mathematics Society for Industrial and Applied Mathematics (SIAM), 1994.
Klee (Ed.), Convexity, The Proceedings of Symposia in Pure Mathematics, Vol. 7, American
Mathematical Society, Providence, RI, 1963, pp. 1-11.
[BF1934] T. Bonnesen and W. Fenchel. Theorie der konvexen Körper. Springer, 1934.
[HUL1993] J.B. Hiriart-Urruty and C. Lemaréchal. Convex Analysis and Minimization Algorithms. Springer-Verlag, 1993. Two Volumes.
[KT1951] H. W. Kuhn, and A. W. Tucker. Nonlinear Programming. Proc. Second Berkeley Symp. on Math. Statist. and Prob. (Univ. of Calif. Press, 1951), 481-492.
[KT1956] H. W. Kuhn, and A. W. Tucker. Linear Inequalities and related systems. Princeton University Press, 1956.
[NN1994] Nesterov, A. Nemirovski. Interior-Point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics, 1994
[R1970] R. T. Rockafellar, Convex analysis, Princeton University Press, Princeton, NJ, 1970.
[VN1961] J. Von Neumann. Some matrix-inequalities and metrization of matrix-space. In A. H. Taub editor, Continous geometry and other topics (Collected works), volume IV, pages 205-219. Pergamon Press Ltd., 1961.
[VNM1944] J. Von Neumann and O. Morgenstern. Theory of games and economic behavior. John Wiley & Sons, 1964. Third Edition.
Comments