Linear complementarity problems solvable by a single linear program

Linear programming (90C05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Review text

The principal result of this paper is, that the linear complementarity problem in \(\mathbb R^n\): \[ Mz+q\geq 0,\;z\geq 0,\;z^T(Mz+q)=0\tag{1} \] has a solution, which can be obtained by solving the linear program \[ \{p^Tz\mid Mz+q\geq 0,\;z\geq 0,\;p=r+M^Ts\}=\min! \tag{2} \] where \(M\) satisfies \(MZ_1=Z_2\), \(r^TZ_1+s^TZ_2>0\) and \(Z_1,Z_2\) are \((n,n)\)-matrices of Z-type (real square matrix with non-positive off-diagonal elements). Some earlier papers in this direction with smaller classes of matrices are reviewed, further hints are given, that a number of free boundary problems of fluid mechanics can be solved by solving a problem like (1) with \(M\) a Z-matrix. The paper concludes with two corollaries on finding the least element of a polyhedral set and solving certain quadratic programming problems (in connection with problems of type (1) and (2)).

Recommendations

Cites work

Cited in

(66)

This page was built for publication: Linear complementarity problems solvable by a single linear program

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