Leonid Khachiyan

Leonid Genrikhovitch Khatchian (né le 3 mai 1952 à Saint-Pétersbourg – mort le 29 avril 2005 à 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).