こんにちは。@tsum_tsumです！

最近忙しかったのですが、ようやく余裕が出てきましたので、久しぶりに記事を書こうと思います。

今回のテーマは、「ラグランジュの未定乗数法」「KKT条件」です！

大学では数学を専攻していた筆者ですが、ラグランジュの未定乗数法は学んだ当時「面白い計算だな～」という印象があり、Qiitaを始めた頃からいつか記事にしてみたいと思っていました。

一方、KKT条件は少なくとも筆者の大学時代で講義に出てきた記憶はなく、似たような概念でありながらこの概念を知るのはずっと先になります。ラグランジュの未定乗数法と同じく、非常に面白い概念ではありますし、是非大学でも学んでみたかったなと思います。（使われる計算分野が違うという背景もあったりするのでしょうか？）

ところで、KKT条件はカルーシュ・クーン・タッカー条件（Karush-Kuhn-Tucker condition）の略ですが、言ってみたい数学系ワードトップ５に入りませんかね…？それぐらいインパクトを感じる名前で、一度聞いたら忘れないワードになっています。

…さて。話が脱線してしまいましたが、さっそく本題に移っていきましょう！

はじめに

最大値・最小値を求めよう

いきなりラグランジュの未定乗数法を説明する前に、まずは「最大値・最小値を求める」とはどういうことか振り返っていきましょう。

皆さんは学校で学んだ数学の中で「最小値・最大値」を学ぶ機会があったと思います。例えば、『関数 $f(x)$ を
$$
f(x) = \sin^2x - \frac{1}{2}x + 4
$$
と定めたとき、$f(x)$ の最大値・最小値を求めよ』みたいな感じですね。

このときの共通の解き方として、「微分」がキーワードになってきます。さて、実際に $f(x)$ を微分してみましょう。すると、
$$
\frac{df}{dx} = 2\sin x \cos x -\frac{1}{2}
$$
のような結果が得られます。さて、なぜ微分するか？という問いですが、それは グラフの山や谷になっている部分を知りたい からですね。

微分した関数に具体的な値（ここでは $a$）を代入した時の値、つまり $\frac{df}{dx}(a)$ とは、『グラフ $ y=f(x) $ を $xy$ 平面上に書いたときの $x=a$ での傾き』を表しています。最大値（最小値）を取るということは、グラフの山の部分（谷の部分）と予想できますね？なので、

\frac{df}{dx}(a)=0 \Rightarrow x=a で最小値(最小値)を取る可能性がある

ということが言えそうです。ちなみに上記の式を解いてみると、

\begin{eqnarray}
\frac{df}{dx} &=& 2\sin x \cos x -\frac{1}{2} = 0  \\
\sin(2x) &=& \frac{1}{2}  \\
x &=& \frac{\pi}{12} + n\pi, \frac{5\pi}{12} + n\pi \ (n \in \mathbb{Z})
\end{eqnarray}

となりますね。なので、$x = \frac{\pi}{12}, \frac{5\pi}{12}, \frac{13\pi}{12}, \frac{17\pi}{12}, \cdots$ は最大値・最小値の候補になるわけです。

ここで注意してほしいのは、ここで得た値は最大値・最小値の候補なのであって、最大値・最小値のどちらかを取るとは言っていないことです。この計算のオチを言ってしまうと、最大値・最小値いずれも実際は存在しません。（まぁ、$|x|$ を十分大きくすれば、$f(x) \sim - \frac{1}{2}x + 4$ なのでその事実からも何となくお分かりいただけるかと思います。）

この話は、もし高校数学のことを覚えてらっしゃる方はお分かりかと思いますが、これは極値という言葉で定義されています。極大値・極小値のことですね。先ほど、

$\frac{df}{dx}(a)=0$ ⇒ $x=a$ で最小値（最小値）を取る可能性がある

と書きましたが、「可能性がある」とは何ともあいまいな表現ですね…。このようなあいまいな表現をしたのは、

$\frac{df}{dx}(a)=0$ ⇒ $x=a$ で極大値（極小値）を取る

