梯度下降

梯度下降用局部斜率寻找函数的较小值。对可微函数 $f : ℝ^{n} \to ℝ$ ，迭代式为 $x_{k + 1} = x_{k} - η_{k} \nabla f (x_{k}),$ 其中 $η_{k} > 0$ 是步长。负梯度是当前点一阶近似中下降最快的方向；但步长过大仍可能越过低谷，使函数值上升。

二次函数的每一步

取 $f (x) = (x - 3)^{2}$ ，梯度 $f^{'} (x) = 2 (x - 3)$ 。若 $x_{0} = 0$ 、固定步长 $η = 1 / 4$ ，则 $x_{k + 1} = x_{k} - \frac{1}{2} (x_{k} - 3) = \frac{1}{2} x_{k} + \frac{3}{2}$ 。于是 $x_{1} = 1.5$ 、 $x_{2} = 2.25$ ；令误差 $e_{k} = x_{k} - 3$ ，可见 $e_{k + 1} = e_{k} / 2$ ，因此趋向 0。若步长取 1，则 $e_{k + 1} = - e_{k}$ ，在 0 与 6 之间来回跳，不会收敛。

图中金点依次是 $x_{0}, x_{1}, x_{2}$ ，白点是最小点 3。每次横向位置到 3 的距离缩成一半，纵向函数值则从 9 变成 $9 / 4$ 、 $9 / 16$ ；轨迹说明步长合适时的收敛，但不能替代误差递推式的证明。

抛物线f等于x减三的平方上，梯度下降从x零等于零到x一等于一点五、x二等于二点二五，逐步靠近最小点三 — 固定四分之一步长使横向误差每轮减半，函数值也随之降低。

可运行的 Python 例子

Python 3

def gradient_descent(start: float, step: float, rounds: int) -> list[float]:
    """Minimize (x - 3)^2; return x_0,...,x_rounds."""
    if step <= 0 or rounds < 0:
        raise ValueError("step must be positive and rounds nonnegative")
    x = float(start)
    path = [x]
    for _ in range(rounds):
        x -= step * 2 * (x - 3)
        path.append(x)
    return path

print(gradient_descent(0, 0.25, 3))  # [0.0, 1.5, 2.25, 2.625]

代码不改写传入对象，返回含初值的迭代轨迹。运行 $k$ 步需 $O (k)$ 时间和 $O (k)$ 输出空间；若只需终点，可不保存轨迹，将额外空间降为 $O (1)$ 。

收敛条件

对于梯度 $L$ -Lipschitz 的函数，固定 $0 < η < 2 / L$ 可保证常见的下降性质；若再有适当凸性，还能得到到最优值的收敛结论。上例 $L = 2$ ，所以 $0 < η < 1$ 对应误差因子 $| 1 - 2 η | < 1$ 。一般非凸函数可能停在局部极小点或鞍点附近，不能仅凭“反复下降”宣称找到全局最优。

参考资料

Boyd 与 Vandenberghe，Convex Optimization，迭代优化章节。
MIT 6.079，凸优化讲义。
继续阅读：凸函数、最小二乘法、条件数。