正定値行列

$$x^{\top }Ax>0\text{for all }x\ne 0$$

（$\ge 0$ なら半正定値。）通常は対称な行列について言う。

同値な条件#

• すべての固有値が正
• すべての首座小行列式が正（Sylvester の判定法）
• $A=L{L}^{\top }$ とコレスキー分解できる

実装ではコレスキー分解を試みて成功するかで判定するのが最も速く安定。

何を意味するか#

$x^{\top }Ax$ は二次形式。 正定値ならこれは上に開いた「お椀」の形になる。

場面	正定値であることの意味
ヘッセ行列	その点で狭義凸。極小点である
共分散行列	どの方向にも分散がある（退化していない）
Newton 法	$-H^{-1}\nabla f$ が下る方向になる
二次計画	問題が凸で、多項式時間で解ける

半正定値との違い#

半正定値（固有値に 0 を含む）は、ある方向に平坦であることを意味する。 共分散行列なら、その方向に分散が無い＝データが低次元の部分空間に載っている。 CMA-ES で共分散行列が半正定値に近づくと、 その方向の探索が止まってしまうため、数値的な下限を設ける実装がある。

参考文献#

• Lloyd N. Trefethen, David Bau III. Numerical Linear Algebra. SIAM, 1997. https://doi.org/10.1137/1.9780898719574
• Stephen Boyd, Lieven Vandenberghe. Convex Optimization, Appendix A. Cambridge University Press, 2004. https://web.stanford.edu/~boyd/cvxbook/