On the proximal point algorithms for solving the monotone inclusion problem

Abstract

We consider finding a zero point of the maximally monotone operator $T$. First, instead of using the proximal point algorithm (PPA) for this purpose, we employ PPA to solve its Yosida regularization $T_{\lambda }$. Then, based on an $O(a_{k+1})$ ($a_{k+1}\ge \epsilon >0$) resolvent index of $T$, it turns out that we can establish a convergence rate of $O(1/\sqrt{{\sum }_{i=0}^k{a}_{i+1}^2})$ for both the $\Vert T_{\lambda }(\cdot )\Vert$ and the gap function $\mathtt{Gap}(\cdot )$ in the non-ergodic sense, and $O(1/{\sum }_{i=0}^k{a}_{i+1})$ for $\mathtt{Gap}(\cdot )$ in the ergodic sense. Second, to enhance the convergence rate of the newly-proposed PPA, we introduce an accelerated variant called the Contracting PPA. By utilizing a resolvent index of $T$ bounded by $O(a_{k+1})$ ($a_{k+1}\ge \epsilon >0$), we establish a convergence rate of $O(1/{\sum }_{i=0}^k{a}_{i+1})$ for both $\Vert T_{\lambda }(\cdot )\Vert$ and $\mathtt{Gap}(\cdot )$, considering the non-ergodic sense. Third, to mitigate the limitation that the Contracting PPA lacks a convergence guarantee, we propose two additional versions of the algorithm. These novel approaches not only ensure guaranteed convergence but also provide sublinear and linear convergence rates for both $\Vert T_{\lambda }(\cdot )\Vert$ and $\mathtt{Gap}(\cdot )$, respectively, in the non-ergodic sense.