Comparison of three classes of algorithms for the solution of the linear complementarity problem with an H+-matrix

摘要

There are three main classes of iterative methods for the solution of the linear complementarity problem (LCP). In order of appearance these classes are: the “projected iterative methods”, the “(block) modulus algorithms” and the “modulus-based matrix splitting iterative methods”. Which of the three classes of methods is the “best” one to use for the solution of a certain problem is more or less an “open” question despite the fact that the “best” method within each class is known. It is pointed out that by “best” we mean the minimal upper bound of the norm of the matrix operator of the absolute error vector at any iteration step with respect to the norm of the absolute initial error vector. Note that the first and the third classes of methods are iterative ones while the second one is iterative but needs outer (≤n) and unknown number of inner iteration steps to terminate. One of the main objectives of this work is to consider the solution of the LCP with an H+-matrix and compare and decide, theoretically if possible otherwise by numerical experiments, as to which of the three “best” methods is the “best” one to use in practice.