Polyhedral Complementarity Problem With Quasimonotone Decreasing Mappings

Authors

  • Vadim I. Shmyrev Sobolev Institute of Mathematics, Novosibirsk, Russia + Novosibirsk State University, Novosibirsk, Russia

DOI:

https://doi.org/10.2298/YJOR2111016031S

Keywords:

Polyhedral complementarity, piecewise constant mappings, fixed point, duality, monotonicity, algorithm

Abstract

The fixed point problem of piecewise constant mappings in Rn is investigated. This is a polyhedral complementarity problem, which is a generalization of the linear complementarity problem. Such mappings arose in the author’s research on the problem of economic equilibrium in exchange models, where mappings were considered on the price simplex. The author proposed an original approach of polyhedral complementarity, which made it possible to obtain simple algorithms for solving the problem. The present study is a generalization of linear complementarity methods to related problems of a more general nature and reveals a close relationship between linear complementarity and polyhedral complementarity. The investigated method is an analogue of the well-known Lemke method for linear complementarity problems. A class of mappings is described for which the process is monotone, as it is for the linear complementarity problems with positive principal minors of the constraint matrix (class P). It is shown that such a mapping has always unique fixed point.

References

V. I. Shmyrev, ”On an approach to the determination of equilibrium in elementary exchange models”, Soviet Mathematics - Doklady, vol. 27, no 1, pp 230-233, 1983.

V. I. Shmyrev, “An algorithm for finding equilibrium in the linear exchange model with fixed budgets”, Journal of Applied and Industrial Mathematics, vol. 3, no. 4, pp. 505-518, 2009, doi: 10.1134/s1990478909040097.

V. I. Shmyrev, ”An algorithm for the search of equilibrium in the linear exchange model”, Siberian Mathematical Journal, vol. 26, no. 2, pp. 288-300, 1985, doi: 10.1007/bf00968776.

V. I. Shmyrev, ”On the determination of fixed points of pieswise constant monotone mappings in Rn”, Soviet Mathematics - Doklady, vol 24, no 1, pp 88-90, 1981.

K. G. Murty, Linear complementarity, Linear and Nonlinear programming, Berlin: Heldermann, 1988.

C. E. Lemke, ”A survey of complementarity theory”, in inequalities and complementarity problems, John Wiley and Sons, Ltd, pp 213-239, 1980.

V. I. Shmyrev, ”Polyhadral complementarity on a simplex. Method of meeting paths for decreasing quasi-regular mappings”, Trudy Instituta Matematiki i Mekhaniki URO RAN , vol.25, no 2, pp.273-286, 2019.

L. S. Pontryagin, Fundamentals of Combinatorial Topology, Moscow: Nauka, 1986. [In Rassian]

Downloads

Published

2022-12-15

Issue

Vol. 33 No. 2 (2023)

Section

Research Articles

License

Copyright (c) 2023 YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.