User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Smooth minimization of non-smooth functions

Primary tabs

Nesterov, Yurii [UCL]

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.

Document type Article de périodique (Journal article)
Publication date 2005
Language Anglais
Journal information "Mathematical Programming" - Vol. 103, no. 1, p. 127-152 (Mai 2005)
Peer reviewed yes
Publisher Springer (Heidelberg, Germany)
issn 0025-5610
e-issn 1436-4646
Publication status Publié
Affiliation UCL - EUEN/CORE - Center for operations research and econometrics
Keywords Non-smooth optimization ; Convex optimization ; Optimal methods ; Complexity theory
Links
  1. Ben-Tal, A., Nemirovskii, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. (SIAM, Philadelphia, 2001)
  2. Bertsekas, D.P.: Constrained optimization and Lagrange multiplier methods. (Academic Press, New York, 1982)
  3. Goffin, J.-L.: On the convergence rate of subgradient optimization methods. Mathematical Programming 13, 329?347 (1977)
  4. Hiriart-Urruty, J.-B., Lemarechal, C.: Convex Analysis and Minimization Algorithms. (Springer-Verlag, 1993)
  5. Polyak, B.: On Bertsekas? method for minimization of composite function. In: Bensoussan, A., Lions, J.L. (eds) Inter. Symp. Systems Opt. 1979, Analysis Springer, pp. 179?186
  6. Polyak, R.: Nonlinear rescaling vs. smoothing technique in convex optimization. Mathematical Programming Ser. A 92, 197?235 (2002)
  7. Polyak, B.: Introduction to Optimization. (Optimization Software, Inc., Publications Division, New York, 1987)
  8. Nemirovsky, A., Yudin, D.: Informational Complexity and Efficient Methods for Solution of Convex Extremal Problems. (J. Wiley & Sons, New York, 1983)
  9. Nesterov, Yu.: A method for unconstrained convex minimization problem with the rate of convergence Doklady AN SSSR (translated as Soviet Math. Docl.) 269, 543?547 (1983)
  10. Nesterov, Yu.: Introductory Lectures on Convex Optimization: Basic course. (Kluwer, Boston, 2003)
  11. Shor, N.: Minimization Methods for Non-Differentiable Functions. (Springer-Verlag, Berlin, 1985)
Bibliographic reference Nesterov, Yurii. Smooth minimization of non-smooth functions. In: Mathematical Programming, Vol. 103, no. 1, p. 127-152 (Mai 2005)
Permanent URL http://hdl.handle.net/2078.1/23377