ラグランジュの未定乗数法を実例で理解する

ラグランジュの未定乗数法の説明が式だけだとよくわからなかったので実例で理解したメモです。

# ラグランジュの未定乗数法

Wikipediaが詳しいです（[ラグランジュの未定乗数法](http://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%B0%E3%83%A9%E3%83%B3%E3%82%B8%E3%83%A5%E3%81%AE%E6%9C%AA%E5%AE%9A%E4%B9%97%E6%95%B0%E6%B3%95)）。
ざっくり概要は、束縛条件がある場合に式の最適化をする方法です。

式で表すと、ある式$f(x,y,z)$があってその極値を求めたいけれど、条件として$g(x,y,z)=0$となるように$x,y,z$を選ばないと行けないという状況です。

## 計算方法
極値を求めたい式$f(x,y,z)$と、束縛条件$g(x,y,z)$がある場合に、新たな式

```math
F(x,y,z,\lambda)=f(x,y,z)-\lambda g(x,y,z)
```

を作ります。突然$\lambda$が現れましたがこれが肝です。
この式$F(x,y,z,\lambda)$に対して

```math
\frac{\partial F(x,y,z,\lambda)}{\partial x}=0 \\
\frac{\partial F(x,y,z,\lambda)}{\partial y}=0 \\
\frac{\partial F(x,y,z,\lambda)}{\partial z}=0 \\
\frac{\partial F(x,y,z,\lambda)}{\partial \lambda}=0 \\
```

となるような$x,y,z,\lambda$を求めたものが解です。

# 例として四角形の4つの角度を求めてみる

数式だけで理解できるほど物分かりがよくないので具体的な式を作って理解しようと思います。

例として、ある四角形の4つの角度を5回ずつ測ったところ少しずつ誤差が出たとして、この誤差を最小にするような角度$a,b,c,d$を求めようと思います。

|No.|a|b|c|d|
|:--:|:--:|:--:|:--:|:--:|
|1|140.02|40.14|80.16|100.02|
|2|140.05|40.12|80.05|100.10|
|3|139.85|39.94|79.89|99.94|
|4|139.92|40.13|79.92|99.87|
|5|140.03|39.94|80.10|100.18|


## まずは素直に最小二乗法

すべての誤差を最小にするということで最小二乗法を使います。
各測定結果を$a_1,\cdots,a_5,b_1,\cdots,b_5,c_1,\cdots,c_5,d_1,\cdots,d_5$と置くと残差平方和は

```math
f(a,b,c,d)=\sum_{i=1}^{5}{(a_i-a)^2}+\sum_{i=1}^{5}{(b_i-b)^2}+\sum_{i=1}^{5}{(c_i-c)^2}+\sum_{i=1}^{5}{(d_i-d)^2}
```

となります。
残差を最小にするために各変数で偏微分して

```math
\frac{\partial f(a,b,c,d)}{\partial a}=-2\sum_{i=1}^{5}{(a_i-a)}=-2\sum_{i=1}^{5}{a_i}+
2\sum_{i=1}^{5}{a}=-2\sum_{i=1}^{5}{a_i}+10a
```

他の変数も同様に偏微分すると

```math
\frac{\partial f(a,b,c,d)}{\partial b}=-2\sum_{i=1}^{5}{b_i}+10b \\
\frac{\partial f(a,b,c,d)}{\partial c}=-2\sum_{i=1}^{5}{c_i}+10c \\
\frac{\partial f(a,b,c,d)}{\partial d}=-2\sum_{i=1}^{5}{d_i}+10d \\
```

二乗和の最小は偏微分がすべて0になることなので。

```math
-2\sum_{i=1}^{5}{a_i}+10a=0 \\
-2\sum_{i=1}^{5}{b_i}+10b=0 \\
-2\sum_{i=1}^{5}{c_i}+10c=0 \\
-2\sum_{i=1}^{5}{d_i}+10d=0 \\
```

試しに$a$を計算すると、

```math
-\sum_{i=1}^{5}{a_i}+5a=0 \\
5a = \sum_{i=1}^{5}{a_i} \\
a = \frac{1}{5} \sum_{i=1}^{5}{a_i}
```

結局は各測定値の平均でしたね。
ということで平均した各値は以下の通りになりました。

|a|b|c|d|
|:-:|:-:|:-:|:-:|
|139.974|40.054|80.024|100.022|


## 内角の和

そのままの結果でも問題なさそうですが、よく考えると四角形は内角の和が360度にならなければいけません。

試しに最初の結果を合計すると$360.074$になってしまい満たしていません。
そこでこれを制約条件として追加して計算することにします。

制約を式にすると

```math
a+b+c+d=360
```

です。
ラグランジュの未定乗数法ではこの式を右辺が0になるように変形します。

```math
a+b+c+d-360=0
```

そしてこの式の左辺を関数$g(a,b,c,d)$として

```math
g(a,b,c,d)=a+b+c+d-360
```

と置きます。
この式と最小二乗法の式を組み合わせて新しい式$F(a,b,c,d,\lambda)$を以下のように作ります。

```math
F(a,b,c,d,\lambda) = f(a,b,c,d)-\lambda g(a,b,c,d)
```

この式の極値が、制約を満たした値のうち誤差が最小になる値ということになります。
そこでまた各変数で偏微分して0になる値を求めます。

```math
\frac{\partial F(a,b,c,d,\lambda)}{\partial a} = -2 \sum_{i=1}^{5}{a_i}+10a-\lambda = 0
```

他の$b,c,d$も同様で

```math
\frac{\partial F(a,b,c,d,\lambda)}{\partial b} = -2 \sum_{i=1}^{5}{b_i}+10b-\lambda = 0 \\
\frac{\partial F(a,b,c,d,\lambda)}{\partial c} = -2 \sum_{i=1}^{5}{c_i}+10c-\lambda = 0 \\
\frac{\partial F(a,b,c,d,\lambda)}{\partial d} = -2 \sum_{i=1}^{5}{d_i}+10d-\lambda = 0
```

そして今回追加した$\lambda$で偏微分した式

```math
\frac{\partial F(a,b,c,d,\lambda)}{\partial \lambda} = -a-b-c-d+360 = 0
```

合計5個の式を0にするような$a,b,c,d,\lambda$を求めます。
5個の式に5個の変数なので連立1次方程式を解くために以下の式にまとめられます。

```math
\pmatrix{ 10 & 0 & 0 & 0 & -1 \\ 0 & 10 & 0 & 0 & -1 \\ 0 & 0 & 10 & 0 & -1 \\ 0 & 0 & 0 & 10 & -1 \\ 1 & 1 & 1 & 1 & 0 } \pmatrix{ a \\ b \\ c \\ d \\ \lambda } = \pmatrix{ 2 \sum_{i=1}^{5}{a_i} \\ 2 \sum_{i=1}^{5}{b_i}  \\ 2 \sum_{i=1}^{5}{c_i}  \\ 2 \sum_{i=1}^{5}{d_i}  \\ 360 }
```

左辺の逆行列を計算して右辺にかけると解がでます。なにを使ってもいいですが、今回はExcelの`MINVERSE`関数を使って計算して結果は以下になりました。

|a|b|c|d|$\lambda$|
|:-:|:-:|:-:|:-:|:-:|
|139.9555|40.0355|80.0055|100.0035|-0.185|

合計してみるとちゃんと360になるのがわかります。

## 制約を追加する

さらに追加の例として、測定した四角形が台形だったとします。

台形は角度の和が180度になる組み合わせがあります。
確かめてみると

```math
a+b=179.991 \\
c+d=180.009
```

やっぱり微妙に満たしてません。
そこでこの制約

```math
h(a,b,c,d)=a+b-180
```

を加えて計算してみます。
まず同じように$F(a,b,c,d,\lambda_1,\lambda_2)$を定義します。

```math
F(a,b,c,d,\lambda_1,\lambda_2) = f(a,b,c,d) - \lambda_1 g(a,b,c,d) - \lambda_2 h(a,b,c,d)
```

一つ前と同じように$a,b,c,d,\lambda_1,\lambda_2$で偏微分したものが0になるように式変形して

```math
\pmatrix{ 10 & 0 & 0 & 0 & -1 & -1 \\ 0 & 10 & 0 & 0 & -1 & -1 \\ 0 & 0 & 10 & 0 & -1 & 0 \\ 0 & 0 & 0 & 10 & -1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 } \pmatrix{ a \\ b \\ c \\ d \\ \lambda_1 \\ \lambda_2 } = \pmatrix{ 2 \sum_{i=1}^{5}{a_i} \\ 2 \sum_{i=1}^{5}{b_i}  \\ 2 \sum_{i=1}^{5}{c_i}  \\ 2 \sum_{i=1}^{5}{d_i}  \\ 360 \\ 180 }
```

この連立1次方程式を解くと

|a|b|c|d|$\lambda_1$|$\lambda_2$|
|:-:|:-:|:-:|:-:|:-:|:-:|
|139.96|40.04|80.001|99.999|-0.23|0.09|

制約を足しても同じように解けることが確認できました。

今回は理解のために線形の式だけで計算しましたが、ラグランジュの未定乗数法自体は非線形な式でも使用できるようです。