Linear Complementarity,
Linear and Nonlinear Programming

Internet Edition

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


This book was first published in 1988 by Heldermann Verlag, Berlin, and has been out of print since 1994. The author has been receiving several enquiries about its availability. So it has been decided to provide public access to this book on the web. Dr. Samer Takriti initially took the compressed postscript files provided by the publisher and posted them on the web. However, these postscript files do not contain figures and the subject index is missing.

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.

Table of Contents

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
Index Subject Index lcpindex.pdf
Complete PDF of entire book prepared by Claude Lacoursière ( lcp-complete.pdf


You can download each chapter in PDF format by clicking the link following each chapter in the table of contents.

Last Update on 5/6/2010
By Vincent F. Yu