What did Nemirovski and Yudin actually do in their 1978 article problem complexity and method efficiency in optimization?

Question

What did Nemirovski and Yudin actually do in their 1978 book problem complexity and method efficiency in optimization? I'm struggling to find very much on it.

Answer 1

The English translation of the book, Problem Complexity and Method Efficiency in Optimization, can be downloaded. The answer below was written before I was able to obtain a copy of the book.

---

I haven't seen the book itself, but a review of the English translation of the book (which was published in 1983) provides some information that is sufficient to tie this in with later work.

For the review, see:

Darzentas, J. Problem Complexity and Method Efficiency in Optimization. J Oper Res Soc 35, 455 (1984). https://doi.org/10.1057/jors.1984.92

Nemirovski and Yudin analyze the iteration complexity of optimization problems, particularly, the minimization of a convex objective function for which an oracle is available that can compute objective function and gradient values. The difference between the objective function value of the $k$th iterate and the optimal objective, $f(x^{k})-f(x^{*})$, is studied. A solution is $\epsilon$-approximate if $f(x^{k})-f(x^{*}) \leq \epsilon$.

For example, it can be shown that for a smooth convex objective function, any algorithm that uses only the objective function and gradient can at best attain $\epsilon=O(1/k^2)$, and that gradient descent is non-optimal because it attains only $\epsilon=O(1/k)$.

In a 1983 paper, Yuri Nesterov introduced an accelerated gradient method that improves on gradient descent and achieves the $O(1/k^{2})$ bound- that result apparently hadn't been obtained when the Nemirovski and Yudin book was published in 1978.

A more recent reference that discusses these kinds of results is Yuri Nesterov's Lectures on Convex Optimization, 2nd ed. Springer, 2018.