16

勾配降下法を使用して、N 個のパラメーターで関数の最小値を見つけようとしています。ただし、パラメーターの絶対値の合計を 1 (または <= 1 は関係ありません) に制限しながら、それを行いたいと考えています。このため、ラグランジュ乗数の方法を使用しているため、関数が f(x) の場合、f(x) + ラムダ * (g(x)-1) を最小化します。ここで、g(x) は滑らかな近似値です。パラメータの絶対値の合計。

私が理解しているように、この関数の勾配は g(x)=1 の場合にのみ 0 になるため、局所的最小値を見つけるメソッドは、条件も満たされる関数の最小値を見つける必要があります。問題は、この関数の追加が制限されていないため、Gradient Descent がますます大きなパラメーター (絶対値) を持つますます大きなラムダを単純に見つけ、決して収束しないことです。

現時点では、Python (scipy) による CG の実装を使用しているため、自分で CG コードを書き直したり微調整したりする必要はなく、既存の方法を使用する提案を希望します。

4

3 に答える 3

29

問題は、ラグランジュ乗数を使用する場合、臨界点はラグランジュの極小値では発生せず、代わりに鞍点で発生することです。最急降下アルゴリズムは極小値を見つけるように設計されているため、制約の問題を与えると収束に失敗します。

通常、次の3つの解決策があります。

  • ニュートン法など、鞍点を見つけることができる数値法を使用します。ただし、これらには通常、勾配とヘッセ行列の両方の分析式が必要です。
  • ペナルティメソッドを使用します。ここで、コスト関数に余分な（滑らかな）項を追加します。これは、制約が満たされている（またはほぼ満たされている）場合はゼロであり、満たされていない場合は非常に大きくなります。その後、通常どおり最急降下法を実行できます。ただし、これは、パラメータが制約を満たすように多くの小さな調整を行うため、収束特性が不十分であることがよくあります。
  • ラグランジアンの臨界点を探す代わりに、ラグランジアンの勾配の二乗を最小化します。明らかに、ラグランジアンのすべての導関数がゼロの場合、勾配の2乗はゼロになります。また、何かの2乗がゼロ未満になることはないため、ラグランジアンを極値化する場合と同じ解が見つかります。ただし、最急降下法を使用する場合は、ラグランジアンの勾配の2乗の勾配の式が必要です。これは簡単に入手できない場合があります。

個人的には、3番目のアプローチを使用して、分析式を取得するのが難しすぎる場合は、ラグランジアンの勾配の2乗の勾配を数値的に見つけます。

また、あなたはあなたの質問でそれを完全に明確にしていません-あなたは勾配降下法、またはCG（共役勾配法）を使用していますか？

于 2012-09-05T15:31:01.730 に答える
5

おそらくOPに役立つには遅すぎますが、同じ状況の他の人には役立つかもしれません:

絶対値制約を伴う問題は、多くの場合、いくつかの「ヘルパー」変数を追加することで、線形制約のみを持つ同等の問題に再定式化できます。

たとえば、問題 1 を考えてみましょう。

非線形制約 |x1|+|x2|<=10 に従って f(x1,x2) を最小化する (x1,x2) を見つけます。

線形制約バージョンの問題 2 があります。

次の線形制約に従って f(x1,x2) を最小化する (x1,x2,x3,x4) を見つけます。

  1. x1<=x3
  2. -x1<=x3
  3. x2<=x4
  4. -x2<=x4
  5. x3+x4<=10

ノート：

  • (x1,x2,x3,x4) が問題 2 の制約を満たす場合、(x1,x2) は問題 1 の制約を満たします (x3 >= abs(x1)、x4 >= abs(x2) であるため)。
  • (x1,x2) が問題 1 の制約を満たす場合、x3=abs(x1)、x4=abs(x2) を設定することにより、問題 2 の制約を満たす (x1,x2,x3,x4) に拡張できます。
  • x3,x4 はターゲット関数に影響を与えません

したがって、問題 2 の最適解を見つけると問題 1 の最適解が得られ、その逆も成り立ちます。

于 2014-12-17T02:19:38.903 に答える