グラデーション法。 勾配最適化手法

勾配法

勾配制約なし最適化法は、目的関数の一次導関数のみを使用し、各ステップでの線形近似法です。 各ステップの目的関数は、現在の点でのグラフへの接線超平面に置き換えられます。

勾配法の k 番目の段階では、点 Xk から点 Xk+1 への遷移は次の関係で表されます。

ここで、k はステップ サイズ、k は Xk+1-Xk 方向のベクトルです。

最急降下法

この方法は、18 世紀に O. Cauchy によって最初に検討され、適用されました。 その考え方は単純です。任意の点における目的関数 f(X) の勾配は、関数の値が最大に増加する方向のベクトルです。 その結果、反勾配は関数の最大の減少に向けられ、最も急な降下方向になります。 反勾配 (および勾配) は、点 X で水平面 f(X) に直交します。(1.2) で方向を導入すると、

この場合、これが点 Xk での最も急な降下方向になります。

Xk から Xk+1 への遷移の式を取得します。

反勾配は降下方向のみを示し、段差の大きさは示しません。 一般に、1 回のステップでは最小ポイントが得られないため、降下手順を数回適用する必要があります。 最小点では、すべての勾配成分はゼロに等しくなります。

すべての勾配法は前述の考え方を使用しており、技術的な詳細が互いに異なります。つまり、解析公式または有限差分近似を使用した導関数の計算です。 ステップ サイズは一定にすることも、何らかのルールに従って変更することも、反勾配方向などに 1 次元の最適化手法を適用した後に選択することもできます。 等々。

詳細には触れません。なぜなら... 最急降下法は、一般に、本格的な最適化手順としては推奨されません。

この方法の欠点の 1 つは、鞍点を含む任意の静止点に収束するため、解決策にならないことです。

しかし、最も重要なことは、一般的な場合における最急降下の収束が非常に遅いことです。 重要なのは、その下りが現地の意味で「最速」であるということです。 検索ハイパースペースが非常に長く伸びている (「渓谷」) 場合、反勾配は「渓谷」の底にほぼ直角に向けられます。 最小値を達成するための最良の方向。 この意味で、英語の用語「最急降下」の直訳、すなわち、 ロシア語の専門文献で採用されている「最速」という用語よりも、最も急な斜面に沿って降下するほうが、より状況と一致しています。 この状況を回避する 1 つの方法は、二次偏導関数によって提供される情報を使用することです。 もう 1 つの方法は、変数のスケールを変更することです。

線形近似微分勾配

フレッチャー・リーブス共役勾配法

共役勾配法では、一連の検索方向が構築されます。これは、現在の最急降下方向と以前の検索方向の線形結合です。

さらに、係数は探索方向が共役になるように選択されます。 ことが証明されています

これは、高速で効果的な最適化アルゴリズムを構築できる非常に貴重な結果です。

フレッチャー・リーブスアルゴリズム

1. X0 で計算されます。

2. k 番目のステップでは、その方向に 1 次元検索を使用して最小 f(X) が見つかり、これにより点 Xk+1 が決定されます。

• 3. f(Xk+1) と が計算されます。
• 4. 方向は次の関係から決定されます。

• 5. (n+1) 回目の反復後 (つまり、k=n の場合)、再開が行われます。X0=Xn+1 が想定され、ステップ 1 への移行が実行されます。
• 6. アルゴリズムは次の場合に停止します。

ここで、 は任意の定数です。

Fletcher-Reeves アルゴリズムの利点は、ニュートン法で使用される行列を必要としないため、行列の反転を必要とせず、コンピューター メモリを節約できることですが、同時に準ニュートン アルゴリズムとほぼ同じくらい効率的です。 なぜなら 探索方向が相互に共役である場合、二次関数は n ステップ以内で最小化されます。 一般的なケースでは、再起動が使用され、結果を取得できます。

