Unconstrained Convex Minimization in Relative Scale

Nesterov, Yurii
(2009) Mathematics of operations research — Vol. 34, n° 1, p. 180-193 (2009)

Files

pdfdocument.pdf
  • Restricted Access
  • Adobe PDF
  • 1001.21 KB
Request a copy

Details

Authors
  • Nesterov, YuriiUCLouvain
    Author
Abstract
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 · m1/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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Nesterov, Y. (2009). Unconstrained Convex Minimization in Relative Scale. Mathematics of operations research, 34(1), 180-193. https://doi.org/10.1287/moor.1080.0348 (Original work published 2009)