[1] Tao Min,. Comparison of two kinds of approximate proximal point algorithmsfor monotone variational inequalities [J]. Journal of Southeast University (English Edition), 2008, 24 (4): 537-540. [doi:10.3969/j.issn.1003-7985.2008.04.028]

Copy

Comparison of two kinds of approximate proximal point algorithmsfor monotone variational inequalities()

求解单调变分不等式的两类近似邻近点算法比较

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

24

Issue:

2008 4

Page:

537-540

Research Field:

Mathematics, Physics, Mechanics

Publishing date:

2008-12-30

Info

Title:

Comparison of two kinds of approximate proximal point algorithmsfor monotone variational inequalities

求解单调变分不等式的两类近似邻近点算法比较

Author(s):

Tao Min

School of Applied Mathematics and Physics, Nanjing University of Posts and Telecommunications, Nanjing 210046, China

陶敏

南京邮电大学数理学院, 南京 210046

Keywords:

monotone variational inequality;  approximate proximate point algorithm;  inexactness criterion

单调变分不等式;  近似邻近点算法;  非精确准则

PACS:

O221.2

DOI:

10.3969/j.issn.1003-7985.2008.04.028

Abstract:

This paper proposes two kinds of approximate proximal point algorithms(APPA)for monotone variational inequalities, both of which can be viewed as two extended versions of Solodov and Svaiter’s APPA in the paper “Error bounds for proximal point subproblems and associated inexact proximal point algorithms” published in 2000. They are both prediction-correction methods which use the same inexactness restriction; the only difference is that they use different search directions in the correction steps. This paper also chooses an optimal step size in the two versions of the APPA to improve the profit at each iteration. Analysis also shows that the two APPAs are globally convergent under appropriate assumptions, and we can expect algorithm 2 to get more progress in every iteration than algorithm 1. Numerical experiments indicate that algorithm 2 is more efficient than algorithm 1 with the same correction step size.

将 Solodov 和 Svaiter于2000年发表的Error bounds for proximal point subproblems and associated inexact proximal point algorithms一文中提出的方法进行推广, 得到2类近似邻近点算法.这2类算法都是预测-校正方法, 预测点满足相同的非精确准则, 不同之处在于校正步的下降方向.为了使每次迭代产生的迭代点更加靠近解点, 在校正步均采用了最优步长的技巧.在一定条件下, 可以证明这2种邻近点算法是全局收敛的.并且, 从理论上证明了采用算法2每一步所产生的下降量的下界大于算法1的, 所以算法2比算法1能更快地收敛到解点.数值试验也表明了这一点.

References:

[1] Harker P T, Pang J S.Finite-dimensional variational inequality and nonlinear complementarity problem:a survey of theory, algorithms and application [J].Mathematical Programming, 1990, 48:61-220.
[2] Bertsekas D P, Tsitsiklis J N.Numerical methods[M].Englewood Cliffs:Prentice-Hall, 1989:267-268.
[3] Rockafellar R T.Augmented Lagrangians and applications of the proximal point algorithm in convex programming[J].Mathematics of Operations Research, 1976, 1:97-116.
[4] Rockafellar R T.Monotone operators and the proximal point algorithm[J].SIAM, Journal on Control and Optimization, 1976, 14:877-898.
[5] Solodov M V, Svaiter B F.Error bounds for proximal point subproblems and associated inexact proximal point algorithms[J].Mathematical Programming:Ser B, 2000, 88:371-389.
[6] Zhu T, Yu Z G.A simple proof for some important properties of the projection mapping[J].Mathematical Inequalities and Applications, 2004, 7:453-456.
[7] Yuan Y X.Numerical linear algebra and optimization[C]//Proceedings of the 2001 International Conference on Numerical Optimization and Numerical Linear Algebra.Beijing:Science Press, 2004:15-41.
[8] He B S, Liao L Z.Improvements of some projection methods for monotone nonlinear variational inequalities [J].J Optim Theory Appl, 2002, 112:111-128.

Memo

Memo:

Biography: Tao Min(1979—), female, master, lecturer, taominnju@yahoo.com.
Citation: Tao Min.Comparison of two kinds of approximate proximal point algorithms for monotone variational inequalities[J].Journal of Southeast University(English Edition), 2008, 24(4):537-540.

Common functions