Fletcher-Reeves アルゴリズムは 1 次元検索の精度に影響されるため、発生する可能性のある丸め誤差を排除するために使用する必要があります。 さらに、ヘッシアンの条件が悪くなる状況ではアルゴリズムが失敗する可能性があります。 このアルゴリズムには、いつでもどこでも収束するという保証はありませんが、実践では、アルゴリズムがほぼ常に結果を生成することが示されています。

ニュートン法

最急降下に対応する検索方向は、目的関数の線形近似に関連付けられます。 二次導関数を使用する方法は、目的関数の二次近似から生まれました。つまり、テイラー級数で関数を展開する場合、三次以降の項は破棄されます。

ここで、 はヘッセ行列です。

右辺の最小値 (存在する場合) は、2 次形式の最小値と同じ場所で達成されます。 検索方向を決定するための式を書き留めてみましょう。

最小値に達するのは、

この関係から探索方向を決める最適化アルゴリズムをニュートン法といい、その方向をニュートン方向といいます。

二次導関数の正行列を使用して任意の二次関数の最小値を見つける問題では、開始点の選択に関係なく、ニュートン法は 1 回の反復で解を与えます。

ニュートン法の分類

ニュートン法自体は、ニュートン方向を 1 回適用して二次関数を最適化することで構成されています。 関数が 2 次関数でない場合、次の定理が当てはまります。

定理1.4。 最小点 X* における一般形式の非線形関数 f のヘッセ行列が正定値であり、開始点が X* に十分近い値で選択され、ステップ長が正しく選択されている場合、ニュートン法は二次方程式で X* に収束します。レート。

Newton の方法は参照方法とみなされ、開発されたすべての最適化手順と比較されます。 ただし、ニュートンの方法は、正定でよく条件付けされたヘッセ行列に対してのみ効率的です (行列式はゼロより大幅に大きい必要があります。より正確には、最大固有値と最小固有値の比が 1 に近い必要があります)。 この欠点を克服するために、可能な限りニュートン方向を使用し、必要な場合にのみニュートン方向から逸脱する、修正ニュートン法が使用されます。

ニュートン法を修正する一般原則は次のとおりです。反復ごとに、最初に「関連する」特定の正定行列が構築され、次に次の式を使用して計算されます。

正定値なので、必然的に - が降下方向になります。 構築手順は、正定値の場合にヘッセ行列と一致するように編成されています。 これらの手順は、特定の行列分解に基づいています。

もう 1 つのグループの方法は、実質的にニュートン法と速度が劣らないもので、有限差分を使用したヘッセ行列の近似に基づいています。 最適化のために導関数の正確な値を使用する必要はありません。 これらの方法は、導関数の分析的計算が難しい場合、または単に不可能な場合に役立ちます。 このような方法は離散ニュートン法と呼ばれます。

ニュートン型手法の有効性の鍵は、ヘッセ行列に含まれる最小化関数の曲率に関する情報を考慮に入れ、局所的に正確な目的関数の二次モデルの構築を可能にすることです。 ただし、下降反復中の勾配の変化の観察に基づいて、関数の曲率に関する情報を収集および蓄積することは可能です。

ヘッセ行列を明示的に形成せずに非線形関数の曲率を近似できる可能性に基づいた対応する方法は、準ニュートン法と呼ばれます。

ニュートン型 (準ニュートン型を含む) の最適化手順を構築する場合、鞍点の出現の可能性を考慮する必要があることに注意してください。 この場合、最適な検索方向のベクトルは、鞍点から下方向に離れるのではなく、常に鞍点に向かうことになります。

ニュートン・ラフソン法

この方法は、二次関数ではない関数を最適化するときにニュートン方向を繰り返し使用することで構成されます。

多次元最適化のための基本的な反復公式

このメソッドでは、関係から最適化の方向を選択するときに使用されます。

実際のステップ長は、正規化されていないニュートン方向には隠されています。

