Improved algorithms for convex minimization in relative scale

Peter Richtárik*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


In this paper we propose two modifications to Nesterov's algorithms for minimizing convex functions in relative scale. The first is based on a bisection technique and leads to improved theoretical iteration complexity, and the second is a heuristic for avoiding restarting behavior. The fastest of our algorithms produces a solution within relative error O(1/k) of the optimum, with k being the iteration counter.

Original languageEnglish (US)
Pages (from-to)1141-1167
Number of pages27
JournalSIAM Journal on Optimization
Issue number3
StatePublished - 2011
Externally publishedYes


  • Convex optimization
  • Löwner-John ellipsoids
  • Nesterov's smoothing technique
  • Relative scale
  • Sublinearity

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science


Dive into the research topics of 'Improved algorithms for convex minimization in relative scale'. Together they form a unique fingerprint.

Cite this