線形相補性問題

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

$n\times n$行列$M$と$n$次元ベクトル$q$が与えられているとき, 任意の$i$ ($i=1, \dots, n$)に対して, \[ x_i \ge 0, \ (Mx+q)_{i} \ge 0, \ x_i (Mx+q)_{i} = 0 % \quad (i=1,\dots,n) \] となる点$x\in {\bf R}^n$を求める問題. 双行列ゲーム, 2次計画問題などの重要な問題が線形相補性問題に帰着できる.