Linear complementarity problem with upper bounds (Q1823162): Difference between revisions

The linear complementarity problem with upper bounds is studied. The main result of the first part of the paper is that the number of solutions to this problem is odd. The proof parallels the classical proof for \textit{E. Sperner}'s Lemma [``Neuer Beweis für die Invarianz der Dimensionszahlen und des Gebietes'', Abh. Math. Semin., Univ. Hamburg 6, 265-272 (1928)]. In the second part a variable dimension algorithm based on complementary pivoting is described to find such a solution. The notion `variable dimension' is used in the sense that in the solution process a sequence of lower-dimensional problems are solved while always the whole matrix is updated. As noted by the author the algorithm is similar to the one developed by \textit{L. van der Heyden} [Math. Program. 19, 328-364 (1980; Zbl 0442.90090)].