Journal
SIAM JOURNAL ON OPTIMIZATION
Volume 23, Issue 2, Pages 1092-1125Publisher
SIAM PUBLICATIONS
DOI: 10.1137/110833786
Keywords
complexity; extragradient; variational inequality; maximal monotone operator; proximal point; ergodic convergence; hybrid; convex programming; accelerated gradient; accelerated Newton
Categories
Funding
- NSF [CCF-0808863, CMMI-0900094, CMMI-1300221]
- ONR [ONR N00014-11-1-0062]
- CNPq [303583/2008-8, 302962/2011-5, 480101/2008-6, 474944/2010-7]
- FAPERJ [E-26/102.821/2008, E-26/102.940/2011]
- PRONEX-Optimization
- Directorate For Engineering
- Div Of Civil, Mechanical, & Manufact Inn [1300221] Funding Source: National Science Foundation
- Directorate For Engineering
- Div Of Civil, Mechanical, & Manufact Inn [0900094] Funding Source: National Science Foundation
Ask authors/readers for more resources
This paper presents an accelerated variant of the hybrid proximal extragradient (HPE) method for convex optimization, referred to as the accelerated HPE (A-HPE) framework. Iteration-complexity results are established for the A-HPE framework, as well as a special version of it, where a large stepsize condition is imposed. Two specific implementations of the A-HPE framework are described in the context of a structured convex optimization problem whose objective function consists of the sum of a smooth convex function and an extended real-valued nonsmooth convex function. In the first implementation, a generalization of a variant of Nesterov's method is obtained for the case where the smooth component of the objective function has Lipschitz continuous gradient. In the second implementation, an accelerated Newton proximal extragradient (A-NPE) method is obtained for the case where the smooth component of the objective function has Lipschitz continuous Hessian. It is shown that the A-NPE method has a O(1/k(7/2)) convergence rate, which improves upon the O(1/k(3)) convergence rate bound for another accelerated Newton-type method presented by Nesterov. Finally, while Nesterov's method is based on exact solutions of subproblems with cubic regularization terms, the A-NPE method is based on inexact solutions of subproblems with quadratic regularization terms and hence is potentially more tractable from a computational point of view.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available