  This paper investigates the optimal ergodic sublinear convergence rate of the
relaxed proximal point algorithm for solving monotone variational inequality
problems. The exact worst case convergence rate is computed using the
performance estimation framework. It is observed that, as the number of
iterations getting larger, this numerical rate asymptotically coincides with an
existing sublinear rate, whose optimality is unknown. This hints that, without
further assumptions, sublinear convergence rate is likely the best achievable
rate. A concrete example is constructed, which provides a lower bound for the
exact worst case convergence rate. Amazingly, this lower bound coincides with
the exact worst case bound computed via the performance estimation framework.
This observation motivates us to conjecture that the lower bound provided by
the example is exactly the worse case iteration bound, which is then verified
theoretically. We thus have established an ergodic sublinear convergence rate
that is optimal in terms of both the order of the sublinear rate and all the
constants involved.
