What did Nemirovski and Yudin actually do in their 1978 article problem complexity and method efficiency in optimization? 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.
 A: 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 Nemirovsky's 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, Nemirovksi introduced an accelerated gradient method that improves on gradient descent and achieves the $O(1/k^{2})$ bound- that result hadn't been obtained when the Nemirovski and Yudin book was published in 1978.  
It's not clear to me from the book review exactly what early results in this work were included in this book- Nemirovski has continued to work in this general area in the decades since.  
A more recent reference that discusses these kinds of results is Nemirovski's Lectures on Convex Optimization, 2nd ed. Springer, 2018.   
