The linear complementarity problem / Richard W. Cottle, Jong-Shi Pang, Richard E. Stone

Bibliogr. p. 701-751. Index

In this book, the authors attempt to include every major aspect of the LCP. They cover all topics of traditional and current importance, presenting them in a style consistent with a contemporary point of view, and providing the most comprehensive available list of references. This monograph is intended for readers with some background in linear algebra, linear programming and real analysis. All seven chapters of this volume are divided into sections. The opening chapter sets forth a precise statement of the linear complementarity problem and then offers a selection of settings in which such problems arise. Chapter 1 includes a number of other topics, such as equivalent formulations and generalizations of the LCP. The essential background materials needed for the rest of the book is collected in Chapter 2. Chapter 3 is concerned with questions on the existence and multiplicity to linear complementarity problems. Chapter 4 covers the better-known pivoting algorithms (notably principal pivoting methods and Lemke’s method) for solving linear complementarity problems of various kinds; parametric versions are also presented. Algorithms of the latter sort (e.g., matrix splitting methods, a damped Newton method, and interior-point methods) are treated in Chapter 5. Chapter 6 offers a more geometric view of the linear complementarity problem. The concluding Chapter 7 focuses on sensitivity and stability analysis, the study of how small changes in the data affect various aspects of the problem (zbMath)