前言

寫完了牛頓法，來寫梯度下降法。
擬牛頓法有點深奧，應該暫時不會寫。

主體

想法類似於牛頓法，但是少了Hessian矩陣的計算:

迭代公式:
$x_{k+1}=x_k - \alpha \nabla f(x_k)$
同樣，這邊$x$是一堆變量$a, b, c …$。

$\nabla f(x_k)$為梯度，可以利用對各變數偏微分得到，例如:
$\nabla f(x, y) = \frac{\partial f}{\partial x}(x, y)i + \frac{\partial f}{\partial y}(x, y)j$

而$\alpha$則是一個調整係數，一般都是在區間(0, 1]裡，具體什麼用途，必須配合等下的例子才能說明。

code

import numpy as np
import matplotlib.pyplot as plt

f = lambda x, y: np.sqrt(x ** 2 + y ** 2 / 3)

def dfdx(x0, y0):
    h = 1e-6
    return (f(x0 + h, y0) - f(x0, y0)) / h

def dfdy(x0, y0):
    h = 1e-6
    return (f(x0, y0 + h) - f(x0, y0)) / h

# 梯度矩陣
def grad(x, y):
    return np.array([dfdx(x, y), dfdy(x, y)])

X = np.linspace(-5, 10, 256)
Y = np.linspace(-5, 10, 256)

X, Y = np.meshgrid(X, Y)
Z = f(X, Y)
plt.xlabel("x")
plt.ylabel("y")
C = plt.contour(X, Y, Z)

# 調整係數
a = .8

# 起始點
preP = np.array([8.3, 7.6])
nowP = preP - grad(preP[0], preP[1]) * a
plt.plot((preP[0], nowP[0]), (preP[1], nowP[1]), 'bo-')

# 迭代
for i in range(50):
	preP = nowP
    nowP = preP - grad(preP[0], preP[1]) * a
    plt.plot((preP[0], nowP[0]), (preP[1], nowP[1]), 'ro-')
    
print(nowP)
print(f(nowP[0], nowP[1]))

測試

$\sqrt{x^2 + \frac{y^2}{3}}$, 起始值=(8.3, 7.6), $\alpha = 1$, 迭代次數 16
收斂值 $(x,y) = (-0.00243513, -0.10515567), f(x, y) = 0.06076047183997639$

$xe^{-x^2 - y^2}$, 起始值=(0.3, 0.6), $\alpha = 0.7$, 迭代次數 4
收斂值 $(x,y) = (-0.7073123, 0.11798947), f(x, y) = -0.42295258860276885$

$(3x - 2)^2(y - 5)^2 - 1$, 起始值=(-4, 0), $\alpha = 0.1$, 迭代次數 1
收斂值 無法收斂
註解: 無法收斂的原因在下面會講

$(3x - 2)^2(y - 5)^2 - 1$, 起始值=(-4, 0), $\alpha = 0.001$, 迭代次數 100
收斂值 $(x,y) = (0.65374851, 3.42158651), f(x, y) = -0.9962581603349078$

$(2x + 5)^2(213y - 0.65)^2 - 5$, 起始值=(0, 0), $\alpha = 0.1$, 迭代次數 4
收斂值 無法收斂

觀察結論

以上面的結果與其餘未放上來的資料來說，這個版本的梯度下降法不那麼實用。
當我們的函數值在 某點梯度極大 ，我們的迭代點將會因為這個梯度”衝過頭”，更糟糕的是，衝過頭後的點梯度可能會更大(類似遊樂園的海盜船，但是停不下來)，導致 無法收斂 的情況，上面雖然只放了兩個例子，但是非常容易構造此種函數。

因為這樣子，所以才需要引入 調整係數 ，但是又出現了另一個缺點，收斂太慢。
調整係數低確實可以提高收斂的機率，但是以此為代價，迭代次數亦會跟著成長。