optimization - 最適化の収束では、初期推定が優れていると悪化する可能性があります

Question

解決する必要のある多くのパラメーターを持つ非常に複雑なモデルがあります。モデルは複雑ですが、各ステップの関数形式は不規則ではありません。

開始値でいくつかの奇妙な動作が見られます。標準のランダムな値（すべて0）から始めると、ソルバーは673秒で「局所的に最適な解が見つかりました」という0CGの反復で収束します。

解に近いことがわかっている値から始めると、ソルバーは「主要な実行可能な解の推定を改善することはできません。」、1718年代の493回のCG反復で収束します。

どちらの場合も、最終的な値は同じ（または非常に類似）であることに注意してください。

2つの質問：

• ソルバーが共役勾配を計算する必要がある場合のように、共役勾配の反復回数は正確には何回ですか？ここでは、1つのケースで0 CGの反復が見られ、他のケースでは493のCGの反復が見られます。それはどういう意味ですか？（私はCGメソッドが何であるかを知っていることに注意してください。ここで、1つのケースで0と大きな違いがある理由はわかりません。）
• 「より良い」初期値が最適化の収束を大幅に遅らせる可能性があるという考えられるすべての説明は何ですか？

Answer 1

共役勾配法は、勾配型の最適化アルゴリズム（「最急降下法」とも呼ばれます）であり、場合によっては収束が遅くなる傾向があります。たとえあなたが最適に近づいても。

ウィキペディアでは、この振る舞いを説明するための図を見つけることができます。私はそれらの1つをここに適応させました。

表示されるのは、等高線図の等コスト（または等目的）線です。ポイント1から開始するとします。これは、非常に適切な開始値です。赤い線は、最適に到達するためにたどった経路を示しています。最適に向かってジグザグに動くことがわかります。これには多くの機能評価が必要であり、したがって時間がかかります。

これを開始値としてポイントAを選択したときのパフォーマンスと比較すると、収束が速くなります（または、少なくとも、この場合はそれが期待されます）。その場合、1回の反復で済むと仮定しましょう。

ここでポイント5を見てください。これは明らかに最適に近いですが、最適に到達するには多くの反復が必要です。狭い谷を通り抜けると、アルゴリズムは一方の側からもう一方の側にジャンプし、途中で最適に向かってわずかな進歩しかしません。谷の広い側から近づくと、勾配が最適に向けられていることがわかります。これにより、収束が速くなります。

あなたの場合、初期値が上記のポイント5にいくらか似ているのに対し、一般的な開始値はポイントAに匹敵するという事実かもしれません。これは、開始値が真の値に収束することを前提としています。場合。開始値が近いが、それとグローバル最適値の間にピークがある場合、次の図のように正しい値に収束しません。

knitroがCGまたは他のアルゴリズムのいずれかに変更された場合、それはドキュメントに記載されているか、knitroの開発者だけが知っているものです。

Answer 2

最初の質問から、「スマート」ソルバーを採用していることがわかりました。つまり、アルゴリズムを動的に調整して最適に収束させるということです。共役勾配法は、最適値を「長距離」で見つけるのに適した方法ですが、浅い最適値に近づくと収束が遅くなります。

すべての「スマート」コードと同様に、ヒューリスティックが失敗する状況があり、その状況に遭遇したことがあります。パラメータが少し変化しても、目的関数（つまり、最適化しようとしている実際の基準）はほとんど変化しないように、最適化はかなり浅いと思います。これで、パラメーターが既に最適値に非常に近づいていることをソルバーが知る方法はありません。目的関数がかなりフラットな領域では、解から非常に遠くなる可能性があることがわかっています。したがって、いくつかの初期テストの後、デフォルトで共役勾配法が使用されます。これは、時間はかかりますが安全に最適値に近づく方法です。ただし、多くの検索を行っても実際にはそれほど遠くないため、運が良ければ最適に近いスタートを切ることができますが、運が悪ければ解は遠いということになります。

最初の推測がかなり良いことがわかっている場合は、ソルバーがどのアルゴリズムを使用する必要があるかどうかを指定できるかどうかを確認する必要があります。

Answer 3

これは、開始値が問題の解の近似にすぎないためです。反復解は最終値に収束しようとすることで近づこうとするため、解答の開始値に近づくほど少なくなります。収束する必要のある反復。また、収束しきい値もカウントする必要があります。

これは古典的な情報に基づく問題と情報に基づいていない問題です。アドホックな値から始めると、適切な非アドホックな値から始めると結果を見つけるのが難しくなります。