Linear complementarity problems solvable by a single linear program (Q4127631)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3554016
Language Label Description Also known as
default for all languages
No label defined
    English
    Linear complementarity problems solvable by a single linear program
    scientific article; zbMATH DE number 3554016

      Statements

      Linear complementarity problems solvable by A single linear program (English)
      0 references
      Linear complementarity problems solvable by a single linear program (English)
      0 references
      1976
      0 references
      0 references
      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)).
      0 references

      Identifiers