Barrier subgradient method

Nesterov, Yurii
(2011) Mathematical Programming — Vol. 127, n° 1, p. 31-56 (2011)

Files

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

Details

Authors
  • Nesterov, YuriiUCLouvain
    Author
Abstract
In this paper we develop a new affine-invariant primal–dual subgradient method for nonsmooth convex optimization problems. This scheme is based on a self-concordant barrier for the basic feasible set. It is suitable for finding approximate solutions with certain relative accuracy. We discuss some applications of this technique including fractional covering problem, maximal concurrent flow problem, semidefinite relaxations and nonlinear online optimization. For all these problems, the rate of convergence of our method does not depend on the problem’s data.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Nesterov, Y. (2011). Barrier subgradient method. Mathematical Programming, 127(1), 31-56. https://doi.org/10.1007/s10107-010-0421-3 (Original work published 2011)