Naissance de Leonid Khachiyan, mathématicien et numéricien d’origine arménienne

Leonid Genrikhovitch Khatchian 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).

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 (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 : 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.