多元标量函数的梯度下降优化

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。