Leonid Khachiyan, 1952–2005: An Appreciation
December 1, 2005
Leonid Khachiyan
Astonishing Early ResultLeo was famous in the optimization community for his use of the ellipsoid algorithm to demonstrate that linear programming, in the Turing machine model, has a polynomial-time algorithm. For this work, he received the Fulkerson Prize of the American Mathematical Society and the Mathematical Programming Society.
This was an astonishing result, not only in settling a long-open problem in complexity, but also in introducing radically new viewpoints and techniques to linear programming. Whereas David Yudin and Arkadi Nemirovski, and independently Naum Shor, had developed the ellipsoid method for convex optimization (in 1976–77), Khachiyan used it in a tour-de-force to crack the complexity problem for linear programming. Because the algorithm was designed for the real-number model, and required an estimate of the distance to an optimal solution, Khachiyan had to establish a number of bounds on sizes of solutions, volumes of polyhedra, and the precision required to carry out the computations to achieve his goal.
The result was first published in a four-page note, without proofs, in Soviet Mathematics Doklady in February 1979. It was brought to the attention of Western researchers in a presentation at the Montreal Mathematical Programming Symposium in August 1979 and in a later publication by Peter Gács and Laci Lovász. To those not used to thinking from the varying-coordinate-systems viewpoint of Soviet researchers, the later presentation was far clearer than the original. In a 1980 paper in the journal USSR Computational Mathematics and Mathematical Physics, Khachiyan provided the proofs for the results in his earlier work.
In linear programming the simplex method, since its development in 1947 by George Dantzig, had sloughed off the challenge of a number of alternative algorithms, notably iterative methods based on fictitious play in two-person games, in the 1950s. Through the '50s and '60s, the simplex method was successfully applied to a wider range of problems of a vastly larger scale. Then, in the '70s, it ran into a theoretical no-man's-land with the new-found notion of polynomial-time algorithms and Victor Klee and George Minty's discovery of a class of problems for which Dantzig's pivot rule for the simplex method led to an exponential number of pivots. While subsequent versions remain highly competitive with the more recent interior-point methods and an indispensable part of the arsenal of any optimizer, exponential behavior is still encountered on some examples.
Leo's result was a bombshell in this environment. The use of the ellipsoid method, with its approximation of the polyhedral feasible region by ellipsoids, seemed counter to all we held dear: vertices, edges, phase 1–phase 2, and even finite convergence to an exact solution in exact arithmetic. Instead, we had to start with gigantic spheres, and then generate a sequence of shrinking ellipsoids until finding one sufficiently small that its center could be rounded to give an exact solution--assuming that all the data was rational. This was a pretty wild approach to a problem that we knew had a finite solution via pivoting; in fact, it bore some resemblance to the iterative methods tried in the '50s, but with a twist: The changing shapes of the ellipsoids gave a sort of variable-metric slant to the earlier relaxation methods.
Conveying the Significance of the New ResultIt was natural that such a result would get a huge amount of press. Linear programming was big business, and leading papers around the world tried to educate their readers to the significance of the result, with very spotty results. The late Gene Lawler captured the ensuing brouhaha in an article titled
"The Great Mathematical Sputnik of 1979."
The effect on the optimization community was more rational. Many people tried, and failed, to turn Leo's result into a practical method for the solution of large-scale linear programming problems. (Part of the problem lies in the fact that the algorithm seems to require in practice a number of iterations close to its worst-case bound; it al-so leads to very ill-conditioned linear systems.)
A lot of attention was directed to the amazing theory of Yudin and Nemirovski on the informational complexity of nonlinear programming. And a few people, notably Martin Grötschel, Laci Lovász, and Lex Schrijver, realized that the ellipsoid method could be a powerful tool in combinatorial optimization, thereby lending a (very) little credence to some of the outrageous claims that had been made in the popular press. (Just one example: The Guardian headlined its story "Soviet Answer to the ‘Traveling Salesmen.'" Of course, the ellipsoid method has not shed any light on the complexity of the Traveling Salesman Problem.) The ellipsoid method was also the first theoretically good algorithm for the burgeoning field of semidefinite programming.
Old and New Research ThemesSo Khachiyan became famous: But what of his other research and its significance? Interestingly, in his first work he had studied the convergence rate of iterative processes for solving matrix games, obtaining some negative results. After his linear programming paper, he extended the polynomial algorithm to convex quadratic programming with M.K. Kozlov and S.P. Tarasov, and then considered the size of solutions and the complexity of solving convex polynomial programming problems, in either continuous or integer variables. He wrote a lovely survey of results in this area for the Proceedings of the 1983 International Congress of Mathematicians.
Another beautiful result, with Tarasov and I.I. Erlikh, replaced the sequence of circumscribing ellipsoids in the usual ellipsoid method with a sequence of inscribed ellipsoids (each inscribed in the current localizing set). This method, in decreasing the complexity of approximately solving a convex minimization problem by a factor of n, the dimension of the problem, obtained the optimal (worst-case) complexity. The cost was the requirement at each iteration that an (approximately) largest-volume inscribed ellipsoid be found; the authors suggested doing this via the original ellipsoid method (but without further function oracle calls)! This paper also had a surprising geometric theorem concerning volumes of inscribed ellipsoids, which Leo later improved. This concern with volumes led to later work on the complexity of polytope volume computation and on the conductance of Markov chains (involving another neat geometric inequality) to bound the mixing time for randomized methods.
After moving to the States, Leo continued to explore some of his old themes, including his work on the complexity of maximal-volume ellipsoids inscribed in a polytope and his fascinating paper on rounding polytopes. He also added some new ones: He wrote a series of papers with Bahman Kalantari on various matrix scaling and balancing problems, and another series with Michael Grigoriadis on fast approximations of multicommodity flows, of matrix games in sublinear time, and of block angular convex programming problems, establishing a link to the work of Dantzig and Philip Wolfe on the decomposition principle. Indeed, one of Khachiyan and Grigoriadis's papers is titled "Coordination Complexity of Parallel Price-Directive Decomposition."
In 1996, Michael Fredman and Khachiyan established the surprising result that there is a quasi-polynomial-time algorithm for testing the duality of monotone disjunctive normal forms. This work had many applications and led to a number of papers, with Endre Boros, Vladimir Gurvich, Khachiyan's student Khaled Elbassioni, and others, on a variety of topics in combinatorics: hypergraphs, polymatroids, matroids, and enumeration of all minimal solutions of implicitly stated monotone systems, with numerous applications.
Finally, I want to mention his work with his student Lorant Porkolab. Porkolab and Khachiyan extended Leo's earlier work on convex polynomial programming to consider much more general formulae in the first-order theory of the reals and obtain related results. One consequence of their work is that testing the feasibility of an inequality-constrained semidefinite programming problem in real or integer matrices of fixed dimension can be performed in polynomial time.
Abundant Sharp WitSeveral of Leo's colleagues shared some impressions of him for this piece. Arkadi Nemirovski recalls Leo's nostalgia for Russia, unusual for a scientific emigré, and his very strongly expressed feelings on how the Bolsheviks almost destroyed it. He remembers Leo as "a very sensitive person . . . I remember his explanation why he does not like to visit New York--he said that people there are somehow afraid of each other and try to be at a distance from each other--a rare sensitivity for a Moscovite!"
Michael Grigoriadis writes that "Over [Leo's] 15 years at Rutgers, his office increasingly became the place where graduate students and colleagues went first with a broad range of technical questions. He was a respectful and careful listener, and one who invariably returned thoughtful suggestions. . . . Leo cared a lot about what students derived from his lectures and for this reason he prepared meticulously for each class; likewise, he invested substantial intellectual capital on his advisees. Our days at the office were often enlivened by his incisive humor, such as his observations on the similarity between what a Soviet party apparatchik may have declared versus self-aggrandizing statements by local politicians here. He was a greatly valued colleague and friend. We shall miss him."
These sentiments were reinforced by Vladimir Gurvich: "Leo was always interested to learn other people's problems, sometimes very far from his standard fields. Often, his first ideas were very strange . . . but then suddenly he jumped to a much higher level." For Khaled Elbassioni, Leo was "an ideal example of how a good adviser could be. . . . It was really great fun to work with him."
In conclusion, a couple of stories illustrate Leo's humor and sharp wit. Leo was very modest and kind to his friends, but he was also extremely cynical about politics and intolerant of condescension and pomposity. Because he had received the Young Investigators Award in Science and Technology, the Party Secretary at the Computing Center at the USSR Academy of Sciences indicated to him that it might be good for him to join the Party. Leo explained that he replied, with all innocence, "What party?" and added that he thought that was the right response.
Later, looking for a house to buy near Rutgers, he was being shown around by a real estate agent, who was obviously trying to empathize as much as possible. She pointed out that one house she showed him was close to the local synagogue, since she knew many Russian immigrants were Jewish; Leo said he wasn't Jewish. Somewhat flustered, she mentioned that there were many churches close by. Seeing his opening, Leo replied, "Actually, all I really believe in is the Communist Party." This caused some consternation, but finally the realtor saw a way to form a bond: "Well, they had some good ideas at the beginning."
Leonid Khachiyan was a great scholar and a much-loved father, husband, and friend. In the words of Arkadi Nemirovski, "All of us who knew Lenya loved him and are missing him."--Michael Todd, School of Operations Research, Cornell University.
Copyright © 2012, Society for Industrial and Applied Mathematics
3600 Market Street, 6th Floor | Philadelphia, PA 19104-2688 USA
Phone: +1-215-382-9800 | FAX: +1-215-386-7999
site map | privacy policy | webmaster@siam.org | suggestions
Banner art adapted from a figure by Hinke M. Osinga and Bernd Krauskopf (University of Bristol, UK).
No comments:
Post a Comment
Thank you