この方法は、現時点での目的関数の値を必要としないため、間接的または分析的最適化方法と呼ばれることもあります。 1 回の計算で 2 次関数の最小値を決定できる機能は、一見すると非常に魅力的に見えます。 しかし、この「一回の計算」には多大なコストがかかります。 まず第一に、1 次の n 個の偏導関数と 2 次の n(n+1)/2 - を計算する必要があります。 さらに、ヘッセ行列を逆行列にする必要があります。 これには、約 n3 回の計算操作が必要です。 同じコストで、共役方向法または共役勾配法は約 n ステップかかります。つまり、 ほぼ同じ結果が得られます。 したがって、ニュートン・ラフソン法の反復は、二次関数の場合には利点がありません。

関数が二次関数でない場合は、

• - 一般に、最初の方向は実際の最小点を示さなくなり、反復を数回繰り返す必要があることを意味します。
• - 単位長さのステップにより、目的関数の値が悪化する点が得られる可能性があり、たとえばヘッセ行列が正定値でない場合、検索で間違った方向が得られる可能性があります。
• - ヘッセ行列の状態が悪くなり、反転できなくなる可能性があります。 次の反復の方向を決定します。

戦略自体は、探索がどの静止点 (最小値、最大値、鞍点) に近づいているかを区別せず、関数が増加しているかどうかを追跡するために使用できる目的関数の値の計算は行われません。 これは、検索の開始点がアトラクション ゾーン内のどの静止点にあるかによってすべてが決まることを意味します。 ニュートン・ラフソン戦略が何らかの変更を加えずに単独で使用されることはほとんどありません。

ピアソン法

ピアソンは、二次導関数を明示的に計算せずに逆ヘッセ行列を近似するいくつかの方法を提案しました。 反勾配の方向の変化を観察することによって。 この場合、共役方向が得られる。 これらのアルゴリズムは詳細が異なるだけです。 応用分野で最も広く使用されているものを紹介します。

ピアソン アルゴリズム No. 2。

このアルゴリズムでは、逆ヘシアンは行列 Hk によって近似され、次の式を使用して各ステップで計算されます。

任意の正定対称行列が初期行列 H0 として選択されます。

このピアソン アルゴリズムは、行列 Hk が悪条件になる状況、つまり、行列の行列式がゼロに近いにもかかわらず、正定値と非正定値の間で振動し始める状況を引き起こすことがよくあります。 この状況を回避するには、n ステップごとに行列を再定義し、それを H0 に等しくする必要があります。

ピアソン アルゴリズム No. 3。

このアルゴリズムでは、行列 Hk+1 は次の式から決定されます。

Hk+1 = Hk +

このアルゴリズムによって生成される降下軌道は、Davidon-Fletcher-Powell アルゴリズムの動作に似ていますが、ステップがわずかに短くなります。 ピアソンは、巡回行列リセットを使用したこのアルゴリズムのバリエーションも提案しました。

射影ニュートン・ラフソンアルゴリズム

ピアソンは、次の関係から行列を計算するアルゴリズムのアイデアを提案しました。

H0=R0、ここで行列 R0 は前のアルゴリズムの初期行列と同じです。

k が独立変数の数 n の倍数である場合、行列 Hk は行列 Rk+1 に置き換えられ、合計として計算されます。

量 Hk(f(Xk+1) - f(Xk)) は、前のステップのすべての勾配増分ベクトルに直交する勾配増分ベクトル (f(Xk+1) - f(Xk)) の投影です。 n ステップごとに、Rk は逆ヘッセ行列 H-1(Xk) の近似値となるため、実際には (近似の) ニュートン検索が実行されます。

デビドン・フレッチャー・パウエル法

この方法には、変数計量法、準ニュートン法という別の名前もあります。 彼はこれら両方のアプローチを使用しています。

Davidon-Fletcher-Powell (DFP) 法はニュートン方向の使用に基づいていますが、各ステップで逆ヘッセ行列を計算する必要はありません。