が成り立たないからなんですね。では、どんな関係であれば成り立つのでしょうか？実は、

\frac{df}{dx}(a)=0 \ かつ \ \frac{d^2f}{dx^2}(a)>0 \ (<0) \Rightarrow x=a で極小値(極大値)を取る

であれば成り立ちます。

多変数関数の最大値・最小値

ということで、最大値・最小値を紹介していきました。最大値・最小値を求めるには、まずは極値を求める必要があるということを説明してまいりました。振り返ると、

$\frac{df}{dx}(a)=0$ かつ $\frac{d^2f}{dx^2}(a)>0 \ (<0)$ ⇒ $x=a$ で極小値（極大値）を取る

は成り立つので、まずは「$\frac{df}{dx}(a)=0$ を求める」ことで極大値・極小値の候補、ひいては最大値・最小値の候補を求めるんでしたね。もしこれが多変数関数になった場合、どうなるでしょうか？それを紐解くには、$\frac{df}{dx}(a)=0$ と $\frac{d^2f}{dx^2}(a)>0$ を言い換える必要があります。

ここからは簡単のため、$z = f(x, y)$ のような二変数関数で考えてみましょう。最初の式 $\frac{df}{dx}(a)=0$ は、勾配ベクトル $\nabla f(a,b)$ に対し、
$$
\nabla f(a,b) = \left(
\frac{\partial f}{\partial x}(a,b), \frac{\partial f}{\partial y}(a,b)
\right)= {\rm 0}
$$
であると置き換えられます。

では、$\frac{d^2f}{dx^2}(a)>0$ はどのように言い換えられるでしょうか？これは実はちょっと難しいのですが、ヘッセ行列

\nabla^2 f(a,b) = \begin{pmatrix}
\frac{\partial^2 f}{\partial x^2}(a,b) & \frac{\partial^2 f}{\partial x \partial y}(a,b) \\
\frac{\partial^2 f}{\partial x \partial y}(a,b) & \frac{\partial^2 f}{\partial y^2}(a,b)
\end{pmatrix}

が正定値行列であれば極大値、負定値行列であれば極小値、という条件で表すことができます。二変数関数の場合、かなりシンプルに表すことができて、

\frac{\partial^2 f}{\partial x^2}(a,b)\frac{\partial^2 f}{\partial y^2}(a,b) -  \left(\frac{\partial^2 f}{\partial x \partial y}(a,b)\right)^2 > 0 \\

かつ $\frac{\partial^2 f}{\partial x^2}(a,b)>0$ が極小値の場合の条件です。極大値の場合は$\frac{\partial^2 f}{\partial x^2}(a,b)<0$ とします。

ちなみに「$\nabla f(a,b) = 0, \nabla^2 f(a,b)$ が正定値（負定値）行列」⇒「$(x,y)=(a,b)$ は極大値（極小値）である」の証明ですが、定義を与えた上でテイラー展開を用いる方法が知られています。詳細は割愛させてください。こちらに二変数の場合の証明がありますので、参照いただければと思います。

ここまでをいったん整理しましょう。最初に一変数の最大値・最小値を求める方法を紹介していきました。次に多変数（本記事では二変数）の最大値・最小値を求める方法を紹介していきました。これらは勾配ベクトルとヘッセ行列によって特徴づけられました。しかし、一変数関数と多変数以上の関数で決定的に異なる点があります。それは、制約条件です。

ラグランジュの未定乗数法とは

そもそも一変数関数と多変数関数の違いは何でしょう？それは、変数の数が一変数関数は１つで多変数関数は２つ以上ということですね。

「なんだ当たり前じゃないか…。」というかそれが定義なんですが、それによって制約条件というものを考えることができます。制約条件とは、関数の変数を特定の値（やその組）に固定する関数のことです。例えば、二変数関数 $z=f(x,y)$ に対して、$x+y=1$ と変数の組み合わせに制限をかけることができます。このような関数のことを指すんですね。

一変数しかない場合、制約をかけてしまうと関数がただの値になってしまうので、あまり数学的対象として面白いものではないですね…。一方、多変数関数であれば、たくさんある変数のうち、一部の変数に対して制限をかけようということも可能になってきます。

