BFGS 最適化アルゴリズムが厳密に凸の問題に対して超線形に収束することは「よく知られています」が、厳密に凸ではない問題に対する分析はありますか。たとえば、あるスカラー x に対して f(x) が凸であるとします。次に、g(x1,x2)=f(x1+x2) を最適化するとします。これでも常に超線形収束しますか?
3 に答える
1
非凸の問題で BFGS がまったく収束するかどうかは、まだ未解決の問題です。実際、1984 年に Powell は、不正確なライン検索検索を使用した BFGS が収束に失敗する可能性があることを示す反例を示しました。作成できるのは、次のようなローカル ステートメントです。 ローカル ミニマム x* が与えられた場合、最終的に x* 付近の空間領域に入ると、BFGS は超線形に収束します。この理由は、x* の近くでは、目的関数を凸二次によって正確にモデル化できるためです。
あなたが与えた合成関数で何が知られているかについては、よくわかりません。BFGS のプロパティの詳細な説明については、Dennis と Schnabel または Nocedal と Wright を参照してください。
幸運を祈ります。
于 2010-02-22T22:43:26.593 に答える
0
私が間違っている場合は訂正してください。しかし、この場合の「解決策」は実際には単一の点ではなく線ではないでしょうか? x' が f(x) の最小化関数である場合、g(x1, x2) にメソッドを適用するときに期待できる最善の方法は、x2 = x' - x1 の行に収束することです。
于 2010-02-16T23:17:17.920 に答える
0
実際には、慎重に作成されたアルゴリズムは収束しますが、必ずしも超線形ではないことがわかりました。丸め誤差が原因です。収束基準が作用します。これは、「ほぼ」凸でない関数、つまり「硬い」関数についても同じです。
BFGS の更新には注意して、理論上のヘッセ行列がそうでなくても、結果の近似ヘッセ行列が「十分に」正定のままであることを確認する必要があります。私がしていることは、ヘッセ行列自体またはその逆ではなく、ヘッセ行列のコレスキー分解を維持および更新することです。
于 2012-07-16T00:28:38.800 に答える