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

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].

Citation

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

Article

Download

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