ではいよいよ、ラグランジュの未定乗数法について説明していきましょう。ここでは簡単のため、まずは2変数で説明していきます。制約条件を $g(x,y)=0$ とし、最大値・最小値を求めたい関数を $f(x,y)$ とします。

定理

細かい条件は一旦無視して、まずはラグランジュの未定乗数法の主張を書いていきます。

制約条件を $g(x,y)=0$ の仮定の元、$f(x,y)$ が $(x,y)=(a,b)$ で極値を持つとします。この時、
$$
L(x,y) = f(x,y) - \lambda g(x,y)
$$
とおくと、
$$
\frac{\partial L}{\partial x}(a,b) = \frac{\partial L}{\partial y}(a,b) = \frac{\partial L}{\partial \lambda}(a,b) = 0
$$
が成り立つ。ただし、$\frac{\partial g}{\partial x}(a,b) \ne 0$ または $\frac{\partial g}{\partial y}(a,b) \ne 0$ とする。この計算によって、極値を求める方法をラグランジュの未定乗数法という。

解説

ということで主張を書いていきました。この証明についてはこちらの記事がかなり理解しやすいかと思いますので、ご興味があればご確認ください。

ここで少し疑問が浮かんできた方は鋭い（というかこの記事を読まなくてもいいくらいご理解いただいている）方かと思いますが、「こんな解き方しなくても普通に解けばいいんじゃない？」って思いませんか？まだ@tsum_tsumが大学の頃、ラグランジュの未定乗数法を学んだ時はそう思ったものです。

どういうことか説明するために、例を１つ考えてみます。皆さんは高校数学の中で円と直線の交点を求める計算をしたことがあるかと思います。例えば、『$x^2+y^2=1$ と $2x+y=1$ の交点の座標を求めなさい』みたいな問題ですね。この問題の一番シンプルな方法として、$2x+y=1$ を $y=-2x+1$ にして、$x^2+y^2=1$ に代入するという方法が思いつくかと思います。これであれば、一変数関数の問題に帰着できますね。

ラグランジュの未定乗数法も同じように、$g(x,y)=0$ を $y=h(x)$ に変形し、$f(x,y)=f(x,h(x))$ とすればいいのでは？って思ったわけです。しかし、実際に演習問題をやってみたときに気づきます。$g(x,y)=0$ を $y=h(x)$ に直すのって、結構面倒な上に、そもそも変形できない（初等的な関数で表せない）場合ですね。

上記の話からまとめると、ラグランジュの未定乗数法は $g(x,y)=0$ を $y=h(x)$ に変形できない（変形するのが面倒） な場合に便利なんですね。

具体例

ここまでラグランジュの未定乗数法を解説していきました。実際に例題を使ってその威力を確かめてみましょう。とはいえ、普通の問題を解いても面白さがないなぁと思い、少し癖のある問題を考えてみます。

問題

半径1の円に内接する三角形のうち、面積が最大になる三角形は何か？

解説

実は過去の入試問題（京都大学理系後期日程 1999）にも類題があり、ラグランジュの未定乗数法を紹介するのにぴったりかと思い、この問題にしてみました。

半径1の円に内接する三角形の3頂点を$A, B, C$、それぞれのなす角を $x, y, z$ とします。

すると三角形の内角の和は $\pi$ なので
$$
x+y+z = \pi,
$$

正弦定理より
$$
2 = \frac{AB}{\sin z} = \frac{BC}{\sin x} = \frac{CA}{\sin z},
$$
よって、

AB = 2 \sin z, BC = 2 \sin x, CA = 2 \sin y

が得られます。また、三角形ABCの面積を $S$ とすると、

\begin{eqnarray}
S &=& \frac{1}{2} AB \cdot BC \cdot \sin y \\
&=& \frac{1}{2} (2\sin z)(2\sin x) \sin y \\
&=& 2\sin x \sin y \sin z \\
\end{eqnarray}

