An algorithm for the linear complementarity problem

Abstract

A practical algorithm for solving the linear complementarity problem is presented. This algorithm is based on the n-cycle algorithm, which is known to converge if M is a nondegenerate Q-matrix. A brief survey of other available algorithms is also given. Some typical test results are included.

Keywords:

• linear complementarity problem
• complementarity
• n-cycle algorithm
• Bard's algorithm
• quadratic programming
• nonlinear programming
• numerical stability
• stable algorithm
• implicit pivoting

C.R. Categories:

• 5.41
• 5.49

†Current address: Department of Mathematics, Michigan State University, East Lansing, Michigan 48824, U.S.A. Most of this work is contained in the author's thesis submitted in partial fulfillment of the requirements for the Ph.D. degree at The University of Michigan.

†Current address: Department of Mathematics, Michigan State University, East Lansing, Michigan 48824, U.S.A. Most of this work is contained in the author's thesis submitted in partial fulfillment of the requirements for the Ph.D. degree at The University of Michigan.

Notes

†Current address: Department of Mathematics, Michigan State University, East Lansing, Michigan 48824, U.S.A. Most of this work is contained in the author's thesis submitted in partial fulfillment of the requirements for the Ph.D. degree at The University of Michigan.