Linear complementarity problem with upper bounds

DOI10.1016/0377-2217(89)90426-8MaRDI QIDQ1823162zbMATH OpenOpenAlexFDO

Authors Hans-Jakob Lüthi

Publication date 1989

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(89)90426-8

zbMATH Keywords

complementary pivotinglinear complementarityupper boundsvariable dimension algorithm

Mathematics Subject Classification ID

Variational inequalities (49J40) Linear programming (90C05) Quadratic programming (90C20) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Review text

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)].

Recommendations

• scientific article; zbMATH DE number 579399
• scientific article; zbMATH DE number 3982937
• An algorithm for the linear complementarity problem with upper and lower bounds
• Simplicial approximation of solutions to the nonlinear complementarity problem with lower and upper bounds
• scientific article; zbMATH DE number 4011811

Cites work

• A variable dimension algorithm for the linear complementarity problem
• An algorithm for the linear complementarity problem with upper and lower bounds
• On the basic theorem of complementarity

Cited in

(3)

• An algorithm for the linear complementarity problem with upper and lower bounds
• scientific article; zbMATH DE number 4029291 (Why is no real title available?)
• scientific article; zbMATH DE number 579399 (Why is no real title available?)

This page was built for publication: Linear complementarity problem with upper bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1823162)