Optimization Online


An accelerated non-Euclidean hybrid proximal extragradient-type Algorithm for convex-concave saddle-point Problems

Oliver Kolossoski(OliverKolossoski***at***gmail.com)
Renato Monteiro(renato.monteiro***at***isye.gatech.edu)

Abstract: This paper describes an accelerated HPE-type method based on general Bregman distances for solving monotone saddle-point (SP) problems. The algorithm is a special instance of a non-Euclidean hybrid proximal extragradient framework introduced by Svaiter and Solodov [28] where the prox sub-inclusions are solved using an accelerated gradient method. It generalizes the accelerated HPE algorithm presented in [13] in two ways, namely: a) it deals with general monotone SP problems instead of bilinear structured SPs; and b) it is based on general Bregman distances instead of the Euclidean one. Similar to the algorithm of [13], it has the advantage that it works for any constant choice of proximal stepsize. Moreover, a suitable choice of the stepsize yields a method with the best known iterationcomplexity for solving monotone SP problems. Computational results show that the new method is superior to Nesterovís smoothing scheme [23].

Keywords: convex programming, complexity, ergodic convergence, maximal monotone operator, hybrid proximal extragradient method, accelerated gradient method, inexact proximal method, saddle point problem, Bregman distances

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Submitted to Optimization Methods and Software, September 18th, 2015

Download: [PDF]

Entry Submitted: 09/18/2015
Entry Accepted: 09/18/2015
Entry Last Modified: 09/18/2015

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