線形相補性問題

【せんけいそうほせいもんだい (linear complementarity problem)】

$n\times n\,$行列$M\,$と$n\,$次元ベクトル$q\,$が与えられているとき, 任意の$i\,$ ($i=1,\dots ,n\,$)に対して,

$x_{i}\geq 0,\ (Mx+q)_{i}\geq 0,\ x_{i}(Mx+q)_{i}=0\quad (i=1,\dots ,n)\,$

となる点$x\in \mathbf {R} ^{n}\,$を求める問題. 双行列ゲーム, 2次計画問題などの重要な問題が線形相補性問題に帰着できる.