ラグランジュの未定乗数法(不等式制約とKKT条件)
前回までで、「等式制約」のラグランジュの未定乗数法が
わかったかと思います。
次に不等式制約について考えていきます。
前回までは
$$\boldsymbol{x}=(x_1,x_2,\cdots,x_n)\tag{変数}$$
$$h_i(\boldsymbol{x})=0\tag{制約条件}$$
$$f(\boldsymbol{x})\rightarrow最大or最小\tag{目的関数}$$
のような形でした。
この制約条件の部分が
$${h_i(\boldsymbol {x} ) } \geq {0} \tag{制約条件}$$
のように不等式である場合のことです。
この時はさっきのようにラグランジュ関数を使って=0の時を解くだけではいけません。
以下の目的関数を考えているとします。
範囲がなければ、点Eが最小値です。
ここに制約条件を入れていきます。
まず等式条件を入れてみましょう。
青色のラインが制約条件だとします。
制約条件が等式だと、「制約条件上」じゃないといけないので
最適解は点Fになりますね。
ではこれが、「不等式制約」だとどうなるか
これの青線の範囲での最大や最小を求める問題となります。
これの場合最小値は点Fですね。
この時制約条件は=0で考えるだけで大丈夫です。
という範囲になります。
この場合は最小値は点Eですね。
この時制約条件が=0ではないことに注意してください。
前回もお話しましたが、制約条件が=0ではないことを
「制約条件がアクティブでない」と言います。
と、こう見ると高校一年生などの内容になりますがこんな図が
書けることは稀なので
勾配ベクトルを使ってどういう状況なら
制約条件をアクティブで考えてよい、パターン①で
制約条件がアクティブでないパターン②の時はどうなのか。
それをまとめたのが「KKT条件」です。
KKT条件のまとめは後ほど行うとして
じゃあ、大きくどのような方針でこれを定めるか
ということから説明していきます。
まず、簡単な例として制約条件が一つの場合で
目的関数をf(x)、制約条件をg(x)と定めます。
■目的関数⇒MAX
■制約条件<=0
とした時、
■目的関数は正方向に持っていきたい!
(増えていけばどんどん大きくなるから)
■制約条件は負の方向に持っていきたい!
(<=0より小さい分は問題がないので)
となります。
目的関数の正方向とは
目的関数の勾配ベクトルの正の向きで
制約条件の負の方向とは
制約条件の勾配ベクトルの負の向きです。
$$$$