収束

反復を重ねるにつれ解が定まっていくこと。 ただし何を指すかは文脈で変わる。

3 つの意味#

意味	内容
数列としての収束	$x_k\to x^{\star }$ が成り立つ
停止条件を満たした	更新量が閾値未満になり、実装が止まった
実用上の収束	目標値に十分近づいた

論文の「収束した」がどれを指すかで主張の強さが変わる。 ヒューリスティックの多くは 1 を保証しない。

収束の速さ#

$e_k=\Vert x_k-x^{\star }\Vert$ として、

種類	条件	例
線形	$e_{k+1}\le c{e}_k$（$0<c<1$）	勾配降下法
超線形	$e_{k+1}/e_k\to 0$	準 Newton 法
二次	$e_{k+1}\le c{e}_k^2$	Newton 法（解の近く）

二次収束は正しい桁数が反復ごとに倍になる。

何を横軸に取るか#

反復回数で比べると、1 反復のコストが違う手法を不当に扱う。 評価回数（目的関数を何回測ったか）を横軸に取るのが、 ブラックボックス最適化では標準。

CMA-ES は 1 世代で $\lambda$ 回評価するので、 世代数ではなく $\lambda \times$ 世代数で比べる必要がある。

停滞と収束の区別#

改善が止まったとき、最適解に到達したのか、 局所解や平坦地に捕まったのかは区別できない。 CMA-ES の停止条件が 複数用意されているのは、どの理由で止まったかを分けるため。

参考文献#

• Jorge Nocedal, Stephen J. Wright. Numerical Optimization, 2nd ed., §3.3. Springer, 2006. https://doi.org/10.1007/978-0-387-40065-5
• Nikolaus Hansen et al. COCO: A Platform for Comparing Continuous Optimizers in a Black-Box Setting. Optimization Methods and Software 36(1), 2021. https://doi.org/10.1080/10556788.2020.1808977