Smooth minimization of non-smooth functions

In this paper we propose anew approach for constructing efficient schemes for non-smooth convex optimization. It is based on a special smoothing technique, which can be applied to 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 O (1/is an element of(2)) to O (1/is an element of), keeping basically the complexity of each iteration unchanged.