Optimization Online


An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems

Yunlong He(heyunlong***at***gatech.edu)
Renato D.C. Monteiro(monteiro***at***isye.gatech.edu)

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 )


Download: [PDF]

Entry Submitted: 04/29/2014
Entry Accepted: 04/29/2014
Entry Last Modified: 04/29/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society