共役勾配法

出典: ORWiki

【きょうやくこうばいほう (conjugate gradient method)】

$n \,$ 次正定値対称行列 $G \,$ に対して, $n \,$ 次元ベクトル $u, v\neq 0 \,$ が $u^{\top}Gv = 0 \,$ を満たすとき, $u \,$ と $v \,$ は $G \,$ に関して互いに共役であるという. $G \,$ をヘッセ行列にもつ狭義凸2次関数を最小化する問題において, 勾配を利用して $G \,$ に関して互いに共役な探索方向を生成する反復法を共役勾配法という. この解法は, 正確な直線探索をすれば高々 $n \,$ 回の反復で最小解を得ることができる. 一般の制約なし最適化問題への拡張も考えられている.