An Implicit Enumeration Procedure for the General Linear Complementarity Problem,
Abstract
An algorithm is presented for solving a quadratic programming formulation of the linear complementarity problem. No assumptions on the problem data are required. The algorithm is designed to solve the problem by implicitly enumerating the 2 superscript n complementary cones. Geometrically, the procedure amounts to searching the extreme points of a sequence of faces of the constraint polyhedron of decreasing dimension. An extension to the procedure for finding all solutions of an arbitrary complementarity problem is also discussed. The procedure has been implemented and tested on forty randomly generated problems (up to fifty dimensional) having dense indefinite defining matrices. The results of these tests demonstrate the superiority of this approach over two competing methods.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1986
- Accession Number
- ADA170397
Entities
People
- Faiz A. Al-khayyal
Organizations
- Georgia Tech