一次アクティブセット法 (FOAS)
[handle_solve_bounds_foas
| e04kff
| e04kfc
]
一次法の実装は普遍的で広く使用されているだけでなく、産業界が課す問題サイズの絶え間ない増大という課題にも耐えることが実証されています。最も注目すべきは統計学での応用で、例えば対数線形モデルのパラメータ較正、条件付きランダムフィールド(L2正則化)、ロジスティック多クラス回帰など、多くのものがあります。一次法、特に共役勾配法は50年以上にわたって研究対象となっており、今も改良が続けられています。
FOASは、大規模な境界制約付き非線形最適化のための一次非線形共役法です。このソルバーは、一次導関数が利用可能であるか、比較的_安価に_推定できる非常に大規模な問題(数万以上の変数)に理想的です。
e04kfはnAG最適化モデリングスイート共通ハンドルインターフェースの一部でもあります。スイート内のソルバーのインターフェースの明確さと一貫性を提供し、互換性のあるソルバー間の切り替えを容易にします。
以下の例は、FOASを使用して境界制約付き2次元版のロゼンブロック関数を解く簡単な使用法を示しています。これはソルバーのパフォーマンスを測定およびプロファイリングするための古典的なテスト関数です。この例のソースはrosenbrock2d.htmで利用可能です。
図1. 2次元ロゼンブロック関数、(左)最小値は黄色の点でx=(1,1)に示されています。右側は境界制約付きバージョンで、紫の点線は境界上の制約された解点への経路を示しています。
詳細情報
- FOAS情報ページ
- nAG Library for PythonにおけるFOAS
- FOASドキュメントページ [ C | Fortran ]
- 例 [ Python例 | C例 | Fortran例 ]
nAGソルバー uncon_conjgrd_comp
(e04dg
)の現代的な代替
handle_solve_bounds_foas
(e04kf
)の主要な設計目標の1つは、Mark
12で導入されたCGソルバーe04dg
に対して現代的で魅力的な代替を提供することでした。このソルバーは無制約NLPを対象としていましたが、e04kf
はアクティブセット法を拡張して境界制約付きNLPを解決できるようになりました。
e04kf
にはより最新で現代的な手法が組み込まれており、e04dg
よりもはるかに高速になっています。以下の図2は、114の無制約NLP
CUTEst問題に対するe04kf
とe04dg
の両ソルバーのパフォーマンスプロファイルを示しています。3つのプロットを比較すると、新しいソルバーが時間的に効率的(40%高速)で、一般的にコストが低いことは明らかです:関数と勾配の評価回数が少なくて済みます。
図2.
ソルバーe04kf
とe04dg
を比較するパフォーマンスプロファイル。左の時間プロットでは、線が高いほど高速なソルバーを示します。中央と右のプロットでは、線が高いほど関数(NF)または勾配(NG)の呼び出しが少ないことを表します。3つのプロットすべてにおいて、e04kf
が時間的に40%高速で、関数と勾配の呼び出しが少ないことがわかります。
Mark 25および26からMark 27への移行
uncon_conjgrd_comp (e04dg)
から新しいFOASソルバーhandle_solve_bounds_foas
(e04kff
,
e04kfc
)へのコード移行に関する注意事項とコメント:
Beale関数
この例では、Beale関数の解点を見つけるためにFOASとL-BFGS-B 3.0が取るステップを比較しています。これは、非線形最適化ソルバーのベンチマークに使用される古典的な非凸テスト関数です。
両方のソルバーは関数の最小値を見つけるために使用され、同じ初期点(2, 2)から開始されます。以下の図は、各ソルバーが関数の最小値を見つけるために取るステップのアニメーションを示しています。 これは、BFGSのより保守的なステップと比較して、共役勾配法が取る積極的なステップを示しています。
図3. Beale関数の等高線プロット(細い青線)と、FOAS(赤)とL-BFGS-B 3.0(青)がBeale関数の最小値(3, 0.5)(マゼンタの星印で示されている)を見つけるために取ったステップ。FOASは8ステップ目までに解点の合理的な近似を提供しているのに対し、L-BFGS-Bはまだそれから比較的遠いことがわかります。
参考文献
- Hager W W and Zhang H (2005) A New Conjugate Gradient Method with Guaranteed Descent and an Efficient Line Search. SIAM J. Optim. 16(1) 170–192
- Hager W W and Zhang H (2006a) Algorithm 851: CG DESCENT, a Conjugate Gradient Method with Guaranteed Descent. ACM Trans. Math. Software 32(1) 113–137
- Hager W W and Zhang H (2006b) A New Active Set Algorithm for Box Constrained Optimization. SIAM J. Optim. 17(2) 525–557
- Hager W W and Zhang H (2013) The Limited Memory Conjugate Gradient Method. SIAM J. Optim. 23(4) 2150–2168
- Nocedal J and Wright S J (2006) Numerical Optimization. (2nd Edition) Springer Series in Operations Research, Springer, New York