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

Feng-Tien Yu
Dept. of Industrial and Operations Engineering
The University of Michigan, Ann Arbor

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 Feng-Tien Yu at fengtien@umich.edu

Overview

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, Mr. Feng-Tien 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.ps
Chapter 1 Linear Complementarity Problem, Its Geometry and Applicationskat1.ps
Chapter 2 The Complementary Pivot Algorithm and Its Extension to Fixed Point Computing kat2.ps
Chapter 3 Seperation Properties, Principle Pivot Tansforms, Classes of Matrices kat3.ps
Chapter 4 Principal Pivoting Methods for LCP kat4.ps
Chapter 5 The Parametric Linear Complementarity Problem kat5.ps
Chapter 6 Computational Complexity of Complementary Pivot Methods kat6.ps
Chapter 7 Nearest Point Problems on Simplicial Cones kat7.ps
Chapter 8 Polynomially Bounded Algorithms for Some Classes of LCP's kat8.ps
Chapter 9 Iterative Methods for LCP's kat9.ps
Chapter 10 Survey of Descent Based Methods for Unconstrained and Linearly Constrained Minimization kat10.ps
Chapter 11 New Linear Programming Algorithms, and Some Open Problems in Linear Complemetarity kat11.ps
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.ps
Index Subject Index lcpindex.ps

Download

You can download each chapter in postscript format by clicking the link following each chapter in the table of contents. You can also download the compressed version of the entire book by clicking here. The file name is "lcpbook.tgz" and its size is about 2.6 MB.

Last Update on 3/19/99
By Feng-Tien Yu
Email: fengtien@umich.edu.