Abstract
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 ≥ 0, z ≥ 0} with a single linear affine inequality constraint.
Similar content being viewed by others
References
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).
R.W. Cottle and G.B. Dantzig, “Complementary pivot theory in mathematical programming,”Linear Algebra and its Applications 1 (1968) 103–125.
M.C. Ferris, “Finite termination of the proximal point algorithm,” to appear inMathematical Programming Series A.
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.
A.S. Householder,The Theory of Matrices in Numerical Analysis (Blaisdell, New York, 1964).
O.L. Mangasarian, “Characterizations of bounded solutions of linear complementarity problems,”Mathematical Programming Study 19 (1982) 153–166.
O.L. Mangasarian, “A simple characterization of solution sets of convex programs,”Operations Research Letters 7 (1988) 21–26.
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).
O.L. Mangasarian and R.R. Meyer, “Nonlinear perturbation of linear programs,”SIAM Journal on Control and Optimization 17 (1979) 745–752.
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.
O.L. Mangasarian and T.-H. Shiau, “Error bounds for monotone linear complementarity problems,”Mathematical Programming 36 (1986) 81–89.
J.M. Ortega,Numerical Analysis: A Second Course (Academic Press, New York, 1972).
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.
R.T. Rockafellar, “Monotone operators and the proximal point algorithm,”SIAM Journal on Control and Optimization 14 (1976) 877–898.
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.
Author information
Authors and Affiliations
Additional information
This material is based on research supported by National Science Foundation Grants CCR-8723091 and DCR-8521228 and Air Force Office of Scientific Research Grant AFOSR-86-0172.
Rights and permissions
About this article
Cite this article
Mangasarian, O.L. Error bounds for nondegenerate monotone linear complementarity problems. Mathematical Programming 48, 437–445 (1990). https://doi.org/10.1007/BF01582267
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582267