Linear complementarity, linear and nonlinear programming.

*(English)*Zbl 0634.90037
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.

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 |