この記事ではラグランジュの未定乗数法について徹底的に解説していく。
なぜラグランジュの未定乗数法はあれで導出することができるのか、厳密な証明、直感的な理解、幾何的な解釈をすべて取り扱う渾身の記事である。
この記事を読めばラグランジュの未定乗数法の理解が深淵に達すること請け合い。
ラグランジュの未定乗数法とは
ラグランジュの未定乗数法とは、多変数関数がある制約条件を満たすときの最大値または最小値を求めるための手法である。経済学や物理学、工学、機械学習など、様々な場面で活用される。
まず、僕たちが通常扱う最適化問題は、目的関数と呼ばれる関数を最大化または最小化する変数の値を見つけることだ。これは、制約条件がない場合には、微分を使って解くことができる。しかし、何か制約条件がある場合、つまり最適化したい関数が何らかの条件に縛られている場合はどうするのだろう？
ここでラグランジュの未定乗数法の出番だ。この方法では、制約条件を満たす最適化問題を、制約条件がない問題に変換して解く。それでは、どのようにしてそれを達成するのかを見てみよう。
まず、目的関数を \(f(\mathbf{x})\)、制約条件を \(g(\mathbf{x}) = 0\) とする。ここで、\(\mathbf{x}\) はベクトルで、複数の変数が存在する場合を考慮している。ラグランジュの未定乗数法では、新しい関数、ラグランジュ関数を次のように定義する。
ラグランジュ関数の定義
$$ L(\mathbf{x}, \lambda) = f(\mathbf{x}) - \lambda g(\mathbf{x}) $$
ここで、\(\lambda\) はラグランジュ乗数と呼ばれる。新たにこの\(\lambda\)という未知数が加わった。ラグランジュの未定乗数法では、このラグランジュ関数の勾配がゼロになる点を求める。
つまり、次の連立方程式を解く。
$$ \frac{\partial L}{\partial \mathbf{x}} = 0 $$
$$ \frac{\partial L}{\partial \lambda} = 0 $$
いま、\(\mathbf{x}\)が\(D\)次元のベクトルとすると、計\(D+1\)個の方程式を得ることができる。それを解くことによって制約条件下での最大化（最小化）されている点\(\mathbf{x}\)とそれに対応するラグランジュ乗数\(\lambda\)の値を求めることができる。
そして、解いた結果得られた \(\mathbf{x}\) が元の制約条件 \(g(\mathbf{x}) = 0\) を満たす最適な値となる。つまり、この方法を用いると、制約のある最適化問題を、制約のない最適化問題に変換することができるのだ。
具体的に計算してみる
簡単な例を使って具体的に計算してみよう。
【例題①】
目的関数 \(f\left(x_1, x_2\right)=1-x_1^2-x_2^2 \rightarrow\) 最大
制約条件 \(g\left(x_1, x_2\right)=x_1+x_2-1=0\)
制約条件\(g\left(x_1, x_2\right)=x_1+x_2-1=0\)の下で、\(f\left(x_1, x_2\right)=1-x_1^2-x_2^2\)を最大化することを考える。
青色の同心円は\(f\left(x_1, x_2\right)\)の等高線を表していて、斜めの赤色の直線は制約面（この問題では二次元なので線）\(g\left(x_1, x_2\right)=0\)を表している。
この場合のラグランジュ関数は次の式で与えられる。
$$
L(\mathbf{x}, \lambda)=1-x_1^2-x_2^2+\lambda\left(x_1+x_2-1\right)
$$
したがって、ラグランジュ関数の\(x_1,x_2,\lambda\)に対する最大化の条件は
$$
\begin{aligned}
-2 x_1+\lambda & =0 \\
-2 x_2+\lambda & =0 \\
x_1+x_2-1 & =0 .
\end{aligned}
$$
この方程式を解くことで、最大化される点\(\left(x_1^{\star}, x_2^{\star}\right)=\left(\frac{1}{2}, \frac{1}{2}\right)\)および対応するラグランジュ乗数\(\lambda=1\)が求まる。
事前知識の整理
ここでは、ラグランジュの未定乗数法、延いては最適化問題において必要不可欠であり、この記事を理解するために必要不可欠である概念をまとめる。
用語の導入
基礎になる空間\(X\)（多くの場合\(\Re^n\)あるいは\(\mathbb{Z}^n\)）と\(\Re^n\)の部分集合\(S\)、さらに\(X\)上で定義された関数\( f: X \rightarrow \Re^n \)が与えられたとき\(f\)を最小にする解\( x \in S \cap X \)を求める問題、すなわち
目的関数 \(f(x) \rightarrow\) 最小
制約条件 \( x \in S \cap X \)
を最適化問題もしくは計画問題という。通常\(S\)は関数\(g_i: \Re^n \rightarrow \Re, i=1,2,\dots,m\)による不等式および等式（制約式）を用いて
$$
\begin{array}{r}
S=\left\{x \in \Re^n \mid g_i(x) \leq 0, i=1,2, \ldots, l,\right. \\
\left.g_i(x)=0, i=l+1, \ldots m\right\}
\end{array}
$$
と表現される。\(S \cap X\)を実行可能領域といい、\(S \cap X \neq \phi\)ならばその問題は実行可能、\( x \in S \cap X \)を実行可能解という\(S \cap X = \phi\)ならばその問題は実行不能であるという。
目的関数を最小にする実行可能解、すなわち任意の\( x \in S \cap X \)に対して\( f\left(x^*\right) \leq f(x) \)を満たす\( x^* \in S \cap X \)が存在すれば、それを最適解という。
最適化問題において、目的関数の\(f(x)\)の最大化は\(-f(x)\)の最小化と同じで、不等式の向き\( \geq \)は両辺に\(-1\)を乗じると\(\leq\)に変換できるので上のように統一して議論を進めても一般性を失わない。
そして、\(x^* \in S\)に対しある近傍\(B\)が存在して、任意の\( x \in S \cap B \)に対して\( f\left(x^*\right) \leq f(x) \)が成立するとき、\(x^*\)は局所最小解であるという。逆に\( f\left(x^*\right) \geq f(x) \)ならば局所最大解という。これらをまとめて局所最適解というが、先ほど述べた通り最大化は最小化と同義なので、ここでは局所最小解＝局所最適解とする。
テイラー展開
テイラー展開
関数\( f: \Re^n \rightarrow \Re \)の点\(x' \in \Re^n\)におけるテイラー展開はの一回微分の項まで取ることによって
$$
f(x)=f\left(x^{\prime}\right)+\nabla f\left(x^{\prime}\right)^{\top}\left(x-x^{\prime}\right)+O\left(\left\|x-x^{\prime}\right\|^2\right) \tag{1}
$$
任意の\(\Delta x \in \Re^n\)およびスカラー\(\alpha > 0\)を使用して書き換えると、次の式が成立する。
$$
f\left(x^{\prime}+\alpha \Delta x\right)=f\left(x^{\prime}\right)+\alpha \nabla f\left(x^{\prime}\right)^T \Delta x+O\left(\alpha^2\|\Delta x\|^2\right) \tag{2}
$$
ここで\(f\)は連続微分可能であると仮定している。そして最後の項\(O\)はオーダー表記と呼ばれ、\(O(w)\)は十分小さい全ての\(w>0\)に対して、定数\(\beta > 0\)が存在して、それが表す量の絶対値が\(\beta w\)以下に抑えられることを意味する。例えば(2)では、左辺と右辺の誤差の絶対値\(\left|f\left(x^{\prime}+\alpha \Delta x\right)-\left(f\left(x^{\prime}\right)+\alpha \nabla f\left(x^{\prime}\right)^T \Delta x\right)\right|\)がオーダー\(O\left(\alpha^2\|\Delta x\|^2\right)\)であることを述べている。すなわち\(\|\Delta x\| \rightarrow 0\)ならば誤差も0に近づき、その速さは\(\|\Delta x\|^2\)と評価される。\(\alpha\)についても同様である。
ワイエルシュトラスの最大値定理
ワイエルシュトラスの最大値定理
\(K\)は\(\Re^n\)の空でない有界な閉集合であり、\( f: K \rightarrow \Re \)は\(K\)で連続であるとする。このとき、\(f\)は最大値を持つ。すなわち、
$$
(\exists \boldsymbol{c} \in K)(\forall \boldsymbol{x} \in K) f(\boldsymbol{c}) \geq \boldsymbol{f}(\boldsymbol{x})
$$
が成り立つ。最小値についても同様である。
この証明は長くなり、本筋からそれるのでここでは割愛する。
制約なし問題の最適性必要条件
まずは、そもそもの制約がない場合を考えてみよう。
制約なし問題の設定
目的関数 \(f(x) \rightarrow\) 最小
制約条件 \(x \in \Re^n\)
この設定の上で\(f\)の局所最適解を探すにはシンプルに微分して0になる点を調べてやればよい。つまり
制約なし問題の最適性必要条件
制約条件なし問題において\(f\)は連続微分可能であるとする。このとき、点\(x^*\)が局所最適解であれば
$$ \nabla f(x^*)=0 $$
が成立する。ただし、0はn次元0ベクトルである。
尚、この式を満たす点を停留点という
【証明】
\( \Delta x \in \Re^n\)とスカラー\(\alpha > 0 \)を考える。\(\alpha\)が十分小さければ、点\(x^*\)から\(\alpha \Delta x\)および\( -\alpha \Delta x\)だけ移動したとき、\(f(x^*)\)の局所最適性より
$$
f\left(x^*+\alpha \Delta x\right) \geq f\left(x^*\right), \quad f\left(x^*-\alpha \Delta x\right) \geq f\left(x^*\right)
$$
を得る。これらの左辺にテイラー展開した式を代入すると(\(x' = x^*\)とおく)
$$
\left|\nabla f\left(x^*\right) \Delta x\right|=O\left(\alpha^2\|\Delta x\|^2\right) / \alpha
$$
を得る。\(\Delta x\)は任意であるので\(\alpha \rightarrow 0\)を考えると\( \nabla f(x^*)=0 \)が成り立つ。
ポイント
ここで必要条件ということに注意しておこう。つまり全ての停留点が実際に最小値または最大値を示しているわけではない。ある場合には、停留点は最小値または最大値ではなく、「鞍点」となる場合がある。具体的には、関数\(f(x)=x^3\)の時、この関数の微分は\(f'(x)=3x^2\)で、これが\(0\)になるのは\(x=0\)のときだが、\(x=0\)は最小値でも最大値でもない。
等式制約問題の最適性必要条件
制約条件が等式であるものを示してみよう。すなわち
等式制約条件の問題設定①
目的関数 \(f(x) \rightarrow\) 最小
制約条件 \(g_i(x)=0, i=1,2, \ldots m\), \(x \in \Re^n\)
という問題を考える。この問題設定を今後①と省略する。
ここでは
$$
g(x)=\left(g_1(x), g_2(x), \ldots, g_m(x)\right)^T
$$
とおき、ここでは\(u \in \Re^n\)はラグランジュ乗数ベクトルとする。
さて、いよいよ等式による制約条件ありでの目的関数の最小化を考えるわけだが、
目指すべき指針としては新しい関数を用意して、制約なんて考慮せずにそれを最小化すれば目的の関数の最小化を達成できるというものがあれば手っ取り早い
その関数は\(f(x)\)は勿論、\(g(x)\)も制約に対して違反すればするほど大きくなってしまうように組み込まれているようなものであると想像できる。
等式条件のペナルティ関数
等式制約条件の問題設定とパラメータ\(k=1,2,\dots\)から次の関数を定義する
等式条件のペナルティ関数
$$
F^k(x)=f(x)+\frac{k}{2}\|g(x)\|^2+\frac{\alpha}{2}\left\|x-x^*\right\|^2 \tag{1}
$$
ただし、\(x^*\)は①の局所最適解であり、\( \alpha>0 \)はある定数である。
二項目の\(\frac{k}{2}\|g(x)\|^2\)は等式制約条件\(g_i(x),i=1,2,\dots\)の違反に対するペナルティと解釈できる。
三項目の\(\frac{\alpha}{2}\left\|x-x^*\right\|^2\)は、\(g(x)=0\)をみたす解\(x\)を考えるとき、\(x^*\)が、その近傍内で、関数\(F^k(x)=f(x)+\frac{\alpha}{2}\left\|x-x^*\right\|^2\)の唯一の局所最適解となるように導入されたものである。
\(x^*\)は局所最適解であるので、適当な\( \varepsilon>0 \)を選べば、\(x^*\)の近傍（の閉包）
$$
\bar{B}_\epsilon\left(x^*\right)=\left\{x \in \Re^n \mid\left\|x-x^*\right\| \leq \epsilon\right\}
$$
において、そこに属す任意の実行可能解\(x\)に対し\(f(x^*) \leq f(x)\)である。
最適化問題
目的関数 \(F^k(x) \rightarrow\) 最小
制約条件 \(\quad x \in \bar{B}_\epsilon\left(x^*\right)\)
を新しく定義する（これを問題②と呼ぶ）と、\(\bar{B}_\epsilon\left(x^*\right)\)は有界閉集合なので、ワイエルシュトラスの最大値定理より最小解が存在する。それを\(x^k\)と記す。
目指すべき目標はこの\(x^k\)による点列\(\{x^k\}\)が\(x^*\)に収束することを示すことである。
まずは、任意の\(k\)に対し、\(x^k\)の最小性より
$$
\begin{aligned}
F^k\left(x^k\right) & =f\left(x^k\right)+\frac{k}{2}\left\|g\left(x^k\right)\right\|^2+\frac{\alpha}{2}\left\|x^k-x^*\right\|^2 \qquad (1)\\
& \leq F^k\left(x^*\right)=f\left(x^*\right)
\end{aligned}
$$
が成立するので
$$
\lim _{k \rightarrow \infty}\left\|g\left(x^k\right)\right\|=0
$$
でなければならない。もしそうでなければ、(1)の項、\((k / 2)\left\|g\left(x^k\right)\right\|^2\)は\(k \rightarrow \infty\)のとき発散するが、他の項の変化は微小なので矛盾を生じてしまう。従って、\(\{x^k\}\)の任意の極限点\(\bar{x}\)は\(g(\bar{x}=0\)をみたす。つまり、等式制約条件の最適化問題設定①の実行可能解である。その結果(1)に戻って
$$
f(\bar{x})+\frac{\alpha}{2}\left\|\bar{x}-x^*\right\|^2 \leq f\left(x^*\right)
$$
を得ることができる。\(\bar{x}\)が①の実行可能解であることから\(f\left(x^*\right) \leq f(\bar{x})\)であり、上式と併せて\(\left\|\bar{x}-x^*\right\|^2=0\)つまり\(\bar{x}=x^*\)を得る。要するに\(\{x^k\}\)は\(x^*\)へ収束する。
点\(x^*\)は問題②の実行可能領域の内点であるので、\(k\)が十分大きければ、\(x^k\)も内点である。その結果、\(x^k\)は制約なし最適化問題
目的関数 \(F^k(x) \rightarrow\) 最小
制約条件 \(\quad x \in \Re^n\)
の局所最適化でもある。（これを問題③と呼ぶ）つまり端的に換言すると等式制約問題の最適化は\(F^k(x)\)の最小化と同義なのである。
さて、何を示したかったのか今一度整理する。
等式制約問題の最適性必要条件の証明
等式制約条件の問題設定①
目的関数 \(f(x) \rightarrow\) 最小
制約条件 \(g_i(x)=0, i=1,2, \ldots m\), \(x \in \Re^n\)
において実行可能解\(x^* \in \Re^n\)、すなわち
$$
g_i\left(x^*\right)=0, \quad i=1,2, \ldots, m
$$
を考え、さらに局所最適解であるとする。
このとき我々が示したいのは以下である。
等式制約問題の最適性必要条件
\(f(x)\)と\(g_i(x),i=1,2,\dots,m\)はすべて連続微分可能、また\(x^*\)は正則であるとする。このときつぎの条件をみたすラグランジュ乗数ベクトル\(u^* \in \Re^m\)が存在する。
$$
\nabla f\left(x^*\right)+\sum_{i=1}^m u_i^* \nabla g_i\left(x^*\right)=0
$$
つまりこれを満たす\(x^*\)は最適解となる可能性があるということ。（十分条件ではないので、必ずしも最適解とは限らない）
「正則」について
\(m\)個の制約関数の勾配ベクトル\(\nabla g_i(x), i=1,2, \ldots,m\)が互いに一次独立であるとき、点\(x\)は正則であるという。また
$$
\nabla g(x)=\left(\nabla g_1(x), \nabla g_2(x), \ldots, \nabla g_m(x)\right)^T
$$
によって定義される\(m \times n\)行列を\(g(x)\)のヤコビ行列という。その\(ij\)要素は\(\partial g_i(x) / \partial x_j\)である
【証明】
先ほどの\(F^k(x)\)に関する議論から、制約なし問題③の局所最適解\(x^k\)に最適性必要条件を適用することができて、つまり\(F^k(x)\)の勾配をとって
$$
\left(\nabla F^k\left(x^k\right)=\right) \nabla f\left(x^k\right)+k \nabla g\left(x^k\right)^T g\left(x^k\right)+\alpha\left(x^k-x^*\right)=0 \tag{1}
$$
を得る。\(x^*\)の正則性から、\(k\)が十分大きければ\(x^k\)も正則であり、したがって\(\nabla g\left(x^k\right)^T\)およびその転置行列\(\nabla g\left(x^k\right)\)の階数は\(m\)である。これはそれらの積である\(m\)次正方行列\(\nabla g\left(x^k\right) \nabla g\left(x^k\right)^T\)が正則であることを意味する。そこで(1)の両辺に左から\(\left(\nabla g\left(x^k\right) \nabla g\left(x^k\right)^T\right)^{-1} \nabla g\left(x^k\right)\)を乗じ整理すると、
$$
k g\left(x^k\right)=-\left(\nabla g\left(x^k\right) \nabla g\left(x^k\right)^T\right)^{-1} \nabla g\left(x^k\right)\left(\nabla f\left(x^k\right)+\alpha\left(x^k-x^*\right)\right)
$$
を得る。この式において\(k \rightarrow \infty\)とすると、\(\{x^k\}\)は\(x^*\)に収束するので、点列\(\{kg(x^k)\}\)は\(m\)次元ベクトル
$$
u^*=-\left(\nabla g\left(x^*\right) \nabla g\left(x^*\right)^T\right)^{-1} \nabla g\left(x^*\right) \nabla f\left(x^*\right)
$$
に収束する。従って、式(1)において\(k \rightarrow \infty\)とすれば
$$
\nabla f\left(x^*\right)+\nabla g\left(x^*\right)^T u^*=0
$$
よって示された。
これはまさにラグランジュ関数\( L(\mathbf{x}, \lambda) = f(\mathbf{x}) - \lambda g(\mathbf{x}) \)を\(x\)について偏微分したものであり、
結局ラグランジュの未定乗数法での一連の計算過程は
$$ \frac{\partial L}{\partial \mathbf{x}} = 0 \tag{1}$$
$$ \frac{\partial L}{\partial \lambda} = 0 \tag{2}$$
これを解くことであったが
(1)はここで示したように、局所最適解であるための必要条件をみたす\(x\)を探すための方程式を出していて
(2)は\(g(x)=0\)つまり制約条件そのものである。
ラグランジュの未定乗数法のココロ
証明まで済んだわけだが、改めてラグランジュ関数を見てみて何をしているのか、その本質部分を見ていこう。
そもそも関数の最大最小は微分が0になるところを探すという基本原則があるのだが、制約条件がある場合なかなかうまくいかない。
先ほど冒頭で行った例題を使ってみてみる
【例題①】
目的関数 \(f\left(x_1, x_2\right)=1-x_1^2-x_2^2 \rightarrow\) 最大
制約条件 \(g\left(x_1, x_2\right)=x_1+x_2-1=0\)
さてこれを計算した結果の最大になる点は\((x,y)=(1/2,1/2)\)となるのだった。
本当にそうなのか制約条件である直線上で関数を考えてみよう。
直線方向の変化
\(u \in \Re\)として、\((x,y)=(1/2,1/2)\)から\(x\)方向に\(u\),\(y\)方向に\(-u\)だけ移動した点を考えてそれを\(f\)に代入した関数を改めて\( \tilde{f}_1 \)として考える。
$$
\begin{aligned}
\tilde{f}_1: & =f\left(\frac{1}{2}+u, \frac{1}{2}-u\right) \\
& =\left(\frac{1}{2}+u\right)^2+\left(\frac{1}{2}-u\right)^2 \\
& =2 u^2+\frac{1}{2}
\end{aligned}
$$
$$
\tilde{f}_1^{\prime}(u)=4 u \quad \text{なので} \quad \tilde{f}_1^{\prime}(0)=0
$$
\(\frac{\partial f}{\partial x}\)も\(\frac{\partial f}{\partial y}\)も\((x,y)=(1/2,1/2)\)で0でない。しかし、上記の計算より直線\(x+y=1\)方向の微分は0なので\(x+y=1\)の中では\((x,y)=(1/2,1/2)\)は最小であることが分かる。
ここで気になることが出てくる。それは、制約条件の直線方向以外の微分はどうなるのだろうか？
直線方向以外の変化
ここでは、直線に対して垂直な、跨ぐような方向に\((x,y)=(1/2,1/2)\)から\(x\)方向に\(u\),\(y\)方向に\(v\)だけ移動した点を考えてそれを\(f\)に代入した関数を改めて\( \tilde{f}_2 \)として考える。
$$
\begin{aligned}
\widetilde{f}_2(v) & =f\left(\frac{1}{2}+v, \frac{1}{2}+v\right) \\
& =\left(\frac{1}{2}+v\right)^2+\left(\frac{1}{2}+v\right)^2 \\
& =\frac{1}{4}+v+v^2+\frac{1}{4}+v+v^2 \\
& =2 v^2+2 v+\frac{1}{2}
\end{aligned}
$$
$$
\tilde{f}_2^{\prime}(v)=4 v+2 \quad \text{なので} \quad \tilde{f}_2^{\prime}(0)=2 .
$$
このように直線\(x+y=1\)方向以外の微分は0にならない。なので\(\frac{\partial f}{\partial x}\)も\(\frac{\partial f}{\partial y}\)も\((x,y)=(1/2,1/2)\)で0にならない。
つまり、この制約している直線方向のみでしか微分が0にならないというのが制約付きの極値問題が難しい原因で諸悪の根源なのである。
制約条件の関数の微分の変化
ここで、制約条件の関数\(g\)についても調べてみる。
$$
\left\{\begin{array}{l}
\tilde{g}_1(u)=g\left(\frac{1}{2}+u, \frac{1}{2}-u\right)=0 . \\
\tilde{g}_2(v)=g\left(\frac{1}{2}+v, \frac{1}{2}+v\right)=2 v
\end{array}\right.
\Leftrightarrow\left\{\begin{array}{l}
\tilde{g}_1^{\prime}(u)=0 \quad \text{なので} \quad \tilde{g}_1^{\prime}(0)=0 \\
\tilde{g}_2^{\prime}(v)=2 \quad \text{なので} \quad \tilde{g}_2^{\prime}(0)=2
\end{array}\right.
$$
\(\tilde{f}\)の場合と同様に計算してみると、直線方向の微分は0になるがそうでない方向の微分は0にならない。
つまり、\(\tilde{g}\)は\(\tilde{f}\)と似た性質を持っているということがわかる。
ここまでの議論をまとめると。
| \(\tilde{f}\) | \(\tilde{g}\) | |
| 直線方向の微分 | \(\widetilde{f}_1^{\prime}(0)=0\) | \(\widetilde{g}_1^{\prime}(0)=0\) |
| 直線方向に垂直方向の微分 | \(\tilde{f}_2^{\prime}(0) \neq 0\) | \(\tilde{g}_2^{\prime}(0) \neq 0\) |
となっているが、ということは適当な\(\lambda\)を使って\( L(\mathbf{x},\mathbf{y}, \lambda) = f(\mathbf{x},\mathbf{y}) - \lambda g(\mathbf{x},\mathbf{y}) \)と定義した関数\(L(\mathbf{x},\mathbf{y}, \lambda)\)に同様の計算を施すと
$$
\begin{aligned}
& \widetilde{L}_1(u, \lambda)=L\left(\frac{1}{2}+u, \frac{1}{2}-u, \lambda\right) \\
& \widetilde{L_2}(v, \lambda)=L\left(\frac{1}{2}+v, \frac{1}{2}+v, \lambda\right)
\end{aligned}
$$
とすると\(\tilde{f}_1^{\prime}(0)-\lambda \tilde{g}_1^{\prime}(0)=0\)は任意の\(\lambda\)で成り立つので
$$
\frac{\partial \tilde{L_1}}{\partial u}(0, \lambda)=0
$$
\(\tilde{f}_2^{\prime}(0)-\lambda \tilde{g}_2^{\prime}(0)=0\)は\(\lambda=\frac{\widetilde{f}_2^{\prime}(0)}{\widetilde{g}_2^{\prime}(0)}\)とすれば
$$
\frac{\partial \tilde{L_2}}{\partial v}(0, \lambda)=0
$$
になる。つまり制約条件とは別方向の微分を制約条件の微分で打ち消すという発想で、これがラグランジュの未定乗数法のココロである。
等式制約条件の幾何的解釈
では続けて幾何的な解釈について考察してみる。先ほどまでの例題の議論を引き継いで\(z = f(x,y) \)のグラフを考えてみる。（回転放物面）
ここで最小となる点（上図の赤い点）での接平面を考えてみると、以下の図のようになる。
最小の点を通る緑色の線は直線\(x+y=1\)と平行でこの直線を\(l\)と置くことにする。
この接平面を見ると最小となる点において\(l\)方向には平ら（\(f\)の微分が\(0\))だが、この直線から出ていく方向に関しては接平面が傾いているので関数の値が変わってしまうことが視覚的にも分かる。
ここで、\(f(x,y)\)に\(-\lambda g(x,y)\)を加えるという動作を考えると、この\(g(x,y)\)は\(l\)上では常に\(0\)なので\(-\lambda g(x,y)\)は\(l\)方向では変化しないので\(L(x,y,\lambda)\)の接平面は\(l\)方向には常に水平。言い換えるとこの接平面はどんな\(\lambda\)でも\(l\)を含むということで、さらに言い換えると\(\lambda\)を変化させると接平面は\(l\)を軸に回転するということなのである。
つまり小さい\(\lambda\)を取ると、接平面は\(l\)を軸に少し回転し水平に近づき、ラグランジュ関数の回転放物面は先ほどの\(f(x,y)\)の回転放物面から形が変化する。
そして適当な\(\lambda\)をとってやれば接平面が水平になる。つまり微分したときに\(0\)になる。
不等式制約問題（KKT条件）の最適性条件
これまでは、等式による制約条件を考えていたが、ここからは最も一般的な等式制約と不等式制約をもつ最適化問題を扱う。まとめて書くと
KKT条件の問題設定③
目的関数 \(F^k(x) \rightarrow\) 最小
制約条件
$$
\begin{aligned}
& g_i(x) \leq 0, \quad i=1,2, \ldots, l, \\
& g_i(x)=0, \quad i=l+1, \ldots, m, \\
& x \in \Re^n
\end{aligned}
$$
である。実行可能解\(x\)は各不等式条件\(g_i(x) \leq 0\)を等式で満たす場合と真の不等式で満たす場合がある。\(g_i(x)=0\)のときこの制約条件は有効であるという。有効制約条件の添え字集合を
$$
A(x)=\left\{i \mid g_i(x)=0, i=1,2, \ldots, l\right\}
$$
と書く。実行可能解\(x\)において等式で成立する条件の勾配ベクトル\(\nabla g_i(x),i \in A(x)\)と\(\nabla g_i(x), i = l+1,\dots,m\)が互いに一次独立であるとき、\(x\)は正則であるという。
「有効」について
制約条件が「有効」とは、その制約が問題の解を決定する上で重要な役割を果たしている、つまり制約条件によって解が制約されている状態を指している。具体的には\(g_i(x)=0\)（つまり、制約条件が「等号」で満たされる）を満たす解が最適解である場合、その制約条件は「有効」である。例えば、「高さ１００ｍ以下でできるだけ高く飛ぶ」の最適解が「高さ１００ｍ」である場合、制約条件の「高さ１００ｍ以下」は有効である。
一方で、「有効」でない制約条件とは、その制約が解に影響を与えない状態を指す。これは制約条件\(g_i(x) < 0\)（つまり、制約条件が「不等式」で満たされ、さらに余裕がある）を満たす解が最適解である場合である。例えば、「高さ１００ｍ以下でできるだけ高く飛ぶ」問題で、もし最適解が「高さ５０ｍ」であれば、制約条件「高さ１００ｍ以下」は有効ではない（つまり、解に影響を与えていない）と言える。
この条件はラグランジュ関数に基づく等式条件問題の最適性条件を一般化したものであり、研究者W.Karush,H.W.Kuhn,A.W.Tuckerの頭文字を取ってKKT条件と言われている。
最適化問題③において実行可能解\(x^* \in \Re^*\)すなわち
$$
\begin{aligned}
& g_i\left(x^*\right) \leq 0, \quad i=1,2, \ldots, l, \\
& g_i\left(x^*\right)=0, \quad i=l+1, \ldots, m
\end{aligned}
$$
を考え、さらに局所最適解であるとする。
不等式制約問題の最適性必要条件
\(f(x)\)と\(g_i(x),i=1,2,\dots,m\)全て連続微分可能、また\(x^*\)は正則であるとする。このとき、次の条件を満たすラグランジュ乗数ベクトル\(u^* \in \Re^m\)が存在する。
$$
\begin{aligned}
& \left(\nabla_x L\left(x^*, u^*\right)=\right) \nabla f\left(x^*\right)+\sum_{i=1}^m u_i^* \nabla g_i\left(x^*\right)=0 \\
& u_i^* \geq 0, i=1,2, \ldots, l\\
&u_i^*=0, i \in\{1,2, \ldots, l\}-A\left(x^*\right)
\end{aligned}
$$
（等式条件の\(u_i^*,i=1,\dots,m\)に対する符号制約はない。）
【証明】
不等式条件を考慮して、等式制約条件での証明に使用したペナルティ関数をつぎのように拡張する。
$$
F^k(x)=f(x)+\frac{k}{2} \sum_{i=1}^l\left(g_i^{+}(x)\right)^2+\frac{k}{2} \sum_{i=l+1}^m g_i(x)^2+\frac{\alpha}{2}\left\|x-x^*\right\|^2
$$
ここに、\(k\)は\(1,2,\dots\)の値を取るパラメータ、また
$$
g_i^{+}(x)=\max \left\{0, g_i(x)\right\}
$$
である。\((g_i^{+}(x))^2\)は\(g_i(x)=0\)の時に微分不可能な点を持つことがあるが、この問題は今回のような最適化問題やＫＫＴ条件の証明においては通常無視できる。それは、制約条件の不等式を満たす解\(x^*\)（つまり、\(g_i(x^*) \leq 0\)）に関心があるからで、具体的には、制約条件の不等式がちょうど等式で成り立つ点、つまり\(g_i(x^*) = 0\)となる点に関心がある。このような点では\(g_i^{+}(x)\)は常に０で、したがって微分可能。よってここでは微分可能とみなせる。
その勾配ベクトルは\(2 g_i^{+}(x) \nabla g_i(x)\)である。上の\(F^k(x)\)を用いて問題②（等式制約の時のペナルティ関数の時と同様）を定義し、その最小解を\(x^k\)と記すと、\(k \rightarrow \infty\)のとき\(x^k \rightarrow x^*\)へ収束する。これに伴って
$$
u_i^*=\lim _{k \rightarrow \infty} k g_i^{+}\left(x^k\right), \quad i=1,2, \ldots, l
$$
$$
u_i^*=\lim _{k \rightarrow \infty} k g_i\left(x^k\right), \quad i=l+1, \ldots, m
$$
を定義すると、やはり同様の議論で不等式制約問題の最適性必要条件を示すことができる。２番目の非負条件は\(u_i^* \geq 0\)は\(g_i^{+}\left(x^k\right) \geq 0\)から従う。また、\(i \in \{1,2,\dots,l\}-A(x^*)\)に対する条件\(u_i^* = 0\)は、そのような\(i\)では\(g_i(x^*) < 0 \)つまり\(g_i^{+}\left(x^*\right)=0\)であることから明らか。□
不等式制約条件（KKT条件）の幾何的解釈
具体的な問題を通して考えてみよう
非線形計画問題として、目的関数と制約条件が二次関数によって定義された問題を考えてみる。
【例題②】
目的関数 \(f(x)=2 x_1^2+x_1 x_2+x_2^2+x_1-3 x_2+3\rightarrow\) 最小
制約条件
$$
\begin{aligned}
& g_1(x)=x_1^2+x_2^2-1 \leq 0 \\
& g_2(x)=-x_1 \leq 0 \\
& g_3(x)=-x_2 \leq 0
\end{aligned}
$$
目的関数の等高線は楕円である。楕円の中心を\(\nabla f(x) = 0\)を解いて求めると、\(x^{\prime}=(-5 / 7,13 / 7)\)であり、等高線の様子は以下のようになる
ＫＫＴ条件を適応するには、どの制約条件が有効であるかを予想しなければならない。計算の結果、ＫＫＴ条件が成立すれば、予想が正しかったことになる。問題の構造が単純でない場合、有効制約の予想は困難であり、最悪の場合、全ての可能性を調べなくてはならない。
今回の場合は、上図より、最適解\(x^*\)における有効制約は\(g_1(x)\)と\(g_2(x)\)の二つであると予想される。そこで、ＫＫＴ条件において\(u_3^*\)と置いて、有効制約条件と併せて書くと
$$
\begin{gathered}
\nabla f(x)+u_1 \nabla g_1(x)+u_2 \nabla g_2(x)=\left(\begin{array}{c}
4 x_1+x_2+1 \\
x_1+2 x_2-3
\end{array}\right)+u_1\left(\begin{array}{c}
2 x_1 \\
2 x_2
\end{array}\right) \\
+u_2\left(\begin{array}{c}
-1 \\
0
\end{array}\right)=\left(\begin{array}{l}
0 \\
0
\end{array}\right) \\
x_1^2+x_2^2-1=0 \\
x_1=0
\end{gathered}
$$
である。これを解くと\(\left(x_1^*=0, x_2^*=1, u_1^*=1 / 2, u_2^*=2, u_3^*=0\right)\)と\(\left(x_1^*=0, x_2^*=-1, u_1^*=-5 / 2, u_2^*=0, u_3^*=0\right)\)の二つの解が得られる。前者は必要条件をすべて満たしているが、一方後者は実行可能ではなく、また\(u_i^*\)の非負条件も満たさないので棄却される。
この結果を用いて幾何学的な意味を考えてみる。
\(x^* = (0,1)^T\)における三つのベクトル。\(-\nabla f_2\left(x^*\right)=(-2,1)^T, \nabla g_1\left(x^*\right)=(0,2)^T, \nabla g_2\left(x^*\right)=(-1,0)^T\)を\(x^*\)を始点として書くと以下の図のようになる。
図では右下の薄い赤色の領域が実行可能領域であるが、\(\nabla g_i(x^*)\)は\(g_i(x)\)の\(x^*\)における増加方向を示すので、有効制約\(g_i(x) = 0 \)の\(x^*\)における接線と直交する。次に、目的関数の\(\nabla f(x^*)\)は\(x^*\)における\(f_2(x)\)の増加方向を示すベクトルである。ここでは\(f_2(x)\)を最小化することから、その逆方向\(-\nabla f(x^*)\)へ進むことが望ましい。正確には、このベクトルと鋭角へ進むことができれば目的関数値は減少する。ところで、\(\nabla g_i(x^*)\)を非負重み\(u_i^* \geq 0 \)によって加えたベクトルの領域
$$
G\left(x^*\right)=\left\{u_1 \nabla g_1\left(x^*\right)+u_2 \nabla g_2\left(x^*\right) \mid u_1 \geq 0, u_2 \geq 0\right\}
$$
を定義すると、ＫＫＴ条件はベクトル\(-\nabla f(x^*)\)がこの領域内に入ることを要求している。ここまでの説明から、この条件は、\(x^*\)から実行可能領域のどの方向を選んでも\(-\nabla f(x^*)\)と鋭角をなすことはできず、目的関数値を減少できないことを示している。すなわち、\(x^*\)の局所最適性の必要条件になっているのである。
参考先
