On the convergence rate of the scaled proximal decomposition on the graph of a maximal monotone operator (SPDG) algorithm

Abstract

Relying on fixed point techniques, Mahey, Oualibouch and Tao introduced in a 1995 paper the scaled proximal decomposition on the graph of a maximal monotone operator (SPDG) algorithm and analysed its performance on inclusions for strongly monotone and Lipschitz continuous operators. The SPDG algorithm generalizes the Spingarn’s partial inverse method by allowing scaling factors, a key strategy to speed up the convergence of numerical algorithms. In this note, we show that the SPDG algorithm can alternatively be analysed by means of the original Spingarn’s partial inverse framework, tracing back to the 1983 Spingarn’s paper. We simply show that under the assumptions considered in by Mahey, Oualibouch and Tao, the Spingarn’s partial inverse of the underlying maximal monotone operator is strongly monotone, which allows one to employ recent results on the convergence and iteration-complexity of proximal point-type methods for strongly monotone operators. By doing this, we additionally obtain a potentially faster convergence for the SPDG algorithm and a more accurate upper bound on the number of iterations needed to achieve prescribed tolerances, specially on ill-conditioned problems.

Keywords:

• SPDG algorithm
• partial inverse method
• strongly monotone operator
• rate of convergence
• complexity

Acknowledgements

We are thankful to the two anonymous referees for their constructive suggestions which have improved the first version of this paper and for bringing to our attention the references [10,11,29,30].

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

The work of this first author was partially supported by CNPq [grant number 406250/2013-8], [grant number 306317/2014-1], [grant number 405214/2016-2]. The work of this second author was partially supported by CAPES [Scholarship number 201302180].