Improved algorithms for convex minimization in relative scale

Peter Richtarik

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume21
Issue number3
DOIs
Publication statusPublished - 2011

Keywords

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

Cite this