本文提出了一类求解单调变分不等式的具有相对误差准则的非精确邻近点算法。在提出的方法中,可以通过两种方式得到下一个迭代点。在一般假设条件下,建立了新算法的全局收敛性。通过选择一种特殊的误差形式,所提出的非精确邻近点算法退化为一类带有线搜索的投影收缩算法,这揭示了非精确邻近点算法和投影类算法之间的联系。数值实验验证了新方法的有效性。
n this paper, we propose a class of inexact proximal point algorithms with relative error criterion for solving monotone variational inequalities. The next iterate in the proposed methods can be obtained in two ways. Under general hypothetical conditions, the global convergence of the new algorithms is established. By choosing a special form for the error, the proposed inexact proximal point algorithms reduce to a class of projection and contraction methods with linesearch, which reveals the connection between inexact proximal point algorithms and a class of projection methods. Numerical experiments demonstrate the efficiency of the new methods.
[1] Ferris M C, Pang J S. Engineering and economic applications of complementarity problems [J]. SIAM Review, 1997, 39(4): 669-713.
[2] Harker P T, Pang J S. Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications [J]. Mathematical Programming, 1990, 48(1-3): 161-220.
[3] Noor M A. Some recent advances in variational inequalities, Part I, basic concepts [J]. New Zealand Journal of Mathematics, 1997, 26(1): 53-80.
[4] Bertsekas D, Nedic A, Ozdaglar A. Convex Analysis and Optimization [M]. MIT: Athena Scientific, 2003.
[5] Martinet B. Regularization d’inequations variationelles par approximations successives [J]. Revue Francaise d’Informatique et de Recherche Opérationelle, 1970, 4: 154-159.
[6] Rockafellar R T. Monotone operators and the proximal point algorithm [J]. SIAM Journal on Control and Optimization, 1976, 14(5): 877-898.
[7] Goldstein A A. Convex programming in Hilbert space [J]. Bulletin of American Mathematical Society 1964, 70: 709-710.
[8] Levitin E S, Polyak B T. Constrained minimization methods [J]. USSR Computational Mathematics and Mathematical Physics, 1966, 6(5): 1-50.
[9] Korpelevich G M. The extragradient method for finding saddle points and other problems [J]. Matecon, 1976, 12: 747-756.
[10] Khobotov E N. Modification of the extra-gradient method for solving variational inequalities and certain optimization problems [J]. USSR Computational Mathematics and Mathematical Physics, 1987, 27(5): 120-127.
[11] He B. A class of projection and contraction methods for monotone variational inequalities [J]. Applied Mathematics and Optimization, 1997, 35(1): 69-76.
[12] He B, Liao L. Improvements of some projection methods for monotone nonlinear variational inequalities [J]. Journal of Optimization Theory and Applications, 2002, 112: 111-128.
[13] He B, Yuan X, Zhang J J Z. Comparison of two kinds of prediction-correction methods for monotone variational inequalities [J]. Computational Optimization and Applications, 2004, 27: 247-267.
[14] Malitsky Y. Projected reflected gradient methods for monotone variational inequalities [J]. SIAM Journal on Optimization, 2015, 25(1): 502-520.
[15] Malitsky Y, Tam M K. A forward-backward splitting method for monotone inclusions without cocoercivity [J]. SIAM Journal on Optimization, 2020, 30(2): 1451-1472.
[16] Mainge P E, Gobinddass M L. Convergence of one-step projected gradient methods for variational inequalities [J]. Journal of Optimization Theory and Applications, 2016, 171: 146-168.
[17] Yang J, Liu H. A modified projected gradient method for monotone variational inequalities [J]. Journal of Optimization Theory and Applications, 2018, 179: 197-211.
[18] Malitsky Y. Golden ratio algorithms for variational inequalities [J]. Mathematical Programming, 2020, 184(1-2): 383-410.
[19] Shehu Y, Li X, Dong Q. An efficient projection-type method for monotone variational inequalities in Hilbert spaces [J]. Numerical Algorithms, 2020, 84: 365-388.
[20] Solodov M V, Svaiter B F. A hybrid projection-proximal point algorithm [J]. Journal of Convex Analysis, 1999, 6(1): 59-70.
[21] Solodov M V, Svaiter B F. An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions [J]. Mathematics of Operations Research, 2000, 25(2): 214-230.
[22] He B, Liao L, Yang Z. A new approximate proximal point algorithm for maximal monotone operator [J]. Science in China Series A: Mathematics, 2003, 46(2): 200-206.
[23] He B, Yang Z, Yuan X. An approximate proximal-extragradient type method for monotone variational inequalities [J]. Journal of Mathematical Analysis and Applications, 2004, 300(2): 362-374.
[24] Solodov M V, Svaiter B F. A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator [J]. Set-Valued Analysis, 1999, 7(4): 323-345.
[25] Monteiro R D C, Svaiter B F. On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean [J]. SIAM Journal on Optimization, 2010, 20(6): 2755- 2787.
[26] Han D, He B. A new accuracy criterion for approximate proximal point algorithms [J]. Journal of Mathematical Analysis and Applications, 2001, 263(2): 343-354.
[27] Jiang F, Cai X, Han D. The indefinite proximal point algorithms for maximal monotone operators [J]. Optimization, 2021, 70(8): 1759-1790.
[28] Cai X, Guo K, Jiang F, et al. The developments of proximal point algorithms [J]. Journal of the Operations Research Society of China, 2022, 10(2): 197-239.
[29] Yang L, Toh K C. Bregman proximal point algorithm revisited: A new inexact version and its inertial variant [J]. SIAM Journal on Optimization, 2022, 32(3): 1523-1554.
[30] Tseng P. A modified forward-backward splitting method for maximal monotone mappings [J]. SIAM Journal on Control and Optimization, 2000, 38(2): 431-446.
[31] Mokhtari A, Ozdaglar A E, Pattathil S. Convergence rate of O(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems [J]. SIAM Journal on Optimization, 2020, 30(4): 3230-3251.
[32] Mokhtari A, Ozdaglar A, Pattathil S. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach [C]//International Conference on Artificial Intelligence and Statistics, 2020: 1497-1507.
北大中文核心期刊