Abstract:

A unified efficient algorithm framework of proximal-based decomposition methods has been proposed for monotone variational inequalities in 2012, while only global convergence is proved at the same time. In this paper, we give a unified proof on theO(1/t) iteration complexity, together with the linear convergence rate for this kind of proximal-based decomposition methods. Besides the ε-optimal iteration complexity result defined by variational inequality, the non-ergodic relative error of adjacent iteration points is also proved to decrease in the same order. Further, the linear convergence rate of this algorithm framework can be constructed based on some special variational inequality properties, without necessary strong monotone conditions.

Key words: Variational inequality ·, Proximal point algorithm ·, Iteration complexity ·Relative error ·, Convergence rate ·, Error bound