A method for solving a general multi-valued complementarity problem

I. V. Konnov ; I. A. Pastukhov

Izvestiâ vysših učebnyh zavedenij. Matematika, no. 2 (2011), pp. 46-53

Résumé

We propose an extended version of Chandrasekaran's method for general complementarity problems with multi-valued weakly off-diagonally antitone cost mappings. It allows one either to construct a sequence converging to a solution or to recognize that the problem has no solutions. We also suggest versions of Jacobi's methods for multi-valued inclusions subject to one- and two-sided constraints.

Détail

Keywords: complementarity problem, multi-valued mapping, off-diagonal antitonicity, coordinate descent method, multi-valued inclusions.

Bibliographie

[1] Berschanskii Ya. M., Meerov M. V., “Teoriya i metody resheniya zadach dopolnitelnosti”, Avtomatika i telemekhanika, 1983, no. 6, 5–31

[2] Cottle R. W., Pang J. S., Stone R. E., The linear complementarity problem, Academic Press, Boston, 1992 | MR | Zbl

[3] Isac G., Complementarity problems, Springer-Verlag, Berlin, 1992 | MR | Zbl

[4] Facchinei F., Pang J. -S., Finite-dimensional variational inequalities and complementarity problems, v. I, Springer-Verlag, Berlin, 2003

[5] Facchinei F., Pang J. -S., Finite-dimensional variational inequalities and complementarity problems, v. II, Springer-Verlag, Berlin, 2003

[6] Konnov I. V., Equilibrium models and variational inequalities, Elsevier, Amsterdam, 2007 | MR

[7] Nikaido Kh., Vypuklye struktury i matematicheskaya ekonomika, Mir, M., 1972

[8] Polterovich V. M., Spivak V. A., “Otobrazheniya s valovoi zamenimostyu v teorii ekonomicheskogo ravnovesiya”, Itogi nauki i tekhn. Sovremen. probl. matem., 19, VINITI, M., 1982, 111–154 | MR | Zbl

[9] Lapin A. V., “Domain decomposition and parallel solution of free boundary problems”, Tr. matem. tsentra im. N. I. Lobachevskogo, 13, DAS, Kazan, 2001, 90–126

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

[11] Konnov I. V., Kostenko T. A., “Mnogoznachnaya smeshannaya zadacha dopolnitelnosti”, Izv. vuzov. Matematika, 2004, no. 12, 28–36 | MR

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

[13] Allevi E., Gnudi A., Konnov I. V., “An extended Gauss–Seidel method for a class of multi-valued complementarity problems”, Optimization Letters, 2:4 (2008), 543–553 | DOI | MR | Zbl

[14] Konnov I. V., “Metody koordinatnogo spuska s relaksatsiei dlya mnogoznachnoi zadachi dopolnitelnosti”, Zhurn. vychisl. matem. i matem. fiz., 49:6 (2009), 1021–1036 | MR | Zbl

[15] Konnov I. V., “Iterative algorithms for multi-valued inclusions with $Z$ mappings”, J. Comput. and Appl. Math., 206:1 (2007), 358–365 | DOI | MR | Zbl

[16] Chandrasekaran R., “A special case of the complementarity pivot problem”, Operations Research, 7 (1970), 263–268 | MR

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

[18] Bagrinovskii K. A., Osnovy soglasovaniya planovykh reshenii, Nauka, M., 1977 | MR