ラグランジュの未定乗数法(不等式制約とKKT条件)

ラグランジュの未定乗数法(不等式制約と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の時を解くだけではいけません。

以下の目的関数を考えているとします。

Lag_1_

範囲がなければ、点Eが最小値です。

ここに制約条件を入れていきます。
まず等式条件を入れてみましょう。

lag_2_

 

青色のラインが制約条件だとします。
制約条件が等式だと、「制約条件上」じゃないといけないので
最適解は点Fになりますね。

 

ではこれが、「不等式制約」だとどうなるか

パターン①
lag_3_(汚くてすみません)

これの青線の範囲での最大や最小を求める問題となります。
これの場合最小値は点Fですね。
この時制約条件は=0で考えるだけで大丈夫です。

範囲が大なり小なり逆だと、パターン②
lag_4_

という範囲になります。
この場合は最小値は点Eですね。
この時制約条件が=0ではないことに注意してください。
前回もお話しましたが、制約条件が=0ではないことを
「制約条件がアクティブでない」と言います。

 

と、こう見ると高校一年生などの内容になりますがこんな図が
書けることは稀なので
勾配ベクトルを使ってどういう状況なら
制約条件をアクティブで考えてよい、パターン①で
制約条件がアクティブでないパターン②の時はどうなのか。

それをまとめたのが「KKT条件」です。
KKT条件のまとめは後ほど行うとして

じゃあ、大きくどのような方針でこれを定めるか
ということから説明していきます。

まず、簡単な例として制約条件が一つの場合で
目的関数をf(x)、制約条件をg(x)と定めます。

■目的関数⇒MAX
■制約条件<=0

とした時、
■目的関数は正方向に持っていきたい!
(増えていけばどんどん大きくなるから)

■制約条件は負の方向に持っていきたい!
(<=0より小さい分は問題がないので)
となります。

目的関数の正方向とは
目的関数の勾配ベクトルの正の向きで

制約条件の負の方向とは
制約条件の勾配ベクトルの負の向きです。

$$$$

SNSでもご購読できます。

コメントを残す