Strong convergence of multi-parameter projection methods for variational inequality problems
Abstract
In this paper, we introduce a multi-parameter projection method for solving a variational inequality problem, and establish its strong convergence in a Hilbert space under appropriate conditions. The method involves two projectionsteps with different variable stepsizes where one of them is computed explicitly on a specifically structural half-space. The proof of strong convergence of the method is based on the regularization solutions depending on parameters of the original problem. It turns out that the solution obtained by the method is the solution of a bilevel variational inequality problem whose constraint is the solution set of our considered problem. In order to support the obtained theoretical results, we perform some experiments on transportation equilibrium and optimal control problems, and also involve comparisons. Numerical results show the computational effectiveness and the fast convergence of the new method over some existing ones.
Keyword : variational inequality, monotonicity, Lipschitz continuity, iterative method, regularization
How to Cite
Van Hieu, D., Dung Muu, L., & Kim Quy, P. (2022). Strong convergence of multi-parameter projection methods for variational inequality problems. Mathematical Modelling and Analysis, 27(2), 242–262. https://doi.org/10.3846/mma.2022.14479
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
M. Abbas and H. Iqbal. Two inertial extragradient viscosity algorithms for solving variational inequality and fixed point problems. Journal of Nonlinear and Variational Analysis, 4(3):377–398, 2020. https://doi.org/10.23952/jnva.4.2020.3.04
Ya.I. Alber and I. Ryazantseva. Nonlinear Ill-posed Problems of Monotone Type. Springer, Dordrecht, 2006. https://doi.org/10.1007/1-4020-4396-1
H.H. Bauschke and P.L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York, 2011.
X. Cai, G. Gu and B. He. On the o(1/t) convergence rate of the projection and contraction methods for variational inequalities with Lipschitz continuous monotone operators. Computational Optimization and Applications, 57:339–363, 2014. https://doi.org/10.1007/s10589-013-9599-7
Y. Censor, A. Gibali and S. Reich. Strong convergence of subgradient extragradient methods for the variational inequality problem in Hilbert space. Optimization Methods and Software, 26(4-5):827–845, 2011. https://doi.org/10.1080/10556788.2010.551536
Y. Censor, A. Gibali and S. Reich. The subgradient extragradient method for solving variational inequalities in Hilbert space. Journal of Optimization Theory and Applications, 148:318–335, 2011. https://doi.org/10.1007/s10957-010-9757-3
Y. Censor, A. Gibali and S. Reich. Extensions of Korpelevich’s extragradient method for the variational inequality problem in Euclidean space. Optimization, 61(9):1119–1132, 2012. https://doi.org/10.1080/02331934.2010.539689
Q.L. Dong, Y.J. Cho and T.M. Rassias. The projection and contraction methods for finding common solutions to variational inequality problems. Optim. Lett., 12:1871–1896, 2018. https://doi.org/10.1007/s11590-017-1210-1
Q.L. Dong, Y.J. Cho, L.L. Zhong and T.M. Rassias. Inertial projection and contraction algorithms for variational inequalities. Journal of Global Optimization, 70:687–704, 2018. https://doi.org/10.1007/s10898-017-0506-0
Q.L. Dong, A. Gibali, D. Jiang and S.H. Ke. Convergence of projection and contraction algorithms with outer perturbations and their applications to sparse signals recovery. Journal of Fixed Point Theory and Applications, 20(16), 2018. https://doi.org/10.1007/s11784-018-0501-1
Q.L. Dong, D. Jiang and A. Gibali. A modified subgradient extragradient method for solving the variational inequality problem. Numerical Algorithms, 79:927– 940, 2018. https://doi.org/10.1007/s11075-017-0467-x
N.T. Vinh D.V. Thong and Y.J. Cho. New strong convergence theorem of the inertial projection and contraction method for variational inequality problems. Numerical Algorithms, 84:285–305, 2020. https://doi.org/10.1007/s11075-019-00755-1
F. Facchinei and J.S. Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, Berlin, 2003. https://doi.org/10.1007/b97544
R. Glowinski. Numerical Methods for Nonlinear Variational Problems. Springer, New York, 1984. https://doi.org/10.1007/978-3-662-12613-4
K. Goebel and S. Reich. Uniform Convexity, Hyperbolic Geometry, and Nonexpansive Mappings. Marcel Dekker, New York and Basel, 1984.
B.S. He. A class of projection and contraction methods for monotone variational inequalities. Applied Mathematics and Optimization, 35:69–76, 1997. https://doi.org/10.1007/BF02683320
B.S. He and L.-Z. Liao. Improvements of some projection methods for monotone nonlinear variational inequalities. Journal of Optimization Theory and Applications, 112:111–128, 2002. https://doi.org/10.1023/A:1013096613105
B.S. He, X.M. Yuan and J.J.Z. Zhang. Comparison of two kinds of prediction-correction methods for monotone variational inequalities. Computational Optimization and Applications, 27:247–267, 2004. https://doi.org/10.1023/B:COAP.0000013058.17185.90
D.V. Hieu, Y.J. Cho, Y.B. Xiao and P. Kumam. Modified extragradient method for pseudomonotone variational inequalities in infinite dimensional Hilbert spaces. Vietnam Journal of Mathematics, 49:1165–1183, 2021. https://doi.org/10.1007/s10013-020-00447-7
D.V. Hieu, L.D. Muu, P.K. Quy and H.N. Duong. Regularization extragradient methods for equilibrium programming in Hilbert spaces. Optimization, 0(0):1– 31, 2021. https://doi.org/10.1080/02331934.2021.1873988
D.V. Hieu, J.J. Strodiot and L.D. Muu. An explicit extragradient algorithm for solving variational inequalities. Journal of Optimization Theory and Applications, 185:476–503, 2020. https://doi.org/10.1007/s10957-020-01661-6
I. Hlavacek, J. Haslinger, J. Necas and J. Lovicek. Solution of Variational Inequalities in Mechanics. Springer, New York, 1982. https://doi.org/10.1007/978-1-4612-1048-1
E.V. Khoroshilova. Extragradient-type method for optimal control problem with linear constraints and convex objective function. Optimization Letters, 7:1193– 1214, 2013. https://doi.org/10.1007/s11590-012-0496-2
D. Kinderlehrer and G. Stampacchia. An Introduction to Variational Inequalities and Their Applications. Academic Press, New York, 1980.
I.V. Konnov. Equilibrium Models and Variational Inequalities. Amsterdam, Elsevier, 2007.
G.M. Korpelevich. The extragradient method for finding saddle points and other problems. Ekonomikai Matematicheskie Metody, 12:747–756, 1976.
R. Kraikaew and S. Saejung. Strong convergence of the Halpern subgradient extragradient method for solving variational inequalities in Hilbert spaces. Journal of Optimization Theory and Applications, 163:399–412, 2014. https://doi.org/10.1007/s10957-013-0494-2
L. Lampariello, C. Neumann, J. M. Ricci, S. Sagratella and O. Stein. An explicit Tikhonov algorithm for nested variational inequalities. Computational Optimization and Applications, 77:335–350, 2020. https://doi.org/10.1007/s10589-020-00210-1
P.E. Maing´e. A hybrid extragradient-viscosity method for monotone operators and fixed point problems. SIAM Journal on Control and Optimization, 47(3):1499–1515, 2008. https://doi.org/10.1137/060675319
Y.V. Malitsky. Projected reflected gradient methods for monotone variational inequalities. SIAM Journal on Optimization, 25(1):502–520, 2015. https://doi.org/10.1137/14097238X
Y.V. Malitsky. Golden ratio algorithms for variational inequalities. Mathematical Programming, 184:383–410, 2020. https://doi.org/10.1007/s10107-019-01416-w
P.D. Panagiotopoulos. Inequality Problems in Mechanics and Applications. Boston, Birkha¨user, 1985. https://doi.org/10.1007/978-1-4612-5152-1
L.D. Popov. A modification of the Arrow-Hurwicz method for searching for saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28:845–848, 1980. https://doi.org/10.1007/BF01141092
S. Sabach and S. Shtern. A first-order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640–660, 2017. https://doi.org/10.1137/16M105592X
M. Seydenschwanz. Convergence results for the discrete regularization of linearquadratic control problems with bang-bang solutions. Computational Optimization and Applications, 629:731–760, 2015. https://doi.org/10.1007/s10589-015-9730-z
M.V. Solodov and P. Tseng. Modified projection-type methods for monotone variational inequalities. SIAM Journal on Control and Optimization, 34(5):1814– 1830, 1996. https://doi.org/10.1137/S0363012994268655
D.F. Sun. A class of iterative methods for solving nonlinear projection equations. Journal of Optimization Theory and Applications, 91:123–140, 1996. https://doi.org/10.1007/BF02192286
B. Tan and S. Xu. Strong convergence of two inertial projection algorithms in Hilbert spaces. Journal of Applied and Numerical Optimization, 2(2):171–186, 2020. https://doi.org/10.23952/jano.2.2020.2.04
D.V. Thong and D.V. Hieu. Some extragradient-viscosity algorithms for solving variational inequality problems and fixed point problems. Numerical Algorithms, 82:761–789, 2019. https://doi.org/10.1007/s11075-018-0626-8
M. Tian and G. Xu. Inertial modified Tseng’s extragradient algorithms for solving monotone variational inequalities and fixed point problems. Journal of Nonlinear Functional Analysis, 2020:1–19, 2020. https://doi.org/10.23952/jnfa.2020.35
P. Tseng. A modified forward-backward splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, 38(2):431–446, 2000. https://doi.org/10.1137/S0363012998338806
P.T. Vuong and Y. Shehu. Convergence of an extragradient-type method for variational inequality with applications to optimal control problems. Numerical Algorithms, 81:269–291, 2019. https://doi.org/10.1007/s11075-018-0547-6
H.K. Xu. Iterative algorithms for nonlinear operators. Journal of the London Mathematical Society, 66(1):240–256, 2002. https://doi.org/10.1112/S0024610702003332
P.T. Vuong Y. Shehu and A. Zemkoho. An inertial extrapolation method for convex simple bilevel optimization. Optimization Methods and Software, 36(1):1– 19, 2021. https://doi.org/10.1080/10556788.2019.1619729
Ya.I. Alber and I. Ryazantseva. Nonlinear Ill-posed Problems of Monotone Type. Springer, Dordrecht, 2006. https://doi.org/10.1007/1-4020-4396-1
H.H. Bauschke and P.L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York, 2011.
X. Cai, G. Gu and B. He. On the o(1/t) convergence rate of the projection and contraction methods for variational inequalities with Lipschitz continuous monotone operators. Computational Optimization and Applications, 57:339–363, 2014. https://doi.org/10.1007/s10589-013-9599-7
Y. Censor, A. Gibali and S. Reich. Strong convergence of subgradient extragradient methods for the variational inequality problem in Hilbert space. Optimization Methods and Software, 26(4-5):827–845, 2011. https://doi.org/10.1080/10556788.2010.551536
Y. Censor, A. Gibali and S. Reich. The subgradient extragradient method for solving variational inequalities in Hilbert space. Journal of Optimization Theory and Applications, 148:318–335, 2011. https://doi.org/10.1007/s10957-010-9757-3
Y. Censor, A. Gibali and S. Reich. Extensions of Korpelevich’s extragradient method for the variational inequality problem in Euclidean space. Optimization, 61(9):1119–1132, 2012. https://doi.org/10.1080/02331934.2010.539689
Q.L. Dong, Y.J. Cho and T.M. Rassias. The projection and contraction methods for finding common solutions to variational inequality problems. Optim. Lett., 12:1871–1896, 2018. https://doi.org/10.1007/s11590-017-1210-1
Q.L. Dong, Y.J. Cho, L.L. Zhong and T.M. Rassias. Inertial projection and contraction algorithms for variational inequalities. Journal of Global Optimization, 70:687–704, 2018. https://doi.org/10.1007/s10898-017-0506-0
Q.L. Dong, A. Gibali, D. Jiang and S.H. Ke. Convergence of projection and contraction algorithms with outer perturbations and their applications to sparse signals recovery. Journal of Fixed Point Theory and Applications, 20(16), 2018. https://doi.org/10.1007/s11784-018-0501-1
Q.L. Dong, D. Jiang and A. Gibali. A modified subgradient extragradient method for solving the variational inequality problem. Numerical Algorithms, 79:927– 940, 2018. https://doi.org/10.1007/s11075-017-0467-x
N.T. Vinh D.V. Thong and Y.J. Cho. New strong convergence theorem of the inertial projection and contraction method for variational inequality problems. Numerical Algorithms, 84:285–305, 2020. https://doi.org/10.1007/s11075-019-00755-1
F. Facchinei and J.S. Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, Berlin, 2003. https://doi.org/10.1007/b97544
R. Glowinski. Numerical Methods for Nonlinear Variational Problems. Springer, New York, 1984. https://doi.org/10.1007/978-3-662-12613-4
K. Goebel and S. Reich. Uniform Convexity, Hyperbolic Geometry, and Nonexpansive Mappings. Marcel Dekker, New York and Basel, 1984.
B.S. He. A class of projection and contraction methods for monotone variational inequalities. Applied Mathematics and Optimization, 35:69–76, 1997. https://doi.org/10.1007/BF02683320
B.S. He and L.-Z. Liao. Improvements of some projection methods for monotone nonlinear variational inequalities. Journal of Optimization Theory and Applications, 112:111–128, 2002. https://doi.org/10.1023/A:1013096613105
B.S. He, X.M. Yuan and J.J.Z. Zhang. Comparison of two kinds of prediction-correction methods for monotone variational inequalities. Computational Optimization and Applications, 27:247–267, 2004. https://doi.org/10.1023/B:COAP.0000013058.17185.90
D.V. Hieu, Y.J. Cho, Y.B. Xiao and P. Kumam. Modified extragradient method for pseudomonotone variational inequalities in infinite dimensional Hilbert spaces. Vietnam Journal of Mathematics, 49:1165–1183, 2021. https://doi.org/10.1007/s10013-020-00447-7
D.V. Hieu, L.D. Muu, P.K. Quy and H.N. Duong. Regularization extragradient methods for equilibrium programming in Hilbert spaces. Optimization, 0(0):1– 31, 2021. https://doi.org/10.1080/02331934.2021.1873988
D.V. Hieu, J.J. Strodiot and L.D. Muu. An explicit extragradient algorithm for solving variational inequalities. Journal of Optimization Theory and Applications, 185:476–503, 2020. https://doi.org/10.1007/s10957-020-01661-6
I. Hlavacek, J. Haslinger, J. Necas and J. Lovicek. Solution of Variational Inequalities in Mechanics. Springer, New York, 1982. https://doi.org/10.1007/978-1-4612-1048-1
E.V. Khoroshilova. Extragradient-type method for optimal control problem with linear constraints and convex objective function. Optimization Letters, 7:1193– 1214, 2013. https://doi.org/10.1007/s11590-012-0496-2
D. Kinderlehrer and G. Stampacchia. An Introduction to Variational Inequalities and Their Applications. Academic Press, New York, 1980.
I.V. Konnov. Equilibrium Models and Variational Inequalities. Amsterdam, Elsevier, 2007.
G.M. Korpelevich. The extragradient method for finding saddle points and other problems. Ekonomikai Matematicheskie Metody, 12:747–756, 1976.
R. Kraikaew and S. Saejung. Strong convergence of the Halpern subgradient extragradient method for solving variational inequalities in Hilbert spaces. Journal of Optimization Theory and Applications, 163:399–412, 2014. https://doi.org/10.1007/s10957-013-0494-2
L. Lampariello, C. Neumann, J. M. Ricci, S. Sagratella and O. Stein. An explicit Tikhonov algorithm for nested variational inequalities. Computational Optimization and Applications, 77:335–350, 2020. https://doi.org/10.1007/s10589-020-00210-1
P.E. Maing´e. A hybrid extragradient-viscosity method for monotone operators and fixed point problems. SIAM Journal on Control and Optimization, 47(3):1499–1515, 2008. https://doi.org/10.1137/060675319
Y.V. Malitsky. Projected reflected gradient methods for monotone variational inequalities. SIAM Journal on Optimization, 25(1):502–520, 2015. https://doi.org/10.1137/14097238X
Y.V. Malitsky. Golden ratio algorithms for variational inequalities. Mathematical Programming, 184:383–410, 2020. https://doi.org/10.1007/s10107-019-01416-w
P.D. Panagiotopoulos. Inequality Problems in Mechanics and Applications. Boston, Birkha¨user, 1985. https://doi.org/10.1007/978-1-4612-5152-1
L.D. Popov. A modification of the Arrow-Hurwicz method for searching for saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28:845–848, 1980. https://doi.org/10.1007/BF01141092
S. Sabach and S. Shtern. A first-order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640–660, 2017. https://doi.org/10.1137/16M105592X
M. Seydenschwanz. Convergence results for the discrete regularization of linearquadratic control problems with bang-bang solutions. Computational Optimization and Applications, 629:731–760, 2015. https://doi.org/10.1007/s10589-015-9730-z
M.V. Solodov and P. Tseng. Modified projection-type methods for monotone variational inequalities. SIAM Journal on Control and Optimization, 34(5):1814– 1830, 1996. https://doi.org/10.1137/S0363012994268655
D.F. Sun. A class of iterative methods for solving nonlinear projection equations. Journal of Optimization Theory and Applications, 91:123–140, 1996. https://doi.org/10.1007/BF02192286
B. Tan and S. Xu. Strong convergence of two inertial projection algorithms in Hilbert spaces. Journal of Applied and Numerical Optimization, 2(2):171–186, 2020. https://doi.org/10.23952/jano.2.2020.2.04
D.V. Thong and D.V. Hieu. Some extragradient-viscosity algorithms for solving variational inequality problems and fixed point problems. Numerical Algorithms, 82:761–789, 2019. https://doi.org/10.1007/s11075-018-0626-8
M. Tian and G. Xu. Inertial modified Tseng’s extragradient algorithms for solving monotone variational inequalities and fixed point problems. Journal of Nonlinear Functional Analysis, 2020:1–19, 2020. https://doi.org/10.23952/jnfa.2020.35
P. Tseng. A modified forward-backward splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, 38(2):431–446, 2000. https://doi.org/10.1137/S0363012998338806
P.T. Vuong and Y. Shehu. Convergence of an extragradient-type method for variational inequality with applications to optimal control problems. Numerical Algorithms, 81:269–291, 2019. https://doi.org/10.1007/s11075-018-0547-6
H.K. Xu. Iterative algorithms for nonlinear operators. Journal of the London Mathematical Society, 66(1):240–256, 2002. https://doi.org/10.1112/S0024610702003332
P.T. Vuong Y. Shehu and A. Zemkoho. An inertial extrapolation method for convex simple bilevel optimization. Optimization Methods and Software, 36(1):1– 19, 2021. https://doi.org/10.1080/10556788.2019.1619729