Pythonと機械学習

Pythonも機械学習も初心者ですが、頑張ってこのブログで勉強してこうと思います。

トップ > 機械学習 > ラグランジュの未定乗数法

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

機械学習

最適化問題

世の中には非常に多くの最適化問題が存在します。ある条件の下で、この値を最適化したい等、良く耳にすることが多いです。

燃費低減の為自動車のエンジン軽くしたい。でもあまり軽すぎると強度が心配。強度を保ちつつどこまで軽くできるか？等、いくらでもありますよね。

エンジン壁の肉厚を{x}として、エンジンの総重量を{f}とした場合、肉厚を厚くするとエンジンが重くなるので、{f}は{x}の関数になっているのがわかると思います。

一般的に変数{x}の事を設計変数と呼びます。また、{x}の関数である最適化したい関数{f(x)}を目的関数と呼びます。

また、エンジン壁の肉厚を無限に薄くすることができないので、{x}にここまでという制約がつくことも多いです。

最適化問題における設計変数の制約を制約条件と呼びます。

制約条件も設計変数{x}の関数{g(x) \leq 0}の様に、等式、または不等式で表すことができます。{g(x)}の事を制約関数と言います。

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

一般的に、目的関数は設計変数の複雑な関数になっており、良くわからない場合が多いです。

もし目的関数が設計変数の簡単な式であらわされると分かっている時は、解析的に最適解を求めることができる場合があります。

ラグランジュの未定乗数法は、設計変数を{x}としたときに(複数可です)、{x}の1次関数である制約条件の下、{x}の2次関数である目的関数を最適化するアルゴリズムです。

制約条件は複数あってもいいです。ただし全て等式でなければいけません。

今、{m}個の制約条件{\mathbf{g}(\mathbf{x})=0}の下で、{n}個ある設計変数{\mathbf{x}}の2次関数{f(\mathbf{x})}の最小値を求める問題を考えます。

設計変数{\mathbf{x}}は、{n}個あるので{n×1}のベクトルで表します。

{
\displaystyle
\begin{eqnarray}
\mathbf{x}=\left[
\begin{array}{c}
x_{1} \\
x_{2} \\
\vdots \\
x_{n}
\end{array}
\right]
\end{eqnarray} \tag{1}
}

{\mathbf{c}}を{n×1}の定数ベクトル、

{
\displaystyle
\begin{eqnarray}
\mathbf{c}=\left[
\begin{array}{c}
c_{1} \\
c_{2} \\
\vdots \\
c_{n}
\end{array}
\right]
\end{eqnarray}  \tag{2}
}

{\mathbf{Q}}を{n×n}の定数行列としたときに、

{
\displaystyle
\begin{eqnarray}
\mathbf{Q}=\left[
\begin{array}{ccc}
q_{11} & q_{12} & \cdots & q_{1n} \\
q_{21} & q_{22} & \cdots & q_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
q_{n1} & q_{n2} & \cdots & q_{nn}
\end{array}
\right]
\end{eqnarray}  \tag{3}
}

2次関数である目的関数{f(\mathbf{x})}は、以下の式であらわされます。
※定数項があってもなくても目的関数{f(\mathbf{x})}を最小にする{\mathbf{x}}は一意に決まるので考慮しなくていいです。

{\displaystyle
f(\mathbf{x})=\frac{1}{2}\mathbf{x}^T\mathbf{Q} \mathbf{x} -\mathbf{c}^T \mathbf{x}  \tag{4}
}

{\mathbf{b}}を{m×1}の定数ベクトル、

{\displaystyle
\begin{eqnarray}
\mathbf{b}=\left[
\begin{array}{c}
b_{1} \\
b_{2} \\
\vdots \\
b_{m}
\end{array}
\right]
\end{eqnarray}  \tag{5}
}

{\mathbf{A}}を{m×n}の定数行列としたときに、

{\displaystyle
\begin{eqnarray}
\mathbf{A}=\left[
\begin{array}{cccc}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1} & a_{m2} & \cdots & a_{mn}
\end{array}
\right]
\end{eqnarray}  \tag{6}
}

一次関数である制約条件{\mathbf{g}(\mathbf{x})=0}は以下の式であらわされます。
{m}個あるので{m×1}のベクトルです。{\mathbf{g}(\mathbf{x})=0}の形にしておきます。

{\displaystyle
\mathbf{g}(\mathbf{x})=\mathbf{A}\mathbf{x}-\mathbf{b}=0  \tag{7}
}

ここで以下の様に、制約条件の数だけ、ラグランジュ乗数という変数{\lambda}を導入し、ラグランジュ関数{h(\mathbf{x},\mathbf{\lambda})}を定義します。 {\lambda}は{m×1}のベクトルです。

{\displaystyle
\begin{eqnarray}
\mathbf{\lambda}=\left[
\begin{array}{c}
\lambda_{1} \\
\lambda_{2} \\
\vdots \\
\lambda_{m}
\end{array}
\right]
\end{eqnarray}  \tag{8}
}

ラグランジュ関数は、制約条件{\mathbf{g}(\mathbf{x})}とラグランジュ乗数{\lambda}の内積を取って、目的関数{f(\mathbf{x})}に足した関数です。

{\displaystyle
h(\mathbf{x},\mathbf{\lambda})=f(\mathbf{x}) + \mathbf{\lambda}^T\mathbf{g}(\mathbf{x})  \tag{9}
}

次にラグランジュ関数{h(\mathbf{x},\mathbf{\lambda})}を設計変数{\mathbf{x}}で偏微分した値を0と置いてやります。

