User menu

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

Universal gradient methods for convex optimization problems

Primary tabs

Nesterov, Yurii [UCL]

In this paper, we present new methods for black-box convex minimization. They do not need to know in advance the actual level of smoothness of the objective function. The only essential input parameter is the required accuracy of the solution. At the same time, for each particular problem class they automatically ensure the best possible rate of convergence. We confirm our theoretical results by encouraging numerical experiments, which demonstrate that the fast rate of convergence, typical for the smooth optimization problems, sometimes can be achieved even on nonsmooth problem instances.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès interdit
Publication date 2015
Language Anglais
Journal information "Mathematical Programming" - Vol. 152, p. 381–404 (2015)
Peer reviewed yes
Publisher Springer (Berlin Heidelberg)
issn 0025-5610
e-issn 1436-4646
Publication status Publié
Affiliations UCL - SSH/LIDAM/CORE - Center for operations research and econometrics
UCL - SST/ICTM/INMA - Pôle en ingénierie mathématique
Keywords convex optimization ; black-box methods ; complexity bounds ; optimal methods ; weakly smooth functions
Links
  1. Babonneau Frédéric, Nesterov Yurii, Vial Jean-Philippe, Design and Operations of Gas Transmission Networks, 10.1287/opre.1110.1001
  2. Beck Amir, Teboulle Marc, A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems, 10.1137/080716542
  3. Devolder Olivier, Glineur François, Nesterov Yurii, First-order methods of smooth convex optimization with inexact oracle, 10.1007/s10107-013-0677-5
  4. Elster, K.-H. (ed.): Modern Mathematical Methods in Optimization. Academie Verlag, Berlin (1993)
  5. Lan Guanghui, Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization, 10.1007/s10107-013-0737-x
  6. Lemaréchal Claude, Nemirovskii Arkadii, Nesterov Yurii, New variants of bundle methods, 10.1007/bf01585555
  7. Nemirovskii, A., Nesterov, Yu.: Optimal methods for smooth convex optimization. Zh. Vychisl. Mat. i Mat. Fiz. 25(3), 356–369 (1985). in Russian
  8. Nemirovsky, A., Yudin, D.: Problem Complexity and Method Efficiency in Optimization. Wiley, New York (1983)
  9. Nesterov Yurii, Introductory Lectures on Convex Optimization, ISBN:9781461346913, 10.1007/978-1-4419-8853-9
  10. Nesterov Yu., Smooth minimization of non-smooth functions, 10.1007/s10107-004-0552-5
  11. Nesterov Yu., Gradient methods for minimizing composite functions, 10.1007/s10107-012-0629-5
  12. Nesterov Yurii, Primal-dual subgradient methods for convex problems, 10.1007/s10107-007-0149-x
Bibliographic reference Nesterov, Yurii. Universal gradient methods for convex optimization problems. In: Mathematical Programming, Vol. 152, p. 381–404 (2015)
Permanent URL http://hdl.handle.net/2078.1/131514