NAG数値計算ライブラリ > NAG Library 数理最適化 > NAGライブラリの最適化関数の収束性能ベンチマーク

NAGライブラリの最適化関数の収束性能ベンチマーク

イントロダクション

本ドキュメントでは、NAG（Numerical Algorithms Group）ライブラリの数理最適化関数の収束性に関する評価を行います。特に、最適化問題において広く利用されるL-BFGS-B（Limited-memory Broyden-Fletcher-Goldfarb-Shanno with Box constraints）と、NAGライブラリが提供する対応する最適化関数との性能比較に焦点を当てます。収束性は、最適化アルゴリズムの性能を評価する上で重要な要素です。

性能比較は、最適化の分野で広く知られ、ベンチマークに適した問題セットを提供するCUTEst（Constrained and Unconstrained Testing Environment）に含まれる130個の非線形計画問題（境界制約ありおよびなし）を用いて行われました。CUTEstは、最適化アルゴリズムの評価において高い信頼性と広範な利用実績を持つベンチマーク環境です。詳細はCUTEstの公式ページをご覧ください。

この調査では、計算時間と勾配評価回数の2点について分析しました。これらの結果を通じて、NAG関数の収束性と効率性の特徴を明らかにし、実際の最適化問題における有用性を確認します。以降のセクションでは、具体的なベンチマーク結果とその分析を詳細に説明します。

性能比較ベンチマーク

以下のグラフは、130個のベンチマーク問題に対するNAG関数とL-BFGS-Bの計算時間の比較結果を示しています。

Solver comparison of 130 problems (time s)

横軸は、各問題に対してより速かった方のソルバーの計算時間を基準とした時間比率を2の冪乗で示しています。例えば、ある問題で速い方のソルバーが10秒かかった場合、横軸が0のところでは基準の10秒と同じ時間、1のところではその2倍の20秒、2のところでは4倍の40秒を意味します。

縦軸は、130個の問題のうち、その時間比率以内で解けた問題の割合を示しています。

グラフの青い線はNAG関数を、オレンジの線はL-BFGS-Bを表しています。

x=0の位置で青い線が約90%の高さにあることから、NAG関数は130個の問題のうち約90%の問題でL-BFGS-Bと同等もしくはより速かったことを示しています。

一方、オレンジの線は同じ位置で約16%の高さにあり、L-BFGS-BがNAGと同等もしくはより速く解けた問題が約16%にとどまっている事を示しています。

これらの合計が100%を超えているのは、一部の問題では両方のソルバーが同じ時間で問題を解いたためです。

さらに、x=1の位置では、NAG関数は130個の問題のうち95%をL-BFGS-Bの2倍以内の時間で解いているのに対し、L-BFGS-BがNAG関数の2倍以内の時間で解けた問題は45%にとどまっています。

特筆すべきは、x=5の位置を見ると、NAG関数は130個の問題のうち99%をL-BFGS-Bの32倍以内の時間で解いているのに対し、L-BFGS-BがNAG関数の32倍以内の時間で解けた問題は95%にとどまっています。これは、L-BFGS-BがNAG関数の32倍以上の時間をかけても解けない問題が5%存在することを意味します。実用上、これはNAG関数の方がより多くの問題に対して収束性が高いことを示しています。

次のグラフは、勾配評価回数の比較結果です。

Solver comparison of 130 problems (df(x) calls)

横軸と縦軸の意味は計算時間の比較と同様です。このグラフでは、ほとんどの問題で両者の勾配評価回数の差が2倍以内に収まっており、勾配評価回数という点では同等の性能を示していることがわかります。

これらの結果から、NAG関数とL-BFGS-Bは勾配評価回数ではほぼ同等の性能を示すものの、計算時間と収束性ではNAG関数の方が優れていることが確認されました。

NAGライブラリの最適化関数の収束性能ベンチマーク

イントロダクション

性能比較ベンチマーク

関連資料

NAGライブラリ最適化機能の詳細

NAG Library for Python 数理最適化スタートガイド

分野別の数理最適化サンプルコード

問題の種類別の数理最適化サンプルコード

NAGライブラリの開発環境