两类近似邻近点算法的比较及其推广

Comparison and Extension of Two Kinds of Approximate Proximal Point Algorithms for Monotone Variational Inequalities

邻近点算法(PPA)是求解单调变分不等式的一种常用的有效方法。然而在许多实际应用中,用PPA算法精确求解子变分不等式花费很大。为了保持PPA算法的优点,同时又解决上述困难,人们采用近似临近点算法(Approxim ate Proxim al PointA lgorithm)来求解。通过对两类APPA算法的收敛性的证明和进一步探讨,从理论上证明了算法二在通常情况下比算法一收敛性好。文中所要讨论的算法一是基于对Forward-backward Sp litting方法的推广;算法二是基于对外梯度方法的推广。

Proximal point algorithms （PPA） arc attractive methods solving monotone variational inequalities （VI）. Since solving the sub-problem in each iteration exactly is costly or sometime impossible, various approximate versions of PPA （APPA） are developed for practical application. In this paper, we compare two kinds of APPA methods. Both of the methods can be viewed as prediction-correction methods. The only difference is that they use different search directions in the correction-step. By extending the general forward-backward splitting methods, we obtain Algorithm Ⅰ, in the same way, Algorithm Ⅱ is proposed by spreading the general extra-gradient methods. The iteration process and convergence analysis of every algorithm are discussed in detail. Our analysis explains theoretically why Algorithm Ⅱ usually outperform Algorithm Ⅰ.