Smooth minimization of nonsmooth functions：（光滑的非光滑函数的最小化）.pdfVIP

Smooth minimization of non-smooth functions Yu. Nesterov January 10, 2003 CORE, Catholic University of Louvain, 34 voie du Roman Pays, 1348 Louvain-la-Neuve, Belgium; e-mail: nesterov@core.ucl.ac.be 1 Abstract In this paper we propose a new approach for constructing efficient schemes for non- smooth 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 gra- dient schemes from 1 to 1 , keeping basically the complexity of each iteration 2 unchanged. Keywords: Non-smooth optimization, convex optimization, optimal methods, complex- ity theory, structural optimization. 2 1 Introduction Motivation. Historically, the subgradient methods were the first numerical schemes for non-smooth convex minimization (see [10] and [6] for historical comments). Very soon it was proved that the efficiency estimate of these schemes is of the order 1 (1.1) 2 where is the desired accuracy of the approximate solution (see also [3]). Up to now some variants of these methods remain attractive for the researchers (e.g. [4, 1]). This is not too surprising since the main drawback of these schemes, the slow rate of convergence, is compensated by t