Abstract
In this paper, we propose and analyse an approximate variant of the level method of Lemaréchal, Nemirovskii and Nesterov for minimizing nonsmooth convex functions. The main per-iteration work of the level method is spent on (i) minimizing a piecewise-linear model of the objective function and (ii) projecting onto the intersection of the feasible region and a level set of the model function. We show that, by replacing exact computations in both cases by approximate computations, in relative scale, the theoretical iteration complexity increases only by a small factor which depends on the approximation level and reduces to one in the exact case.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Kelley, J.E.: The cutting plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8, 703–712 (1960)
Nesterov, Y.: Introductory Lectures on Convex Optimization. A Basic Course. Applied Optimization, vol. 87. Kluwer Academic, Boston (2004)
Lemaréchal, C.: Nonsmooth optimization and descent methods. IIASA Research Report 78-4 (1978)
Kiwiel, K.C.: An aggregate subgradient method for nonsmooth convex minimization. Math. Program. 27, 320–341 (1983)
Lemaréchal, C., Nemirovskii, A., Nesterov, Y.: New variants of bundle methods. Math. Program. 69(1), 111–147 (1995). doi:10.1007/BF01585555
Shor, N.Z.: Minimization Methods for Non-differentiable Functions. Springer Series in Computational Mathematics. Springer, Berlin (1985)
Polyak, B.T.: Minimization of unsmooth functionals. U.S.S.R. Comput. Math. Math. Phys. 9(3), 14–29 (1969)
Kim, S., Ahn, H., Cho, S.C.: Variable target value subgradient method. Math. Program. 49(1–3), 359–369 (1991). doi:10.1007/BF01588797
Kiwiel, K.C.: The efficiency of subgradient projection methods for convex optimization, part I: general level methods. SIAM J. Control Optim. 34, 660–676 (1996)
Kiwiel, K.C.: The efficiency of subgradient projection methods for convex optimization, part II: implementations and extensions. SIAM J. Control Optim. 34, 677–697 (1996)
Cegielski, A.: A method of projection onto an acute cone with level control in convex minimization. Math. Program. 85(3), 469–490 (1999)
Cegielski, A., Dylewski, R.: Residual selection in a projection method for convex minimization problems. Optimization 52, 211–220 (2003). doi: 10.1080/0233193031000079883
Nesterov, Y.: Unconstrained convex minimization in relative scale. CORE Discussion Paper #2003/96, November (2003)
Richtárik, P.: Improved algorithms for convex minimization in relative scale. Tech. rep. (2009)
Richtárik, P.: Simultaneously solving seven optimization problems in relative scale. Tech. rep. (2009)
Nesterov, Y., Nemirovski, A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics, vol. 13. SIAM, Philadelphia (1994)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Marcin Studniarski.
The research results presented in this paper have been supported by a grant “Action de recherche concertée ARC 04/09-315” from the “Direction de la recherche scientifique—Communauté française de Belgique”. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister’s Office, Science Policy Programming. The scientific responsibility is assumed by the author(s).
The author wishes to thank Yurii Nesterov for enlightening discussions and suggestions that greatly helped to improve the paper, and to Robert Chares and two anonymous referees for carefully reading the manuscript.
Rights and permissions
About this article
Cite this article
Richtárik, P. Approximate Level Method for Nonsmooth Convex Minimization. J Optim Theory Appl 152, 334–350 (2012). https://doi.org/10.1007/s10957-011-9908-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-011-9908-1