他の同種のソルバーと比較して、大きなパフォーマンス向上が見られる
nAG ライブラリはMark 27で、nAGは大規模な非制約または境界制約付き非線形最適化問題と解くための新しいソルバー handle_solve_bounds_foas (e04kf) を発表しました。このソルバーは、他の選択肢と比較して、パフォーマンスが大幅に向上しています。本ソルバーは非線形共役勾配法に基づいていますが、計算に必要なメモリ量が少なく、数百万以上の変数の問題にも適しています。
大規模非線形最適化問題は以下のように表現できます。
ここでf(x)は一次導関数で滑らかであり、現実のアプリケーションに良く出てきます。 この種の問題は、探索空間がある程度以上大きい（n=105以上）場合、解決が非常に困難になります。 2次導関数(ヘシアン)を評価するのは、時間的にも資源的にも法外なコストがかかるか、不可能な場合が多いです。 一次法は一次導関数(勾配)のみに依存するように設計されており、勾配情報を巧みに利用してf(x)のモデルを構築し、良い探索方向を見つけることができます。共役勾配(CG)や準ニュートン(QN)などの方法がよく研究されており、(1)を解くのによく使われています。
確立された方法の改善
CG法は線形最適化に起源があり、非線形最適化に拡張されています。この手法の主な特徴は、必要メモリ量が少なく、収束速度が速いことです。最近では、数値の悪条件に対処する新しい方法と非常に高速なラインサーチアルゴリズムが導入され、その人気が高まっています。CG法は、単純な急峻降下法と、よりメモリを必要とするQN法との魅力的な妥協点に位置付けられます。
一次法の実装は、広く利用されているだけでなく、産業界が課す増大し続ける問題規模にも耐えられることが実証されています。 特に統計学や機械学習の分野では、対数線形モデルのパラメータ校正や条件付き乱数場（l2正則化）などの応用が注目されています。
最もよく使用されている一次法に、BFGS QNアルゴリズムのメモリ制限付き制約版であるL-BFGS-Bがあります。メインとなる考え方は、限られた量の方向ベクトルと勾配ベクトルを用いて逆ヘシアン行列を近似し、その近似を暗黙的に表現することが挙げられます。最近のCG法は、ヘシアンに対するQN近似によって提供される曲率情報を利用しながら、収束速度と低メモリ要件を維持しているQNの考え方を取り入れています [5]。この組み合わせにより、メモリ制限付きCGはL-BFGS-Bに代わる競争力のある手法となっています。
nAGのe04kfは、L-BFGS-Bと同様の考え方で、制限されたメモリのQN近似を組み込んだ、制約付き非線形CG手法の最新の実装です。この新しいソルバーに実装された手法は、必要メモリが非常に少なく、一次法の分野における画期的な研究に基づいています。
新ソルバーの特徴
- ボックス境界の影響を受ける大規模な非線形問題を解くように設計されています。
- 一次情報のみを使用します。
- 悪条件の問題により数値的な困難が生じた場合にのみヘッセ行列を近似します。
- 最先端の括弧付きラインサーチを組み込んでいます[3]。
- 与えられた点で関数f（x）またはその勾配を評価することができないときに回復する能力。
- メモリ要件はL-BFGS-Bの半分です。 このアルゴリズムでは方向と勾配の情報を個別に保存する必要がありますが、e04kfは最近の方向のみを保存するため、必要メモリ量が半分になります。 L-BFGS-Bを1対1で置き換えることができます。
e04kf は QN 法に代わる競争力のある手法を開発するために設計されました。CUTEstセットの130の問題をベンチマークした結果、e04kfはL-BFGS-B (3.0)よりもかなり高速であることがわかりました。図 1 は、時間呼び出しと勾配呼び出しの性能プロファイルを示しています。(a)と(b)のプロットでソルバーを比較すると、どちらのソルバーもほぼ同じ量の勾配呼び出しを使用していることがわかります(b)が、e04kfは70%の問題を高速に解いています(a)。
図 1：130 の CUTEst 非線形拘束問題と非拘束問題の性能プロファイル。
線が上にあるほどソルバーが高速であることを示します。
(a)の比較指標は時間であり、(b)の比較指標は勾配呼び出し回数である
(a)
(b)
nAGソルバー unconjgrd_compの置き換え (e04dg)
e04kfの主な設計目的の一つは、Mark 12で導入されたCGソルバーuncon_conjgrd_comp (e04dg)の最新かつ魅力的な代替品を提供することでした。e04dgは制約のないNLPを対象としていましたが、e04kfは制約のあるNLPを解くために拡張されただけでなく、顕著な性能向上を提供しています。図 2 は、ソルバー e04kf と e04dg の両方について、CUTEst の制約なし NLP 問題のセットに対する性能プロファイルを使用したベンチマークを示しています。2つのプロットを比較してみると、新しいソルバーの方が時間的にもユーザーのコールバックにおいても効率的であることがわかります。問題の45％をより速く解き（上のプロット）、問題の60％はより少ない勾配評価回数で解いています。（下のプロット）。ベンチマークのタイミングデータは、問題の13％が10倍以上速く解かれ、7％が少なくとも100倍速く解けたことも示しています。これらの結果は、e04dgよりもe04kfの方が明らかに有利であることを示しており、現在uncon_conjgrd_comp (e04dg)を使っている人はアップグレードすることを強く勧めます。
図 ２：114のCUTEstの制約なしNLP問題に関して、ソルバーe04kfとe04dgを比較
(a)の比較指標は時間であり、(b)の比較指標は勾配呼び出し回数である
時間プロット（a）では、線が上にあればあるほどソルバーが速いことを示し、
(b)のプロットでは、線が上にあればあるほど勾配呼び出しの回数が少ないことを示す。
(a)
(b)
問題に適したソルバーの選択
最適化問題を解く際によくある問題は、どのソルバーを使用するかということです。最も強力なソルバーを使用することが必ずしも最良の選択とは限りません。一般的に、e04kfのような単純な1次(勾配)法は、e04stのような2次(ヘシアン)法よりも多くの反復を必要とします。勾配の評価がヘシアンの評価に比べて無視できるほどしかかからない問題では、一次法は非常に競争力があります。反復回数が多いにもかかわらず、全体的なコストはかなり低く抑えることができます。
ここでは例として、e04kf と e04st を使用して、決定空間の値が増加する n の CUTEst COSINE(n) 問題を解いています。図3 は、10 から 1000000 までの n の各インスタンスを解くために e04kf と e04st が必要とする時間をプロットしたものです。サイズが与えらえた後のヘシアン行列の評価と因数分解は無視できないほどのコストがかかることがわかります。事実、n=106の場合、e04kfはe04stよりも18/5=3.6倍高速であることがわかります。このように、解くべき問題の特性を知り、それをソルバーの強さと一致させることは重要です。
図 3：CUTEst COSINE問題の異なるサイズ(n)のインスタンスを解いた場合のe04kfとe04stの時間(s)での性能比較
e04kfはnAG最適化モデリングスイートの一部であり、スイート内のソルバーのインターフェースの明確さと一貫性を提供します。
参考文献
[1] D. C. Liu and J. Nocedal. (1989). On the Limited Memory Method for Large Scale Optimization. Mathematical Programming B. 45 (3) 503-528.
[2] R. H. Byrd, P. Lu and J. Nocedal. (1995). A Limited Memory Algorithm for Bound Constrained Optimization. SIAM Journal on Scientific and Statistical Computing, 16(5) 1190-1208.
[3] W. W. Hager and H. Zhang. (2005). A New Conjugate Gradient Method with Guaranteed Descent and an Efficient Line Search. SIAM J. Optim. 16(1) 170-192.
[4] W. W. Hager and H. Zhang. (2006b). A New Active Set Algorithm for Box Constrained Optimization. SIAM J. Optim. 17(2) 525-557.
[5] W. W. Hager and H. Zhang. (2013). The Limited Memory Conjugate Gradient Method. SIAM J. Optim. 23(4) 2150-2168.