{
\displaystyle
\begin{align}

\frac{\partial h(\mathbf{x},\mathbf{\lambda})}{\partial \mathbf{x}}&=\frac{\partial}{\partial \mathbf{x}}\left[ f(\mathbf{x}) + \mathbf{\lambda}^T\mathbf{g}(\mathbf{x})  \right] \\
\\

&=\frac{\partial}{\partial \mathbf{x}}\left[ \frac{1}{2}\mathbf{x}^T\mathbf{Q} \mathbf{x} -\mathbf{c}^T \mathbf{x} +\mathbf{\lambda}^T ( \mathbf{A}\mathbf{x}-\mathbf{b}) \right] \\
\\

&=\frac{1}{2} \frac{\partial \mathbf{x}^T\mathbf{Q} \mathbf{x}}{\partial \mathbf{x}}
- \frac{\partial \mathbf{c}^T \mathbf{x} }{\partial \mathbf{x}}
+ \frac{\partial \mathbf{\lambda}^T\mathbf{A} \mathbf{x} }{\partial \mathbf{x}}
- \frac{\partial \mathbf{\lambda}^T \mathbf{b} }{\partial \mathbf{x}} \\
\\

&=\frac{1}{2} \left[ \mathbf{Q} \mathbf{x} +(\mathbf{x}^T\mathbf{Q} )^T \right]
- \mathbf{c}
+ (\mathbf{\lambda}^T\mathbf{A})^T
- 0 \\
\\

&=\mathbf{Q} \mathbf{x} - \mathbf{c} +\mathbf{A}^T \mathbf{\lambda} =0  \tag{10}

\end{align}
}

上記(10)式と、制約条件(7)式で連立方程式をたてて、{\mathbf{x}}と{\mathbf{\lambda}}について解いてやります。

{
\displaystyle
\begin{align}
\mathbf{A}\mathbf{x}-\mathbf{b}=0
\\

\mathbf{Q} \mathbf{x} +\mathbf{A}^T \mathbf{\lambda}- \mathbf{c} =0   \tag{11}
\end{align}
}

行列でくくってまとめてかくと、

{
\displaystyle
\begin{eqnarray}
\left[
\begin{array}{cc}
\mathbf{A} & \mathbf{0}  \\
\mathbf{Q} & \mathbf{A}^T \\
\end{array}
\right]

\left[
\begin{array}{c}
\mathbf{x}   \\
\mathbf{\lambda}  \\
\end{array}
\right]

=\left[
\begin{array}{c}
\mathbf{b}   \\
\mathbf{c}  \\
\end{array}
\right]
\end{eqnarray}   \tag{12}
}

{
\displaystyle
\begin{eqnarray}
\therefore ~~~
\left[
\begin{array}{c}
\mathbf{x}   \\
\mathbf{\lambda}  \\
\end{array}
\right]

=\left[
\begin{array}{cc}
\mathbf{A} & \mathbf{0}  \\
\mathbf{Q} & \mathbf{A}^T \\
\end{array}
\right]^{-1}
\left[
\begin{array}{c}
\mathbf{b}   \\
\mathbf{c}  \\
\end{array}
\right]
\end{eqnarray}   \tag{13}
}

(13)式で求めた解{\mathbf{x}}が、制約条件{\mathbf{g}(\mathbf{x})}の下で、目的関数{f(\mathbf{x})}を最小にする最適解になります。

制約条件が多すぎると、複数の制約条件を同時に満たす{\mathbf{x}}が存在しなくなるので、(13)式の逆マトリックスが解けなくなります。

試してないですが、制約条件の個数が設計変数の個数より多くなると、恐らく逆マトリックスが存在しなくなると思います。

例

簡単な例で試してみましょう。

目的関数{f(\mathbf{x}) = x_1^{2}+x_2^{2}}を制約条件{\mathbf{g}(\mathbf{x}) = x_1+x_2 -1 =0}の下で最小化する、{x_1,x_2}を求めてみましょう。

{
\displaystyle
\begin{eqnarray}
\mathbf{x}=\left[
\begin{array}{c}
x_{1} \\
x_{2} 
\end{array}
\right]
,~~
\mathbf{c}=\left[
\begin{array}{c}
0 \\
0 
\end{array}
\right]
,~~
\mathbf{Q}=\left[
\begin{array}{cc}
2 & 0 \\
0 & 2
\end{array}
\right]
,~~
\mathbf{b}=\left[
\begin{array}{c}
1
\end{array}
\right]
,~~
\mathbf{A}=\left[
\begin{array}{cc}
1 & 1
\end{array}
\right]
\end{eqnarray}
,~~
\mathbf{\lambda}=\left[
\begin{array}{c}
\lambda_1
\end{array}
\right]
}

{
\displaystyle
\begin{align}

\therefore ~~~
\left[
\begin{array}{c}
\mathbf{x}   \\
\mathbf{\lambda}  \\
\end{array}
\right] 

&=\left[
\begin{array}{cc}
\mathbf{A} & \mathbf{0}  \\
\mathbf{Q} & \mathbf{A}^T \\
\end{array}
\right]^{-1}

\left[
\begin{array}{c}
\mathbf{b}   \\
\mathbf{c}  \\
\end{array}
\right]
\\

\Rightarrow ~~~
\left[
\begin{array}{c}
x_1  \\
x_2  \\
\lambda_1  \\
\end{array}
\right] 

&=\left[
\begin{array}{cccc}
1 & 1 & 0 \\
2 & 0 & 1 \\
0 & 2 & 1
\end{array}
\right]^{-1}

\left[
\begin{array}{c}
1 \\
0 \\
0
\end{array}
\right]
\\

&=\left[
\begin{array}{c}
0.5 \\
0.5 \\
-1
\end{array}
\right]
\\

\end{align}
}

よって目的関数の最小値を与える解は、{(x_1,x_2) = ( 0.5,0.5) }で、最小値は{f(x_1,x_2) = 0.5 }となります。