\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

A smoothing Newton method preserving nonnegativity for solving tensor complementarity problems with $ P_0 $ mappings

  • *Corresponding author: Liping Zhang

    *Corresponding author: Liping Zhang

This work is supported by the National Natural Science Foundation of China (Grant No. 12171271)

Abstract Full Text(HTML) Figure(0) / Table(4) Related Papers Cited by
  • In this paper, we prove that the tensor complementarity problem with the $ P_0 $ mapping on the $ n $-dimensional nonnegative orthant is solvable and the solution set is nonempty and compact under mild assumptions. Since the involved homogeneous polynomial is a $ P_0 $ mapping on the $ n $-dimensional nonnegative orthant, the existing smoothing Newton methods are not directly used to solve this problem. So, we propose a smoothing Newton method preserving nonnegativity via a new one-dimensional line search rule for solving such problem. The global convergence is established and preliminary numerical results illustrate that the proposed algorithm is efficient and very promising.

    Mathematics Subject Classification: Primary: 90C33, 90C30; Secondary: 65K10.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  Numerical results for the TCP in Example 5.1

    $ {\bf q} $ $ {\bf{x}} $ Iter NH NormH Time (sec.)
    [-10 0] [2.0976 0.6397] 6 10 3.0591e-14 3.1250e-02
    [0 -5] [0.5077 1.6648] 7 8 8.8818e-16 0.0000e+00
    [-7 -1] [1.8240 0.7709] 7 10 2.6738e-15 3.1250e-02
    [2 -9] [0.2226 2.0724] 7 11 1.9860e-15 0.0000e+00
    [-8 3] [2.0000 0.0000] 7 10 0.0000e+00 3.1250e-02
     | Show Table
    DownLoad: CSV

    Table 2.  Numerical results for the TCP in Example 5.2

    $ {\bf q} $ $ {\bf{x}} $ Iter NH NormH Time (sec.)
    [0 9] [0.3825 0.0000] 4 5 6.6613e-16 0.0000e+00
    [5 3] [0 0] 4 5 0.0000e+00 0.0000e+00
    [-12 9] [3.0000 2.0000] 6 10 5.6843e-14 0.0000e+00
    [2 -3] —It has no solution— 6.2500e-02
    [-8 -5] —It has no solution— 6.2500e-02
     | Show Table
    DownLoad: CSV

    Table 3.  Numerical results for the TCP in Example 5.3

    $ {\bf q} $ $ {\bf{x}} $ Iter NH NormH Time (sec.)
    [0 4] [6.9194 0.0000] 41 42 5.2224e-13 0.0000e+00
    [8 9] [0 0 ] 41 42 8.5937e-13 0.0000e+00
    [-3 -3] [1.4422 1.4422] 5 6 1.4445e-14 0.0000e+00
    [-10 0] — It has no solution — 3.1250e-02
    [5 -3] — It has no solution — 7.8125e-02
    [-12 9] — It has no solution — 2.8125e-01
     | Show Table
    DownLoad: CSV

    Table 4.  Numerical results for the TCP in Example 5.4

    $ {\bf q} $ $ {\bf{x}} $ Iter NH NormH Time (sec.)
    [0 5 8 9] [0.8683 0.0000 0.0000 0.0000] 22 23 6.5455e-13 0.0000e+00
    [0 -5 8 -0.5] [0 1.7100 0.0000 0.7937] 6 9 8.9509e-16 0.0000e+00
    [-7 -1 0.01 0] [1.9001 0.2714 0.0000 0.0001] 24 32 3.6965e-13 7.8125e-02
    [12 -1 -28 0] [0.0000 1.0000 3.0366 0.0001] 23 26 4.2783e-13 0.0000e+00
    [-8 15 0 -23] [2.0000 0.0000 0.0001 2.8439] 23 27 6.3022e-13 1.5625e-02
     | Show Table
    DownLoad: CSV
  • [1] B. W. Bader and T. G. Kolda, et al., Matlab tensor toolbox version 2.6, 2015.
    [2] X. BaiZ. Huang and L. Qi, Global uniqueness and solvability for tensor complementarity problems, J. Optim. Theory Appl., 170 (2016), 72-84. 
    [3] M. CheL. Qi and Y. Wei, Positive-definite tensors to nonlinear complementarity problems, J. Optim. Theory Appl., 168 (2016), 475-487.  doi: 10.1007/s10957-015-0773-1.
    [4] B. Chen and P. T. Harker, A noninterior-point continuation method for linear complementarity problem, SIAM J. Matrix Anal. Appl., 14 (1993), 1168-1190.  doi: 10.1137/0614081.
    [5] B. Chen and P. T. Harker, Smooth approximations to nonlinear complementarity problems, SIAM J. Optim., 7 (1997), 403-420.  doi: 10.1137/S1052623495280615.
    [6] B. Chen and N. Xiu, A global linear and local quadratic non-interior continuation method for nonlinear complementarity problems based on chen-mangasarian smoothing functions, SIAM J. Optim., 9 (1999), 605-623.  doi: 10.1137/S1052623497316191.
    [7] C. Chen and L. Zhang, Finding Nash equilibrium for a class of multi-person noncooperative games via solving tensor complementarity problem, Appl. Numer. Math., 145 (2019), 458-468.  doi: 10.1016/j.apnum.2019.05.013.
    [8] X. ChenL. Qi and D. Sun, Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities, Math. Comp., 67 (1998), 519-540.  doi: 10.1090/S0025-5718-98-00932-6.
    [9] R. W. CottleJ.-S. Pang and  R. E. StoneThe Linear Complementarity Problem, Academic Press, Boston, 1992. 
    [10] S. Du and L. Zhang, A mixed integer programming approach to the tensor complementarity problem, J. Global Optim., 73 (2019), 789-800.  doi: 10.1007/s10898-018-00731-4.
    [11] F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. I and II, Springer, New York, 2003.
    [12] A. Fischer, Solution of monotone complementarity problems with locally lipschitz functions, Math. Program., 76 (1997), 513-532.  doi: 10.1007/BF02614396.
    [13] A. Fischer, A special Newton-type optimization method, Optim., 24 (1992), 269-284.  doi: 10.1080/02331939208843795.
    [14] M.-S. Gowda, Polynomial complementarity problems, Pac. J. Optim., 13 (2017), 227-241. 
    [15] M.-S. Gowda and D. Sossa, Weakly homogeneous variational inequalities and solvability of nonlinear equations over cones, Math. Program., 177 (2019), 149-171.  doi: 10.1007/s10107-018-1263-7.
    [16] J. Han, N. Xiu and H. Qi, Nonlinear Complementarity Theory and Algorithms, Shanghai Science and Technology Press, Shanghai (in Chinese), 2006.
    [17] P. T. Harker and J.-S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications, Math. Program., 48 (1990), 161-220.  doi: 10.1007/BF01582255.
    [18] K. Hotta and A. Yoshise, Global convergence of a class of non-interior point algorithms using the Chen-Harker-Kanzow-Smale functions for nonlinear complementarity problems, Math. Program., 86 (1999), 105-133.  doi: 10.1007/s101070050082.
    [19] Z. HuangJ. HanD. Xu and L. Zhang, The non-interior continuation methods for solving the $P_0$-function nonlinear complementarity problem, Sci. China Math., 44 (2001), 1107-1114.  doi: 10.1007/BF02877427.
    [20] Z. Huang and L. Qi, Formulating an $n$-person noncooperative game as a tensor complementarity problem, Comput. Optim. Appl., 66 (2017), 557-576.  doi: 10.1007/s10589-016-9872-7.
    [21] Z. Huang and L. Qi, Tensor complementarity problems – part I: Basic theory, J. Optim. Theory Appl., 183 (2019), 1-23.  doi: 10.1007/s10957-019-01566-z.
    [22] Z. Huang and L. Qi, Tensor complementarity problems – part III: Applications, J. Optim. Theory Appl., 183 (2019), 771-791.  doi: 10.1007/s10957-019-01573-0.
    [23] Z. HuangL. Qi and D. Sun, Sub-quadratic convergence of a smoothing Newton algorithm for the $P_0$ and monotone LCP, Math. Program., 99 (2004), 423-441.  doi: 10.1007/s10107-003-0457-8.
    [24] Z. HuangY. Suo and J. Wang, On Q-tensors, Pac. J. Optim., 16 (2020), 67-86. 
    [25] C. Kanzow, Some non-interior continuation methods for linear complementarity problems, SIAM J. Matrix Anal. Appl., 17 (1996), 851-868.  doi: 10.1137/S0895479894273134.
    [26] X. MaM. Zheng and Z. Huang, A Note on the nonemptiness and compactness of solution sets of weakly homogeneous variational inequalities, SIAM J. Optim., 30 (2020), 132-148.  doi: 10.1137/19M1237478.
    [27] H. Qi, A regularized smoothing Newton method for box constrained variational inequality problems with $P_0$-functions, SIAM J. Optim., 10 (2000), 315-330.  doi: 10.1137/S1052623497324047.
    [28] L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symb. Comput., 40 (2005), 1302-1324.  doi: 10.1016/j.jsc.2005.05.007.
    [29] L. Qi, H. Chen and Y. Chen, Tensor Eigenvalues and Their Applications, Springer, Singapore, 2018. doi: 10.1007/978-981-10-8058-6.
    [30] L. Qi and Z. Huang, Tensor complementarity problems – part II: Solution methods, J. Optim. Theory Appl., 183 (2019), 365-385.  doi: 10.1007/s10957-019-01568-x.
    [31] L. Qi and Z. Luo, Tensor Analysis: Spectral Theory and Special Tensors, SIAM, Philadelphia, 2017.
    [32] L. Qi and D. Sun, Improving the convergence of non-interior point algorithm for nonlinear complementarity problems, Math. Comp., 69 (2000), 283-304.  doi: 10.1090/S0025-5718-99-01082-0.
    [33] L. QiD. Sun and G. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems, Math. Program., 87 (2000), 1-35.  doi: 10.1007/s101079900127.
    [34] Y. Song and L. Qi, Properties of some classes of structured tensors, J. Optim. Theory Appl., 165 (2015), 854-873.  doi: 10.1007/s10957-014-0616-5.
    [35] Y. Song and L. Qi, Properties of tensor complementarity problem and some classes of structured tensors, Ann. Appl. Math., 33 (2017), 308-323. 
    [36] Y. Song and G. Yu, Properties of solution set of tensor complementarity problem, J. Optim. Theory Appl., 170 (2016), 85-96.  doi: 10.1007/s10957-016-0907-0.
    [37] D. Sun, A regularization Newton method for solving nonlinear complementarity problems, Appl. Math. Optim., 40 (1999), 315-339.  doi: 10.1007/s002459900128.
    [38] Y. WangZ. Huang and L. Qi, Global uniqueness and solvability of tensor variational inequalities, J. Optim. Theory Appl., 177 (2018), 137-152.  doi: 10.1007/s10957-018-1233-5.
    [39] L. Zhang and Z. Gao, Superlinear/quadratic one-step smoothing Newton method for $P_0$-NCP without strict complementarity, Math. Meth. Oper. Res., 56 (2002), 231-241.  doi: 10.1007/s001860200221.
    [40] L. ZhangL. Qi and G. Zhou, M-tensors and some applications, SIAM J. Matrix Anal. Appl., 35 (2014), 437-452.  doi: 10.1137/130915339.
    [41] L. ZhangS.-Y. Wu and T. Gao, Improved smoothing Newton methods for $P_0$ nonlinear complementarity problems, Appl. Math. Comput., 215 (2009), 324-332.  doi: 10.1016/j.amc.2009.04.088.
    [42] X. Zhao and J. Fan, A semidefinite method for tensor complementarity problems, Optim. Meth. Softw., 34 (2019), 758-769.  doi: 10.1080/10556788.2018.1439489.
  • 加载中

Tables(4)

SHARE

Article Metrics

HTML views(382) PDF downloads(316) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return