An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems
Abstract: This article proposes a new algorithm for solving a class of composite convex-concave saddle-point problems. The new algorithm is a special instance of the hybrid proximal extragradient framework in which a Nesterov's accelerated variant is used to approximately solve the prox subproblems. One of the advantages of the new method is that it works for any constant choice of proximal stepsize. Moreover, a suitable choice of the latter stepsize yields a method with the best known (accelerated inner) iteration complexity for the aforementioned class of saddle-point problems. In contrast to the smoothing technique, our accelerated method does not assume that feasible set is bounded due to its proximal point nature. Experiment results on three problem sets show that the new method significantly outperforms Nesterov's smoothing technique as well as a recently proposed accelerated primal-dual method.
Keywords: saddle-point problem, composite convex optimization, monotone inclusion problem, inexact proximal point method, hybrid proximal extragradient, accelerated method, complexity, smoothing.
Category 1: Convex and Nonsmooth Optimization (Convex Optimization )
Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )
Category 3: Convex and Nonsmooth Optimization (Generalized Convexity/Monoticity )
Entry Submitted: 04/29/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|