我们知道, 函数沿着负梯度方向下降是最快的, 因此利用梯度下降法是计算函数极小值的常用的方法.因此如果我们确定一个初始点\(x_0\), 那么利用迭代公式:

$$x_{k+1} = x_k - \alpha_k \nabla f(x_k) $$

其中\(\alpha_k\)为步长.

举一个简单的例子(一下的代码是在jupyter-notebook中运行的):

f = lambda x, y: x**2+y**2-2*x*y+y**2-2*y # 所要优化的函数
diff_fx = lambda x, y: 2*x-2*y#偏导数
diff_fy = lambda x, y: 4*y-2*x-2
# 设置起始点, 步长
init_point = [30, 6]
alph = 0.1

for ii in range(30):
    init_point[0] = init_point[0] - alph*diff_fx(*init_point)
    init_point[1] = init_point[1] - alph*diff_fy(*init_point)
print(diff_fx(*init_point), diff_fy(*init_point))

## 经过30步的优化, x变成了:
1.386617494686719 0.526631421096333


print(f(* init_point))
### 此时的函数值:

0.3958073725790734

实际上我们设置的函数为: $$f(x, y) = (x-y)^{2}+(y-1)^{2}-1$$ 很明显, 当\(x = y = 1\)的时候函数取得极小值, 为-1. 对比上诉的结果很明显并不尽人意. 上面的方法是步长是不变的, 如果改变不长会不会是效果变好呢, 答案是显然的. 但是什么样的步长是最佳的呢? 这里我们考虑一个正定二次型函数: $$f = \frac{1}{2} x^{T}Qx$$

我们知道沿着负梯度的方向, 函数值会变小, 但是这里涉及到步长的取值, 我们可以采用一般的一维搜索的方法, 也即为

\begin{equation} \alpha_k = argmin ~ f(x_k -\alpha_kg(x_k)) \end{equation}

其中\(g(x_k)=\nabla f(x_k)\). 因此我们对\(\alpha_k\)求一个极值即可.

所以有

\begin{equation} 0 = g(x_k)^{T}f’(x_k -\alpha_kg(x_k)) =g(x_k)^{T}Q(x_k -\alpha_kg(x_k)) \end{equation}

从而得出

$$\alpha_k = \frac{g(x_k)^{T}g(x_k)^{T}}{g(x_k)^{T}Qg(x_k)^{T}}$$

因此对于二次型的函数而言, 步长为\(\alpha_{k}\)的梯度下降法为最佳步长, 因此该种算法也被称为最速下降法.

仍然以上面的函数为例


f = lambda x, y: x**2+y**2-2*x*y+y**2-2*y # 所要优化的函数
diff_fx = lambda x, y: 2*x-2*y#偏导数
diff_fy = lambda x, y: 4*y-2*x-2
Q = [[2, -2], [-2, 4]]
# 设置起始点
init_point = [30, 6]

import copy
gx, gy = diff_fx(*init_point), diff_fy(*init_point)
path = [copy.deepcopy(init_point)]
for ii in range(30):
    Q = [[2, -2], [-2, 4]]
    alph = (gx**2 + gy**2)/(Q[0][0]*gx**2+Q[1][1]*gy**2+Q[0][1]*gx*gy*2)
    init_point[0] = init_point[0] - alph*diff_fx(*init_point)
    init_point[1] = init_point[1] - alph*diff_fy(*init_point)
    path.append(copy.deepcopy(init_point))
    gx, gy = diff_fx(*init_point), diff_fy(*init_point)
print(diff_fx(*init_point), diff_fy(*init_point))
## 输出梯度, 可见此时30步就已经收敛了
7.2984678589627094e-06 -1.2736575571992148e-07

为了让该过程更加形象一点, 我们可以画一个示意图来标识在搜寻过程中x的位置走向.

# 定义等高线图的横纵坐标x,y
#从左边取值为从 -3 到 3 ,各取5个点,一共取 5*5 = 25 个点
%matplotlib inline ## 这个是jupyter-notebook 的magic命令, 可以inline显示图片
import numpy as np
import matplotlib.pyplot as plt
x = np.linspace(-35, 35, 120)
y = np.linspace(-35, 35, 120)
# 将原始数据变成网格数据
X, Y = np.meshgrid(x, y)

Height = (X-Y)**2+(Y-1)**2-1
# 填充颜色
plt.contourf(X, Y, Height, 10, alpha = 0.6, cmap = plt.cm.hot)
# 绘制等高线
C = plt.contour(X, Y, Height, 10, colors = 'black')
# 显示各等高线的数据标签
plt.clabel(C, inline = True, fontsize = 10)

for ii in range(len(path)-1):
    plt.plot([path[ii][0], path[ii+1][0]], [path[ii][1], path[ii+1][1]], color='red')
plt.plot(init_point[0], init_point[1], 'go')
plt.show()

x的轨迹图

该份博客的代码已经用jupyter-notebook实现, 地址在.