Principal pivoting algorithms for a concave generalized linear complementarity problem

The authors discuss a single and a block principal pivoting algorithms for the solution of a linear complementarity problem with finite upper-bounds of the variables (BLCP) when its matrix is negative semi-definite (NSD). They show that both algorithms possess finite convergence when M is a symmetric NSD matrix. The algorithms can still process the BLCP in the unsymmetric case, but the authors have not been able to establish their finite terminations. However, they show that the block algorithm has finite convergence and is strongly polynomial if all the nonzero off diagonal elements of the NSD matrix have the same sign. The same properties are shared by the single method when M is a nonpositive NSD matrix. Computational experience is included to highlight the great efficiency of these two algorithms for the solution of large-scale BLCPs with NSD matrices.