多元標量函數的梯度下降優化

Question

我試圖在rosenbrock函數上測試我的梯度下降程序。但無論我如何調整自己的學習率（step參數），精度（precision參數）和迭代次數（iteration參數），我都無法獲得非常接近的結果。

import numpy as np 

def minimize(f, f_grad, x, step=1e-3, iterations=1e3, precision=1e-3): 
    count = 0 
    while True: 
     last_x = x 
     x = x - step * f_grad(x) 
     count += 1 
     if count > iterations or np.linalg.norm(x - last_x) < precision: 
      break 
    return x 

def rosenbrock(x): 
    """The Rosenbrock function""" 
    return sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0) 

def rosenbrock_grad(x): 
    """Gradient of Rosenbrock function""" 
    xm = x[1:-1] 
    xm_m1 = x[:-2] 
    xm_p1 = x[2:] 
    der = np.zeros_like(x) 
    der[1:-1] = 200*(xm-xm_m1**2) - 400*(xm_p1 - xm**2)*xm - 2*(1-xm) 
    der[0] = -400*x[0]*(x[1]-x[0]**2) - 2*(1-x[0]) 
    der[-1] = 200*(x[-1]-x[-2]**2) 
    return der 

x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2]) 
minimize(rosenbrock, rosenbrock_grad, x0, step=1e-6, iterations=1e4, precision=1e-6) 

例如，像上面的代碼給我array([ 1.01723267, 1.03694999, 1.07870143, 1.16693184, 1.36404334])。但如果我使用scipy.optimize中的任何內置優化方法，我可以得到非常接近的答案或完全相等array([ 1., 1., 1., 1., 1.])（這是真實的答案）。

但是，如果我在我的程序中使用非常小的step,precision和非常大的iterations，計算只需要在我的計算機上永久存在。

我不知道這是由於

在我的程序中的任何錯誤

或者僅僅因爲

梯度下降是低效這裏的要求很低 step，precision和非常大的iterations產生非常接近的 解決方案

，或者因爲

我需要做一些特殊的功能擴展。

（聚苯乙烯。我還試圖繪製二維圖，其中的函數值是在y軸上和迭代次數是在X軸上爲「調試」梯度下降，但即使我得到一個nice-解決方案仍然不是非常接近。）

Answer 1

您的方法容易出現過沖。在瞬間高梯度的情況下，您的解決方案將跳得很遠。當優化不能降低成本時拒絕採取措施通常是合適的。

搜索下

一旦通過compuing梯度選擇了一個方向，搜索沿那個方向，直到你通過漸變的規範的某些部分降低成本。

I.e.以$ x _ {[n + 1]} = x - \ alpha *漸變開始$

將$ \ alpha $從1.0改爲0.0，接受x的值，如果已將成本降低一小部分的梯度。這是一個很好的收斂規則，稱爲Armijo規則。

其他建議

首先考慮優化2D Rosenbrock函數，並在該領域的成本策劃你的路徑。

考慮用數字驗證您的梯度實現是否正確。往往不是，這是問題所在。

Answer 2

引述Rosenbrock Wikipedia page：

的全局最小值是一個長而窄的，拋物線形的平坦山谷的內部。找到山谷是微不足道的。然而，要收斂到全球最低限度是困難的。

漸變下降是一個簡單的算法，所以它可能並不奇怪，它不能找到最小值。讓我們來看看在2D發生了什麼不同的起點：

正如維基百科說：它很容易找到的山谷，但隨後未能進一步收斂。與其他功能相比，山谷中的坡度非常平坦。

我會斷定您的實現能夠正常工作，但也許Rosenbrock函數並不是測試它的最合適的函數。

與其他答案相反，我進一步認爲步長太小而不是太大。問題不在於超調，而是算法卡住了。如果我將步長設置爲1e-3而不更改其他設置，算法會在兩位數內收斂到最大值。儘管在2D情況下從一些起始位置超過了山谷，但這種情況發生了，但是您需要速度不要稍後卡住，這樣說。

下面是修改的代碼重現上圖：

import numpy as np 
import matplotlib.pyplot as plt 

def minimize(f, f_grad, x, step=1e-3, iterations=1e3, precision=1e-3): 
    count = 0 
    while True: 
     last_x = x 
     x_hist.append(x) 
     x = x - step * f_grad(x) 
     count += 1 
     if count > iterations or np.linalg.norm(x - last_x) < precision: 
      x_hist.append(x) 
      break 
    return x 

def rosenbrock(x): 
    """The Rosenbrock function""" 
    return sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0) 

def rosenbrock_grad(x): 
    """Gradient of Rosenbrock function""" 
    xm = x[1:-1] 
    xm_m1 = x[:-2] 
    xm_p1 = x[2:] 
    der = np.zeros_like(x) 
    der[1:-1] = 200*(xm-xm_m1**2) - 400*(xm_p1 - xm**2)*xm - 2*(1-xm) 
    der[0] = -400*x[0]*(x[1]-x[0]**2) - 2*(1-x[0]) 
    der[-1] = 200*(x[-1]-x[-2]**2) 
    return der 


k = np.linspace(0, 2, 101) 
f = np.empty((k.shape[0], k.shape[0])) 
for i, y in enumerate(k): 
    for j, x in enumerate(k): 
     f[i, j] = rosenbrock(np.array([x, y])) 
plt.imshow(np.log10(f), extent=[k[0], k[-1], k[-1], k[0]], cmap='autumn') 

for start in [[0.5, 0.5], [1.0, 0.5], [1.5, 0.5], 
       [0.5, 1.0], [1.0, 1.0], [1.5, 1.0], 
       [0.5, 1.5], [1.0, 1.5], [1.5, 1.5]]: 

    x0 = np.array(start) 

    x_hist = [] 

    minimize(rosenbrock, rosenbrock_grad, x0, step=1e-6, iterations=1e4, precision=1e-9) 


    x_hist = np.array(x_hist) 
    plt.plot(x_hist[:, 0], x_hist[:, 1], 'k') 
    plt.plot(x0[0], x0[1], 'ok') 

Answer 3

想象你正在沿着這是越來越窄一 knife-edge 山路登山。 A 常數步長會帶你過邊，aieeeee; 你想在攀登時採取更短，更謹慎的步驟。 同樣，要跟隨羅森布魯克山谷，隨着山谷變窄，計劃必須採取更短，更謹慎的步驟。 step0/t^0.5遞減步長或0.25 有助於Rosenbrock上的GD位， ，但仍然是很對step0敏感。

真正的步長 - 學習率必須適應問題地形，例如， 尋找順暢的問題，Ada *爲 SGD。

順便說一句，Rosenbrock函數是一個正方形的總和， ，並且有強大的方法;見 scipy.optimize.least_squares。