On quasi-solution to infeasible linear complementarity problem obtained by Lemke’s method
L. Popov
Open Mathematics, Tome 2 (2004), p. 76-86 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

For a linear complementarity problem with inconsistent system of constraints a notion of quasi-solution of Tschebyshev type is introduced. It’s shown that this solution can be obtained automatically by Lemke’s method if the constraint matrix of the original problem is copositive plus or belongs to the intersection of matrix classes P 0 and Q 0.

Publié le : 2004-01-01
EUDML-ID : urn:eudml:doc:268770 
@article{bwmeta1.element.doi-10_2478_BF02475952,
     author = {L. Popov},
     title = {On quasi-solution to infeasible linear complementarity problem obtained by Lemke's method},
     journal = {Open Mathematics},
     volume = {2},
     year = {2004},
     pages = {76-86},
     zbl = {1053.65045},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_BF02475952}
}

L. Popov. On quasi-solution to infeasible linear complementarity problem obtained by Lemke’s method. Open Mathematics, Tome 2 (2004) pp. 76-86. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_BF02475952/

[1] C.E. Lemke, J.T. Howson: “Equilibrium points of bimatrix games”, SIAM Review., Vol. 12, (1964), pp. 45–78. | Zbl 0128.14804

[2] R.W. Cottle, G.B. Dantzig: “Complementarity pivote theory of mathematical programming”, Linear Algebra and its Applications, Vol. 1, (1968), pp. 103–125. http://dx.doi.org/10.1016/0024-3795(68)90052-9

[3] B.C. Eaves: “The linear complementarity problem”, Management Science., Vol. 17, (1971), pp. 612–634. http://dx.doi.org/10.1287/mnsc.17.9.612 | Zbl 0228.15004

[4] M. Aganagic, R.W. Cottle: “A constructive characterization of Q 0-matrices with nonnegative principal minors”, Math. Programming., Vol. 37, (1987), pp. 223–231. | Zbl 0618.90091

[5] R.W. Cottle, J.S. Pang, R.E. Stone: The Linear Complementarity Problem, Academic Press, Boston, 1992.

[6] O.L. Managasarian: “The ill-posed linear complementarity problem”, In: M.C. Ferris, J.S. Pang: Complementarity and variational problems: State of the Art, SIAM Publications, Philadelphia, PA, 1997, pp. 226–233.

[7] I.I. Eremin: Theory of Linear Optimization, Inverse and Ill-Posed Problems Series. VSP. Utrecht, Boston, Koln, Tokyo, 2002.

[8] I.I. Eremin, Vl.D. Mazurov, N.N. Astaf’ev: Improper Problems of Linear and Convex Programming, Nauka, Moscow. 1983. (in Russian)

[9] Y. Fan, S. Sarkar, and L. Lasdon: “Experiments with successive quadratic programming algorithms”, J. Optim. Theory Appl., VOl. 56, (1988), pp. 359–383. http://dx.doi.org/10.1007/BF00939549 | Zbl 0619.90056

[10] P.E. Gill, W. Murray, A.M. Saunders: “SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization”, SIAM Journal on Optimization, Vol. 12, (2002), pp. 979–1006. http://dx.doi.org/10.1137/S1052623499350013 | Zbl 1027.90111

[11] G. Isac, M.M. Kostreva, M.M. Wiecek: “Multiple objective approximation of feasible but unsolvable linear complementarity problems”, Journal of Optimization Theory and Applications, Vol. 86, (1995), pp. 389–405. http://dx.doi.org/10.1007/BF02192086 | Zbl 0838.90120

[12] L.D. Popov: “On the approximative roots of maximal monotone mapping”, Yugoslav Journal of Operations Research, Vol. 6, (1996), pp. 19–32. | Zbl 0851.65043