Similar articles

Abstract: Proximal point algorithms (PPA) are attractive methods for solving monotone variational inequalities (MVI). Since solving the sub-problem exactly in each iteration is costly or sometimes impossible, various approximate versions of PPA (APPA) are developed for practical applications. In this paper, we compare two APPA methods, both of which 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 I; in the same way, Algorithm II is proposed by spreading the general extra-gradient methods. Our analysis explains theoretically why Algorithm II usually outperforms Algorithm I. For computation practice, we consider a class of MVI with a special structure, and choose the extending Algorithm II to implement, which is inspired by the idea of Gauss-Seidel iteration method making full use of information about the latest iteration. And in particular, self-adaptive techniques are adopted to adjust relevant parameters for faster convergence. Finally, some numerical experiments are reported on the separated MVI. Numerical results showed that the extending Algorithm II is feasible and easy to implement with relatively low computation load.

[1] Bertsekas, D.P., Tsitsiklis, J.N., 1989. Parallel and Distributed Computation, Numerical Methods. Prentice-Hall, Engle-wood Clis, NJ, p.267-268.

[2] Harker, P.T., Pang, J.S., 1990. Finite-dimensional variational inequality and nonlinear complementarity problem: a survey of theory, algorithms and application. Math. Programming, 48:161-220.

[3] He, B.S., Qian, M.J., Wang, Y.M., 2004. Study on Some Approximate Proximal Point Algorithms for Monotone Variational Inequalities. In: Yuan, Y.X. (Ed.), Numerical Linear Algebra and Optimization. Proc. 2003 Int. Conf. Numerical Optimization and Numerical Linear Algebra. Science Press, Beijing/New York, p.15-41 (in Chinese).

[4] Korpelevich, G.M., 1976. The extragradient method for finding saddle points and other problems. Ekonomika i Matematchskie Metody, 12:747-756. [English Translation: Matecon, 13(1977):35-49]

[5] Li, C.L., Zeng, J.P., 2003. Much splitting and adding Schwarz iteration for nonlinear complementarity problems. Num. Comput. Appl. Computer, 25:269-275 (in Chinese).

[6] Rockafellar, R.T., 1976. Monotone operators and the proximal point algorithm. SIAM J. Control & Optim., 14:877-898.

[7] Tseng, P., 2000. A modified forward-backward splitting method for maximal monotone mappings. SIAM J. Control & Optim., 38:431-446.

[8] Zhu, T., Yu, Z.G., 2004. A simple proof for some important properties of the projection mapping. Math. Ineq. Appl., 7:453-456.