最急降下法を解説！(最適化講座②)

最急降下法、かっこいい名前の最適化法ですね。ただ最適化法ってたくさんある割に解法が似てるものが多いので、頭の中がこんがらがってしまいそうになります(笑).

今回の講座では最急降下法についてわかりやすく解説し、実際の例題まで解いていきたいと思います。

最急降下法とは？

最急降下法（Steepest Descent Method）は、関数の最小値を求めるための数値最適化手法の一つです。この手法は、現在の位置での勾配（関数の傾き）を利用して、関数の値が最も急激に減少する方向に進むことで、最小値を見つけようとします。

原理

最急降下法の基本的な考え方は、関数$f(x)$の値が減少する方向に向かって進むことです。関数$f(x)$が与えられた場合、その勾配$\nabla f(x)$は関数の傾きを示します。最急降下法では、この勾配の反対方向に進むことで関数の値を減少させます。具体的には、現在の位置$x_k$から次の位置$x_{k+1}$への更新は以下のように行われます：

$$x_{k+1} = x_k – \alpha \nabla f(x_k)$$

ここで、$\alpha$はステップサイズ（学習率）と呼ばれるパラメータで、各ステップでどれだけ進むかを決定します。

定義式

最急降下法の更新式は次の通りです：

$$x_{k+1} = x_k – \alpha \nabla f(x_k)$$

ここで、

$x_k$は現在の位置（k番目の反復の解）
$\alpha$はステップサイズ
$\nabla f(x_k)$は現在の位置での関数の勾配

例題

例題1：二次関数の最小化

関数$f(x) = x^2 + 4x + 4$の最小値を最急降下法で求めてみましょう。この関数の勾配は$\nabla f(x) = 2x + 4$です。

初期点$x_0$を適当に選びます。ここでは$x_0 = 10$とします。
ステップサイズ$\alpha$を設定します。ここでは$\alpha = 0.1$とします。
更新式を用いて次の位置を計算します：

$$\begin{align}
x_{1} &= x_0 – \alpha \nabla f(x_0) \\
&= 10 – 0.1 \cdot (2 \cdot 10 + 4) \\
&= 10 – 0.1 \cdot 24 = 10 – 2.4 = 7.6
\end{align}$$

同様にして次のステップを計算します：

$$\begin{align}
x_{2} &= x_1 – \alpha \nabla f(x_1) \\
&= 7.6 – 0.1 \cdot (2 \cdot 7.6 + 4) \\
&= 7.6 – 0.1 \cdot 19.2 = 7.6 – 1.92 = 5.68
\end{align}$$

この手順を繰り返すと、関数の最小値に近づいていきます。実際に何回の反復で十分に収束しているのかPythonコードで計算し、確認してみましょう。以下がソースコードです。

import numpy as np

def f(x):
    return x**2 + 4*x + 4

def grad_f(x):
    return 2*x + 4

def gradient_descent(grad_f, x0, alpha, tol=1e-7, max_iter=1000):
    x = x0
    for i in range(max_iter):
        grad = grad_f(x)
        x_new = x - alpha * grad
        print(f"Iteration {i+1}: x = {x_new}")
        if abs(x_new - x) < tol:
            break
        x = x_new
    return x

# 初期値 x0
x0 = 10.0

# ステップサイズ α
alpha = 0.1

# 最急降下法を実行
solution = gradient_descent(grad_f, x0, alpha)

print(f"求められた解: x = {solution}")

実行結果は以下の通りになります。

