Linear complementarity problems solvable as linear programs

Authors

  • Zakia Kebbiche Department of mathematics, Faculty of Sciences, University of Ferhat Abbas, Sétif1, Algeria

DOI:

https://doi.org/10.33993/jnaat472-1156

Keywords:

linear programming, linear complementarity problem, Lemke's algorithm, Karmarkar algorithm, simplex algorithm, hidden Z-matrix
Abstract views: 319

Abstract

In this paper, we present a theoretical and numerical study of linear complementary problems solvable as linear programs.

We give several examples of linear complementarity problems which can be solved as linear programs using linear programming appraoches. Also, we propose two examples solved by the simplex and Karmarkar's method, while the most widely know method for solving linear complementarity problems "the complementarity pivoting algorithm due to Lemke" has failed to find a solution.

Downloads

Download data is not yet available.

References

R.W. Cottle, J.S. Pang, On solving linear complementarity problems as linear program, Math. Program. Stud., 7 (1978), 88-107, https://doi.org/10.1007/bfb0120784 DOI: https://doi.org/10.1007/BFb0120784

R. W. Cottle, J.S. Pang, R. E. Stone, The linear complementarity problem, Academic press, Boston, 1992, https://doi.org/10.1137/1.9780898719000 DOI: https://doi.org/10.1137/1.9780898719000

O. L. Mangasarian, Solution of linear complementarity problem by linear programming, Tech. Report No. 257, Computer Sciences Dept, Univ. of Wisconsin, Madison, 1975, https://doi.org/10.1007/bfb0080123 DOI: https://doi.org/10.1007/BFb0080123

O. L. Mangasarian, Linear complementarity problems solvable by a single linear program, Math. Program. 10 (1976), 263-270, https://doi.org/10.1007/bf01580671 DOI: https://doi.org/10.1007/BF01580671

O. L. Mangasarian, Characterization of linear complementarity problems as linear program, Math. Program. Stud. 7 (1978), 74-87, https://doi.org/10.1007/bfb0120783 DOI: https://doi.org/10.1007/BFb0120783

K. G. Murty, The linear complementarity, linear and nonlinear programming, Herderman Vertay, Berlin, 1988

S. K. Neogy, On hidden Z-matrices and the linear complementarity problem, Linear Algebra. App. 496 (2016), 81-100, https://doi.org/10.1016/j.laa.2016.01.045 DOI: https://doi.org/10.1016/j.laa.2016.01.045

J.S. Pang, Hidden Z-matrices with positive principal minors, Linear Algebra App., 23 (1979), 201-215, https://doi.org/10.1016/0024-3795(79)90103-4 DOI: https://doi.org/10.1016/0024-3795(79)90103-4

Downloads

Published

2018-12-31

How to Cite

Kebbiche, Z. (2018). Linear complementarity problems solvable as linear programs. J. Numer. Anal. Approx. Theory, 47(2), 150–158. https://doi.org/10.33993/jnaat472-1156

Issue

Vol. 47 No. 2 (2018)

Section

Articles

License

Copyright (c) 2019 Journal of Numerical Analysis and Approximation Theory

Creative Commons License

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

Open Access. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.