TAKEO

TAKEO

図で理解する最適化シリーズ 第2回 / 全3回

偏微分で解く非線形最適化 — 3D曲面の底を探す

前回 は、3x+2y3x+2y のような一次式を最大化する問題を、直線を平行移動する方法で解いた。

では、目的関数が次のように曲がっていたらどうだろう。

f(x,y)=x2+xy+2y2−6x−8yf(x,y)=x^2+xy+2y^2-6x-8y

今度は f(x,y)=kf(x,y)=k が直線にならない。かわりに登場するのが、3D曲面・等高線・偏微分だ。

この記事では制約条件を付けず、x,yx,y を自由に動かせる場合の最小化を考える。

1. 2変数関数を3Dで見る

1変数関数 y=f(x)y=f(x) のグラフは、平面上の曲線だった。

2変数関数 z=f(x,y)z=f(x,y) では、各 (x,y)(x,y) に対して高さ zz が決まるので、グラフは空間内の曲面になる。

まずは単純な例を見よう。

f(x,y)=(x−2)2+2(y−1)2+1f(x,y)=(x-2)^2+2(y-1)^2+1

どちらも2乗なので、

f(x,y)≥1f(x,y)\geq1

は常に成り立つ。等号が成り立つのは (x,y)=(2,1)(x,y)=(2,1) のときだけだ。したがって最小値は 11 である。

3Dで描くと、(2,1,1)(2,1,1) に底がある、お椀のような曲面になる。

インタラクティブ

曲面を回して、底を探す

z = (x − 2)² + 2(y − 1)² + 1

底が (2,1,1) の曲面、視点角度 35 度x方向y方向底 (2, 1, 1)

最も低い点は (2, 1, 1)。等高線は同じ高さの点を結んだ線です。中心へ進むと高さが下がります。

3Dの表示範囲は x = 0〜4、y = −1〜3。色付きの線は、底からのx方向・y方向の断面です。

2. 偏微分は「片方だけ動かしたときの傾き」

1変数関数の微分 f′(x)f'(x) は、グラフのその点における傾きだった。

2変数では動ける方向がたくさんある。まずは xx 方向と yy 方向を別々に見る。

  • xx に関する偏微分 ∂f∂x\frac{\partial f}{\partial x}：yy を固定して、xx だけを少し動かしたときの変化率
  • yy に関する偏微分 ∂f∂y\frac{\partial f}{\partial y}：xx を固定して、yy だけを少し動かしたときの変化率

さきほどの単純な関数なら、

∂f∂x=2(x−2),∂f∂y=4(y−1)\frac{\partial f}{\partial x}=2(x-2),\qquad \frac{\partial f}{\partial y}=4(y-1)

となる。

底では、どちらの方向にも傾いていないので、

∂f∂x=0,∂f∂y=0\frac{\partial f}{\partial x}=0,\qquad \frac{\partial f}{\partial y}=0

が成り立つ。

3. 二つの偏微分をまとめたものが「勾配」

偏微分をベクトルとしてまとめると、**勾配（gradient）**になる。

∇f(x,y)=(∂f∂x∂f∂y)\boxed{ \nabla f(x,y)= \begin{pmatrix} \frac{\partial f}{\partial x}\\[4pt] \frac{\partial f}{\partial y} \end{pmatrix} }

勾配ベクトルは、その点で関数が最も急激に増える方向を指す（通常のユークリッド距離で考えた場合）。逆向きの −∇f-\nabla f は、最も急激に減る方向だ。

微小な移動 (Δx,Δy)(\Delta x,\Delta y) に対して、

Δf≈∂f∂xΔx+∂f∂yΔy=∇f⋅(ΔxΔy)\Delta f\approx \frac{\partial f}{\partial x}\Delta x+ \frac{\partial f}{\partial y}\Delta y = \nabla f\cdot \begin{pmatrix}\Delta x\\\Delta y\end{pmatrix}

と近似できる。内積なので、移動方向と勾配の向きがそろうほど、増加量は大きくなる。

