行列分割法

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

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

$\mathbf{find}\,\,x \in X \quad \mathbf{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\,$ を適切に選ぶことにより, 大規模問題を効率的に解くための様々なアルゴリズムが得られる.