| This thesis investigates the optimal sublinear convergence rate of the relaxed prox-imal 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 asymp-totically 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.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 a sublinear convergence rate that is optimal in terms of both the order of the sublinear rate and all the constants involved. |
