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  where the prox sub-inclusions are solved using an accelerated gradient method. It generalizes the accelerated HPE algorithm presented in  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 , 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 .
Submitted to Optimization Methods and Software, September 18th, 2015