Leonid Khatchian

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 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 (février 1979). 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'août 1979, 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.

• DBLP: Bibliographie de Leonid Khatchian.
• (en) « Hommage à Leonid Khatchian », sur Département d'informatique de l'Université Rutgers, mai 2005.
• (en) « Leonid Khachiyan, 1952–2005: An Appreciation », sur SIAM news.
• « Leonid Khachiyan », sur The Mathematics Genealogy Project.

• Portail de l'informatique théorique