が得られます。よって、これは制約条件 $x+y+z = \pi$ における $S = 2\sin x \sin y \sin z$ の最大値を求める問題に帰着しますね。よってラグランジュの未定乗数法が利用できそうです。
$$
L(x,y,z,\lambda) = 2\sin x \sin y \sin z - \lambda(x+y+z-\pi)
$$
とおいて、それぞれの変数で偏微分しましょう。

\begin{eqnarray}
\frac{\partial L}{\partial x} &=& 2\cos x \sin y \sin z - \lambda = 0  \\
\frac{\partial L}{\partial y} &=& 2\sin x \cos y \sin z - \lambda = 0
\end{eqnarray}

これらの式から $\lambda$ を削除して、整理すると

$$
\sin z \ (\cos x \sin y - \sin x \cos y) = 0
$$

となりますが、$\sin z = 0$ だと、$z=0, \pi$ で不適ですね。よって、$\cos x \sin y - \sin x \cos y = 0$ ですが、

$$
\cos x \sin y - \sin x \cos y = \sin(y - x) = 0
$$

なので、$y - x = 0$ ですね。あとは同様の計算を行うことで $z - y = 0$ も得られるので、

$$
x = y = z = \frac{\pi}{3}
$$

が得られ、求める三角形は正三角形であることが分かりました。

KKT条件とは

ここまでラグランジュの未定乗数法について説明していきました。ラグランジュの未定乗数法とは制約条件が付いた関数の最大値最小値を求める手法のことでした。しかし、よく考えてみてほしいのですが、制約条件は何も方程式に限ったことではないですよね？当然不等式を制約条件としてもいいはずです。では、ここからはKKT条件というものについて説明していきましょう。

先の説明で少しだけネタバレしてしまいましたが、KKT条件とは制約条件が不等式で表されるものとイメージしてもらえればいいと思います。対象となる問題を正しく整理しましょう。

問題設定

KKT条件の問題設定は下記のとおりです。

まず、$f(x_1, \cdots, x_n)$ の最小値を求めることを目的にします。そして、制約関数を $g(x_1, \cdots, x_n) \le 0$ とします。簡単のため、制約関数は1つだけにしておきましょう。このとき、KKT条件は次のように定められます。

定理

$(x_1, \cdots, x_n) = (x^*_1, \cdots, x^*_n)$ が極小点であるとき、ある $\lambda^*$ が存在し、

\begin{eqnarray}
\nabla L(x^*_1, \cdots, x^*_n, \lambda^*) &=& \nabla f(x^*_1, \cdots, x^*_n) - \lambda^* \nabla g(x^*_1, \cdots, x^*_n) = 0  \\
\lambda^* &\ge& 0  \\
g(x^*_1, \cdots, x^*_n) &\le& 0  \\
\lambda^* g(x^*_1, \cdots, x^*_n) &=& 0
\end{eqnarray}

が成り立つ。

まとめ

ということで「ラグランジュの未定乗数法」「KKT条件」について説明していきました。それぞれ似た概念でありながら、$g(x_1, \cdots, x_n) \le 0$ と $g(x_1, \cdots, x_n) = 0$ という条件によって、これだけ変わってくるのもなんですね。ラグランジュの未定乗数法は数学系の学部でも早い段階で学ぶのに対し、KKT条件は仕事でAI関係に携わるまで見ることはありませんでした。

ちなみに発見された経緯も全く違っており、「ラグランジュの未定乗数法」は1700年台には発見（厳密な年は分からず申し訳ないです）されていた一方、「KKT条件」は1951年にクーンとタッカーが見つけたものの、1939年にカルーシュが既に見つけていたためそのように呼ばれるようになりました。不等号が付くか付かないかの違いだけで約200年の差があることを考えると、数学の奥深さが垣間見えたような気がします。

今回はKKT条件の中でも一番簡単な例だけを書きましたが、等号の制約条件$N$個、不等号の制約条件$M$個のような仮定も同じように考えることができます。ご興味があれば、下記の参考文献を見ていただければと思います。

それでは今回も駄文でしたが、最後までお読みいただきありがとうございます！！！

参考文献