不等式制約条件におけるLagrangeの未定乗数法の考え方

特に，不等式制約条件におけるLagrangeの未定乗数法の考え方のメモ．

参考資料：

第4回不等式制約条件の場合の未定乗数法 · levelfour/machine-learning-2014 Wiki · GitHub

等式制約の場合

等式制約条件 $g(\vec{x}) = 0$の下で，目的関数$f(\vec{x})$ の最大化・または最小化する（つまり，そのときの点を求めたい）．

まず解候補は，$g(\vec{x})$と$f(\vec{x})$の交点のどれかになる．交点は交差しているか接しているかの2パターンがある．

$g(\vec{x})$で表される平面（2次元の場合は直線）と $f(\vec{x})$で表される平面が交差しているとき， $f(\vec{x}) > 0$になる点または$f(\vec{x}) < 0$が存在するので極大・極小値になりえない．（つまり，被っている領域のほうに解がある．）

この辺については，この記事ラグランジュの未定乗数法の解説と直感的な証明 | yunabe.jp がわかりやすい．

接している場合，$g(\vec{x})$と$f(\vec{x})$の2つの接線ベクトルが平行になり，また接線ベクトルと直交関係にある勾配ベクトルも平行になる．この点から$f(\vec{x})$の勾配方向にズラして最適化してしまうと，制約条件から外れてしまうので，接している点のときに，制約条件を満たした極大値または極小値になる．

勾配ベクトルが平行になるを式に表すと

$$ \vec{\nabla} f = \lambda \vec{\nabla} g $$

