A NEW ALGORITHM FOR SOME LINEAR COMPLEMENTARITY PROBLEMS WIT APPLICATIONS

Abstract

The linear complementarity problem is one of the most widely studied problems in mathematical programming due to its diverse applications in engineering, sciences, and economics. Various algorithms were introduced to solve this problem. These algorithms differ in their complexity, theoretical importance and practical efficiency. In this thesis a new algorithm for positive definite (PD) and positive serfi~definite (PSD) linear complementarity problems (LCPs) is introduced. The algorithm preserves the complementarity and seeks the feasibility of a sequence of points produced during the iterations. This is achieved by starting fro@a point on the boundary on which the complementarity condition is satisfied and then generating a sequence of points on that same boundary. These points converge to the solution. The algorithm exploits the ellipsoid method to find the starting point for both PDLCPs and PSDLCPs. The ellipsoid method is also used to check for the problem feasibility in case of PSDLCPs. The theoretical basis of the algorithm including the convergence and the convergence rate are proved. The convergence rate is then compared with the convergence rate of the ellipsoid algorithm. In some PDLCPs and PSDLCPs that arise in certain applications, a set of active constraints is known apriori. The algorithm is modified to take advantage of this fact to speed up the convergence. Numerical examples are solved to test the algorithm. Practical examples in robotics are also considered. The model presented is concerned with the formulation of the static grasping and quasi-static manipulation of an object by a multifingered robot as a LCP. The solution of this LCP finds the value of the minimal forces and displacements associated with these forces.