Optimization Online


Improved algorithms for convex minimization in relative scale

Peter Richtarik(peter.richtarik***at***uclouvain.be)

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.

Keywords: convex optimization, relative scale, sublinearity, Nesterov's smoothing technique, Lowner-John ellipsoids

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 02/09/2009
Entry Accepted: 02/09/2009
Entry Last Modified: 02/09/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society