Leonid Khatchian

Leonid Khachiyan
une illustration sous licence libre serait bienvenue
Biographie
Naissance
Décès
Voir et modifier les données sur Wikidata (à 52 ans)
New JerseyVoir et modifier les données sur Wikidata
Nom dans la langue maternelle
Լեոնիդ Գենրիխովիչ ԽաչիյանVoir et modifier les données sur Wikidata
Nationalité
Domicile
Formation
Faculté de gestion et de mathématique appliquée de l'institut de physique et de technologie de Moscou (d)Voir et modifier les données sur Wikidata
Activités
Enfant
Anna Khachiyan (en)Voir et modifier les données sur Wikidata
Autres informations
A travaillé pour
Distinctions
Œuvres principales

modifier - modifier le code - modifier WikidataDocumentation du modèle

Leonid Genrikhovitch Khatchian (né le à Saint-Pétersbourg – mort le à South Brunswick, New Jersey) est un mathématicien américain d’origine arménienne qui enseignait l’informatique à l’Université Rutgers. Il a acquis une célébrité mondiale en tant qu’inventeur de l’algorithme des ellipsoïdes (1979), qui bouleversa les conceptions en vigueur en optimisation linéaire, en montrant l’existence d'un algorithme à coût polynomial : depuis la fin des années 1940, le meilleur algorithme connu restait en effet l'algorithme du simplexe qui, quoique très efficace dans la plupart des cas, est à coût exponentiel. Malgré le caractère encore très théorique de l'invention de Khatchian (le coût en temps était un polynôme, certes, mais de degré élevé), ce fut une percée décisive qui a stimulé les recherches en optimisation convexe (algorithmes probabilistes).

Biographie

La famille de Khatchian avait emménagé à Moscou alors qu'il n'avait que 9 ans. Affecté au centre de calcul de l'Académie des Sciences de l'URSS, il soutint une première thèse de doctorat en Sciences numériques (1978) puis en informatique (1984). Dans son article Polynomial Algorithms in Linear Programming[1] (1980), il montra comment certains programmes linéaires, pour lesquels l'algorithme du simplexe est inefficace, peuvent être traités en construisant une suite d'ellipsoïdes inscrits au convexe associé au problème. Comme a pu l'écrire Michael D. Grigoriadis, professeur de l'université Rutgers, cette découverte a, à l'époque, bouleversé la discipline et même mérité l'attention du New York Times[2] : « Ce travail amenait une vision entièrement nouvelle, et permit de concevoir de nouveaux algorithmes destinés à résoudre des problèmes encore plus complexes. » La méthode des ellipsoïdes a été améliorée par d'autres chercheurs dans les années 1980, et a trouvé diverses applications, de la finance à la logistique en passant par l'industrie, pour l'optimisation d’itinéraires ou l'allocation optimale des ressources.

En 1982, l’American Mathematical Society lui décerna le prestigieux Prix Fulkerson pour ses recherches en mathématiques discrètes. Il enseigna encore à l'Institut de physique et de technologie de Moscou puis émigra aux États-Unis (1989), où le département de recherche opérationnelle et de génie industriel de l’Université Cornell l’avait accueilli comme visiting professor. Il fut recruté par l’Université Rutgers l’année suivante. Là, il poursuivit sur la lancée des idées qu'il avait agitées en Russie sur les convexes extrémaux et la complexité du calcul de l’ellipsoïde inscrit de volume maximum qui débouchèrent sur un article consacré à l’approche polyédrique. Avec Bahman Kalantari, il consacra une série d'articles à la mise à l'échelle des matrices et la répartition de charge en calcul parallèle. Il s’est aussi intéressé aux problèmes cycliques, qui interviennent en intelligence artificielle et en théorie des jeux.

Khatchian est mort d’une crise cardiaque[3] alors qu'il n'avait que 52 ans.

La méthode des ellipsoïdes

