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

Yan Li; Liping Zhang

doi:10.3934/jimo.2022041

Article Contents

2023, Volume 19, Issue 3: 2251-2267. Doi: 10.3934/jimo.2022041

This issue Previous Article Optimal investment, consumption and life insurance strategies under stochastic differential utility with habit formation Next Article

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

Yan Li and
Liping Zhang^,

Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China

^*Corresponding author: Liping Zhang
^*Corresponding author: Liping Zhang

Received: April 30, 2021

Revised: December 31, 2021

Early access: March 2022

Published: March 2023

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

Abstract

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.

Keywords:

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

Citation:

FullText(HTML)

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

Related Papers

Cited by

References

[1]	B. W. Bader and T. G. Kolda, et al., Matlab tensor toolbox version 2.6, 2015.
[2]	X. Bai, Z. Huang and L. Qi, Global uniqueness and solvability for tensor complementarity problems, J. Optim. Theory Appl., 170 (2016), 72-84.
[3]	M. Che, L. 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. Chen, L. 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. Cottle, J.-S. Pang and R. E. Stone, The 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. Huang, J. Han, D. 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. Huang, L. 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. Huang, Y. 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. Ma, M. 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. Qi, D. 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. Wang, Z. 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. Zhang, L. Qi and G. Zhou, M-tensors and some applications, SIAM J. Matrix Anal. Appl., 35 (2014), 437-452. doi: 10.1137/130915339.
[41]	L. Zhang, S.-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.