ステップ k での探索方向は次の方向です。

ここで、 Hi は各ステップで更新される正定対称行列で、極限内では逆ヘッセ行列と等しくなります。 通常、単位行列は初期行列 H として選択されます。 反復 DFT 手順は次のように表すことができます。

• 1. ステップ k には、点 Xk と正定行列 Hk があります。
• 2. 新しい検索方向として選択します

3. 方向に沿った 1 次元の探索 (通常は 3 次補間) により、関数を最小化する k が決定されます。

4. 依存する。

5. 依存する。

6. 決まっている。 Vk または が十分に小さい場合、手順は終了します。

• Ｕｋ＝ｆ（Ｘｋ＋１）−ｆ（Ｘｋ）と仮定する。
• 8. マトリックス Hk は次の式に従って更新されます。

9. k を 1 つ増やし、ステップ 2 に戻ります。

この方法は、勾配計算の誤差が小さく、行列 Hk が悪条件にならない場合に実際に有効です。

行列 Ak は Hk の G-1 への収束を保証し、行列 Bk はすべての段階で Hk+1 の正定性を保証し、極限で H0 を除外します。

2次関数の場合

それらの。 DFP アルゴリズムは共役方向を使用します。

したがって、DFT 法ではニュートン手法の考え方と共役方向の特性の両方が使用され、二次関数を最小化する場合、n 回以下の反復で収束します。 最適化された関数が 2 次関数に近い形状の場合、G-1 (ニュートン法) の近似が優れているため、DFT 法が有効です。 目的関数が一般的な形式を持つ場合、共役方向を使用するため DFT 法が効果的です。

この方法は、次の式の反復修正に基づいています。

x k +1 = x k + a k s(x k)、

x k+1 = x k - a k Ñ f(x k)、ここで

a は与えられた正の係数です。

Ñ f(x k) は、一次目的関数の勾配です。

欠点:

適切な値を選択する必要があります ;

この点付近では f(x k) が小さいため、最小点への収束が遅くなります。

最急降下法

最も単純な勾配法の最初の欠点がありません。 a k は、1 次元最適化手法 x k+1 = x k - a k Ñ f(x k) の 1 つを使用して、方向 Ñ f(x k) に沿って Ñ f(x k) を最小化する問題を解くことによって計算されます。

この方法はコーシー法と呼ばれることもあります。

このアルゴリズムは、実際の問題を解決する際の収束率が低いという特徴があります。 これは、変数の変化が勾配値に直接依存し、最小点付近でゼロになる傾向があり、最後の反復には加速メカニズムがないという事実によって説明されます。 したがって、アルゴリズムの安定性を考慮して、(最小点からかなりの距離にある点から) 解を求める最初の手順として、最急降下法がよく使用されます。

共役方向法

制約なし非線形計画法の一般的な問題は、要約すると次のとおりです。 f(x), x E n を最小化します。ここで、f(x) は目的関数です。 この問題を解くときは、方程式 f(x *)=0 で定義される静止点 f(x) を導く最小化手法を使用します。 共役方向法とは、導関数を使用する制約のない最小化法を指します。 問題: f(x)、x E n を最小化します。ここで、f(x) は n 個の独立変数の目的関数です。 重要な特徴は、方向を選択するときに応答曲面のトポロジー領域を記述するヘッセ行列が使用されるという事実による高速収束です。 特に、目的関数が 2 次の場合、問題の次元に等しいステップ数以内で最小点を取得できます。

この方法を実際に適用するには、方向システムの収束性と線形独立性をチェックするための手順を追加する必要があります。 二次メソッド

ニュートン法

二次近似スキームを一貫して適用すると、次の式に従ったニュートンの最適化手法が実装されます。

x k +1 = x k - − 2 f(x k -1) − f(x k)。

ニュートン法の欠点は、非二次目的関数を最適化する際の信頼性が不十分であることです。 したがって、次のように変更されることがよくあります。