La méthode des ellipsoïdes est une technique itérative d'optimisation qui avait été imaginée par David Youdine, Arcadi Nemirovski et, indépendamment, Nahum Chor (1976–77) ; mais l'utilisation qu'en fit Khatchian pour résoudre les programmes linéaires est un véritable tour de force, car l'algorithme exigeait le calcul d'une estimation de la distance à l'optimum ; pour cela, Khatchian établit un certain nombre de majorations sur les volumes de polyèdres, et analysa la précision de calcul requise pour que la méthode soit praticable. Il publia ces résultats sans les démonstrations dans une note de quatre pages des Soviet Mathematics Doklady (). L'algorithme vint à la connaissance des chercheurs occidentaux lors d'une conférence au Symposium de programmation mathématique de Montréal, au mois d', puis grâce à un article de Peter Gács et Laci Lovász[4], qui évitait les changements continuels de systèmes de coordonnées familiers aux mathématiciens russes. Enfin, dans un article publié en 1980, Khatchian publia ses démonstrations[1].

Depuis son invention par George Dantzig en 1947, la méthode du simplexe avait disqualifié un certain nombre d'heuristiques antérieures pour résoudre les problèmes d'affectation sous contraintes linéaires, en particulier les itérations transposant le problème à une compétition entre deux joueurs. Tout au long des années 1950 et 1960, elle fut appliquée à des problèmes de taille de plus en plus grande jusqu'à ce qu'au début des années 1970, Victor Klee et George Minty (de) mettent en évidence l'existence de programmes pour lesquels l'algorithme de Dantzig conduit à examiner un nombre de pivots croissant exponentiellement avec la taille du problème[5].

Dans ce contexte, le résultat obtenu par Khatchian fit l'effet d'une bombe : au lieu de calculs de pivots et de circulation le long d'arêtes de polyèdres convergeant en un nombre fini d'étapes vers un optimum, il s'agissait à présent de partir d'une sphère dans laquelle on inscrivait des ellipsoïdes de volumes décroissants, le centre d'un ellipsoïde minimal donnant une approximation d'un optimum. Finalement, cet algorithme rappelait les algorithmes itératifs abandonnés dans les années 1950, à ceci près que la métrique changeait à chaque nouvel ellipsoïde.

Les problèmes d'optimisation représentaient un tel enjeu que la presse grand public signala cette trouvaille. Gene Lawler résume l'émoi suscité à l'époque dans un article intitulé « The Great Mathematical Sputnik of 1979[6]. »

Cependant, dans la communauté mathématique, plusieurs chercheurs essayaient, en vain, de se servir concrètement de la méthode de Khatchian ; mais il semblait que l'algorithme, quoique de coût polynomial, exigeait en pratique un nombre d'itérations toujours élevé, voisin de celui requis pour le pire des cas ; en outre, il menait à la résolution de systèmes linéaires mal conditionnés, ce à quoi Khatchian se consacra lui-même les années suivantes.

Mais l'engouement pour la méthode de Khatchian avait attiré l'attention sur la théorie de Youdine et Nemirovski, relative à la complexité des problèmes d'optimisation non-linéaire ; et quelques mathématiciens (Martin Grötschel, Laci Lovász et Lex Schrijver) réalisèrent alors que la méthode de l'ellipsoïde pouvait constituer un outil puissant en optimisation combinatoire.

Notes

  1. ↑ a et b L. G. Khatchian, « Polynomial algorithms in linear programming », USSR Computational Mathematics and Mathematical Physics, vol. 20, no 1,‎ , p. 53-72 (DOI 10.1016/0041-5553(80)90061-0)
  2. ↑ Cf. Malcolm W. Browne, « An Approach to Difficult Problems », New York Times,‎ (lire en ligne)
  3. ↑ D'après Jeremy Pearce, « Leonid Khachiyan Is Dead at 52; Advanced Computer Math », New York Times,‎ (lire en ligne).
  4. ↑ Cf. P. Gács et L. Lovász, « Khachiyan’s algorithm for linear programming », Math. Programming Studies, no 14,‎ , p. 61–68.
  5. ↑ Le problème du cube déformé de Klee-Minty a été publié dans Victor Klee, George J. Minty et Shisha Oved (dir.), Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, New York et Londres, Academic Press, , 159–175 p. (MR 332165), « How good is the simplex algorithm? »
  6. ↑ Cf. Eugene L. Lawler, « The Great Mathematical Sputnik of 1979 », The Sciences, vol. 20, no 7,‎ , p. 191-198 (DOI 10.1002/j.2326-1951.1980.tb01345.x, lire en ligne) .

Liens externes