【せんけいそうほせいもんだい (linear complementarity problem)】
n × n {\displaystyle n\times n\,} 行列 M {\displaystyle M\,} と n {\displaystyle n\,} 次元ベクトル q {\displaystyle q\,} が与えられているとき, 任意の i {\displaystyle i\,} ( i = 1 , … , n {\displaystyle i=1,\dots ,n\,} )に対して,
x i ≥ 0 , ( M x + q ) i ≥ 0 , x i ( M x + q ) i = 0 ( i = 1 , … , n ) {\displaystyle x_{i}\geq 0,\ (Mx+q)_{i}\geq 0,\ x_{i}(Mx+q)_{i}=0\quad (i=1,\dots ,n)\,}
となる点 x ∈ R n {\displaystyle x\in \mathbf {R} ^{n}\,} を求める問題. 双行列ゲーム, 2次計画問題などの重要な問題が線形相補性問題に帰着できる.
行列
と
次元ベクトル
が与えられているとき, 任意の
(
)に対して,
を求める問題. 双行列ゲーム, 2次計画問題などの重要な問題が線形相補性問題に帰着できる.