Complexity Bounds for Primal-dual Methods Minimizing the Model of Objective Function

Nesterov, Yurii
(2015) , 15 pages

Files

coredp2015_3web.pdf
  • Open Access
  • Adobe PDF
  • 2.22 MB
Download

Details

Authors
  • Nesterov, YuriiUCLouvain
    Author
Abstract
We provide Frank-Wolfe (≡ Conditional Gradients) method with a convergence analysis allowing to approach a primal-dual solution of convex optimization problem with composite objective function. Additional properties of complementary part of the objective (strong convexity) significantly accelerate the scheme. We also justify a new variant of this method, which can be seen as a trust-region scheme applying the linear model of objective function. Our analysis works also for a quadratic model, allowing to justify the global rate of convergence for a new second-order method. To the best of our knowledge, this is the first trust-region scheme supported by the worst-case complexity bound.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Nesterov, Y. (2015). Complexity Bounds for Primal-dual Methods Minimizing the Model of Objective Function (CORE Discussion Paper 2015/03). https://hdl.handle.net/2078.5/252108