Improved algorithms for convex minimization in relative scale

Peter Richtarik

Research output: Contribution to journalArticlepeer-review


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
Pages (from-to)1141-1167
Number of pages27
JournalSiam journal on optimization
Issue number3
Publication statusPublished - 2011


  • convex optimization
  • relative scale
  • sublinearity
  • Nesterov's smoothing technique
  • Lowner-John ellipsoids
  • minimum volume enclosing ellipsoids


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

Cite this