○×的数学のお部屋
その７ 制約条件が不等式でのラグランジュの未定乗数法
数学のお部屋その２である制約条件の下での関数の極値を求めるラグランジュの未定乗数法を説明しました。そこでは制約条件となる関数をg(x)=0と等号で定義しました。これは制約条件が「境界線」である事を意味しています。例えば、
という制約条件関数だったら、2つの変数x1とx2は半径1の円上でしか認められません：
しかし極値問題では制約条件が「範囲」である事も多いのです。すなわち、
のように円上ではなくて円の内側にあるx1,x2であればどんな値でもOK、みたいな制約条件の下での極値を求めるケースがありえます：
こういう問題の事を「不等式制約付き最適化問題」と呼びます。こういうケースでの極値を求める方法を見ていく事にしましょう。
① 範囲の中に極値があるか？
制約条件の境界での極値と違い、範囲内の極値では元の関数f(x)の極値がその範囲内に含まれているか否かがとても重要になります。例えば元の関数が次のような2変数の2次曲面としましょう：
(a, b)はお椀の底の座標です。もし(a, b) = (0, 0)とすると、お椀の底は原点に位置します。この時、先の円の内側を制約条件とすると、極値はそのお椀の底となります：
お椀に沿うように巻かれているのが円状の制約条件で、その内側に極値（最小値）があるのが分かりますよね。一方で(a, b) = (1, 1)とするとどうでしょうか：
ちょっと分かり辛いかもしれませんが、円の外側にお椀の底があるため、お椀の底は制約条件での極値（最小値）にはなれません。この場合は「境界線上」に極値が存在する事になります（縁の中に凸図形が無いので）。境界線上という事は普通のラグランジュの未定乗数法での極値と同じになります。
つまり不等式制約付き最適化問題では、制約条件の中にお椀のような凸（極値）があるか無いかで場合分けをする必要があるんです。でも、実際はそんな難しい事をする訳ではありません。
② λがゼロかゼロじゃないかがポイント
先程のお話で、制約条件範囲内に極値（お椀の底）がある場合はそれがそのまま求める極値になる、逆に無い場合は制約条件の境界線上に極値がある、という場合分けをしました。で、後者の場合は制約条件が等号の普通のラグランジュの未定乗数法で極値が求まります。つまり、
というラグランジュの式を作って、偏微分をゼロとした連立方程式を解けばいいんです。この場合一般にはλの値が存在する事になります。つまりλはゼロ以外の値になります。一方で範囲の中に凸がある場合、それって元の関数の極値問題、つまり「制約の無い極値問題」と一緒ですよね。という事は、上のラグランジュの式でλ=0としてg(x1,x2)を消した式の極値を求めれば終わりです。
この事から、λがゼロかゼロじゃないかがそのまま場合分けになる事が分かります。実際に上で出てきた2変数の2次曲面f(x1, x2)と円状の制約条件g(x1, y1)で試してみましょうか(^-^)
〇 お椀の底が円の内側にある場合
まずは(a, b) = (0, 0)、お椀の底が原点にあって円の内側に位置する場合を見てみます。f(x),g(x)、そしてラグランジュの式L(x)はそれぞれ以下の通りです：
次にラグランジュの式を各変数で偏微分して連立方程式を作るのですが、まずは制約条件の範囲内に極小値があるか（λがゼロの場合）を調べます。これは単純にf(x1,x2)の極値を算出して、それが制約条件を満たしているかチェックするだけです。上式の場合極値は、
なのでこのx1,x2をg(x1,x2)に放り込むと成立している事が分かります。確かに極値は制約条件である円の内側にあります。
〇 お椀の底が円の外側にある場合
(a, b) = (1, 1)の2次曲面の場合、元の関数f(x1,x2)及びラグランジュの式は以下のようになります：
先と同様にまずλ=0でf(x1,x2)の極値が円の中にあるか否かをチェックします：
この(x1,x2)をg(x1,x2)に代入すると左辺は1になるので不等号が成立していません。つまり極値はg(x1,x2)が描く境界線上にある事が分かります。よって通常のラグランジュの未定乗数法を用いて求めます。ラグランジュの式Lを偏微分して：
1,2段目を3段目に代入して整理すると、
λが2つ出てきました。双方を1,2段目の式に戻すと、以下の2つの極値が制約条件の境界上に求まります：
境界上なのでこれらの(x1,x2)をg(x1,x2)に入れるとゼロになります。
③ カルーシュ・クーン・タッカー条件（KKT条件）
②で見てきたように、制約条件が不等号の場合、極値がその範囲に含まれていればλはゼロじゃなくて制約条件g(x)は非ゼロ、範囲に含まれていない場合はλは非ゼロでg(x)はゼロになりました。また最大値の時にλはプラスで、最小値の時はマイナスになりました。これらの事から、制約条件下に極値が存在する場合に以下の3つの事が同時に言えます：
この3つの条件の事をカルーシュ・クーン・タッカー条件（KTT条件）と言います。1番目は制約条件そのものですから必須です。これはゼロもあり得るのでゼロ以下となっています。2番目は最大値の時で、もし最小値を語るなら不等号の向きは逆になります。最後の3番目がなるほどな所で、極値があればλとg(x)はどちらかがゼロになるので、双方を掛け算すると常にゼロになります。
不等号制約付きの極値問題はラグランジュの未定乗数法と通常の極値問題の合わせ技で考える事が出来るのが分かりました。制約条件が沢山ある場合でも同じような理屈の拡張が出来ます。実際のKKT条件はそういう多数の制約条件下で定義されています（Wikipedia：カルーシュ・クーン・タッカー条件）。極値問題は工学、化学、生物学、経済学、etcと科学のあらゆる所で出てきますので、この理屈は大変に重要です。ラグランジュさんとKKTのお三方に感謝ですね(^-^)
