doi: 10.3934/jimo.2021080

Weakening convergence conditions of a potential reduction method for tensor complementarity problems

School of Mathematics, Tianjin University, Tianjin 300350, China

* Corresponding author: Yong Wang

Received  August 2020 Revised  January 2021 Published  April 2021

Fund Project: The second author's work was supported by the National Natural Science Foundation of China (grant number 11871051)

Recently, under the condition that the included tensor in the tensor complementarity problem is a diagonalizable and positive definite tensor, the convergence of a potential reduction method for tensor complementarity problems is verified in [a potential reduction method for tensor complementarity problems. Journal of Industrial and Management Optimization, 2019, 15(2): 429–443]. In this paper, we improve the convergence of this method in the sense that the condition we used is strictly weaker than the one used in the above reference. Preliminary numerical results indicate the effectiveness of the potential reduction method under the new condition.

Citation: Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2021080
References:
[1]

X.-L. BaiZ.-H. Huang and Y. Wang, Global uniqueness and solvability for tensor complementarity problems, J. Optim. Theory Appl., 170 (2016), 72-84.  doi: 10.1007/s10957-016-0903-4.  Google Scholar

[2]

J. M. Borwein and A. S. Lewis, Convex Analysis and Nonlinear Optimization: Theory and Examples, Springer, Berlin, 2006. doi: 10.1007/978-0-387-31256-9.  Google Scholar

