Linear and Nonlinear Programming

Katta G. Murty

Dept. of Industrial and Operations Engineering

The University of Michigan, Ann Arbor

The Internet edition of this book has been prepared by

Vincent F. Yu

Dept. of Industrial Management

National Taiwan University of Science and Technology, Taipei, Taiwan

Partial funding for presenting this book on the web

has been provided by the

Spring/Summer Research Grants Program

Office of the Vice President for Research

Horace H. Rackham School of Graduate Studies

The University of Michigan, Ann Arbor

Comments and corrections are very welcome, and

should be sent to Vincent F. Yu at *vincent@mail.ntust.edu.tw*

With partial funding prvided by Rachkam Graduate School of The University of Michigan, Ann Arbor, Dr. Vincent F. Yu completed the job of making the original book entirely available on the web.

This book provides an in-depth and clear treatment of all the important practical, technical, computational, geometric, and mathematical aspects of the Linear Complementarity Problem, Quadratic Programming, and their various applications. It discusses clearly the various algorithms for solving the LCP, presents their efficient implementation for the computer, and discusses their computational complexity. It presents the practical applications of these algorithms and extensions of these algorithms to solve general nonlinear programming problems. Finally, it surveys new methods for solving linear programs, such as Khachiyan's and Karmarkar's.

Chapter 0 | Preface, Table of Contents, Notations | kat0.pdf |

Chapter 1 | Linear Complementarity Problem, Its Geometry and Applications | kat1.pdf |

Chapter 2 | The Complementary Pivot Algorithm and Its Extension to Fixed Point Computing | kat2.pdf |

Chapter 3 | Seperation Properties, Principle Pivot Tansforms, Classes of Matrices | kat3.pdf |

Chapter 4 | Principal Pivoting Methods for LCP | kat4.pdf |

Chapter 5 | The Parametric Linear Complementarity Problem | kat5.pdf |

Chapter 6 | Computational Complexity of Complementary Pivot Methods | kat6.pdf |

Chapter 7 | Nearest Point Problems on Simplicial Cones | kat7.pdf |

Chapter 8 | Polynomially Bounded Algorithms for Some Classes of LCP's | kat8.pdf |

Chapter 9 | Iterative Methods for LCP's | kat9.pdf |

Chapter 10 | Survey of Descent Based Methods for Unconstrained and Linearly Constrained Minimization | kat10.pdf |

Chapter 11 | New Linear Programming Algorithms, and Some Open Problems in Linear Complemetarity | kat11.pdf |

Appendix |
1. Theorems of Alternatives for Systems of Linear Constraints 2. Convex Sets 3. Convex, Concave Functions, Their Properties 4. Optimality Conditions for Smooth Optimization Problems 5. Summary of Some Optimality Conditions 6. Exercises 7. References |
kat12.pdf |

Index | Subject Index | lcpindex.pdf |

Complete | PDF of entire book prepared by Claude LacoursiÃ¨re (claude@hpc2n.umu.se) | lcp-complete.pdf |

*Last Update on 5/6/2010
By Vincent F. Yu
Email: vincent@mail.ntust.edu.tw*