×

zbMATH — the first resource for mathematics

On solving linear complementarity problems by DC programming and DCA. (English) Zbl 1237.90234
Summary: In this paper, we consider four optimization models for solving the linear complementarity (LCP) problems. They are all formulated as DC (difference of convex functions) programs for which the unified DC programming and DCA (DC algorithms) are applied. The resulting DCA are simple: they consist of solving either successive linear programs, or successive convex quadratic programs, or simply the projection of points on \(\mathbb{R}_{+}^{2n}\). Numerical experiments on several test problems illustrate the efficiency of the proposed approaches in terms of the quality of the obtained solutions, the speed of convergence, and so on. Moreover, the comparative results with Lemke algorithm, a well known method for the LCP, show that DCA outperforms the Lemke method.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
Keywords:
LCP; DC programming; DCA
PDF BibTeX Cite
Full Text: DOI
References:
[1] Ahn, B.-H.: Iterative methods for linear complementarity problems with upper bounds on primary variables. Math. Program. 26, 295–315 (1983) · Zbl 0506.90081
[2] Chen, X., Ye, Y.: On smoothing methods for the P 0 matrix linear complementarity problem. SIAM J. Optim. 11(2), 341–363 (2000) · Zbl 0994.65077
[3] Cottle, R., Pang, J., Stone, R.: The Linear Complementarity Problem. Academic Press, San Diego (1992) · Zbl 0757.90078
[4] Fathi, Y.: Computational complexity of LCPs associated with positive definite symmetric matrices. Math. Program. 17, 335–344 (1979) · Zbl 0421.90072
[5] Fernandes, L., Friedlander, A., Guedes, M.C., Judice, J.: Solution of a general linear complementarity problem using smooth optimization and its application to bilinear programming and LCP. Appl. Math. Optim. 43, 1–19 (2001) · Zbl 1033.90132
[6] Fletcher, R.: Practical Methods of Optimization. Wiley, New York (1987). ISBN13:978-0471494638
[7] Floudas, C.A., et al.: Handbook of Test Problems in Local and Global Optimization. Nonconvex Optimization and Its Applications, vol. 33. Kluwer Academic, Dordrecht (1999). XV · Zbl 0943.90001
[8] Judice, J., Faustino, A.M., Ribeiro, I.M.: On the solution of NP-hard linear complementarity problems. Top 10(1), 125–145 (2002) · Zbl 1006.90082
[9] Geiger, C., Kanzow, C.: On the resolution of monotone complementarity problems. Comput. Optim. Appl. 5(2), 155–173 (1996) · Zbl 0859.90113
[10] Krause, N., Singer, Y.: Leveraging the margin more carefully In: Proceedings of the 21st International Conference on Machine Learning, ICML, 2004, Banff, Alberta, Canada, p. 63 (2004). ISBN:1-58113-828-5
[11] Le Thi, H.A., Pham Dinh, T.: Solving a class of linearly constrained indefinite quadratic problems by DC algorithms. J. Glob. Optim. 11(3), 253–285 (1997) · Zbl 0905.90131
[12] Le Thi, H.A., Pham Dinh, T.: The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133, 23–46 (2005) · Zbl 1116.90122
[13] Liu, Y., Shen, X., Doss, H.: Multicategory {\(\psi\)}-learning and support vector machine: computational tools. J. Comput. Graph. Stat. 14, 219–236 (2005)
[14] Murty, K.G.: Linear Complementarity, Linear and Nonlinear Programming. Sigma Series in Applied Mathematics, vol. 3. Heldermann, Berlin (1988), · Zbl 0634.90037
[15] Pardalos, P.M.: The linear complementarity problem. In: Gomez, S., Hennart, J.P. (eds.) Advances in Optimization and Numerical Analysis, pp. 39–49. Kluwer Academic, Norwell (1994). · Zbl 0821.90118
[16] Pardalos, P.M., Rosen, J.B.: Global optimization approach to the linear complementarity problem. SIAM J. Sci. Stat. Comput. 92, 341–353 (1988) · Zbl 0646.65051
[17] Pardalos, P.M., Vavasis, S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1(1), 15–22 (1991) · Zbl 0755.90065
[18] Pardalos, P.M., Ye, Y.: A class of linear complementarity problems solvable in polynomial time. Linear Algebra Appl. 152, 3–17 (1991) · Zbl 0742.65054
[19] Pham Dinh, T., Le Thi, H.A.: Convex analysis approach to d.c. programming: theory, algorithms and applications. Acta Math. Vietnam. 22(1), 289–355 (1997) · Zbl 0895.90152
[20] Pham Dinh, T., Le Thi, H.A.: D.c. optimization algorithms for solving the trust region subproblem. SIAM J. Optim. 8(2), 476–505 (1998) · Zbl 0913.65054
[21] Ronan, C., Fabian, S., Jason, W., Léon, B.: Trading convexity for scalability. In: Proceedings of the 23rd International Conference on Machine Learning, ICML 2006, Pittsburgh, Pennsylvania, pp. 201–208 (2006). ISBN:1-59593-383-2
[22] Schnörr, C., Schüle, T., Weber, S.: Variational reconstruction with DC-programming. In: Herman, G.T., Kuba, A. (eds.) Advances in Discrete Tomography and Its Applications. Birkhäuser, Boston (2007) · Zbl 1130.65066
[23] Schüle, T., Schnörr, C., Weber, S., Hornegger, J.: Discrete tomography by convex-concave regularization and d.c. programming. Discrete Appl. Math. 151, 229–243 (2005) · Zbl 1131.68571
[24] Sherali, H., Krishnamurty, R., Al-Khayyal, F.: Enumeration approach for linear complementarity problems based on a reformulation-linearization technique. J. Optim. Theory Appl. 99, 481–507 (1998) · Zbl 0911.90328
[25] Zhao, Y.-B., Li, D.: A globally and locally superlinearly convergent non-interior-point algorithm for P0 LCPs. SIAM J. Optim. 13(4), 1195–1221 (2003) · Zbl 1039.90081
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.