[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.  Google Scholar

[4] R. W. CottleJ.-S. Pang and R. E. Stone, The Linear Complementarity Problem, Academic Press, Boston, 1992.   Google Scholar
[5]

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.  Google Scholar

[6]

F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003.  Google Scholar

[7]

H.-B. Guan and D.-H. Li, Linearized methods for tensor complementarity problems, J. Optim. Theory Appl., 184 (2020), 972-987.  doi: 10.1007/s10957-019-01627-3.  Google Scholar

[8]

Q. GuoM.-M. Zheng and Z.-H. Huang, Properties of $S$-tensors, Linear and Multilinear Algebra, 67 (2019), 685-696.  doi: 10.1080/03081087.2018.1430737.  Google Scholar

[9]

L. Han, A continuation method for tensor complementarity problems, J. Optim. Theory Appl., 180 (2019), 949-963.  doi: 10.1007/s10957-018-1422-2.  Google Scholar

[10]

Z. H. 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.  Google Scholar

[11]

Z.-H. Huang and L. Qi, Tensor complementarity problems–Part Ⅰ: Basic theory, J. Optim. Theory Appl., 183 (2019), 1-23.  doi: 10.1007/s10957-019-01566-z.  Google Scholar

[12]

Z.-H. Huang and L. Qi, Tensor complementarity problems–Part Ⅲ: Applications, J. Optim. Theory Appl., 183 (2019), 771-791.  doi: 10.1007/s10957-019-01573-0.  Google Scholar

[13]

M. Kojima, N. Megiddo, T. Noma and A. Yoshise, A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Springer, Berlin, 1991. doi: 10.1007/3-540-54509-3.  Google Scholar

[14]

M. KojimaT. Noma and A. Yoshise, Global convergence in infeasible-interior-point algorithms, Math. Programming, 65 (1994), 43-72.  doi: 10.1007/BF01581689.  Google Scholar

[15]

T. G. Kolda and B. W. Bader, Tensor decompositions and applications, SIAM Rev., 51 (2009), 455-500.  doi: 10.1137/07070111X.  Google Scholar

[16]

D.-H. Li, C.-D. Chen and H.-B. Guan, A lower dimensional linear equation approach to the $M$-tensor complementarity problem, Calcolo, 58 (2021), Paper No. 5, 21 pp. doi: 10.1007/s10092-021-00397-7.  Google Scholar

[17]

D. LiuW. Li and S.-W. Vong, Tensor complementarity problems: The GUS-property and an algorithm, Linear and Multilinear Algebra, 66 (2018), 1726-1749.  doi: 10.1080/03081087.2017.1369929.  Google Scholar

[18]

Z. LuoL. Qi and N. Xiu, The sparsest solutions to $Z$-tensor complementarity problems, Optim. Lett., 11 (2017), 471-482.  doi: 10.1007/s11590-016-1013-9.  Google Scholar

[19]

L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput., 40 (2005), 1302-1324.  doi: 10.1016/j.jsc.2005.05.007.  Google Scholar

[20]

L. Qi, H. Chen and Y. Chen, Tensor Eigenvalues and their Applications, Springer, Singapore, 2018. doi: 10.1007/978-981-10-8058-6.  Google Scholar

[21]

L. Qi and Z.-H. Huang, Tensor complementarity problems–Part Ⅱ: Solution methods, J. Optim. Theory Appl., 183 (2019), 365-385.  doi: 10.1007/s10957-019-01568-x.  Google Scholar

[22]

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.  Google Scholar

[23]

Y. Song and L. Qi, Properties of tensor complementarity problem and some classes of structured tensors, Ann. Appl. Math., 3 (2017), 308-323.   Google Scholar

[24]

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.  Google Scholar

[25]

D. Sun and L. Qi, On NCP-functions, Comput. Optim. Appl., 13 (1999), 201-220.  doi: 10.1023/A:1008669226453.  Google Scholar

[26]

Y. WangZ.-H. 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.  Google Scholar

[27]

S.-L. XieD.-H. Li and H.-R. Xu, An iterative method for finding the least solution to the tensor complementarity problem, J. Optim. Theory Appl., 175 (2017), 119-136.  doi: 10.1007/s10957-017-1157-5.  Google Scholar

[28]

K. ZhangH. Chen and P. Zhao, A potential reduction method for tensor complementarity problems, J. Ind. Manag. Optim., 15 (2019), 429-443.  doi: 10.3934/jimo.2018049.  Google Scholar

show all references

References:
[1]

X.-L. BaiZ.-H. Huang and Y. Wang, Global uniqueness and solvability for tensor complementarity problems, J. Optim. Theory Appl., 170 (2016), 72-84.  doi: 10.1007/s10957-016-0903-4.  Google Scholar

[2]

J. M. Borwein and A. S. Lewis, Convex Analysis and Nonlinear Optimization: Theory and Examples, Springer, Berlin, 2006. doi: 10.1007/978-0-387-31256-9.  Google Scholar

[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.  Google Scholar

[4] R. W. CottleJ.-S. Pang and R. E. Stone, The Linear Complementarity Problem, Academic Press, Boston, 1992.   Google Scholar
[5]

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.  Google Scholar

[6]

F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003.  Google Scholar

[7]

H.-B. Guan and D.-H. Li, Linearized methods for tensor complementarity problems, J. Optim. Theory Appl., 184 (2020), 972-987.  doi: 10.1007/s10957-019-01627-3.  Google Scholar

[8]

Q. GuoM.-M. Zheng and Z.-H. Huang, Properties of $S$-tensors, Linear and Multilinear Algebra, 67 (2019), 685-696.  doi: 10.1080/03081087.2018.1430737.  Google Scholar

[9]

L. Han, A continuation method for tensor complementarity problems, J. Optim. Theory Appl., 180 (2019), 949-963.  doi: 10.1007/s10957-018-1422-2.  Google Scholar

[10]

Z. H. 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.  Google Scholar

[11]

Z.-H. Huang and L. Qi, Tensor complementarity problems–Part Ⅰ: Basic theory, J. Optim. Theory Appl., 183 (2019), 1-23.  doi: 10.1007/s10957-019-01566-z.  Google Scholar

[12]

Z.-H. Huang and L. Qi, Tensor complementarity problems–Part Ⅲ: Applications, J. Optim. Theory Appl., 183 (2019), 771-791.  doi: 10.1007/s10957-019-01573-0.  Google Scholar

[13]

M. Kojima, N. Megiddo, T. Noma and A. Yoshise, A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Springer, Berlin, 1991. doi: 10.1007/3-540-54509-3.  Google Scholar

[14]

M. KojimaT. Noma and A. Yoshise, Global convergence in infeasible-interior-point algorithms, Math. Programming, 65 (1994), 43-72.  doi: 10.1007/BF01581689.  Google Scholar

[15]

T. G. Kolda and B. W. Bader, Tensor decompositions and applications, SIAM Rev., 51 (2009), 455-500.  doi: 10.1137/07070111X.  Google Scholar

[16]

D.-H. Li, C.-D. Chen and H.-B. Guan, A lower dimensional linear equation approach to the $M$-tensor complementarity problem, Calcolo, 58 (2021), Paper No. 5, 21 pp. doi: 10.1007/s10092-021-00397-7.  Google Scholar

[17]

D. LiuW. Li and S.-W. Vong, Tensor complementarity problems: The GUS-property and an algorithm, Linear and Multilinear Algebra, 66 (2018), 1726-1749.  doi: 10.1080/03081087.2017.1369929.  Google Scholar

[18]

Z. LuoL. Qi and N. Xiu, The sparsest solutions to $Z$-tensor complementarity problems, Optim. Lett., 11 (2017), 471-482.  doi: 10.1007/s11590-016-1013-9.  Google Scholar

[19]

L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput., 40 (2005), 1302-1324.  doi: 10.1016/j.jsc.2005.05.007.  Google Scholar

[20]

L. Qi, H. Chen and Y. Chen, Tensor Eigenvalues and their Applications, Springer, Singapore, 2018. doi: 10.1007/978-981-10-8058-6.  Google Scholar

[21]

L. Qi and Z.-H. Huang, Tensor complementarity problems–Part Ⅱ: Solution methods, J. Optim. Theory Appl., 183 (2019), 365-385.  doi: 10.1007/s10957-019-01568-x.  Google Scholar

[22]

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.  Google Scholar

[23]

Y. Song and L. Qi, Properties of tensor complementarity problem and some classes of structured tensors, Ann. Appl. Math., 3 (2017), 308-323.   Google Scholar

[24]

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.  Google Scholar

[25]

D. Sun and L. Qi, On NCP-functions, Comput. Optim. Appl., 13 (1999), 201-220.  doi: 10.1023/A:1008669226453.  Google Scholar

[26]

Y. WangZ.-H. 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.  Google Scholar

[27]

S.-L. XieD.-H. Li and H.-R. Xu, An iterative method for finding the least solution to the tensor complementarity problem, J. Optim. Theory Appl., 175 (2017), 119-136.  doi: 10.1007/s10957-017-1157-5.  Google Scholar

[28]

K. ZhangH. Chen and P. Zhao, A potential reduction method for tensor complementarity problems, J. Ind. Manag. Optim., 15 (2019), 429-443.  doi: 10.3934/jimo.2018049.  Google Scholar

Figure 1.  The relationships among three classes of tensors
Table 1.  Numerical Results for Example 4.1
$ (z^{0})^{\top} $ $ \mathrm{Iter} $ $ \mathrm{Time(s)} $ $ (z^{*})^{\top} $
(1.2, 0.4, 1.6280, 0.1640) 40 0.3584 (0.4642, 0.0000, 0.0000, 0.1000)
(2.4, 0.8, 13.7240, 0.6120) 46 0.3714 (0.4642, 0.0000, 0.0000, 0.1000)
(3.6, 1.2, 46.5560, 1.8280) 49 0.3776 (0.4642, 0.0000, 0.0000, 0.1000)
(4.8, 1.6,110.4920, 4.1960) 52 0.4612 (0.4642, 0.0000, 0.0000, 0.1000)
(6.0, 2.0,215.9000, 8.1000) 54 0.3880 (0.4642, 0.0000, 0.0000, 0.1000)
(7.2, 2.4,373.1480, 13.9240) 56 0.4293 (0.4642, 0.0000, 0.0000, 0.1000)
$ (z^{0})^{\top} $ $ \mathrm{Iter} $ $ \mathrm{Time(s)} $ $ (z^{*})^{\top} $
(1.2, 0.4, 1.6280, 0.1640) 40 0.3584 (0.4642, 0.0000, 0.0000, 0.1000)
(2.4, 0.8, 13.7240, 0.6120) 46 0.3714 (0.4642, 0.0000, 0.0000, 0.1000)
(3.6, 1.2, 46.5560, 1.8280) 49 0.3776 (0.4642, 0.0000, 0.0000, 0.1000)
(4.8, 1.6,110.4920, 4.1960) 52 0.4612 (0.4642, 0.0000, 0.0000, 0.1000)
(6.0, 2.0,215.9000, 8.1000) 54 0.3880 (0.4642, 0.0000, 0.0000, 0.1000)
(7.2, 2.4,373.1480, 13.9240) 56 0.4293 (0.4642, 0.0000, 0.0000, 0.1000)
Table 2.  Numerical Results for Example 4.2
Table 3.  Numerical Results for Example 4.3
$ {q}^{\top} $ $ (z^{0})^{\top} $ $ \mathrm{Iter} $ $ \mathrm{Time(s)} $ $ (z^{*})^{\top} $
$ (-1, 1) $ (2, 1, 28, 2) 47 0.3207 (1, 0, 0, 1)
$ (-1, 1) $ (4.2, 2.1, 1183.3893, 41.8410) 67 0.4496 (1, 0, 0, 1)
$ (-6, -2) $ (2.8, 1.4,149.9690, 3.3782) 52 0.3200 (1.6438, 1.1487, 0, 0)
$ (-6, -2) $ (8, 4, 29690, 1022) 129 1.3179 (1.6438, 1.1487, 0, 0)
$ (36, -19) $ (4, 2,964, 13) 66 0.4528 (1.8384, 1.8020, 0, 0)
$ (36, -19) $ (24, 12, 7216164, 248813) 760 7.4286 (1.8384, 1.8020, 0, 0)
$ {q}^{\top} $ $ (z^{0})^{\top} $ $ \mathrm{Iter} $ $ \mathrm{Time(s)} $ $ (z^{*})^{\top} $
$ (-1, 1) $ (2, 1, 28, 2) 47 0.3207 (1, 0, 0, 1)
$ (-1, 1) $ (4.2, 2.1, 1183.3893, 41.8410) 67 0.4496 (1, 0, 0, 1)
$ (-6, -2) $ (2.8, 1.4,149.9690, 3.3782) 52 0.3200 (1.6438, 1.1487, 0, 0)
$ (-6, -2) $ (8, 4, 29690, 1022) 129 1.3179 (1.6438, 1.1487, 0, 0)
$ (36, -19) $ (4, 2,964, 13) 66 0.4528 (1.8384, 1.8020, 0, 0)
$ (36, -19) $ (24, 12, 7216164, 248813) 760 7.4286 (1.8384, 1.8020, 0, 0)
[1]

Kaili Zhang, Haibin Chen, Pengfei Zhao. A potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 429-443. doi: 10.3934/jimo.2018049

[2]

Mengmeng Zheng, Ying Zhang, Zheng-Hai Huang. Global error bounds for the tensor complementarity problem with a P-tensor. Journal of Industrial & Management Optimization, 2019, 15 (2) : 933-946. doi: 10.3934/jimo.2018078

[3]

Wanbin Tong, Hongjin He, Chen Ling, Liqun Qi. A nonmonotone spectral projected gradient method for tensor eigenvalue complementarity problems. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 425-437. doi: 10.3934/naco.2020042

[4]

Ya Li, ShouQiang Du, YuanYuan Chen. Modified spectral PRP conjugate gradient method for solving tensor eigenvalue complementarity problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020147

[5]

Nicolas Van Goethem. The Frank tensor as a boundary condition in intrinsic linearized elasticity. Journal of Geometric Mechanics, 2016, 8 (4) : 391-411. doi: 10.3934/jgm.2016013

[6]

Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial & Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259

[7]

Jan Boman, Vladimir Sharafutdinov. Stability estimates in tensor tomography. Inverse Problems & Imaging, 2018, 12 (5) : 1245-1262. doi: 10.3934/ipi.2018052

[8]

Michael Anderson, Atsushi Katsuda, Yaroslav Kurylev, Matti Lassas and Michael Taylor. Metric tensor estimates, geometric convergence, and inverse boundary problems. Electronic Research Announcements, 2003, 9: 69-79.

[9]

Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617

[10]

Yanfei Wang, Dmitry Lukyanenko, Anatoly Yagola. Magnetic parameters inversion method with full tensor gradient data. Inverse Problems & Imaging, 2019, 13 (4) : 745-754. doi: 10.3934/ipi.2019034

[11]

H. M. Hastings, S. Silberger, M. T. Weiss, Y. Wu. A twisted tensor product on symbolic dynamical systems and the Ashley's problem. Discrete & Continuous Dynamical Systems, 2003, 9 (3) : 549-558. doi: 10.3934/dcds.2003.9.549

[12]

Meng Ding, Ting-Zhu Huang, Xi-Le Zhao, Michael K. Ng, Tian-Hui Ma. Tensor train rank minimization with nonlocal self-similarity for tensor completion. Inverse Problems & Imaging, 2021, 15 (3) : 475-498. doi: 10.3934/ipi.2021001

[13]

Yiju Wang, Guanglu Zhou, Louis Caccetta. Nonsingular $H$-tensor and its criteria. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1173-1186. doi: 10.3934/jimo.2016.12.1173

[14]

Aleksander Denisiuk. On range condition of the tensor x-ray transform in $ \mathbb R^n $. Inverse Problems & Imaging, 2020, 14 (3) : 423-435. doi: 10.3934/ipi.2020020

[15]

Mirela Kohr, Sergey E. Mikhailov, Wolfgang L. Wendland. Dirichlet and transmission problems for anisotropic stokes and Navier-Stokes systems with L tensor coefficient under relaxed ellipticity condition. Discrete & Continuous Dynamical Systems, 2021, 41 (9) : 4421-4460. doi: 10.3934/dcds.2021042

[16]

Tomáš Oberhuber, Tomáš Dytrych, Kristina D. Launey, Daniel Langr, Jerry P. Draayer. Transformation of a Nucleon-Nucleon potential operator into its SU(3) tensor form using GPUs. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1111-1122. doi: 10.3934/dcdss.2020383

[17]

Tobias Breiten, Sergey Dolgov, Martin Stoll. Solving differential Riccati equations: A nonlinear space-time method using tensor trains. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 407-429. doi: 10.3934/naco.2020034

[18]

Henry O. Jacobs, Hiroaki Yoshimura. Tensor products of Dirac structures and interconnection in Lagrangian mechanics. Journal of Geometric Mechanics, 2014, 6 (1) : 67-98. doi: 10.3934/jgm.2014.6.67

[19]

Xia Li, Yong Wang, Zheng-Hai Huang. Continuity, differentiability and semismoothness of generalized tensor functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020131

[20]

François Monard. Efficient tensor tomography in fan-beam coordinates. Inverse Problems & Imaging, 2016, 10 (2) : 433-459. doi: 10.3934/ipi.2016007

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (22)
  • HTML views (36)
  • Cited by (0)

Other articles
by authors

[Back to Top]