On solving linear complementarity problems as bilinear programs

Abstract EN

We introduce a new bilinear programming formulation of the linear complementarity problem.

We explore some of its properties and investigate its relationship to similar known formulations.

Two alternative representations of the linear complementarity problem are easily derived from our formulation: the first is a concave minimization problem over the binary n-cube with an implicitly defined objective function; and the second is the problem of finding a specific polyhedron (parameterized by the binary n-vector) which is supported by a certain hyperplane.

Specialized algorithms for the former problem are left to future research.

A heuristic, based on the latter problem, is developed for finding a starting point for any such specialized algorithm.

Several small numerical examples demonstrate that the heuristic is capable of finding complementary solutions for problems in different matrix classes.