The linear complementarity problem.

*(English)*Zbl 0757.90078
Computer Science and Scientific Computing. Boston, MA etc.: Academic Press, Inc.. xxiv, 762 p. (1992).

The literature on the linear complementarity problem now comprises of a rich mathematical theory, a variety of algorithms, and a wide range of applications in applied science and technology. This book is fully devoted to a comprehensive treatment of the linear complementarity problem alone, and seems to be first of its kind to meet a long standing demand of researchers and students interested in the subject. It is divided into seven chapters covering all topics of traditional and current importance. An up to date exhaustive list of reference is given at the end.

Chapter 1 gives a precise statement of the linear complementarity problem along with its various equivalent formulations and generalizations. It also includes discussion on a number of source problems from other disciplines, each of which can be projected into the form of a linear complementarity problem, and hence can be solved by using the theory of the linear complementarity problem. Chapter 2 is devoted to an extensive discussion of background material which an interested reader may require for studying the book.

Chapters 3-5 are concerned with questions on the existence and multiplicity of solutions to linear complementarity problems. There are two general approaches to establishing the existence of a solution of a linear complementarity problem; one is the analytic approach and the other is the constructive approach. In Chapter 3, the authors concentrate on the analytic approach. Here they characterize several classes of matrices for which the linear complementary problem is solvable and establish properties of solutions with such class of matrices. They discuss the existence of solutions by constructive methods in Chapters 4 and 5. Chapter 4 covers the better-known pivoting algorithms and their numerous variants. These methods are all finite and require the recursive solution of systems of linear equations. The pivoting methods are not suitable for solving large-scale linear complementarity problems where as iterative methods have their advantages in solving such problems. Chapter 5 is devoted to the study of different iterative methods including matrix splitting methods, damped Newton method, and interior-point methods.

Chapter 6 offers a more geometric view of the linear complementarity problem, based on the concepts of complementary cones and the formulation of the linear complementarity problem in terms of a certain piecewise linear function. In addition, this chapter features the application of degree theory to the study of the local behaviour of the aforementioned piecewise linear function.

Sensitivity analysis of the linear complementarity problem is concerned with the study of the behaviour of solutions of the problem when the data are subject to small changes. The seventh and concluding chapter focusses on this aspect of the linear complementarity problem.

In preparing this book, the authors have made a commendable effort to see that it is self-contained and that it is suitable both as a text and as a reference. Each chapter contains many exercises. These include exercises to reinforce the material discussed in the text, and exercises introducing new material related to that developed in the text. While most of them are not particularly difficult, several of them are rather challenging and may require some careful analysis. At the end of each chapter, some history of the subjects treated in the chapter, attributes for the results that are stated in it, and pointers to the relevant literature are presented in the form of notes and references.

On the whole, the content of the book has been organised in a very systematic manner. All the chapters though unusually lengthy have been written in a lucid and clear style. The authors have attempted to include every major aspect of the linear complementarity problem. The book will be of great value to researchers, academics and students interested in the linear complementarity problem.

Chapter 1 gives a precise statement of the linear complementarity problem along with its various equivalent formulations and generalizations. It also includes discussion on a number of source problems from other disciplines, each of which can be projected into the form of a linear complementarity problem, and hence can be solved by using the theory of the linear complementarity problem. Chapter 2 is devoted to an extensive discussion of background material which an interested reader may require for studying the book.

Chapters 3-5 are concerned with questions on the existence and multiplicity of solutions to linear complementarity problems. There are two general approaches to establishing the existence of a solution of a linear complementarity problem; one is the analytic approach and the other is the constructive approach. In Chapter 3, the authors concentrate on the analytic approach. Here they characterize several classes of matrices for which the linear complementary problem is solvable and establish properties of solutions with such class of matrices. They discuss the existence of solutions by constructive methods in Chapters 4 and 5. Chapter 4 covers the better-known pivoting algorithms and their numerous variants. These methods are all finite and require the recursive solution of systems of linear equations. The pivoting methods are not suitable for solving large-scale linear complementarity problems where as iterative methods have their advantages in solving such problems. Chapter 5 is devoted to the study of different iterative methods including matrix splitting methods, damped Newton method, and interior-point methods.

Chapter 6 offers a more geometric view of the linear complementarity problem, based on the concepts of complementary cones and the formulation of the linear complementarity problem in terms of a certain piecewise linear function. In addition, this chapter features the application of degree theory to the study of the local behaviour of the aforementioned piecewise linear function.

Sensitivity analysis of the linear complementarity problem is concerned with the study of the behaviour of solutions of the problem when the data are subject to small changes. The seventh and concluding chapter focusses on this aspect of the linear complementarity problem.

In preparing this book, the authors have made a commendable effort to see that it is self-contained and that it is suitable both as a text and as a reference. Each chapter contains many exercises. These include exercises to reinforce the material discussed in the text, and exercises introducing new material related to that developed in the text. While most of them are not particularly difficult, several of them are rather challenging and may require some careful analysis. At the end of each chapter, some history of the subjects treated in the chapter, attributes for the results that are stated in it, and pointers to the relevant literature are presented in the form of notes and references.

On the whole, the content of the book has been organised in a very systematic manner. All the chapters though unusually lengthy have been written in a lucid and clear style. The authors have attempted to include every major aspect of the linear complementarity problem. The book will be of great value to researchers, academics and students interested in the linear complementarity problem.

Reviewer: J.Parida (Rourkela)

##### MSC:

90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |

90-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming |

15A99 | Basic linear algebra |

90C20 | Quadratic programming |