Geodesic
On the numerical solution of the linear complementarity problem
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 8, pp. 1385-1398 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The well-known linear complementarity problem with definite matrices is considered. It is proposed to solve it using a global optimization algorithm in which one of the basic stages is a special local search. The proposed global search algorithm is tested using a variety of randomly generated problems; a detailed analysis of the computational experiment is given. 
@article{ZVMMF_2009_49_8_a3,
     author = {E. O. Mazurkevich and E. G. Petrova and A. S. Strekalovskii},
     title = {On the numerical solution of the linear complementarity problem},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1385--1398},
     year = {2009},
     volume = {49},
     number = {8},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_8_a3/}
}
TY  - JOUR
AU  - E. O. Mazurkevich
AU  - E. G. Petrova
AU  - A. S. Strekalovskii
TI  - On the numerical solution of the linear complementarity problem
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2009
SP  - 1385
EP  - 1398
VL  - 49
IS  - 8
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_8_a3/
LA  - ru
ID  - ZVMMF_2009_49_8_a3
ER  - 
%0 Journal Article
%A E. O. Mazurkevich
%A E. G. Petrova
%A A. S. Strekalovskii
%T On the numerical solution of the linear complementarity problem
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2009
%P 1385-1398
%V 49
%N 8
%U http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_8_a3/
%G ru
%F ZVMMF_2009_49_8_a3
E. O. Mazurkevich; E. G. Petrova; A. S. Strekalovskii. On the numerical solution of the linear complementarity problem. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 8, pp. 1385-1398. http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_8_a3/

[1] Vasilev F. P., Metody optimizatsii, Faktorial-press, M., 2002

[2] Popov L. D., Vvedenie v teoriyu, metody i ekonomicheskie prilozheniya zadach o dopolnitelnosti. Uchebnoe posobie, Izd-vo Uralskogo un-ta, Ekaterinburg, 2001

[3] Pang J. S., “Complementarity problems”, Handbook of Global Optimization, Kluwer Acad. Publ., 1995, 271–338 | MR | Zbl

[4] Chung S. J., “NP-Completeness of the linear complementarity problem”, J. Optimizat. Theory and Applic., 60:3 (1989), 393–399 | DOI | MR | Zbl

[5] Cottle R. W., Pang J. S., Stone R. E., The linear complementarity problem, Academ. Press, New York, 1999 | MR

[6] Simantiraki E. M., Shanno D. F., An infeasible-interior-point method for linear complementarity problems, Rutcor Res. Rept, 1996 | MR

[7] Li L., Kobayashi Y., “A block recursive algorithm for the linear complementarity problem with an $M$-matrix”, Internat. J. Innovative Computing. Information and Control ICIC Internat., 2:6 (2006), 1327–1335

[8] Alefeld G., Wang Z., Shen Z., “Enclosing solutions of linear complementarity problems for $H$-matrices”, Reliable Computing, 10 (2004), 423–435 | DOI | MR | Zbl

[9] Dantzig G. B., Cottle R. W., “Positive (semi-)definite programming”, Nonlinear Programming, North-Holland, Amsterdam, 1967, 55–73 | MR

[10] Lemke E., Howson J. T., “Equilibrium points of bimatrix games”, SIAM J. Appl. Math., 12 (1964), 413–423 | DOI | MR | Zbl

[11] Cottle R. W., “Linear complementarity since 1978”, Variational Analys. and Appls., 79 (2007), 239–257 | DOI | MR

[12] More J. J., “Classes of functions and feasibility conditions in nonlinear complementarity problems”, Math. Program., 6:3 (1974), 327–338 | DOI | MR | Zbl

[13] Tamir A., “Minimality and complementarity problems associated with $Z$-functions and $M$-functions”, Math. Program., 7:1 (1974), 17–31 | DOI | MR | Zbl

[14] Facchinei F., Pang J.-S., Finite-dimensional variational inequalities and complementarity problems, Vol. 1, 2, Springer, Berlin, 2003

[15] Konnov I. V., “Properties of gap functions for mixed variational inequalities”, Siberian J. Numer. Math., 3:3 (2000), 259–270 | Zbl

[16] Konnov I. V., Volotskaya (Mazurkevich) E. O., “Mixed variational inequalities and economic equilibrium problems”, J. Appl. Math., 2:6 (2002), 289–314 | DOI | MR | Zbl

[17] Konov I. V., “Obobschenie algoritma Yakobi dlya zadachi dopolnitelnosti v usloviyakh mnogoznachnosti”, Zh. vychisl. matem. i matem. fiz., 45:7 (2005), 1167–1173 | MR

[18] Konnov I. V., Ali M. S. S., Mazurkevich E. O., “Regularization of nonmonotone variational inequalities”, Appl. Math. and Optimizat., 53:3 (2006), 311–330 | DOI | MR | Zbl

[19] Konnov I. V., “An extension of the Jacobi algorithm for multi-valued mixed complementarity problems”, Optimization, 56:3 (2007), 399–416 | DOI | MR | Zbl

[20] Konnov I. V., Mazurkevich E. O., Ali M. S. S., “On a regularization method for variational inequalities with $P_0$ mappings”, J. Appl. Math. Comput. Sci., 15:1 (2005), 101–110 | MR

[21] Tuy H. D. C., “Optimization: theory, methods and algorithms”, Handbook of Global Optimizat., Kluwer Acad. Publ., 1995, 149–216 | MR | Zbl

[22] Hiriart-Urruty J.-B., “Conditions for global optimization”, Handbook of Global Optimization, Kluwer Acad. Publ., 1995, 1–26 | MR | Zbl

[23] Le Thi Hoai, Pham Dinh Tao, DC programming approaches and DCA for globally solving linear complementarity problems, Res. Rept, Nat. Inst, for Appl. Sci. Rouen, 2004

[24] Nguyen Van Thoai, Yamamoto Y., Yoshise A., “Global optimization method for solving mathematical programs with linear complementarity constraints”, J. Optimizat. and Appl., 124 (2005), 467–490 | DOI | MR

[25] Strekalovskii A. C., Elementy nevypukloi optimizatsii, Nauka, Novosibirsk, 2003

[26] Strekalovskii A. C., “O minimizatsii raznosti dvukh vypuklykh funktsii na dopustimom mnozhestve”, Zh. vychisl. matem. i matem. fiz., 43:3 (2003), 399–409 | MR

[27] Strekalovskii A. C., Orlov A. B., Bimatrichnye igry i bilineinoe programmirovanie, Fizmatlit, M., 2007

[28] Dash optimization, http://www.dashoptimization.com/

[29] Nocedal J., Wright S. J., Numerical optimization, Springer-Verlag, New York – Berlin – Heidelberg, 2000 | MR

[30] http://pages.cs.wisc.edu/ferris/path.html