On the solution of the monotone and nonmonotone Linear Complementarity Problem by an infeasible interior-point algorithm

he use of an Infeasible Interior-Point (IIP) algorithm is investigated for the solution of the Linear Complementary Problem (LCP). Some monotone an nonmonotone LCPs from different sources are solved by two versions of the IIP algorithm, which differ on the line-search technique that computes the stepsize. The first version, denoted by SIIP, employs the simple maximum ratio technique commonly used in IIP methods for linear programming. On the other hand the second variant GIIP incorporates a more sophisticated Armijo-type line-search technique, that ensures global convergence for the procedure under some hypothesis. The computational experiments indicate that both the variants efficiently monotone LCPs and LCPs with P-matrices. On the contrary, the algorithms face many difficulties for solving some LCPs with Po-matrices and LCPs associated with nonzero sum bimatrix games. However, the algorithm GIIP has succeeded in a large number of these problems than the method SIIP. A third version that employs an iterative solver for finding the search direction is also investigated and seems to be efficient for the solution of the monotone LCP that arises in a spatial equilibrium network structured modelAvailable from Departamento de Matematica, Universidade de Coimbra, 3000 Coimbra, Portugal / FCT - Fundação para o Ciência e a TecnologiaSIGLEPTPortuga