最大値の求め方 ~条件付き極値問題をラグランジュの未定乗数法で解く方法~
初めに
今年のワールドカップはどの国が優勝するだろうか。この株はいつ買っていつ売れば最もリターンを得られるだろうか。
関数の最大値/最小値を求めたい場面は多い。しかしどうすればいいだろうか。この記事では、微分可能な関数（例: $f(x, y, z) = x+y+z$）にいくつかの制約（例: $x^2+y^2+z^2=1$）が課されるという条件のもとで極値を求める方法を紹介する。多変数関数の微分が分かれば今回の記事を理解できるようにする。
いつ使えるか
以下では微分可能な関数の最大値/最小値を求める問題に限定して考える。たとえば以下の二つの問題を考えてみることにしよう。
半径 $r > 0$ の球面 $x^2 + y^2 + z^2 = r^2$ 上で $f(x, y, z) = x + y + z$ を最大化する点と、その最大値を求めよ。
$n$ 個の事象からなる集合 $\{1, 2, \ldots, n\}$ 上の確率分布 $p = (p_1, \ldots, p_n)$（$p_i > 0$、$\sum p_i = 1$）に対し、シャノンエントロピー (Shannon entropy) を
$$
H(p) = -\sum_{i=1}^{n} p_i \log p_i
$$
と定める。「情報量の期待値」という解釈のもと、$H(p)$ を最大にする分布を求めよ。
この二つの共通点として、最大値を考えたい関数 $f$（例題 1 では $x+y+z$、例題 2 では $-\sum p_i \log p_i$）と、変数の動く範囲を指定する条件（例題 1 では $x^2+y^2+z^2 = r^2$、例題 2 では $\sum p_i = 1$）を与える関数がある。後者を拘束条件 (constraint) という。つまり次のような問題設定を考えることになる。
$U \subset \mathbb{R}^n$ を開集合、$f, g_1, \ldots, g_m \colon U \to \mathbb{R}$ を $C^1$ 級の関数とする。拘束条件
$$
g_1(x) = 0,\; \ldots,\; g_m(x) = 0
$$
を満たす $x \in U$ 全体からなる集合
$$
S = \{x \in U \mid g_1(x) = 0,\; \ldots,\; g_m(x) = 0\}
$$
の上で、$f$ の最大値・最小値を求めるにはどうすればよいか。
素朴なアプローチは、拘束条件を具体的に解いて変数を減らしてしまうものである。例題 2 なら $p_n = 1 - p_1 - \cdots - p_{n-1}$ と置いて $H$ を $n-1$ 変数の関数に書き直せばよい。しかしこうすると $p_n$ が対数の中で他の変数の和として現れ、偏微分の式が対称性を失って煩雑になる。例題 1 でも球面座標 $(x, y, z) = (r\sin\theta\cos\varphi, r\sin\theta\sin\varphi, r\cos\theta)$ で解けば計算は可能だが、三角関数の合成が絡んで見通しが悪い。
これは、基本対称式の値が与えられたときに対称式の値を求めるのに、まず具体的な解を求めてから代入していくようなアプローチである。変数が増えるほどこの方針はどんどん無謀になっていく。
拘束条件を解くことなく、対称性を保ったままこの問題を解くことはできないだろうか。ラグランジュの未定乗数法はこれに答えてくれる。
主張を述べる前に、そこに登場する勾配ベクトル (gradient) を定義しておく。
$U \subset \mathbb{R}^n$ を開集合、$f \colon U \to \mathbb{R}$ を $C^1$ 級関数とする。$x \in U$ における $f$ の勾配ベクトルを、$f$ の各偏微分を縦に並べた $n$ 次元ベクトル
$$
\nabla f(x) = \begin{pmatrix} \dfrac{\partial f}{\partial x_1}(x) \\[6pt] \dfrac{\partial f}{\partial x_2}(x) \\[6pt] \vdots \\[6pt] \dfrac{\partial f}{\partial x_n}(x) \end{pmatrix}
$$
と定める。
たとえば $f(x, y, z) = x + y + z$ と $g(x, y, z) = x^2 + y^2 + z^2$ の勾配ベクトルはそれぞれ
$$
\nabla f = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}, \qquad \nabla g(x, y, z) = \begin{pmatrix} 2x \\ 2y \\ 2z \end{pmatrix}
$$
である。
$U \subset \mathbb{R}^n$ を開集合、$f, g_1, \ldots, g_m \colon U \to \mathbb{R}$ を $C^1$ 級の関数とし、拘束条件による集合を
$$
S = \{x \in U \mid g_1(x) = 0,\; \ldots,\; g_m(x) = 0\}
$$
とおく。$x^* \in S$ において $f|_S$ が極値をとり、かつ $\nabla g_1(x^*),\; \ldots,\; \nabla g_m(x^*)$ が一次独立であるとする。このとき、ある実数 $\lambda_1, \ldots, \lambda_m$ が存在して
$$
\nabla f(x^*) = \sum_{i=1}^{m} \lambda_i\, \nabla g_i(x^*)
$$
が成り立つ。
$\lambda_i$ をラグランジュ乗数 (Lagrange multiplier) という。
一次独立性の仮定が満たされなければこの定理は使えず、がっかりするかもしれない。しかし、拘束条件の解 $S$ のうち勾配ベクトルの組 $\nabla g_1(x), \ldots, \nabla g_m(x)$ が一次独立な点全体は $U$ の開集合になるので、その中で考え直せばよい。
証明は陰関数定理を用いるもので単純ではない。証明を知らなくても定理は使えるので、使い方だけを知りたい読者は次節「どう使うか」に進んでよい。
- 一次独立性の仮定から陰関数定理を適用でき、$x^*$ の近くでは拘束条件を「解く」ことができる。すなわち $S$ の $x^*$ 近傍を、拘束のない $n-m$ 個のパラメータ $y$ で $x = \Psi(y)$ とパラメータづけられる。
- このパラメータづけで $f$ を書き直した $F(y) = f(\Psi(y))$ は拘束条件をもたない普通の関数となる。
- $f|_S$ が $x^*$ で極値をとるならば $F$ は対応する $y^*$ で極値をとるから、$\nabla F(y^*) = 0$。連鎖律で書き直すと、これは $\nabla f(x^*)$ が $\nabla g_1(x^*), \ldots, \nabla g_m(x^*)$ の張る空間に属するという必要条件になる。
どう使うか
実用上は、変数 $\lambda = (\lambda_1, \ldots, \lambda_m)$ を新たに導入してラグランジュ関数 (Lagrangian)
$$
L(x, \lambda) = f(x) - \sum_{i=1}^{m} \lambda_i\, g_i(x)
$$
を作り、$L$ の $x$ と $\lambda$ に関する偏微分をすべて $0$ とおくのが定石である。$\partial L / \partial x_j = 0$ が上の勾配の等式に、$\partial L / \partial \lambda_i = 0$ が拘束条件 $g_i(x) = 0$ に相当する。こうして極値の候補は $x$ と $\lambda$ に関する連立方程式の解として求まる。
なおラグランジュの未定乗数法が与えるのは極値の必要条件にすぎず、得られた候補が実際に極大か極小かは別途確かめる必要がある。目的関数の凹凸や、$S$ が有界閉集合の場合の最大最小原理などが判定に用いられる。
冒頭で提示した二問に、実際に適用してみよう。
半径 $r > 0$ の球面 $x^2 + y^2 + z^2 = r^2$ 上で $f(x, y, z) = x + y + z$ を最大化する点と、その最大値を求めよ。
$f(x, y, z) = x + y + z$、$g(x, y, z) = x^2 + y^2 + z^2 - r^2$ とおく。$\nabla g$ の成分 $2x, 2y, 2z$ は球面上で同時に $0$ にはならないので、正則性の仮定は満たされる。ラグランジュ関数は
$$
L(x, y, z, \lambda) = x + y + z - \lambda\,(x^2 + y^2 + z^2 - r^2).
$$
各変数で偏微分して $0$ とおくと
$$
\begin{aligned}
\frac{\partial L}{\partial x} &= 1 - 2\lambda x = 0, \\
\frac{\partial L}{\partial y} &= 1 - 2\lambda y = 0, \\
\frac{\partial L}{\partial z} &= 1 - 2\lambda z = 0.
\end{aligned}
$$
いずれからも $\lambda \neq 0$ かつ $x = y = z = 1/(2\lambda)$ を得る。拘束条件 $x^2 + y^2 + z^2 = r^2$ に代入すると $3/(2\lambda)^2 = r^2$ より $2\lambda = \pm\sqrt{3}/r$ となり、極値の候補は
$$
(x, y, z) = \pm\left(\frac{r}{\sqrt{3}},\, \frac{r}{\sqrt{3}},\, \frac{r}{\sqrt{3}}\right).
$$
このとき $f = \pm r\sqrt{3}$ である。球面は有界閉集合で $f$ は連続であるから最大値と最小値をとり、それぞれが極値の候補と一致する。よって最大値は $r\sqrt{3}$、達成する点は $(r/\sqrt{3}, r/\sqrt{3}, r/\sqrt{3})$。
$n$ 個の事象からなる集合 $\{1, 2, \ldots, n\}$ 上の確率分布 $p = (p_1, \ldots, p_n)$（$p_i > 0$、$\sum p_i = 1$）に対し、シャノンエントロピーを
$$
H(p) = -\sum_{i=1}^{n} p_i \log p_i
$$
と定める。$H(p)$ を最大にする分布を求めよ。
拘束条件は「$p$ が確率分布であること」、すなわち
$$
g(p) = \sum_{i=1}^{n} p_i - 1 = 0
$$
の一本である（$p_i > 0$ は開領域の指定として扱う）。$\nabla g$ の全成分は $1$ で $0$ にはならないので、正則性の仮定は自動的に満たされる。ラグランジュ関数は
$$
L(p, \lambda) = -\sum_{i=1}^{n} p_i \log p_i - \lambda \left(\sum_{i=1}^{n} p_i - 1\right).
$$
各 $p_i$ で偏微分すると
$$
\frac{\partial L}{\partial p_i} = -\log p_i - 1 - \lambda = 0 \quad (i = 1, \ldots, n)
$$
より $p_i = e^{-1-\lambda}$。右辺は $i$ に依存しないので、極値点では $p_1 = p_2 = \cdots = p_n$ が成り立つ。拘束条件 $\sum p_i = 1$ と組み合わせると
$$
p_i = \frac{1}{n} \quad (i = 1, \ldots, n).
$$
すなわち一様分布が唯一の極値の候補であり、そのエントロピーは
$$
H\!\left(\tfrac{1}{n}, \ldots, \tfrac{1}{n}\right) = -\sum_{i=1}^{n} \frac{1}{n} \log \frac{1}{n} = \log n
$$
である。
$\lim_{p \to 0} p \log p = 0$ より、$0 \log 0 = 0$ と定めることでエントロピー $H$ の定義域を有界閉集合 $\{p \in \mathbb{R}^n \mid p_i \ge 0,\; \sum p_i = 1\}$ に拡張することができる。これにより $H$ は領域内で最大値をもつことが保証される。ところが境界においては、ある $p_i$ が $0$ となるため $H$ の値は $0$ 以上 $\log n$ 未満にとどまる（実際、$n = 1$ での $H \equiv 0$ から始めて $n$ に関する帰納法でわかる）。したがって最大値は内部で達成され、先ほど得た極値の候補である一様分布 $p_i = 1/n$ こそがエントロピーの最大値 $\log n$ を与える。
まとめ
拘束条件のもとでの最大値・最小値問題は、拘束条件を具体的に解いて変数を減らすと、対称性が失われて計算が煩雑になりがちである。ラグランジュの未定乗数法を用いれば、拘束条件を「解く」ことなく、勾配ベクトルの一次関係として必要条件が書けるため、変数の対称性を保ったまま問題を綺麗に解くことができた。
証明は陰関数定理を用いるもので技巧を要するが、証明を知らなくてもラグランジュ関数を作って偏微分を $0$ とおくという手続きは機械的に使える。この記事でその使い方が理解できたのであれば幸いである。
