Error bounds for nondegenerate monotone linear complementarity problems. (English) Zbl 0716.90094

Summary: Error bounds and upper Lipschitz continuity results are given for monotone linear complementarity problems with a nondegenerate solution. The existence of a nondegenerate solution considerably simplifies the error bounds compared with problems for which all solutions are degenerate. Thus when a point satisfies the linear inequalities of a nondegenerate complementarity problem, the residual that bounds the distance from a solution point consists of the complementarity condition alone, whereas for degenerate problems this residual cannot bound the distance to a solution without adding the square root of the complementarity condition to it. This and other simplified results are a consequence of the polyhedral characterization of the solution set as the intersection of the feasible region \(\{z| Mz+q\geq 0\), \(z\geq 0\}\) with a single linear affine inequality constraint.


90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C05 Linear programming
Full Text: DOI


[1] I. Adler and D. Gale, ”On the solutions of the positive semidefinite complementarity problem,” Report 75-12, Operations Research Center, University of California, (Berkeley, CA, 1975).
[2] R.W. Cottle and G.B. Dantzig, ”Complementary pivot theory in mathematical programming,”Linear Algebra and its Applications 1 (1968) 103–125. · Zbl 0155.28403
[3] M.C. Ferris, ”Finite termination of the proximal point algorithm,” to appear inMathematical Programming Series A. · Zbl 0741.90051
[4] A.J. Goldman and A.W. Tucker, ”Theory of linear programming,” in: H.W. Kuhn and A.W. Tucker, eds.,Linear Inequalities and Related Systems (Princeton University Press, Princeton, NY, 1956) pp. 53–97. · Zbl 0072.37601
[5] A.S. Householder,The Theory of Matrices in Numerical Analysis (Blaisdell, New York, 1964). · Zbl 0161.12101
[6] O.L. Mangasarian, ”Characterizations of bounded solutions of linear complementarity problems,”Mathematical Programming Study 19 (1982) 153–166. · Zbl 0487.90088
[7] O.L. Mangasarian, ”A simple characterization of solution sets of convex programs,”Operations Research Letters 7 (1988) 21–26. · Zbl 0653.90055
[8] O.L. Mangasarian, ”Least norm solution of non-monotone linear complementarity problems,” University of Wisconsin-Madison, Computer Sciences Technical Report #686 (Madison, WI, 1987); to appear in:Kantorovich Memorial Volume (American Mathematical Society, Providence, RI).
[9] O.L. Mangasarian and R.R. Meyer, ”Nonlinear perturbation of linear programs,”SIAM Journal on Control and Optimization 17 (1979) 745–752. · Zbl 0432.90047
[10] O.L. Mangasarian and T.-H. Shiau, ”Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems,”SIAM Journal on Control and Optimization 25 (1987) 583–595. · Zbl 0613.90066
[11] O.L. Mangasarian and T.-H. Shiau, ”Error bounds for monotone linear complementarity problems,”Mathematical Programming 36 (1986) 81–89. · Zbl 0613.90095
[12] J.M. Ortega,Numerical Analysis: A Second Course (Academic Press, New York, 1972). · Zbl 0248.65001
[13] B.T. Polyak and N.V. Tretyakov, ”Concerning an iterative method for linear programming and its economic interpretation,”Economics and Mathematical Methods 8(5) (1972) 740–751.
[14] R.T. Rockafellar, ”Monotone operators and the proximal point algorithm,”SIAM Journal on Control and Optimization 14 (1976) 877–898. · Zbl 0358.90053
[15] A.W. Tucker, ”Dual systems of homogeneous linear relations,” in: H.W. Kuhn and A.W. Tucker, eds.,Linear Inequalities and Related Systems (Princeton University Press, Princeton, NY, 1956) pp. 3–18. · Zbl 0072.37503
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.