N. Z. Shor is well known for his
method of
generalized gradient descent with
space dilation in the direction of the difference of two successive
subgradients (the so-called r-algorithm), that was created in collaboration with Nikolay G. Zhurbenko. The
ellipsoid method was re-invigorated by A.S. Nemirovsky and D.B. Yudin, who developed a careful
complexity analysis of its
approximation properties for problems of
convex minimization with real data. However, it was
Leonid Khachiyan who provided the rational-arithmetic complexity analysis, using an
ellipsoid algorithm, that established that
linear programming problems can be solved in polynomial time. It has long been known that the ellipsoidal methods are special cases of these subgradient-type methods. == R-algorithm ==