This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Nesterov, Y. Search for Related Content

Unconstrained Convex Minimization in Relative Scale

CORE, 1348 Louvain-la-Neuve, Belgium
yurii.nesterov{at}uclouvain.be, http://www.core.ucl.ac.be/nesterov/

In this paper, we present a new approach to constructing schemes for unconstrained convex minimization, which computes approximate solutions with a certain relative accuracy. This approach is based on a special conic model of the unconstrained minimization problem. Using a structural model of the objective function, we can employ the efficient smoothing technique. The fastest of our algorithms solves a linear programming problem with relative accuracy in at most e · m^1/2 (2 + ln m) · (1 + 1/) iterations of a gradient-type scheme, where m is the largest dimension of the problem and e is the Euler number.

Key Words: nonlinear optimization; convex optimization; complexity bounds; relative accuracy; fully polynomial approximation schemes; gradient methods; optimal methods
History: Received: January 27, 2006; revision received: May 31, 2007;