Smooth minimization of non-smooth functions

In this paper we propose a new approach for constructing efficient schemes for nonsmooth convex optimization. It is based on a special smoothing technique, which can be applied to the functions with explicit max-structure. Our approach can be considered as an alternative to black-box minimization. From the viewpoint of efficiency estimates, we manage to improve the traditional bounds on the number of iterations of the gradient schemes from 0 (1/e2) to 0 (1/e), keeping basically the complexity of each iteration unchanged.