x k +1 = x k - a k − 2 f(x k -1) − f(x k)、ここで

a k は、f(x k+1) が最小になるように選択されるパラメータです。

2. 制限なく関数の極値を求める

引数 x の変化の開区間 (a, b) 上で特定の関数 f(x) が与えられるとします。 exst がこの間隔内に存在すると仮定します (一般的な場合、これを事前に数学的に記述することはできないと言わなければなりません。ただし、技術的アプリケーションでは、非常に多くの場合、変化間隔内の特定の変化間隔内に exst が存在します)。議論は物理的考察から予測できます)。

定義は存在します。 区間 (a, b) で与えられる関数 f(x) は、点 x * max(min) を持ちます。この点が、区間 (a, b) 、区間 (x * -ε, x * +ε) に属するすべての点 x について、次の不等式が成り立ちます。

f(x) ≤ f(x *) → 最大値

f(x) ≥ f(x *) → 分

この定義は、関数 f(x) のクラスに制限を課すものではありません。もちろん、これは非常に価値があります。

関数 f(x) を、かなり一般的だがさらに狭いクラスの平滑関数に限定する場合 (平滑関数とは、引数の変化の区間で導関数とともに連続する関数を意味します)、次のようになります。 exst の存在に必要な条件を与えるフェルマーの定理を使用できます。

フェルマーの定理。 関数 f(x) が特定の区間 (a, b) で定義され、この区間の点 "c" で最大 (最小) の値を取るものとします。 この時点で有限導関数の両側が存在する場合、exst の存在が必要になります。

注記。 両側導関数は特性によって特徴付けられます。言い換えれば、点「c」では、点「c」に左からと右から近づいたとき、極限の導関数は同じであるという事実について話しています。つまり、 f (x) は滑らかな関数です。

※min、→maxの場合。 最後に、x=x 0 の場合、2 階導関数を使用しても役に立たず、たとえば exst の定義を使用する必要があります。

問題 I を解くとき、必要条件存在 (つまり、フェルマーの定理) が非常に頻繁に使用されます。

方程式 exst に実根がある場合、これらの根に対応する点は exst で疑わしいことになります (ただし、必要十分条件ではなく必要条件を扱っているため、必ずしも極値自体が疑わしいわけではありません)。 したがって、たとえば、変曲点 X p が発生しますが、知られているように、これは極値ではありません。

次の点にも注意してください。

必要な条件から、最大または最小のどのタイプの極値が見つかったかを言うことは不可能です。これを決定するには追加の調査が必要です。

必要な条件から、この極値がグローバルなのかローカルなのかを判断することは不可能です。

したがって、exst に疑わしい点が見つかった場合には、exst の定義や 2 階導関数などに基づいてさらに調査が行われます。

すでに述べたように、最適化問題はそのような因子の値を見つけるタスクです バツ 1 = バツ 1* , バツ 2 = バツ 2* , …, バツk = バツk * 、応答関数 ( で) が極値に達する で= ext (最適)。

最適化問題を解くための様々な方法が知られている。 最も広く使用されている方法の 1 つは、ボックス-ウィルソン法および急上昇法とも呼ばれる勾配法です。

2 因子応答関数の例を使用して勾配法の本質を考えてみましょう y=f(バツ 1 、 バツ 2 ). 図では、 図 4.3 は、因子空間における応答関数の等しい値の曲線 (水準曲線) を示しています。 座標のある点 バツ 1 *, バツ 2 * は応答関数の極値に対応します で内線

因子空間内の任意の点を最初の点として選択すると ( バツ 1 0 , バツ 2 0) の場合、この点から応答関数の頂点までの最短経路は曲線に沿った経路であり、各点の接線はレベル曲線の法線と一致します。 それは応答関数の勾配の方向のパスです。

連続単値関数の勾配 y=f(バツ 1 、 バツ 2) は、座標の勾配によって方向が決定されるベクトルです。