滑らかな関数が、制約のない内点で局所的な最大値・最小値を取るなら、そこでは通常、

∇f(x,y)=0\boxed{\nabla f(x,y)=\mathbf{0}}

が必要になる。

ただし、これは必要条件であって十分条件ではない。勾配がゼロでも、そこが底とは限らない。

インタラクティブ

勾配は、最も急に高くなる方向

∇f = (2(x − 2), 4(y − 1))

等高線と勾配。現在の点 (3,2) の勾配は (2.0,4.0)00224466xy
∇f = (2.0, 4.0)

黒い矢印が選んだ点の勾配です。逆向きに少し進むと高さが下がります。底では勾配がゼロになり、矢印が消えます。

図をドラッグするか、スライダーで点を動かせます。矢印の長さは勾配の大きさに比例します（背景の矢印は黒い矢印より縮小）。

4. 実際に、少し複雑な関数を最小化してみる

冒頭の関数に戻ろう。

f(x,y)=x2+xy+2y2−6x−8y\boxed{f(x,y)=x^2+xy+2y^2-6x-8y}

今回は xyxy が含まれるので、xx 方向と yy 方向の変化が互いに影響し合う。

それぞれ偏微分すると、

∂f∂x=2x+y−6∂f∂y=x+4y−8\begin{aligned} \frac{\partial f}{\partial x}&=2x+y-6\\ \frac{\partial f}{\partial y}&=x+4y-8 \end{aligned}

勾配がゼロになる点を探す。

