Abstract / Description of output
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 language | English |
---|---|
Pages (from-to) | 1141-1167 |
Number of pages | 27 |
Journal | Siam journal on optimization |
Volume | 21 |
Issue number | 3 |
DOIs | |
Publication status | Published - 2011 |
Keywords / Materials (for Non-textual outputs)
- convex optimization
- relative scale
- sublinearity
- Nesterov's smoothing technique
- Lowner-John ellipsoids
- minimum volume enclosing ellipsoids