どこ 私、j– 座標軸方向の単位ベクトル バツ 1と バツ 2. 偏導関数はベクトルの方向を特徴付けます。

依存の種類が分からないので y=f(バツ 1 、 バツ 2) 偏導関数を見つけて、勾配の真の方向を決定することはできません。

勾配法によれば、因子空間の一部で初期点（初期レベル）が選択されます。 バツ 1 0 , バツ２０． 対称的な 2 レベルの実験計画が、これらの初期レベルに関して構築されます。 さらに、変動間隔は非常に小さく選択されているため、線形モデルが適切です。 十分に小さい領域内の任意の曲線は線形モデルで近似できることが知られています。

対称的な 2 レベルの計画を構築した後、補間問題が解決されます。 線形モデルが構築されます。

そしてその妥当性がチェックされます。

選択した変動区間に対して線形モデルが適切であることが判明した場合、勾配の方向を決定できます。

したがって、応答関数の勾配の方向は回帰係数の値によって決まります。 これは、座標 ( ) 座標のある点に行きましょう:

どこ メートル –グラデーションの方向のステップ サイズを決定する正の数。

なぜなら バツ 1 0 = 0 および バツ 2 0 = 0 の場合 .

グラデーションの方向を定義し ()、ステップ サイズを選択します。 メートル、初期レベルで実験を実行します バツ 1 0 , バツ 2 0 .

応答関数が減少し始めるまで、勾配に沿って移動を続けます。 図では、 4.3 勾配に沿った動きは、点 ( バツ 1 0 , バツ 20）。 応答関数の非線形性により、破線で示す勾配の真の方向から徐々に逸脱します。

次の実験で応答関数の値が減少するとすぐに、勾配に沿った移動が停止され、応答関数の最大値を持つ実験が新しい初期レベルとして取られ、新しい対称的な 2 レベルの計画が描画されます。そうすると、補間問題が再び解決されます。

新しい線形モデルを構築することで 、回帰分析を実行します。 同時に、因子の有意性をチェックして、少なくとも 1 つの係数が

これは、応答関数の極値領域 (最適領域) にまだ到達していないことを意味します。 勾配の新しい方向が決定され、最適な領域に向かって移動が始まります。

勾配の方向と勾配に沿った移動の明確化は、次の内挿問題を解く過程で因子の重要性をチェックして、すべての因子が重要でないことが判明するまで続きます。 全て 。 これは、最適な領域に到達したことを意味します。 この時点で、最適化問題の解法は停止され、応答関数の最大値を使用した実験が最適値として採用されます。

一般に、勾配法を使用して最適化問題を解くために必要な一連のアクションは、ブロック図の形式で表すことができます (図 4.4)。

1) 因子の初期レベル ( バツj 0) 位置について先験的な情報がある場合は、最適点にできるだけ近いものを選択する必要があります。

2) 変化間隔 (Δ バツj) は、線形モデルが適切である可能性が高いように選択する必要があります。 Δ以下の境界 バツjこの場合、これは応答関数が有意なままである変動間隔の最小値です。

3) ステップ値 ( T) 勾配に沿って移動する場合、積の最大値が正規化形式の因子の上位レベルと下位レベルの差を超えないように選択されます。

.

したがって、 。 より低い値で T初期レベルと座標のある点での応答関数の差は、重要ではないことが判明する可能性があります。 ステップ値が大きくなると、応答関数の最適値をオーバーシュートする危険性があります。

最後に、パラメータ m をすべての反復を通じて一定に設定できます。 ただし、m の値が大きい場合、検索プロセスが分岐する可能性があります。 m を選択する良い方法は、最初の反復で勾配方向の極値の条件から m を決定することです。 後続の反復では、m は一定のままです。 これにより、計算がさらに簡素化されます。

たとえば、次の関数の場合、 勾配投影を使用した場合 最急降下法によって決定されます。 すべての反復でパラメーターを定数にします。