{2x+y−6=0x+4y−8=0\begin{cases} 2x+y-6=0\\ x+4y-8=0 \end{cases}

1本目から y=6−2xy=6-2x。2本目に代入して、

x+4(6−2x)−8=0⟹x=167x+4(6-2x)-8=0 \quad\Longrightarrow\quad x=\frac{16}{7}

したがって、

(x,y)=(167,107)\boxed{(x,y)=\left(\frac{16}{7},\frac{10}{7}\right)}

が停留点だ。そのときの値は、

f(167,107)=−887f\left(\frac{16}{7},\frac{10}{7}\right) =-\frac{88}{7}

となる。

でも、これだけでは「本当に最小値か」はまだ証明できない。

5. 勾配ゼロでも最小値とは限らない

例えば、

g(x,y)=x2−y2g(x,y)=x^2-y^2

を考えてみよう。原点 (0,0)(0,0) では、

∇g(0,0)=(00)\nabla g(0,0)=\begin{pmatrix}0\\0\end{pmatrix}

となる。

しかし、y=0y=0 に沿って動くと g(x,0)=x2≥0g(x,0)=x^2\geq0、x=0x=0 に沿って動くと g(0,y)=−y2≤0g(0,y)=-y^2\leq0 だ。

原点は、ある方向には谷、別の方向には山になっている。このような点を**鞍点（あんてん）**という。

インタラクティブ

勾配ゼロでも、底とは限らない

お椀：z = x² + y²　／　鞍点：z = x² − y²

お椀：原点が最小点

原点が最小点のお椀、視点角度 35 度x方向y方向原点 (0, 0, 0)

鞍点：原点は最小点ではない

原点が鞍点の曲面、視点角度 35 度x方向y方向原点 (0, 0, 0)
  • お椀：x軸・y軸方向ともt² = 0.00
  • 鞍点：x軸方向 (t, 0)t² = 0.00
  • 鞍点：y軸方向 (0, t)−t² = 0.00

どちらも原点で勾配はゼロ。鞍点では、x方向に進むと上がり、y方向に進むと下がります。方向ごとの曲がり方を調べる必要があります。

6. ヘッセ行列で「曲がり方」を調べる

そこで使うのが、2階偏微分を並べた**ヘッセ行列（Hessian）**だ。

Hf(x,y)=(∂2f∂x2∂2f∂x∂y∂2f∂y∂x∂2f∂y2)H_f(x,y)= \begin{pmatrix} \frac{\partial^2f}{\partial x^2} & \frac{\partial^2f}{\partial x\partial y}\\[4pt] \frac{\partial^2f}{\partial y\partial x} & \frac{\partial^2f}{\partial y^2} \end{pmatrix}

今回の関数では、

Hf=(2114)H_f= \begin{pmatrix} 2&1\\ 1&4 \end{pmatrix}

となる。左上の成分は 2>02>0、行列式は、

det⁡Hf=2⋅4−1⋅1=7>0\det H_f=2\cdot4-1\cdot1=7>0

だ。この2条件からヘッセ行列が正定値であることが分かる。今回の関数は上に凸の二次関数なので、停留点は局所的な底であるだけでなく、全体でただ一つの最小点になる。

実際、停留点からのずれを u=x−167u=x-\frac{16}{7}、v=y−107v=y-\frac{10}{7} と置くと、

f(x,y)+887=u2+uv+2v2=(u+v2)2+74v2≥0\begin{aligned} f(x,y)+\frac{88}{7} &=u^2+uv+2v^2\\ &=\left(u+\frac{v}{2}\right)^2+\frac74v^2\geq0 \end{aligned}

である。等号は u=v=0u=v=0 のときだけ成立するので、

fmin⁡=−887\boxed{f_{\min}=-\frac{88}{7}}

と厳密に結論できる。

参考までに、2変数でヘッセ行列が対称な場合、停留点付近の判定には D=fxxfyy−fxy2D=f_{xx}f_{yy}-f_{xy}^2 が使える。D>0D>0 かつ fxx>0f_{xx}>0 なら局所最小、D>0D>0 かつ fxx<0f_{xx}<0 なら局所最大、D<0D<0 なら鞍点。D=0D=0 の場合はこの判定だけでは決められない。

7. 計算機はどうやって底を探す？

式が複雑になって連立方程式を直接解けなくても、勾配が分かれば少しずつ値を下げていける。

それが**勾配降下法（gradient descent）**の基本的な考え方だ。

xt+1=xt−η∂f∂x(xt,yt)yt+1=yt−η∂f∂y(xt,yt)\begin{aligned} x_{t+1}&=x_t-\eta\frac{\partial f}{\partial x}(x_t,y_t)\\ y_{t+1}&=y_t-\eta\frac{\partial f}{\partial y}(x_t,y_t) \end{aligned}

η>0\eta>0 は一歩の大きさを表す学習率。大きすぎると行き過ぎ、小さすぎると収束が遅くなる。

今回の関数なら、更新式は、

xt+1=xt−η(2xt+yt−6)yt+1=yt−η(xt+4yt−8)\begin{aligned} x_{t+1}&=x_t-\eta(2x_t+y_t-6)\\ y_{t+1}&=y_t-\eta(x_t+4y_t-8) \end{aligned}

になる。

インタラクティブ

勾配を頼りに、一歩ずつ底へ

f = x² + xy + 2y² − 6x − 8y

勾配降下法 0 ステップ目、現在点 (5.000, 4.000)00224466xy
0歩目：f = 15.0000

現在点 (5.000, 4.000)。最小点 (16/7, 10/7) までの距離は 3.7389 です。

白抜きの点が最小点、緑が現在点です。この二次関数では 0 < η < 2/(3+√2) ≈ 0.4531 なら、どの開始点からも収束します。大きすぎる学習率で振動・発散する様子も試せます。最大60歩、座標の大きさが10⁶を超える手前で停止します。

まとめ：勾配は「次にどちらへ動くか」を教えてくれる

今回は、非線形関数を最小化するために、

  1. 2変数関数を3D曲面と等高線で捉える。
  2. 偏微分で二つの方向の傾きを求める。
  3. 勾配がゼロになる停留点を探す。
  4. ヘッセ行列などを使い、本当に最小点か確認する。

という順番で考えた。

ただし、ここまでは x,yx,y を自由に動かせる場合の話だ。制約条件があると、勾配がゼロではない場所が最適解になることがある。

次回は、その理由を幾何学的に理解し、ラグランジュ未定乗数法とKKT条件につなげよう。

次の記事： ラグランジュ未定乗数法とKKT条件

ホームへ