📂最適化理論

最適化理論：ラグランジュの未定乗数法

説明

非線形な目的関数を持つ非線形最適化問題で、ラグランジュ乗数法という解法があり、ラグランジュ乗数^{lagrangian Multiplier}と呼ばれるものを制約条件に掛けて、目的関数に反映させる方法だ。

$$\begin{matrix} \text{Maximize} & f(x) \\ \text{subject to} & g(x) = 0 \end{matrix}$$

例えば、微分可能なスカラー関数 $f,g : \mathbb{R}^{p} \to \mathbb{R}$ に対する最適化問題が上記のように与えられた場合、私たちの目標は、実現可能解の集合^{feasible solution} $F = \left\{ x \in \mathbb{R}^{n} : g(x) = 0 \right\}$ で $f \left( x^{\ast} \right)$ が最大となるような $x^{\ast} \in F$ を見つけることだ。ラグランジュ乗数法は、この解法の一つとして、ラグランジュ乗数 $-\lambda$ を $g(x)$ に掛けて $f$ に加えたラグランジュ関数 $$L \left( x, \lambda \right) := f(x) - \lambda g(x)$$ を目的関数とする次の最適化問題に変えることだ。 $$\begin{matrix} \text{Maximize} & L \left( x, \lambda \right) \end{matrix}$$

こうして得られた新しい最適化問題は制約条件がなくなり、これは魔法ではなく数学だ。$L$ を最適化する過程で、$L$ の $\lambda$ に対する変化量が $0$ となる点、つまり $${{ \partial L } \over { \partial \lambda }} = 0 \implies -g(x) = 0$$ で、事実上元の制約条件を満たさざるを得なくなるが、これにより制約条件がないか、または弱い最適化技術を使用できるようになるのだ。

例

エントロピーを最大化する分布は一様分布だ ¹

シャノンエントロピーが一様分布で最大化されることをラグランジュ乗数法を通じて確認してみよう。$\left( p_{1} , \cdots , p_{n} \right)$ に対して確率変数 $X$ の確率分布が次のようであるとしよう。 $$P\left( X = k \right) = p_{k}$$

すると、エントロピーを最大にする $\left( p_{1} , \cdots , p_{n} \right)$ を求める最適化問題は次のように書くことができる。

$$\begin{matrix} \text{Maximize} & - \sum_{k=1}^{n} p_{k} \log p_{k} \\ \text{subject to} & \sum_{k=1}^{n} p_{k} - 1 = 0 \\ & p_{k} \ge 0 \end{matrix} \\ k = 1, \cdots, n$$

制約条件$\displaystyle \sum_{k=1}^{n} p_{k} = 1$ は、全ての確率の合計が $1$ である必要があるからだ。元の目的関数 $f \left( p_{1} , \cdots , p_{n} \right) = - \sum_{k=1}^{n} p_{k} \log p_{k}$ は、この制約条件に従って無限に大きくなることができなくなる。この問題に対するラグランジュ関数は次のようになる。 $$L \left( p_{1} , \cdots , p_{n} , \lambda \right) = - \sum_{k=1}^{n} p_{k} \log p_{k} - \lambda \left( \sum_{k=1}^{n} p_{k} - 1 \right)$$ すると、$L$ を $k = 1, \cdots , n$ に対して $p_{k}$ で偏微分したとき $${{ \partial L } \over { \partial p_{k} }} = - \log p_{k} + 1 - \lambda \implies \lambda = 1 - \log p_{k}$$ である。これは $$\begin{align*} & \lambda \\ =& 1 - \log p_{1} \\ & \vdots \\ =& 1 - \log p_{n} \end{align*}$$ を意味するので $$p_{1} = \cdots = p_{n}$$ でなければならない。一方、$\lambda$ に対する偏微分から $${{ \partial L } \over { \partial \lambda }} = 0 \implies \sum_{k=1}^{n} p_{k} = 1$$ であるため、エントロピーを最大化する確率分布は正確に $$p_{1} = \cdots = p_{n} = {{ 1 } \over { n }}$$ である。つまり、一様分布はエントロピーを最大化する。

■

サポートベクターマシン

機械学習では、サポートベクターマシンが超平面を見つける技術としてラグランジュ乗数法が登場することがある。次の段落を参照してください:

• サポートベクターマシン/カーネルトリック