×

Customized Douglas-Rachford splitting methods for structured inverse variational inequality problems. (English) Zbl 07896306

Summary: Recently, structured inverse variational inequality (SIVI) problems have attracted much attention. In this paper, we propose new splitting methods to solve SIVI problems by employing the idea of the classical Douglas-Rachford splitting method (DRSM). In particular, the proposed methods can be regarded as a novel application of the DRSM to SIVI problems by decoupling the linear equality constraint, leading to smaller and easier subproblems. The main computational tasks per iteration are the evaluations of certain resolvent operators, which are much cheaper than those methods without taking advantage of the problem structures. To make the methods more implementable in the general cases where the resolvent operator is evaluated in an iterative scheme, we further propose to solve the subproblems in an approximate manner. Under quite mild conditions, global convergence, sublinear rate of convergence, and linear rate of convergence results are established for both the exact and the inexact methods. Finally, we present preliminary numerical results to illustrate the performance of the proposed methods.

MSC:

65K10 Numerical optimization and variational techniques
49J40 Variational inequalities
90C25 Convex programming
Full Text: DOI

References:

[1] Anceschi, F., Barbagallo, A., and Guarino Lo Bianco, S., Inverse tensor variational inequalities and applications, J. Optim. Theory. Appl.196 (2023), pp. 570-589. · Zbl 1512.49036
[2] Barbagallo, A. and Guarino Lo Bianco, S., A random time-dependent noncooperative equilibrium problem, Comput. Optim. Appl.84 (2023), pp. 27-52. · Zbl 1509.91026
[3] Barbagallo, A. and Mauro, P., Inverse variational inequality approach and applications, Numer Funct Anal Optim.35 (2014), pp. 851-867. · Zbl 1295.49006
[4] Barbagallo, A. and Mauro, P., A general quasi-variational problem of Cournot-Nash type and its inverse formulation, J. Optim. Theory. Appl.170 (2016), pp. 476-492. · Zbl 1346.49010
[5] Bauschke, H.H. and Combettes, P.L., Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics, 2nd edn,Springer, Cham, 2017. · Zbl 1359.26003
[6] Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn.3(1) (2011), pp. 1-122. · Zbl 1229.90122
[7] Cai, X.J., Guo, K., Jiang, F., Wang, K., Wu, Z.M., and Han, D.R., The developments of proximal point algorithms, J. Oper. Res. Soc. China10 (2022), pp. 197-239. · Zbl 1502.47081
[8] Cai, X.J., Han, D.R., and Yuan, X.M., On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function, Comput. Optim. Appl.66 (2017), pp. 39-73. · Zbl 1372.90079
[9] Chen, J.W., Ju, X.X., Köbis, E., and Liou, Y.C., Tikhonov type regularization methods for inverse mixed variational inequalities, Optimization69 (2020), pp. 401-413. · Zbl 1432.49006
[10] Douglas, J. and Rachford, H.H., On the numerical solution of heat conduction problems in two and three space variables, Trans. Am. Math. Soc.82 (1956), pp. 421-439. · Zbl 0070.35401
[11] Glowinski, R., On alternating direction methods of multipliers: A historical perspective, in Modeling, Simulation and Optimization for Science and Technology, Springer, 2014, pp. 59-82. · Zbl 1320.65098
[12] Han, D.R., A survey on some recent developments of alternating direction method of multipliers, J. Oper. Res. Soc. China10(1) (2022), pp. 1-52. · Zbl 1499.90158
[13] Han, D.R., He, H.J., Yang, H., and Yuan, X.M., A customized Douglas-Rachford splitting algorithm for separable convex minimization with linear constraints, Numerische Mathematik127 (2014), pp. 167-200. · Zbl 1295.90046
[14] Han, D.R. and Yuan, X.M., Local linear convergence of the alternating direction method of multipliers for quadratic programs, SIAM. J. Numer. Anal.51 (2013), pp. 3446-3457. · Zbl 1285.90033
[15] He, B.S., Inexact implicit methods for monotone general variational inequalities, Math. Program.86 (1999), pp. 199-217. · Zbl 0979.49006
[16] He, H.J. and Han, D.R., A distributed Douglas-Rachford splitting method for multi-block convex minimization problems, Adv. Comput. Math.42 (2016), pp. 27-53. · Zbl 1332.90198
[17] He, B.S., He, X.Z., and Liu, H.X., Solving a class of constrained ’black-box’ inverse variational inequalities, Eur. J. Oper. Res.204 (2010), pp. 391-401. · Zbl 1181.91148
[18] He, B.S., Liao, L.Z., and Wang, S.L., Self-adaptive operator splitting methods for monotone variational inequalities, Numerische Mathematik94 (2003), pp. 715-737. · Zbl 1033.65047
[19] He, X.Z. and Liu, H.X., Inverse variational inequalities with projection-based solution methods, Eur. J. Oper. Res.208 (2011), pp. 12-18. · Zbl 1208.90168
[20] Hu, R. and Fang, Y.P., Levitin-Polyak well-posedness by perturbations for the split inverse variational inequality problem, J. Fixed Point Theory Appl.18 (2016), pp. 785-800. · Zbl 1357.49101
[21] Hu, R. and Fang, Y.P., Well-posedness of the split inverse variational inequality problem, Bull. Malays. Math. Sci. Soc.40 (2017), pp. 1733-1744. · Zbl 1380.49028
[22] Jiang, Y.N., Cai, X.J., and Han, D.R., Solving policy design problems: Alternating direction method of multipliers-based methods for structured inverse variational inequalities, Eur. J. Oper. Res.280 (2020), pp. 417-427. · Zbl 1430.90530
[23] Ju, X.X., Li, C.D., He, X., and Feng, G., An inertial projection neural network for solving inverse variational inequalities, Neurocomputing406 (2020), pp. 99-105.
[24] Ju, X.X., Li, C.D., He, X., and Feng, G., A proximal neurodynamic model for solving inverse mixed variational inequalities, Neural. Netw.138 (2021), pp. 1-9. · Zbl 1523.49011
[25] Kim, D.S., Vuong, P.T., and Khanh, P.D., Qualitative properties of strongly pseudomonotone variational inequalities, Optim. Lett.10 (2016), pp. 1669-1679. · Zbl 1392.90115
[26] Li, X., Li, X.S., and Huang, N.J., A generalized f-projection algorithm for inverse mixed variational inequalities, Optim. Lett.8 (2014), pp. 1063-1076. · Zbl 1321.90138
[27] Lions, P.L. and Mercier, B., Splitting algorithms for the sum of two nonlinear operators, SIAM. J. Numer. Anal.16 (1979), pp. 964-979. · Zbl 0426.65050
[28] Luo, X.P., Tikhonov regularization methods for inverse variational inequalities, Optim. Lett.8 (2014), pp. 877-887. · Zbl 1310.90113
[29] Luo, Z.Q. and Tseng, P., Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem, SIAM. J. Optim.2 (1992), pp. 43-54. · Zbl 0777.49010
[30] Luo, X.P. and Yang, J., Regularization and iterative methods for monotone inverse variational inequalities, Optim. Lett.8 (2014), pp. 1261-1272. · Zbl 1287.49011
[31] Noor, M.A., Some developments in general variational inequalities, Appl. Math. Comput.152 (2004), pp. 199-277. · Zbl 1134.49304
[32] Pang, J.S., Error bounds in mathematical programming, Math. Program.79 (1997), pp. 299-332. · Zbl 0887.90165
[33] Pang, J.S. and Qi, L.Q., Nonsmooth equations: Motivation and algorithms, SIAM. J. Optim.3 (1993), pp. 443-465. · Zbl 0784.90082
[34] Pang, J.S. and Yao, J.C., On a generalization of a normal map and equation, SIAM J Control Optim.33 (1995), pp. 168-184. · Zbl 0827.90131
[35] Scrimali, L., An inverse variational inequality approach to the evolutionary spatial price equilibrium problem, Optim. Eng.13 (2012), pp. 375-387. · Zbl 1293.91116
[36] Tseng, P., On linear convergence of iterative methods for the variational inequality problem, J. Comput. Appl. Math.60 (1995), pp. 237-252. · Zbl 0835.65087
[37] Tseng, P., Approximation accuracy, gradient methods, and error bound for structured convex optimization, Math. Program.125 (2010), pp. 263-295. · Zbl 1207.65084
[38] Tseng, P. and Yun, S., A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training, Comput. Optim. Appl.47 (2010), pp. 179-206. · Zbl 1226.90062
[39] Van Hieu, D., Cho, Y.J., Xiao, Y.B., and Kumam, P., Modified extragradient method for pseudomonotone variational inequalities in infinite dimensional hilbert spaces, Vietnam J. Math.49 (2021), pp. 1165-1183. · Zbl 07425500
[40] Varga, R.S., Matrix Iterative Analysis, Prentice-Hall, Englewood Cliffs, 1966.
[41] Vuong, P.T., He, X.Z., and Thong, D.V., Global exponential stability of a neural network for inverse variational inequalities, J. Optim. Theory. Appl.190 (2021), pp. 915-930. · Zbl 07403127
[42] Wang, K. and Desai, J., On the convergence rate of the augmented Lagrangian-based parallel splitting method, Optim. Methods Softw.34 (2019), pp. 278-304. · Zbl 1407.65069
[43] Xu, H.K., Dey, S., and Vetrivel, V., Notes on a neural network approach to inverse variational inequalities, Optimization70 (2021), pp. 901-910. · Zbl 1518.49013
[44] Yang, J.F., Dynamic power price problem: An inverse variational inequality approach, J. Ind. Manag. Optim.4 (2008), pp. 673-684. · Zbl 1157.91421
[45] Yang, W.H. and Han, D.R., Linear convergence of the alternating direction method of multipliers for a class of convex optimization problems, SIAM. J. Numer. Anal.54 (2016), pp. 625-640. · Zbl 1342.90138
[46] Yin, L.L., Liu, H.W., and Yang, J., Modified golden ratio algorithms for pseudomonotone equilibrium problems and variational inequalities, Appl. Math.67 (2022), pp. 273-296. · Zbl 1538.47131
[47] Zou, X.J., Gong, D.W., Wang, L.P., and Chen, Z.Y., A novel method to solve inverse variational inequality problems based on neural networks, Neurocomputing173 (2016), pp. 1163-1168.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.