Expected Residual Minimization Method for Stochastic Tensor Variational Inequalities

doi:10.1007/s40305-022-00450-4

Abstract

Abstract: The goal of this paper is to introduce and investigate a model called the stochastic tensor variational inequality (denoted by STVI), which is a natural extension of the stochastic linear complementarity problem and the stochastic affine variational inequality. Firstly, the STVI is transformed into an expected residual minimization (ERM) problem involved the regularized gap function. Then, the properties of the ERM problem are investigated. Finally, a discrete approximation of ERM problem is obtained by quasi-Monte Carlo method. The convergence of optimal solutions and stationary points of the approximation problem are analyzed as well.

Key words: Stochastic tensor variational inequality, Strongly monotone tensor, Level set, Convergence

CLC Number:

Tong-Tong Shang, Guo-Ji Tang. Expected Residual Minimization Method for Stochastic Tensor Variational Inequalities[J]. Journal of the Operations Research Society of China, 2024, 12(4): 1048-1071.

TrendMD

References

[1] Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. vol. I and II. Springer, New York (2003)
[2] Han, J.Y., Xiu, N.H., Qi, H.D.: Nonlinear Complementarity Theory and Algorithms. Shanghai Science and Technology Press, Shanghai (2006). (in Chinese)
[3] Chen, X., Zhang, C., Fukushima, M.: Robust solution of monotone stochastic linear complementarity problems. Math. Program. 117, 51-80(2009)
[4] Chen, X.J., Fukushima, M.: Expected residual minimization method for stochastic linear complementarity problems. Math. Oper. Res. 30, 1022-1038(2005)
[5] Barbagallo, A., Guarino Lo Bianco, S.: Stochastic variational formulation for a general random timedependent economic equilibrium problem. Optim. Lett. 14, 2479-2493(2020)
[6] Luo, M.J., Lin, G.H.: Expected residual minimization method for stochastic variational inequality problems. J. Optim. Theory Appl. 140, 103-116(2009)
[7] Luo, M.J., Lin, G.H.: Convergence results of the ERM method for nonlinear stochastic variational inequality problems. J. Optim. Theory Appl. 142, 569-581(2009)
[8] Fang, H.T., Chen, X.J., Fukushima, M.: Stochastic R₀ matrix linear complementarity problems. SIAM J. Optim. 18, 482-506(2007)
[9] Becker, H., Albera, L., Comon, P., Gribonval, R., Wendling, F., Merlet, I.: Brain-source imaging: from sparse to tensor models. IEEE Signal Process Mag. 32, 100-112(2015)
[10] Qi, L.Q., Yu, G.H., Wu, E.X.: Higher order positive semidefinite diffusion tensor imaging. SIAM J. Imaging Sci. 3, 416-433(2010)
[11] Ng, M., Qi, L.Q., Zhou, G.L.: Finding the largest eigenvalue of a non-negative tensor. SIAM J. Matrix Anal. Appl. 31, 1090-1099(2009)
[12] Qi, L.Q., Wang, F., Wang, Y.: Z-eigenvalue methods for a global polynomial optimization problem. Math. Program. 118, 301-316(2009)
[13] Bai, X.L., Huang, Z.H., Wang, Y.: Global uniqueness and solvability for tensor complementarity problems. J. Optim. Theory Appl. 170, 72-84(2016)
[14] Che, M.L., Qi, L.Q., Wei, Y.M.: Positive definite tensors to nonlinear complementarity problems. J. Optim. Theory Appl. 168(2), 475-487(2016)
[15] Du, S.Q., Zhang, L.P.: Amixed integer programming approach to the tensor complementarity problem. J. Glob. Optim. 73, 789-800(2019)
[16] Hu, S.L., Wang, J., Huang, Z.H.: Error bounds for the solution sets of quadratic complementarity problems. J. Optim. Theory Appl. 179, 983-1000(2018)
[17] Huang, Z.H., Qi, L.Q.: Formulating an n-person noncooperative game as a tensor complementarity problem. Comput. Optim. Appl. 66(3), 557-576(2017)
[18] Luo, Z.Y., Qi, L.Q., Xiu, N.H.: The sparsest solutions to Z-tensor complementarity problems. Optim. Lett. 11, 471-482(2017)
[19] Song, Y.S., Qi, L.Q.: Tensor complementarity problem and semi-positive tensors. J. Optim. Theory Appl. 169, 1069-1078(2016)
[20] Song, Y.S., Qi, L.Q.: Properties of tensor complementarity problem and some classes of structured tensors. Ann. Appl. Math. 33(3), 308-323(2017)
[21] Xu, Y., Gu, W.Z., Huang, Z.H.: Estimations on upper and lower bounds of solutions to a class of tensor complementarity problems. Front. Math. China 14(3), 661-671(2019)
[22] Wang, Y., Huang, Z.H., Qi, L.Q.: Global uniqueness and solvability of tensor variational inequalities. J. Optim. Theory Appl. 177(1), 137-152(2018)
[23] Barbagallo, A., Guarino Lo Bianco, S.: Variational inequalities on a class of structured tensors. J. Nonlinear Convex Anal. 19(5), 711-729(2018)
[24] Che, M.L., Qi, L.Q., Wei, Y.M.: Stochastic R₀ tensors to stochastic tensor complementarity problems. Optim. Lett. 13, 261-279(2019)
[25] Du, S.Q., Che, M.L.,Wei, Y.M.: Stochastic structured tensors to stochastic complementarity problems. Comput. Optim. Appl. 75(3), 649-668(2020)
[26] Ming, Z.Y., Zhang, L.P., Qi, L.Q.: Expected residual minimization method for monotone stochastic tensor complementarity problem. Comput. Optim. Appl. 77, 871-896(2020)
[27] Lathauwer, L.D., Moor, B.D., Vandewalle, J.: On the best rank-1 and rank-(R₁, R₂,…, R_N) approximation of higher-order tensors. SIAM J. Matrix Anal. Appl. 21, 1324-1342(2000)
[28] Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51, 455-500(2009)
[29] Kofidis, E., Regalia, Ph.: On the best rank-1 approximation of higher-order supersymmetric tensors. SIAM J. Matrix Anal. Appl. 23, 863-884(2002)
[30] Fukushima, M.: Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Math. Program. 53, 99-110(1992)
[31] Fukushima, M.: Merit functions for variational inequality and complementarity problems. Nonlinear Optimization and Applications, pp. 155-170. Springer, Boston, MA (1996)
[32] Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia (1992)
[33] Patrick, B.: Probability and Measure. Wiley-Interscience, New York (1995)