(例えば2次元の時，$\vec{\nabla} f =(\frac{df}{dx}, \frac{df}{dy})$

右辺0に直せば，以下の式になる．以下の式を満たす点が極大・極小値になる．

$$ \vec{\nabla} f - \lambda \vec{\nabla} g = \vec{0} $$

勾配ベクトルを考えたときに上式になればいいので，目的関数を作り直すと，

$$ L(\vec{x}, \lambda) = f(\vec{x}) - \lambda g(\vec{x}) $$

特にこれをラグランジュ関数（ラグランジアン）という．この目的関数は，$f(\vec{x}), g(\vec{x})$の2つの勾配ベクトルが平行になる点があるかという最適化問題に置き換わっているので双対問題になっている．この双対問題を解くことで極値を得られる．

解き方：

変数をn個として，偏微分すると

$\begin{eqnarray} \left\{ \begin{array}{l} \frac{\partial L}{\partial x_{1}} = \frac{ \partial f }{\partial x_{1} } - \lambda \frac{\partial g}{\partial x_{1}} = 0 \\\\ \frac{\partial L}{\partial x_{2}} = \frac{ \partial f }{\partial x_{2} } - \lambda \frac{\partial g}{\partial x_{2}} = 0 \\\\ \vdots \\\\ \frac{\partial L}{\partial x_{n}} = \frac{ \partial f }{\partial x_{n} } - \lambda \frac{\partial g}{\partial x_{n}} = 0 \\\\ \frac{\partial L}{\partial \lambda} = g(\vec{x}) = 0 \end{array} \right. \end{eqnarray}$

最後の式は等式制約条件を表しており，この連立方程式を解いた点が極値になる．連立方程式の式の数は，変数の数+等式制約条件の数になる．上記の例だと$n+1$個になる．

連立１次方程式になれば，行列と変数ベクトルに式変形して定数ベクトルを右辺に移項して，係数行列が（式の数と変数の数が一致し）正方行列なので逆行列を解いて求めることができる．

等式制約条件が複数ある場合

以下のような等式制約条件が2つある場合を考える．

$$ g_{1}( \vec{x} ) = 0 \\ g_{2} ( \vec{x} )= 0 $$

目的関数の勾配ベクトルと$g( \vec{x} )_{1}, g( \vec{x} )_{2}$の勾配ベクトルはそれぞれ平行するので，

$$ \vec{\nabla} f = a_{1} \vec{\nabla} g_{1} \\ \vec{\nabla} f = a_{2} \vec{\nabla} g_{2} $$

つまり，等式制約条件の勾配ベクトル同士も平行関係にあり，足しても定数倍されるだけで同じ向きになる．両辺を足すと，

$$ 2 \vec{\nabla} f = a_{1} \vec{\nabla} g_{1} + a_{2} \vec{\nabla} g_{2} \\ \vec{\nabla} f = \frac{a_{1}}{2} \vec{\nabla} g_{1} + \frac{a_{2}}{2} \vec{\nabla} g_{2} $$

定数倍を$\lambda$に置き直す．

$$ \vec{\nabla} f = \lambda_{1} \vec{\nabla} g_{1} + \lambda_{2} \vec{\nabla} g_{2} \\ \vec{\nabla} f - \lambda_{1} \vec{\nabla} g_{1} - \lambda_{2} \vec{\nabla} g_{2} = \vec{0} $$

ラグランジュ関数は，

$$ L( \vec{x}, \vec{\lambda} ) = f( \vec{x} ) - \lambda_{1} g_{1}(\vec{x}) - \lambda_{2} g_{2}( \vec{x} ) = f( \vec{x} ) - \sum_{i=1}^{2} \lambda_{i} g_{i}( \vec{x} ) $$

制約条件が3個以上でも同じ．n個の制約条件のラグランジュ関数は以下になる．

$$ L(\vec{x}, \vec{\lambda}) = f(\vec{x}) - \sum_{i=1}^{n} \lambda_{i} g_{i}( \vec{x} ) $$

不等式制約の場合

参考：第4回不等式制約条件の場合の未定乗数法 · levelfour/machine-learning-2014 Wiki · GitHub

不等式制約条件$g(\vec{x}) \geq 0$の場合を考える．等式では面上（2次元では線上）のみであったが，不等式領域($\geq 0$)により条件が緩くなっている．

下図のような停留点(Statinary Point)が制約条件を満たしている状況では， Lagrange関数にg(x)を含める必要がない。制約条件を含めることのない通常の目的関数の最適化で解ける．

問題は下図のように、停留点が制約の境界上にあるときである。このとき$\nabla f$の向きによっては、最適化しようとすると制約を外れる向き（つまり緑色の領域→白色の領域の向き）に動く可能性がある。そのため、この状況では等式制約条件下で解く必要がある．

最大化，最小化と目的関数と制約条件の勾配ベクトルの向きによってラグランジュ関数がどうなるかみる．

最大化 and 目的関数と制約条件の勾配ベクトルの向きが同じ

下図の場合，最大化するには，$\nabla f$の向きにそのまま動かせばよく，これは制約条件を満たしている．制約条件なしの目的関数$f$の最大化$\lambda =0$に等しい．

最大化 and 目的関数と制約条件の勾配ベクトルの向きが逆

$\vec{\nabla} f$の向きに最大化すると，制約条件を外れてしまうので等式制約条件を入れなければならない．

勾配ベクトルは平行し，向きが逆なので

$$ \vec{\nabla} f = \lambda (-\vec{\nabla} g) \\ \vec{\nabla} f + \lambda \vec{\nabla} g = \vec{0}, (\lambda > 0) $$

ラグランジュ関数は，

$$ L(\vec{x}, \lambda) = f(\vec{x}) + \lambda g(\vec{x}), (\lambda > 0 ) $$

max, 勾配ベクトルが逆向き

最小化 and 目的関数と制約条件の勾配ベクトルの向きが同じ

最小化により，$- \vec{\nabla} f$の方向に動かしていく． $- \vec{\nabla} f$は，$\vec{\nabla} g$の向きと逆向きになる． $- \vec{\nabla} f$の向きに動かしていくと，制約条件から外れてしまうので等式制約を含ませる必要がある．

$$ - \vec{\nabla} f = \lambda (- \vec{\nabla}g )\\ \vec{\nabla} f = \lambda \vec{\nabla}g \\ \vec{\nabla} f - \lambda \vec{\nabla}g = \vec{0}, (\lambda > 0) \\ \vec{\nabla} f + \lambda \vec{\nabla}g = \vec{0}, (\lambda < 0) \\ $$

ラグランジュ関数は，

$$ L(\vec{x}, \lambda) = f(\vec{x}) - \lambda g(\vec{x}), (\lambda > 0) \\ L(\vec{x}, \lambda) = f(\vec{x}) + \lambda g(\vec{x}), (\lambda < 0) \\ $$

最小化 and 目的関数と制約条件の勾配ベクトルの向きが逆向き

不等式領域に動かしていくので,制約条件なしの最適化に等しい．つまり，$\lambda = 0$

まとめる

以上をまとめる．

$$ \text{subject to } g(\vec{x}) \geq 0 \\ \text{max} f(\vec{x}) \\ \Rightarrow L(\vec{x}, \lambda) = f(\vec{x}) + \lambda g(\vec{x}), (\lambda \geq 0) $$

$$ \text{subject to } g(\vec{x}) \geq 0 \\ \text{min} f(\vec{x}) \\ \Rightarrow L(\vec{x}, \lambda) = f(\vec{x}) - \lambda g(\vec{x}), (\lambda \geq 0) $$