x 座標を計算します (1):

点 x (2) の座標を計算するには、点 x (1) での勾配の投影を見つけます。

等

この数列も収束します。

ステップグラジエント法

この方法はエンジニアによって開発され、変数の 1 つのステップが一定とみなされ、他の変数については点の勾配の比例に基づいて選択されるという事実から構成されています。 これは、極端なサーフェスがスケーリングされる方法です。 収束はすべての変数で同じではありません。 したがって、座標に異なるステップを選択することで、すべての変数の収束率をほぼ同じにしようとします。

分離可能な関数と初期点を与える 。 x 1 座標に沿って一定のステップを設定しましょう。Dx 1 =0.2 とします。 x2 座標に沿ったステップは、勾配とステップの比率から求められます。

多くの変数の微分可能な関数の無条件最小化の問題を考えてみましょう。点の勾配値が最小点に近づくようにします。点の小さな近傍での勾配の値が最も速く減少する方向であることはすでに述べました。この関数は反勾配によって与えられます。この特性は多くの最小化手法で大きく使用されます。 以下で検討する勾配法では、勾配法に従って、点からの降下方向が直接選択されます。

ステップを選択するにはさまざまな方法があり、それぞれの方法で勾配法の特定のバージョンを指定します。

1. 最急降下法。

1 つのスカラー変数の関数を考えて、等式が成り立つ値として を選択してみましょう。

この方法は 1845 年に O. Cauchy によって提案され、現在では一般に最急降下法と呼ばれています。

図では、 図 10.5 は、2 変数の関数を最小化するこの方法の幾何学的図を示しています。 レベルラインに垂直な開始点から降下方向に、光線に沿った関数の最小値に到達するまで降下が続けられます。 見つかった点で、この光線はレベル ラインに接触します。次に、その点からレベル ラインに垂直な方向に、対応する光線が点などでこの点を通過してレベル ラインに触れるまで降下が実行されます。

各反復で、ステップの選択には 1 次元の最小化問題 (10.23) を解くことが含まれることに注意してください。 場合によっては、二次関数などの場合、この操作を解析的に実行できることがあります。

最急降下法を使用して二次関数を最小化しましょう

対称正定行列 A を使用します。

したがって、式 (10.8) によれば、この場合、式 (10.22) は次のようになります。

気づいてください、それは

この関数はパラメータ a の二次関数であり、次の値で最小値に達します。

したがって、二次方程式の最小化に関連して、

関数 (10.24) の場合、最急降下法は式 (10.25) を使用した計算と等価です。

備考 1. 関数 (10.24) の最小点は系の解と一致するため、最急降下法 (10.25)、(10.26) は対称正の線形代数方程式系を解くための反復法としても使用できます。明確な行列。

注 2. ここで、 はレイリー比であることに注意してください (§ 8.1 を参照)。

例10.1。 最急降下法を使用して二次関数を最小化しましょう

したがって、最小点の正確な値は事前にわかっていることに注意してください。 この関数を (10.24) の形式で書きましょう。行列とベクトルはわかりやすいように、

初期近似を取得し、式 (10.25)、(10.26) を使用して計算を実行してみましょう。

繰り返します。

IIの繰り返し。

すべての反復で値が取得されることがわかります

したがって、次のようになります。

最急降下法で得られた数列は等比数列の速度で収束し、その分母は

図では、 図 10.5 は、この例で得られた降下軌道を正確に示しています。

二次関数を最小化する場合、次の一般的な結果が当てはまります。

定理10.1。 A を対称正定行列とし、二次関数 (10.24) を最小化します。 次に、初期近似をどのように選択しても、最急降下法 (10.25)、(10.26) が収束し、次の誤差推定値が正確になります。

ここで、Lado は行列 A の最小固有値と最大固有値です。

