[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A Continuation Method for Tensor Complementarity Problems

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

We introduce a Kojima–Megiddo–Mizuno type continuation method for solving tensor complementarity problems. We show that there exists a bounded continuation trajectory when the tensor is strictly semi-positive and any limit point tracing the trajectory gives a solution of the tensor complementarity problem. Moreover, when the tensor is strong strictly semi-positive, tracing the trajectory will converge to the unique solution. Some numerical results are given to illustrate the effectiveness of the method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. SIAM, Philadelphia (2009)

    Book  MATH  Google Scholar 

  2. Song, Y., Qi, L.: Properties of tensor complementarity problem and some classes of structured tensors. Ann. Appl. Math. 33, 308–323 (2017)

    MathSciNet  MATH  Google Scholar 

  3. Bai, X.L., Huang, Z.H., Wang, Y.: Global uniqueness and solvability for tensor complementarity problems. J. Optim. Theory Appl. 170, 72–84 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  4. Che, M., Qi, L., Wei, Y.: Positive-definite tensors to nonlinear complementarity problems. J. Optim. Theory Appl. 168, 475–487 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  5. Chen, H., Qi, L., Song, Y.: Column sufficient tensors and tensor complementarity problems. Front. Math. China 13, 255–276 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  6. Ding, W., Luo, Z., Qi, L.: \(P\)-tensors, \(P_0\)-tensors, and tensor complementarity problem, arXiv:1507.06731 (2015)

  7. Guo, Q., Zheng, M.M., Huang, Z.H.: Properties of \(S\)-tensors. Linear Multilinear Algebra. https://doi.org/10.1080/03081087.2018.1430737 (2018)

  8. Huang, Z.H., Qi, L.: Formulating an \(n\)-person noncoorperative game as a tensor complementarity problem. Comput. Optim. Appl. 66, 557–576 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  9. Liu, D., Li, W., Vong, S.W.: Tensor complementarity problems: the GUS-property and an algorithm. Linear Multilinear Algebra 66, 1726–1749 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  10. Luo, Z., Qi, L., Xiu, N.: The sparsest solutions to Z-tensor complementarity problems. Optim. Lett. 11, 471–482 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  11. Song, Y., Qi, L.: Properties of some classes of structured tensors. J. Optim. Theory Appl. 165, 854–873 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  12. Song, Y., Qi, L.: Tensor complementarity problem and semi-positive tensors. J. Optim. Theory Appl. 169, 1069–1078 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  13. Song, Y., Qi, L.: Strictly semi-positive tensors and the boundedness of tensor complementarity problems. Optim. Lett. 11, 1407–1426 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  14. Song, Y., Yu, G.: Properties of solution set of tensor complementarity problem. J. Optim. Theory Appl. 170, 85–96 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  15. Wang, X., Chen, H., Wang, Y.: Solution structures of tensor complementarity problem. Front. Math. China 13, 935–945 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  16. Wang, Y., Huang, Z.H., Bai, X.L.: Exceptionally regular tensors and tensor complementarity problems. Optim. Methods Softw. 31, 815–828 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  17. Qi, L., Chen, H., Chen, Y.: Tensor Eigenvalues and Their Applications. Springer, Singapore (2018)

    Book  MATH  Google Scholar 

  18. Facchinei, F., Pang, J.S.: Finite Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)

    MATH  Google Scholar 

  19. Xie, S.L., Li, D.H., Xu, H.R.: An iterative method for finding the least solution of the tensor complementarity problem. J. Optim. Theory Appl. 175, 119–136 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  20. Kojima, M., Megiddo, N., Mizuno, M.: A general framework of continuation methods for complementarity problems. Math. Oper. Res. 18, 945–963 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  21. Kojima, M., Megiddo, N., Noma, T.: Homotopy continuation method for nonlinear complementarity problems. Math. Oper. Res. 16, 754–774 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  22. Kojima, M., Mizuno, M., Noma, T.: A new continuation method for complementarity problems with uniform \(P\)-functions. Math. Oper. Res. 14, 107–113 (1989)

    MathSciNet  MATH  Google Scholar 

  23. Xu, Q., Dang, C.: A new homotopy method for solving non-linear complementarity problems. Optimization 57, 681–689 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  24. Zhao, Y.B., Li, D.: On a new homotopy continuation trajectory for nonlinear complementarity problems. Math. Oper. Res. 26, 119–146 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  25. Chen, L., Han, L., Zhou, L.: Computing tensor eigenvalues via homotopy methods. SIAM J. Matrix Anal. Appl. 37, 290–319 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  26. Han, L.: A homotopy method for solving multilinear systems with M-tensors. Appl. Math. Lett. 69, 49–54 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  27. Ni, Q., Qi, L.: A quadratically convergent algorithm for finding the largest eigenvalue of a nonnegative homogeneous polynomial map. J. Global Optim. 61, 627–641 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  28. Naber, G.L.: Topological Method in Euclidean Space. Cambridge University Press, London (1980)

    MATH  Google Scholar 

  29. Moré, J.J.: Global methods for nonlinear complementarity problems. Math. Oper. Res. 21, 589–614 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  30. Allgower, E.L., Georg, K.: Numerical Continuation Methods, an Introduction, Springer Series in Computational Mathematics, vol. 13. Springer, Berlin (1990)

    Google Scholar 

  31. Bader, B.W., Kolda, T.G., et al.: MATLAB Tensor Toolbox Version 2.6 (2015)

  32. Leykin, A., Verschelde, J., Zhao, A.: Newton’s method with deflation for isolated singularities of polynomial systems. Theor. Comput. Sci. 359, 111–122 (2006)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The author would like to thank the two anonymous reviewers for their constructive comments and suggestions that have improved the paper. He also thanks Wen Li and Dongdong Liu for providing him their MATLAB code for the MNN method and Yun-Bin Zhao for the discussion of the continuation methods for nonlinear complementarity problems.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Michigan-Flint, Flint, MI, 48502, USA

    Lixing Han

Authors
  1. Lixing Han
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lixing Han.

Additional information

Communicated by Guoyin Li.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Han, L. A Continuation Method for Tensor Complementarity Problems. J Optim Theory Appl 180, 949–963 (2019). https://doi.org/10.1007/s10957-018-1422-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-018-1422-2

Keywords

Mathematics Subject Classification

Search

Navigation