A projection algorithm for positive definite linear complementarity problems with applications

Abstract

A projection algorithm for positive definite linear complementarity problems is introduced. The algorithm incorporates the basic idea of gradient projection algorithms. A new descent direction, which will be referred to as the vector of centers, is used instead of the negative of the objective function gradient. This descent direction is kept fixed throughout the iterations, thus reducing the computational effort of computing a search direction by per step. The algorithm exploits the ellipsoid algorithm to find an advanced starting point on the boundary of the feasible region. Accordingly, the algorithm is warm-started and the number of iterations required to reach the solution is reduced. Starting from this point, the algorithm generates a series of boundary points that approaches the solution by projecting the proposed descent direction onto the feasible region. A numerical example is solved and a practical example in the simulation of rigid body dynamics is given to demonstrate the usage of the algorithm in solving such types of problem.

Keywords:

• Mathematical programming
• linear complementarity problems
• convex quadratic programming
• linear programming
• rigid body dynamics

Jel Classification:

• C60
• C61