Approximate Level Method for Nonsmooth Convex Minimization

Peter Richtarik*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)334-350
Number of pages17
JournalJournal of Optimization Theory and Applications
Volume152
Issue number2
DOIs
StatePublished - Feb 1 2012

Keywords

  • Approximate projections in relative scale
  • Large-scale optimization
  • Level method
  • Nonsmooth convex minimization
  • Sensitivity analysis

ASJC Scopus subject areas

  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Approximate Level Method for Nonsmooth Convex Minimization'. Together they form a unique fingerprint.

Cite this