このページの翻訳は最新ではありません。ここをクリックして、英語の最新版を参照してください。
制約なしの最小化は、スカラー関数 f(x)の局所的最小値ベクトル xを見つける問題です。
“制約なし“はxの範囲に制限がないことを意味します。
fminunc信赖域アルゴリズム
非線形最小化に対する信頼領域法
优化工具箱™のソルバーで使用される多くのメソッドは,"信頼領域法" を基にしています。信頼領域法はシンプルなものですが最適化では重要な概念です。
最適化の信頼領域法のアプローチを理解するために制約なし最小化問題を考え,f (x)を最小化します。ここで関数はベクトル引数を取り,スカラーを出力します。n空間の点xを想定し,より小さい関数値へ移動して最小化を行う場合を考えてみましょう。基本的な概念は,シンプルな関数问でfを近似することです。この関数は点xの近傍Nで関数fの挙動をよく表すものです。この近傍が信頼領域です。テストステップsがNにおける最小化(または近似最小化)によって計算されます。信頼領域の部分問題を次に示します。
(1)
f(x+s)の場合、現在の点が x+sに更新されます。そうでない場合は現在の点は変更されず、信頼領域 Nは縮小され、テスト ステップの計算が繰り返されます。
f (x)を最小化するための信頼領域を決める上で重要な問題は,近似问(現在の点xで定義)の選択および計算方法,信頼領域Nの選択および変更方法,信頼領域の部分問題を解く精度です。この節では制約なしの問題に焦点をあてます。変数上に制約があるために複雑度が増す問題については,後節で取り扱います。
標準的な信頼領域法 ([48]) では二次近似 Qは、xにおける Fのテイラー近似のはじめの 2.項によって決められます。近傍 Nは球形または楕円体です。数学的に、信頼領域の部分問題は、次のように表現できます。
(2)
ここでgは現在の点xにおけるfの勾配です。Hはヘッセ行列(2次導関数の対称行列)です。Dは対角スケーリング行列であり、Δ は正のスカラーです。∥ . ∥ は 2 ノルムです。式 2.を解くために適したアルゴリズムがあります ([48]を参照)。このようなアルゴリズムは,Hのすべての固有値と以下の 永年方程式に適用されるニュートン過程の計算を一般的に含みます。
このようなアルゴリズムにより式 2.の正確な解が与えられます。しかしHの因子分解に比例して時間が必要になります。そのために,大規模問題に対しては別のアプローチが必要となります。式 2.に基づく近似とヒューリスティックな方法は文献 ([42]と[50]) で提案されています。优化工具箱のソルバーがサポートする近似アプローチとして、信頼領域法の部分問題を 2.次元の部分空間 ([39]と[42]) に制限します。部分空間 sが計算されると、(部分空間では問題は 2.次元になるため) 完全な次元の固有値 / 固有ベクトルの情報が必要な場合でも式 2.を解く作業は簡単になります。ここでの主な仕事は、部分空間を決定することになります。
2.次元の部分空間 sは、以下に示す前処理付き共役勾配法過程を用いて決められます。ソルバーは s1.と s2.で決まる線形空間として年代を定義します。ここで,s1.は勾配gの方向にあります。s2.は近似ニュートン方向,すなわち以下の解
(3)
または負の曲率の方向です。
(4)
このように年代を選択する背景の考え方は,最急降下方向または負の曲率方向にグローバルな収束を進めることと,ニュートンステップが存在する場合は,これを介して迅速にローカルな収束を達成することです。
信頼領域法の概念を使用した制約なしの最小化の概要は以下になります。
2次元の信頼領域の部分問題の定式化
テストステップ年代を決めるため,式 2.を解きます。
f(x+s)の場合,x=x+sとします。
Δ を調節します。
これら 4.つのステップは、収束するまで繰り返されます。信頼領域の大きさ Δ は標準的な規則に基づいて調整されます。特に、使用するステップが適用されない場合、すなわちf(x+s)≥ f(x)の場合、内点集合は小さくなります。詳細は[46]と[49]を参照してください。
优化工具箱のソルバーは特定の関数 Fの重要かつ特別なケースをいくつか扱います。非線形最小二乗法、二次関数、線形最小二乗法を考えてみましょう。しかし、根底に存在するアルゴリズムは、一般的な場合と同じです。これらの特別な場合は後続の節で説明します。
前処理付き共役勾配法
線形方程式系Hp=–gの大きな対称正定値システムを解く一般的な方法は、前処理付き共役勾配法 (PCG)です。この反復法は、形式 H·vの行列ベクトル積を計算する機能を必要とします。ここで vは任意のベクトルです。対称正定値行列 Mは Hの"前提条件子" です。すなわち、M=C2.です。ここで、C–1HC–1は、条件数の良い行列または分類分けされた固有値をもつ行列です。
最小化の過程で,ヘッセ行列Hが対称と仮定します。しかし、Hは強い最小化子の近傍の中でのみ正定値であることが保証されます。PCGアルゴリズムは,負または0の曲率方向が検出された場合に終了します(DT高清≤ 0)。PCG出力方向pは負の曲率方向またはニュートンシステムHp=–gへの近似解のどちらかです。いずれにせよ、Pは信頼領域法のアプローチで使用される 2.次元部分空間を定義するために役立ちます (非線形最小化に対する信頼領域法を参照)。
fminunc拟牛顿法アルゴリズム
制約なしの最適化の基礎
制約なしの最適化に対して、種々の方法が存在していますが、導関数情報を使うか、使わないかにより大きく分類されます。関数評価のみを使う探索法 (たとえば、纳尔德和米德[30]のシンプレックス探索) は、非線形な問題や多くの不連続点をもつ問題に非常に有効です。勾配法は、一般に最小化される関数の 1.次導関数が連続型であれば非常に有効です。ニュートン法のような高次の項を使う方法は、2.次導関数の情報が既に用意されていたり、簡単に計算できるときにのみ有効です。これは、2.次導関数の情報を得るのに数値微分を使い、非常に多くの計算を必要とするためです。
勾配法は,最小値が存在すると考えられる探索の方向を示すために勾配の情報を使います。この中で最も簡単な方法は,最急降下法で∇f(x)を目的関数の勾配とすると–∇f(x)の方向で探索を行うものです。この方法は最小化される関数が長く狭い谷をもつとき、あまり効果的なものではありません。たとえば、。関数の場合です。
(5)
この関数の最小値はf(x)=0となるx = [1]です。この関数の等高線図を下図に示します。点 [-1.9,2] の位置を初期推定値として最急降下法を使った場合の最小値を求めるまでの解の方向も示します。最適化は、1000回の反復の後終了しますが、最小値の位置とかなり離れています。図で黒色で表される部分は、谷の片側へ行ったり来たりのジグザグ運動を連続的に行っていることを示しています。プロット図の中央に向かって、ある点が谷の中心に正確に到達するとき、より多くのステップ数が生じることに注意してください。
図 5-1、罗森布鲁克関数における最急降下法
このような関数は原点回りで曲率が歪んでいるために、制約なしの例の中で悪名高いものでバナナ関数として知られています。罗森布鲁克関数はさまざまな最適化手法の使い方を示すために、この節全体で使われています。等高線は、U字谷の急斜面のために指数的な刻み幅でプロットされています。
反復点を生成するスクリプトを含めたこの図の詳細については,バナナ関数の最小化を参照してください。
準ニュートン法
勾配情報を使う方法の中で,最も良く使われるものは準ニュートン法です。この方法は,各反復で曲率情報を構築し,次の二次モデルの問題を定式化します。
(6)
ここでヘッセ行列Hは正定値対称行列で,cは定数ベクトル,bは定数です。この問題の最適解はxの偏導関数をゼロに近づけたときに求められます。すなわち以下のようになります。
(7)
最適解x *は次のように記述することができます。
(8)
ニュートンタイプの方法は(準ニュートン法と違って)直接Hを計算し,何回かの反復後,最小値に到達するために減少する方向に進みます。数値的にHを計算するには,非常に多くの計算を必要とします。準ニュートン法は観測されたf (x)と∇f(x)の動作から適切な更新法を使って Hを近似するための曲率情報を構築することにより、計算時間が長くならないようにします。
多くのヘッシアン更新法が開発されてきました。しかしながら、布洛伊登[3]弗莱彻[12]戈德法布,[20]、香诺[37]はの式(蓄热法),一般的な問題に使用するのに最も効果的と考えられています。
蓄热法は次のように与えられます。
(9)
ここで、
最適化を始める出発点 H0は、対称な正定値行列、たとえば、単位行列 我を設定してください。ヘッシアン Hの逆行列を計算することを避けるため、更新法を導入します。この方法は各更新でヘッシアンの逆行列 H–1の近似を求める式を使うことにより、Hの逆行列を直接計算することを避けるものです。よく知られた方法として、戴维登[7]弗莱彻和鲍威尔[14]の DFP式があります。これは 高炉煤气メソッド (式 9) と同じ式を使用しますが、QKが sKの代わりに使用される点が異なります。
勾配の情報は、解析的に計算された勾配から得られるか、または有限差分を使った数値微分法により偏導関数として求めるかのどちらかです。これは各設計変数 xに個々の変動を含ませ、目的関数中で変化率を計算するものです。
主要な各反復のk番目でライン探索は次の方向になります。
(10)
準ニュートン法は,図 5-2、罗森布罗克関数の 高炉煤气法の適用にある罗森布鲁克関数の解を求める経路に示されています。方法は、谷の型に従って、有限差分勾配のみを使って 140回の関数評価の後、最小値に収束します。
図 5-2、罗森布罗克関数の 高炉煤气法の適用
反復点を生成するスクリプトを含めたこの図の詳細については,バナナ関数の最小化を参照してください。
ライン探索法
“ライン探索“は大規模最適化アルゴリズムの一部として使用される探索法です。メインアルゴリズムの各ステップで,ライン探索法はメインアルゴリズムが決めるベクトルである,"探索方向"と平行に,現在の点xKを含むラインに沿って探索します。すなわちこの方法は,次式の次の反復xk+1を見つけます。
(11)
ここで xKは現在の反復を示し、DKは探索方向、α* はスカラー ステップ長のパラメーターです。
ライン探索法は、目的関数の多項式の内挿を反復最小化することにより、ラインxK+α*dKに沿って目的関数を減少させようと試みます。ライン探索法には、2 つのメイン ステップがあります。
“囲い込み”段階では探索されるライン
上の点の範囲を決めます。この”囲い”は,αの値の範囲を指定する区間に相当します。
"区分化"ステップはこの囲いを部分区間に分け,その上で目的関数の最小が多項式内挿により近似されます。
結果のステップ長 α は 沃尔夫条件を満たします。
(12)
(13)
ここでc1.と C2.は 01.< c2.< 1を満たす定数です。
第 1.の条件 (式 12) は、αKが目的関数を十分減少させることを要求します。第 2.の条件 (式 13) は、ステップ長が小さすぎないことを保証します。両方の条件 (式 12と式 13) を満たす点は、"許容点" と呼ばれます。
ライン探索法は[13]の2 - 6節で述べるアルゴリズムの実装です。ライン探索の詳細は[31]を参照してください。
ヘッシアンの更新
最適化関数の多くは、高炉煤气法 (式 9) を使用して、各反復でヘッセ行列を更新することにより探索方向を決めます。関数fminuncは準ニュートン法に与えられた DFP法を使用するオプションも提供します (DFP法の選択は选择权でHessUpdateを“dfp”に設定します)。ヘッシアン Hは探索方向 Dが常に減少する方向になるように正定値に保存されます。これは、方向 Dで任意のステップ α に対して目的関数の大きさが必ず小さくなることを意味しています。Hが正定値であることは Hを正定値で初期化し、その後
(式 14から導出)が常に正であることにより保証されます。
の項は、ライン探索ステップ長を表すパラメーター αKと、探索方向 Dと過去および現在の勾配評価を組み合わせたものの積として表せます。
(14)
が正である条件は、十分な精度でライン探索を行うことにより必ず可能になります。これは探索方向 Dが減少する方向であるためで、αKと負の勾配–∇f(x)K)TDは常に正です。したがって、–∇f(x)k+1)TDの項が負の値を取る場合は、ライン探索の精度増加と同程度の小ささにしなければなりません。