A Semidefinite Relaxation Method for Linear and Nonlinear Complementarity Problems with Polynomials

doi:10.1007/s40305-023-00491-3

Abstract

Abstract: This paper considers semidefinite relaxation for linear and nonlinear complementarity problems. For some particular copositive matrices and tensors, the existence of a solution for the corresponding complementarity problems is studied. Under a general assumption, we show that if the solution set of a complementarity problem is nonempty, then we can get a solution by the semidefinite relaxation method; while if it does not have a solution, we can obtain a certificate for the infeasibility. Some numerical examples are given.

Key words: Semidefinite relaxation, Linear complementarity problem, Nonlinear complementarity problem, Tensor complementarity problem

CLC Number:

Jin-Ling Zhao, Yue-Yang Dai. A Semidefinite Relaxation Method for Linear and Nonlinear Complementarity Problems with Polynomials[J]. Journal of the Operations Research Society of China, 2025, 13(1): 268-286.

TrendMD

References

[1] Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Academic, Boston (1992)
[2] Mangasarian, O.L.: Solution of symmetric linear complementarity problems by iterative methods. J. Optim. Theory Appl. 22, 465-485(1977)
[3] Ahn, B.H.: Solution of nonsymmetric linear complementarity problems by iterativemethods. J. Optim. Theory Appl. 33, 175-185(1981)
[4] Chen, B., Harker, P.T.: A non-interior-point continuationmethod for linear complementarity problems. SIAM J. Matrix Anal. Appl. 14, 1168-1190(1993)
[5] Facchinei, F., Pang, J.-S.: Finite Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)
[6] Bai, Z.-Z.: Modulus-based matrix splitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl. 17, 917-933(2010)
[7] Bai, Z.-Z., Zhang, L.-L.: Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems. Numer. Algorithms 62, 59-77(2013)
[8] Li, D.K., Wang, L., Liu, Y.Y.: A relaxation general two-sweep modulus-based matrix splitting iteration method for solving linear complementarity problems. J. Comput. Appl. Math. 409, 114140(2022)
[9] Han, J., Xiu, N., Qi, H.D.: Nonlinear Complementarity Theory and Algorithms. Shanghai Science and Technology Press, Shanghai (2006). (in Chinese)
[10] Huang, Z.H., Qi, L.: Formulating an n-person noncooperative game as a tensor complementarity problem. Comput. Optim. Appl. 66(3), 557-576(2017)
[11] Huang, Z.H., Qi, L.: Tensor complementarity problems - Part I: basic theory. J. Optim. Theory Appl. 183(1), 1-23(2019)
[12] Huang, Z.H., Qi, L.: Tensor complementarity problems - Part III: applications. J. Optim. Theory Appl. 183(3), 771-791(2019)
[13] Zhou, M., Liu, H., Jeng, D.-S., Qi, W., Fang, Q.: Modelling the wave-induced instantaneous liquefaction in a non-cohesive seabed as a nonlinear complementarity problem. Comput. Geotech. 137, 104275(2021)
[14] Fischer, A.: A special Newton-type optimization method. Optimization 24(3-4), 269-284(1992)
[15] Sun, D., Qi, L.: On NCP-functions. Comput. Optim. Appl. 13(1-3), 201-220(1999)
[16] Chen, B., Chen, X., Kanzow, C.: A penalized Fischer-Burmeister NCP-function. Math. Program. 88(1), 211-216(2000)
[17] Chen, J., Pan, S.: A family of NCP functions and a descent method for the nonlinear complementarity problem. Comput. Optim. Appl. 40(3), 389-404(2008)
[18] Chen, C.,Mangasarian,O.L.:A class of smoothingfunctionsfor nonlinear andmixed complementarity problems. Comput. Optim. Appl. 5, 97-138(1996)
[19] Facchinei, F., Soares, J.: A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J. Optim. 7, 225-247(1997)
[20] Qi, H.D., Liao, L.Z.: A smoothing Newton method for general nonlinear complementarity problems. Comput. Optim. Appl. 17, 231-253(2000)
[21] Yamashita, N., Fukushima, M.: Modified Newton methods for solving a semismooth reformulation of monontone complementarity problems. Math. Program. 76, 469-491(1997)
[22] Alcantara, J.H., Chen, J.-S.: Neural networks based on three classes of NCP-functions for solving nonlinear complemenratiry problems. Neurocomputing 359, 102-113(2019)
[23] Potra, F.A., Wright, S.J.: Interior-point methods. J. Comput. Appl. Math. 124, 255-281(2000)
[24] Potra, F.A., Ye, Y.: Interior-point methods for nonlinear complementarity problems. J. Optim. Theory Appl. 88(3), 617-642(1996)
[25] Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control. Optim. 14, 877-898(1976)
[26] Noor, M., Bnouhachem, A.: Modified poximal-pointmethod for nonlinear complementarity problems. J. Comput. Appl. Math. 197(2), 395-405(2006)
[27] Che, M.L., Qi, L., Wei, Y.M.: Positive-definite tensors to nonlinear complementarity problems. J. Optim. Theory Appl. 168(2), 475-487(2016)
[28] Song, Y., Qi, L.: Properties of tensor complementarity problem and some classes of structured tensors. Ann. Appl. Math. 33(3), 308-323(2017)
[29] Song, Y., Qi, L.: Strictly semi-positive tensors and the boundedness of tensor complementarity problems. Optim. Lett. 11(7), 1407-1426(2017)
[30] Ding, W., Luo, Z., Qi, L.: P-tensors, P₀-tensors, and their applications. Linear Algebra Appl. 555, 336-354(2018)
[31] Li, Y., Huang, Z.H., Hu, S.: Connectedness of the solution set of the tensor complementarity problem. J. Math. Anal. Appl. 487, 123965(2020)
[32] Song, Y., Yu, G.H.: Properties of solution set of tensor complementarity problem. J. Optim. Theory Appl. 170, 85-96(2016)
[33] Xu, Y., Gu, W.Z., Huang, Z.H.: Estimations on upper and lower bounds of solutions to a class of tensor complementarity problems. Front. Math. China 14(3), 661-671(2019)
[34] Xie, S.L., Xu, H.R.: A two-level additive Schwarz method for a kind of tensor complementarity problem. Linear Algebra Appl. 584, 394-408(2020)
[35] He, H., Bai, X., Ling, C., Zhou, G.: An index detecting algorithm for a class of TCP(A,q) equipped with nonsingular M-tensors. J. Comput. Appl. Math. 394, 113548(2021)
[36] Wei, P., Wang, X., Wei, Y.: Neural network models for time-varying tensor complementarity problems. Neurocomputing 523, 18-32(2023)
[37] Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of semidefinite programming: Theory, algorithms, and applications. International Series in Operations Research & Management Science, 27. Kluwer Academic Publishers, Boston, MA, (2000)
[38] Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796-817(2001)
[39] Cicconet, F., Almeida, K.C.: Moment-SOS relaxation of the medium term hydrothermal dispatch problem. Electr. Power Energy Syst. 104, 124-133(2019)
[40] Zhao, X., Fan, J.: A semidefinite method for tensor complementarity problems. Optim. Method. Softw. 34(4), 758-769(2019)
[41] Nie, J.: The A-truncated K-moment problem. Found. Comput. Math. 14(6), 1243-1276(2014)
[42] Helton, J., Nie, J.: Semidefinte representation of convex sets. Math. Progr. Ser. A 122(1), 21-64(2010)
[43] Nie, J., Yang, Z., Zhang, X.: A complete semidefinite algorithm for detecting copositive matrices and tensors. SIAM J. Optim. 28(4), 2902-2921(2018)
[44] Lasserre, J.B.: Convex sets with semidefinite representation. Math. Program. 120(2), 457-477(2009)
[45] Nie, J., Zhao, J.: The split feasibility problem with polynomials. Sci. Sinica Math. 51(3), 425-438(2021). (in Chinese)
[46] Hall, M., Newman, M.: Copositive and completely positive quadratic forms. Math. Proc. Cambridge Philos. Soc. 59, 329-333(1963)
[47] Hoffman, A., Pereira, F.: On copositive matrices with -1, 0, 1 entries. J. Combin. Theory Ser. A 14, 302-309(1973)
[48] Helton, J., Nie, J.: Sufficient and necessary conditions for semidefinite representability of convex hulls and sets. SIAM J. Optim. 20(2), 759-791(2009)
[49] Lasserre, J.B.: Convexity in semialgebraic geometry and polynomial optimization. SIAM J. Optim. 19, 1995-2014(2009)
[50] Blekherman, G., Parrilo, P., Thomas, R.: (Eds.). Semidefinite optimization and convex algebraic geometry, MOS-SIAM Series on Optimization, 13. SIAM, (2013)
[51] Reznick, B.: Some concrete aspects of Hilbert’s 17th problem. Contemp. Math. Am. Math. Soc. 253, 251-272(2000)
[52] Putinar, M.: Positive polynomials on compact semi-algebraic sets. Ind. Univ. Math. J. 42, 969-984(1993)
[53] Nie, J.: Certifying convergence of lasserre’s hierarchy via flat truncation. Math. Progr. Ser. A 142(1-2), 485-510(2013)
[54] Nie, J.: Optimality conditions and finite convergence of Lasserre’s hierarchy. Math. Progr. Ser. A. 146, 97-121(2014)
[55] Henrion, D., Lasserre, J., Loefberg, J.: GloptiPoly 3: moments, optimization and semidefinite programming. (2008) http://homepages.laas.fr/henrion/software/gloptipoly3
[56] Pólik, I.: Addendum to the SeDuMi user guide version 1.1. (2005) http://sedumi.ie.lehigh.edu/sedumi/files/sedumi-downloads
[57] Sturm, J.: Using SeDuMi 1.02, A matlab Toolbox for optimizativer over smmetric cones. (2001) http://sedumi.ie.lehigh.edu/sedumi/files/sedumi-downloads