Iteration 1: x = 7.6
Iteration 2: x = 5.68
Iteration 3: x = 4.144
Iteration 4: x = 2.9152
Iteration 5: x = 1.9321599999999999
Iteration 6: x = 1.1457279999999999
Iteration 7: x = 0.5165823999999998
Iteration 8: x = 0.01326591999999982
Iteration 9: x = -0.3893872640000002
Iteration 10: x = -0.7115098112000002
Iteration 11: x = -0.9692078489600002
Iteration 12: x = -1.1753662791680002
Iteration 13: x = -1.3402930233344001
Iteration 14: x = -1.47223441866752
Iteration 15: x = -1.577787534934016
Iteration 16: x = -1.6622300279472129
Iteration 17: x = -1.7297840223577703
Iteration 18: x = -1.7838272178862162
Iteration 19: x = -1.827061774308973
Iteration 20: x = -1.8616494194471784
Iteration 21: x = -1.8893195355577428
Iteration 22: x = -1.9114556284461943
Iteration 23: x = -1.9291645027569555
Iteration 24: x = -1.9433316022055644
Iteration 25: x = -1.9546652817644516
Iteration 26: x = -1.9637322254115612
Iteration 27: x = -1.970985780329249
Iteration 28: x = -1.9767886242633992
Iteration 29: x = -1.9814308994107193
Iteration 30: x = -1.9851447195285754
Iteration 31: x = -1.9881157756228602
Iteration 32: x = -1.9904926204982882
Iteration 33: x = -1.9923940963986306
Iteration 34: x = -1.9939152771189046
Iteration 35: x = -1.9951322216951237
Iteration 36: x = -1.996105777356099
Iteration 37: x = -1.9968846218848793
Iteration 38: x = -1.9975076975079034
Iteration 39: x = -1.9980061580063226
Iteration 40: x = -1.998404926405058
Iteration 41: x = -1.9987239411240465
Iteration 42: x = -1.998979152899237
Iteration 43: x = -1.9991833223193898
Iteration 44: x = -1.999346657855512
Iteration 45: x = -1.9994773262844094
Iteration 46: x = -1.9995818610275276
Iteration 47: x = -1.999665488822022
Iteration 48: x = -1.9997323910576177
Iteration 49: x = -1.9997859128460942
Iteration 50: x = -1.9998287302768754
Iteration 51: x = -1.9998629842215003
Iteration 52: x = -1.9998903873772003
Iteration 53: x = -1.9999123099017602
Iteration 54: x = -1.999929847921408
Iteration 55: x = -1.9999438783371264
Iteration 56: x = -1.9999551026697011
Iteration 57: x = -1.999964082135761
Iteration 58: x = -1.9999712657086088
Iteration 59: x = -1.999977012566887
Iteration 60: x = -1.9999816100535095
Iteration 61: x = -1.9999852880428075
Iteration 62: x = -1.999988230434246
Iteration 63: x = -1.9999905843473968
Iteration 64: x = -1.9999924674779175
Iteration 65: x = -1.999993973982334
Iteration 66: x = -1.9999951791858672
Iteration 67: x = -1.9999961433486937
Iteration 68: x = -1.999996914678955
Iteration 69: x = -1.999997531743164
Iteration 70: x = -1.999998025394531
Iteration 71: x = -1.999998420315625
Iteration 72: x = -1.9999987362525
Iteration 73: x = -1.999998989002
Iteration 74: x = -1.9999991912016
Iteration 75: x = -1.99999935296128
Iteration 76: x = -1.9999994823690241
Iteration 77: x = -1.9999995858952193
Iteration 78: x = -1.9999996687161754
求められた解: x = -1.9999995858952193

ステップサイズを変化させればもっと少ない試行回数で最適解まで収束することができるかもしれませんが、基本的にはステップサイズが小さい方が滑らかに収束します。今回の結果では32回の反復で1/100スケールまで近似できていることがわかります。

結論

最急降下法は、勾配の情報を利用して関数の最小値を見つける強力な手法です。適切なステップサイズを選ぶことが重要であり、問題に応じてステップサイズを調整することで、効率よく最小値を求めることができます。ただし、ニュートン法に比べると収束するまでに時間がかかるかもしれませんね。そのあたりはうまく使い分けていきましょう！

このブログが、最急降下法についての理解を深める一助となれば幸いです。質問やコメントがあれば、ぜひお寄せください。