Over relaxed hybrid proximal extragradient algorithm and its application to several operator splitting methods

In this paper we propose a new over-relaxed variant of the hybrid proximal extragradient (HPE) algorithm, for the monotone inclusion problem, which uses a projection-free extragradient step with explicit over relaxed stepsize. Its global convergence as well as ergodic and nonergodic complexity rates are established. Moreover, local linear convergence rates are derived under some mild regularity condition. One benefit of the new over relaxed variant of the HPE is that it covers a large class of popular operator splitting methods and their over relaxed versions, thus providing a comprehensive insight on these operators splitting methods. In particular, forward Douglas Rachford splitting method, forward Spingarn's Partial Inverse method, forward Spingarn's partial inverse forward method and Davis-Yin's three operator splitting method are all included as special cases of the over relaxed HPE algorithm. Another benefit is that the interval of stepsize relaxation is easily estimated for these operator splitting methods under the presented framework. Additionally, the over relaxed Korpelevich's method and over relaxed forward-backward-forward method are formulated directly with convergence guarantee based on the proposed framework. The third benefit is that the local linear convergence for a large class of operator splitting methods is established effortlessly under metric subregularity condition. Moreover, this linear convergence condition is shown weaker than some existing ones that almost all require the strong monotonicity of the composite operators.