Abstract
In this paper the main focus is on a stability concept for solutions of a linear complementarity problem. A solution of such a problem is robust if it is stable against slight perturbations of the data of the problem. Relations are investigated between the robustness, the nondegenerateness and the isolatedness of solutions. It turns out that an isolated nondegenerate solution is robust and also that a robust nondegenerate solution is isolated. Since the class of linear complementarity problems with only robust solutions or only nondegenerate solutions is not an open set, attention is paid to Garcia's classG n of linear complementarity problems. The nondegenerate problems inG n form an open set.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.W. Cottle, “Solution rays for a class of complementarity problems,”Mathematical Programming Study 1 (1974) 59–70.
R.W. Cottle, “Some recent developments in linear complementarity theory,” in: R.W. Cottle, F. Giannessi and J-L. Lions, eds.,Variational inequalities and complementarity problems (John Wiley, New York, 1980) pp. 97–104.
R.W. Cottle and G.B. Dantzig, “Complementarity pivot theory of mathematical programming,”Linear Algebra and its Applications 1 (1968) 103–125.
R.D. Doverspike, “Some perturbation results for the linear complementarity problem,”Mathematical Programming 23 (1982) 181–192.
C.B. Garcia, “Some classes of matrices in linear complementarity theory,”Mathematical Programming 5 (1974) 299–310.
C.D. Ha, “Stability of the linear complementarity problem at a solution point,”Mathematical Programming 31 (1985) 327–338.
M.J.M. Jansen, “On the structure of the solution set of a linear complementarity problem,”Cahiers du C.E.R.O. 25 (1983) 41–48.
L.M. Kelly and L.T. Watson, “Erratum: Some perturbation theorems forQ-matrices,”SIAM Journal of Applied Mathematics 34 (1978) 320–321.
C.E. Lemke, “Bimatrix equilibrium points and mathematical programming,”Management Science 11 (1965) 681–689.
C.E. Lemke, “A survey of complementarity theory,” in: R.W. Cottle, F. Giannessi and J-L. Lions, eds.,Variational inequalities and complementarity problems (John Wiley, New York, 1980), pp. 213–239.
O.L. Mangasarian, “Locally unique solutions of quadratic programs, linear and nonlinear complementarity problems,”Mathematical Programming 19 (1980) 200–212.
O.L. Mangasarian, “Characterization of bounded solutions of linear complementarity problems,”Mathematical Programming Study 19 (1982) 153–166.
K.G. Murty, “On the number of solutions to the complementarity problem and spanning properties of complementary cones,”Linear Algebra and its Applications 5 (1972) 65–108.
S.M. Robinson, “Strongly regular generalized equations,”Mathematics of Operations Research 5 (1980) 43–62.
R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970).
A. Tamir, “The complementarity problem of mathematical programming,” Ph.D. dissertation, Case Western Reserve University (Cleveland, OH, 1973).
L.T. Watson, “A variational approach to the linear complementarity problem,” Ph.D. dissertation, Department of Mathematics, University of Michigan (Ann Arbor, MI, 1974).
L.T. Watson, “Some perturbation theorems forQ-matrices,”SIAM Journal of Applied Mathematics 31 (1976) 379–384.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Jansen, M.J.M., Tijs, S.H. Robustness and nondegenerateness for linear complementarity problems. Mathematical Programming 37, 293–308 (1987). https://doi.org/10.1007/BF02591739
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02591739