×

Low-order penalty equations for semidefinite linear complementarity problems. (English) Zbl 1410.90227

Summary: We extend the power penalty method for linear complementarity problem (LCP) [S. Wang and X. Yang, ibid. 36, No. 2, 211–214 (2008; Zbl 1163.90762)] to the semidefinite linear complementarity problem (SDLCP). We establish a family of low-order penalty equations for SDLCPs. Under the assumption that the involved linear transformation possesses the Cartesian P-property, we show that when the penalty parameter tends to infinity, the solution to any equation of this family converges to the solution of the SDLCP exponentially. Numerical experiments verify this convergence result.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C22 Semidefinite programming

Citations:

Zbl 1163.90762
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alizadeh, F., Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim., 5, 1, 13-51, (1995) · Zbl 0833.90087
[2] Baes, M., Convexity and differentiability properties of spectral functions and spectral mappings on Euclidean Jordan algebras, Linear Algebra Appl., 422, 2, 664-700, (2007) · Zbl 1138.90018
[3] Balakrishnan, V.; Wang, F., Semidefinite programming in systems and control theory, (Wolkowicz, H.; Saigal, R.; Vandenberghe, L., Handbook of Semidefinite Programming, International Series in Operations Research and Management Science, vol. 27, (2000), Springer US), 421-441 · Zbl 0957.90527
[4] Boyd, S.; El Ghaoui, L.; Feron, E.; Balakrishnan, V., Linear matrix inequalities in system and control theory, (1994), Society for Industrial and Applied Mathematics · Zbl 0816.93004
[5] Chen, X.; Niu, L.; Yuan, Y., Optimality conditions and a smoothing trust region Newton method for nonlipschitz optimization, SIAM J. Optim., 23, 3, 1528-1552, (2013) · Zbl 1291.90238
[6] Chen, X.; Qi, H., Cartesian P-property and its applications to the semidefinite linear complementarity problem, Math. Program., 106, 1, 177-201, (2006) · Zbl 1134.90508
[7] Chen, X.; Tseng, P., Non-interior continuation methods for solving semidefinite complementarity problems, Math. Program., 95, 3, 431-474, (2003) · Zbl 1023.90046
[8] Francisco Facchinei, J.-S. P., Finite-dimensional variational inequalities and complementarity problems, vols. I and II, (2003), Springer New York · Zbl 1062.90001
[9] Gowda, M. S.; Song, Y., On semidefinite linear complementarity problems, Springer Math. Program., 88, 1, 575-587, (2000) · Zbl 0987.90082
[10] Gowda, M. S.; Song, Y., Some new results for the semidefinite linear complementarity problem, SIAM J. Matrix Anal. Appl., 24, 1, 25-39, (2002) · Zbl 1028.90071
[11] Hao, Z.; Wan, Z.; Chi, X., A power penalty method for second-order cone linear complementarity problems, Oper. Res. Lett., 43, 2, 137-142, (2015) · Zbl 1408.90288
[12] Hao, Z.; Wan, Z.; Chi, X.; Chen, J., A power penalty method for second-order cone nonlinear complementarity problems, J. Comput. Appl. Math., 290, 136-149, (2015) · Zbl 1327.90207
[13] Hu, S.-L.; Huang, Z.-H.; Wang, P., A nonmonotone smoothing Newton algorithm for solving nonlinear complementarity problems, Optim. Methods Softw., 24, 3, 447-460, (2009) · Zbl 1173.90552
[14] Huang, C.; Wang, S., A power penalty approach to a nonlinear complementarity problem, Oper. Res. Lett., 38, 1, 72-76, (2010) · Zbl 1182.90090
[15] Kanzow, C.; Nagel, C., Semidefinite programs: new search directions, smoothing-type methods, and numerical results, SIAM J. Optim., 13, 1, 1-23, (2002) · Zbl 1029.90052
[16] Kojima, M.; Shindoh, S.; Hara, S., Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices, SIAM J. Optim., 7, 1, 86-125, (1997) · Zbl 0872.90098
[17] Löwner, K., Über monotone matrixfunktionen, Math. Z., 38, 1, 177-216, (1934) · JFM 60.0055.01
[18] Shida, M.; Shindoh, S.; Kojima, M., Existence and uniqueness of search directions in interior-point algorithms for the SDP and the monotone SDLCP, SIAM J. Optim., 8, 2, 387-396, (1998) · Zbl 0913.90252
[19] Sim, C.-K.; Zhao, G., Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem, Math. Program., 110, 3, 475-499, (2007) · Zbl 1203.90160
[20] Song, Y. J., On positive semidefinite preserving Stein transformation, J. Appl. Math. Inf., 33, 1-2, 229-234, (2015) · Zbl 1320.90094
[21] Sun, D., The strong second-order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications, Math. Oper. Res., 31, 4, 761-776, (2006) · Zbl 1278.90304
[22] Sun, Z.; Liu, Z.; Yang, X., On power penalty methods for linear complementarity problems arising from American option pricing, J. Global Optim., 63, 1, 165-180, (2015) · Zbl 1321.91115
[23] Sun, D.; Sun, J., Strong semismoothness of the fischer-burmeister SDC and SOC complementarity functions, Math. Program., 103, 3, 575-581, (2005) · Zbl 1099.90062
[24] Sun, D.; Sun, J., Löwner’s operator and spectral functions in Euclidean Jordan algebras, Math. Oper. Res., 33, 2, 421-445, (2008) · Zbl 1218.90197
[25] Tian, B.; Hu, Y.; Yang, X., A box-constrained differentiable penalty method for nonlinear complementarity problems, J. Global Optim., 62, 4, 729-747, (2015) · Zbl 1321.90139
[26] Tseng, P., Merit functions for semi-definite complementarity problems, Math. Program., 83, 1-3, 159-185, (1998) · Zbl 0920.90135
[27] Wang, S.; Yang, X., A power penalty method for linear complementarity problems, Oper. Res. Lett., 36, 2, 211-214, (2008) · Zbl 1163.90762
[28] Yamashita, N.; Fukushima, M., A new merit function and a descent method for semidefinite complementarity problems, (Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, (1999), Springer), 405-420 · Zbl 0969.90087
[29] Zhang, L., A global linear and local quadratic single-tep noninterior continuation method for monotone semidefinite complementarity problems, Acta Math. Sci., 27, 2, 243-253, (2007) · Zbl 1125.65062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.