Solvability of monotone tensor complementarity problems
Tóm tắt
The tensor complementarity problem is a special instance in the class of nonlinear complementarity problems, which has many applications in multi-person noncooperative games, hypergraph clustering problems and traffic equilibrium problems. Two most important research issues are how to identify the solvability and how to solve such a problem via analyzing the structure of the involved tensor. In this paper, based on the concept of monotone mappings, we introduce a new class of structured tensors and the corresponding monotone tensor complementarity problem. We show that the solution set of the monotone tensor complementarity problem is nonempty and compact under the feasibility assumption. Moreover, a necessary and sufficient condition for ensuring the feasibility is given via analyzing the structure of the involved tensor. Based on the Huber function, we propose a regularized smoothing Newton method to solve the monotone tensor complementarity problem and establish its global convergence. Under some mild assumptions, we show that the proposed algorithm is superlinearly convergent. Preliminary numerical results indicate that the proposed algorithm is very promising.
Tài liệu tham khảo
Bai X L, Huang Z H, Wang Y. Global uniqueness and solvability for tensor complementarity problems. J Optim Theory Appl, 2016, 170: 72–84
Becker S R, Bobin J, Candès E J. NESTA: A fast and accurate first-order method for sparse recovery. SIAM J Imaging Sci, 2011, 4: 1–39
Che M L, Qi L Q, Wei Y M. Positive-definite tensors to nonlinear complementarity problems. J Optim Theory Appl, 2016, 168: 475–487
Che M L, Qi L Q, Wei Y M. Stochastic R0 tensors to stochastic tensor complementarity problems. Optim Lett, 2019, 13: 261–279
Chen B T, Harker P T. A non-interior-point continuation method for linear complementarity problem. SIAM J Matrix Anal Appl, 1993, 14: 1168–1190
Chen B T, Xiu N H. A global linear and local quadratic noninterior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions. SIAM J Optim, 1999, 9: 605–623
Chen C Y, Zhang L P. Finding Nash equilibrium for a class of multi-person noncooperative games via solving tensor complementarity problem. Appl Numer Math, 2019, 145: 458–468
Chen X, Qi L, Sun D. Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities. Math Comp, 1998, 67: 519–540
Clarke F H. Optimization and Nonsmooth Analysis. New York: Wiley, 1983
Du S Q, Che M L, Wei Y M. Stochastic structured tensors to stochastic complementarity problems. Comput Optim Appl, 2020, 75: 649–668
Facchinei F, Pang J S. Finite-Dimensional Variational Inequalities and Complementarity Problems. New York: Springer, 2003
Fischer A. Solution of monotone complementarity problems with locally Lipschitzian functions. Math Program, 1997, 76: 513–532
Gowda M S. Polynomial complementarity problems. Pac J Optim, 2017, 13: 227–241
Gowda M S, Sossa D. Weakly homogeneous variational inequalities and solvability of nonlinear equations over cones. Math Program, 2019, 177: 149–171
Guo Q, Zheng M M, Huang Z H. Properties of S-tensor. Linear Multilinear Algebra, 2019, 67: 685–696
Han J, Xiu N, Qi H. Nonlinear Complementarity Theory and Algorithms (in Chinese). Shanghai: Shanghai Scientific & Technical Publishers, 2006
Harker P T, Pang J S. Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications. Math Program, 1990, 48: 161–220
Hotta K, Yoshise A. Global convergence of a class of non-interior point algorithms using Chen-Harker-Kanzow-Smale functions for nonlinear complementarity problems. Math Program, 1999, 86: 105–133
Huang Z H, Han J Y, Xu D C, et al. The non-interior continuation methods for solving the P0-function nonlinear complementarity problem. Sci China Ser A, 2001, 44: 1107–1114
Huang Z H, Qi L Q. Formulating an n-person noncooperative game as a tensor complementarity problem. Comput Optim Appl, 2017, 66: 557–576
Huang Z H, Qi L Q. Tensor complementarity problems—part I: Basic theory. J Optim Theory Appl, 2019, 183: 1–23
Huang Z H, Qi L Q. Tensor complementarity problems—part III: Applications. J Optim Theory Appl, 2019, 183: 771–791
Huang Z H, Qi L Q, Sun D F. Sub-quadratic convergence of a smoothing Newton algorithm for the P0- and monotone LCP. Math Program, 2004, 99: 423–441
Huber P J. Robust regression: Asymptotics, conjectures and Monte Carlo. Ann Statist, 1973, 1: 799–821
Isac G, Bulavski V A, Kalashnikov V V. Exceptional families, topological degree and complementarity problems. J Global Optim, 1997, 10: 207–225
Isac G, Carbone A. Exceptional families of elements for continuous functions: Some applications to complementarity theory. J Global Optim, 1999, 15: 181–196
Ma X X, Zheng M M, Huang Z H. A note on the nonemptiness and compactness of solution sets of weakly homogeneous variational inequalities. SIAM J Optim, 2020, 30: 132–148
Mifflin R. Semismooth and semiconvex functions in constrained optimization. SIAM J Control Optim, 1977, 15: 959–972
Ming Z Y, Zhang L P, Qi L Q. Expected residual minimization method for monotone stochastic tensor complementarity problem. Comput Optim Appl, 2020, 77: 871–896
Qi H D. A regularized smoothing Newton method for box constrained variational inequality problems with P0-functions. SIAM J Optim, 2000, 10: 315–330
Qi L Q. Eigenvalues of a real supersymmetric tensor. J Symbolic Comput, 2005, 40: 1302–1324
Qi L Q. Symmetric nonnegative tensors and copositive tensors. Linear Algebra Appl, 2013, 439: 228–238
Qi L Q, Chen H B, Chen Y N. Tensor Eigenvalues and Their Applications. Singapore: Springer, 2018
Qi L Q, Huang Z H. Tensor complementarity problems—part II: Solution methods. J Optim Theory Appl, 2019, 183: 365–385
Qi L Q, Luo Z Y. Tensor Analysis: Spectral Theory and Special Tensors. Philadelphia: SIAM, 2017
Qi L Q, Sun D F. Improving the convergence of non-interior point algorithms for nonlinear complementarity problems. Math Comp, 2000, 69: 283–304
Qi L Q, Sun D F, Zhou G L. A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities. Math Program, 2000, 87: 1–35
Qi L Q, Sun J. A nonsmooth version of Newton’s method. Math Program, 1993, 58: 353–367
Robinson S M. Normal maps induced by linear transformations. Math Oper Res, 1992, 17: 691–714
Song Y S, Qi L Q. Properties of some classes of structured tensors. J Optim Theory Appl, 2015, 165: 854–873
Song Y S, Qi L Q. Properties of tensor complementarity problem and some classes of structured tensors. Ann Appl Math, 2017, 33: 308–323
Song Y S, Yu G H. Properties of solution set of tensor complementarity problem. J Optim Theory Appl, 2016, 170: 85–96
Sun D F. A regularization Newton method for solving nonlinear complementarity problems. Appl Math Optim, 1999, 40: 315–339
Sun D F, Qi L Q. Solving variational inequality problems via smoothing-nonsmooth reformulations. J Comput Appl Math, 2001, 129: 37–62
Wang Y, Huang Z H, Qi L Q. Global uniqueness and solvability of tensor variational inequalities. J Optim Theory Appl, 2018, 177: 137–152
Yi C R, Huang J. Semismooth Newton coordinate descent algorithm for elastic-net penalized Huber loss regression and quantile regression. J Comput Graph Statist, 2017, 26: 547–557
Zhang L P, Gao Z Y. Superlinear/quadratic one-step smoothing Newton method for P0-NCP without strict complementarity. Math Methods Oper Res, 2002, 56: 231–241
Zhang L P, Qi L Q, Zhou G L. M-tensors and some applications. SIAM J Matrix Anal Appl, 2014, 35: 437–452
Zhang L P, Wu S Y, Gao T R. Improved smoothing Newton methods for P0 nonlinear complementarity problems. Appl Math Comput, 2009, 215: 324–332