Full Text:   <2399>

CLC number: O221.2

On-line Access: 

Received: 2005-09-08

Revision Accepted: 2005-12-21

Crosschecked: 0000-00-00

Cited: 0

Clicked: 4052

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2007 Vol.8 No.6 P.969-977

http://doi.org/10.1631/jzus.2007.A0969


Comparison of two approximal proximal point algorithms for monotone variational inequalities


Author(s):  TAO Min

Affiliation(s):  School of Applied Mathematics and Physics, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

Corresponding email(s):   mathsgirl2002@yahoo.com.cn

Key Words:  Projection and contraction methods, Proximal point algorithm (PPA), Approximate PPA (APPA), Monotone variational inequality (MVI), Prediction and correction


TAO Min. Comparison of two approximal proximal point algorithms for monotone variational inequalities[J]. Journal of Zhejiang University Science A, 2007, 8(6): 969-977.

@article{title="Comparison of two approximal proximal point algorithms for monotone variational inequalities",
author="TAO Min",
journal="Journal of Zhejiang University Science A",
volume="8",
number="6",
pages="969-977",
year="2007",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2007.A0969"
}

%0 Journal Article
%T Comparison of two approximal proximal point algorithms for monotone variational inequalities
%A TAO Min
%J Journal of Zhejiang University SCIENCE A
%V 8
%N 6
%P 969-977
%@ 1673-565X
%D 2007
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2007.A0969

TY - JOUR
T1 - Comparison of two approximal proximal point algorithms for monotone variational inequalities
A1 - TAO Min
J0 - Journal of Zhejiang University Science A
VL - 8
IS - 6
SP - 969
EP - 977
%@ 1673-565X
Y1 - 2007
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2007.A0969


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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[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.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2023 Journal of Zhejiang University-SCIENCE