行列分割法

【ぎょうれつぶんかつほう (matrix splitting method)】

行列 $M$, ベクトル $q$ と凸多面体 $X$ により定義される線形変分不等式問題

\[

 \mbox{find} \: x \in X \quad \mbox{s.t.} \: 
 ( z - x )^{\top} ( M x + q ) \geq 0, \: \forall \, z \in X,

\]

に対する反復法. 条件 $M = B + C$ を満たす行列 $B$, $C$ を選び, 変分不等式

\[

 ( z - x )^{\top} ( B x + C x^{(k)} + q ) \geq 0, 
 \: \forall \, z \in X,

\]

の解を $x^{(k+1)}$ とおいて点列 $\{ x^{(k)} \}$ を生成する. 行列 $B$ を適切に選ぶことにより, 大規模問題を効率的に解くための様々なアルゴリズムが得られる.