Linear complementarity, linear and nonlinear programming. (English) Zbl 0634.90037

Murty, K. G.

Sigma Series in Applied Mathematics, 3. Berlin: Heldermann Verlag. XLVIII, 629 p.; DM 148.00 (1988).

The linear complementary slackness theorem, which is a direct corollary of the duality theorem of linear programming, automatically transforms any linear program into the problem of solving a system of linear equations with nonnegative variables.
Since the early stages of the development of algorithms for solving linear programs this approach has been utilized by a number of researchers and extended to quadratic programs with linear constraints. It is the topic of one chapter (no. 16) of a previous book by this author [“Linear and combinatorial programming” (1976; Zbl 0334.90032)].
That chapter 16 has now been expanded to the present book which presents the linear complementarity problems (LCP) as a central topic of the theory of mathematical programming. According to its author “this book is ideally suited for first year graduate level courses in Mathematical Programming”. However it is clear that, in order to use it for such purpose, significant changes in the order of presentation would be necessary as the author himself indicates in the preface. On the other hand the style and degree of sophistication are quite adequate for that kind of teaching and the value of the book as instrument of reference and consultation is beyond doubt.
Chapters 1 through 5 form the core of the book with LCP theory, both linear and quadratic, and related solution algorithms, pivotal, parametric and others, together with numerous examples and applications. A variety of topics more or less related to LCP and treated as such appear in the remaining six chapters. Among them: computational complexity, descent methods (unconstrained and linearly constrained cases), Lagrange multipliers, gradient methods, ellipsoid and Karmarkar type approaches to LCP, etc.
Finally there is an Appendix dealing with basic theory of convex sets and related optimality results (Kuhn-Tucker theorems, separation theorems and others). There is a good selection of exercises and extensive lists of references follow each chapter and the Appendix.

Reviewer: A.G.Azpeitia

MSC:

90C33	Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C30	Nonlinear programming
90C52	Methods of reduced gradient type
90-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
49-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to calculus of variations and optimal control
65K05	Numerical mathematical programming methods
90C99	Mathematical programming
90C05	Linear programming
49M37	Numerical methods based on nonlinear programming
90C20	Quadratic programming
49M29	Numerical methods involving duality

Keywords:

Karmarkar algorithm; linear complementary; computational complexity; descent methods; Lagrange multipliers; gradient methods; ellipsoid; optimality results

Citations:

Zbl 0334.90032