この方法は等比数列の速度で収束し、それらが近い場合、分母は小さくなり、非常に早く収束することに注意してください。 たとえば、例 10.1 では、If Aschakh, then 1 があり、最急降下法の収束が遅いことが予想されます。

例10.2。 最急降下法を適用して初期近似中に 2 次関数を最小化すると、一連の近似が得られます。降下軌跡を図に示します。 10.6.

ここで数列は等比級数の速度で収束します。その分母は次の等分数列に等しい、つまり大幅に遅くなります。

前回よりも試してみます。 ここで得られた結果は推定値 (10.27) と完全に一致しているためです。

備考 1. 目的関数が 2 次の場合の最急降下法の収束に関する定理を定式化しました。 一般的なケースでは、最小化される関数が厳密に凸であり、最小点 x を持つ場合、同様に初期近似の選択に関係なく、この方法で得られる数列は で x に収束します。 この場合、極小点の十分に小さな近傍に入った後、収束は線形になり、対応する等比数列の分母は量によって上から推定され、ヘッセ行列の最小固有値と最大固有値の両方はどこにありますか

注 2. 二次目的関数 (10.24) の場合、1 次元の最小化問題 (10.23) の解は単純な明示的な公式 (10.26) の形で求められます。 ただし、他のほとんどの非線形関数ではこれは実行できず、最急降下法を計算するには、前の章で説明したような 1 次元最小化の数値的手法を使用する必要があります。

2.「渓谷」の問題。

上記の議論から、最小化される関数について水平面が球に近い場合 (レベル ラインが円に近い場合)、勾配法は非常に早く収束することがわかります。 このような関数と 1. 定理 10.1、注釈 1、および例 10.2 の結果は、値が増加するにつれて収束速度が急激に低下することを示しています。実際に、最小化される関数は、いくつかの方向に強く引き伸ばされます。 2 次元の場合、対応する表面の起伏は渓谷のある地形に似ています (図 10.7)。 したがって、このような関数は通常、ガリー関数と呼ばれます。 「谷の底」を特徴づける方向に沿って、ガリー関数はわずかに変化しますが、「谷の傾斜」を特徴づける他の方向では、関数の急激な変化が発生します。

出発点が「谷の斜面」にある場合、勾配降下の方向は「谷の底」にほぼ垂直になり、次のアプローチはその反対の「谷の斜面」に当たります。 次に「谷底」に向かうと、元の「谷の斜面」に戻ります。 その結果、下降軌道は「谷の底」に沿って極小点に向かうのではなく、「谷」をジグザグに飛び越えてゴールに近づくことはほとんどありません（図10.7）。

ガリー関数を最小限に抑えながら勾配法の収束を高速化するために、多くの特別な「ガリー」メソッドが開発されました。 最も簡単なテクニックの 1 つを考えてみましょう。 2 つの近い出発点から「渓谷の底」への勾配降下を行います。 見つかった点を通る直線が引かれ、それに沿って大きな「ガリー」ステップが実行されます (図 10.8)。 このようにして見つけた点から、その点まで再度勾配降下ステップを実行し、次に、点を通過する直線に沿って 2 番目の「ガリー」ステップを実行します。 その結果、「谷の底」に沿って極小点までの移動が大幅に加速されます。

「ガリー」および「ガリー」メソッドの問題に関するさらに詳細な情報は、たとえば、を参照してください。

3. 降下ステップを決定するための他のアプローチ。

容易に理解できるように、各反復では、移動が点から点 x に向かう方向に近い降下方向を選択することが望ましいでしょう。 残念ながら、反勾配 (一般に、失敗した下降方向です。これは特にガリー関数で顕著です。したがって、1 次元の最小化問題 (10.23) の解を徹底的に探索することの妥当性については疑問が生じます。関数の「大幅な減少」を確実にする方向にそのようなステップだけを踏みたいという要望がある。さらに実際には、目的関数の値の減少を単に確実にする値を定義するだけで満足することもある。