单变量梯度下降

梯度下降迭代寻找极小值；若要最大化 $f$，可改为最小化 $-f$。它适用于难以解析求解的优化问题。

梯度下降的概念

• 先从单变量情形入手，再推广到更复杂的多变量梯度下降。
• 根据函数的导数系统地更新当前点，以迭代逼近函数最小值。

数学形式

对于 $f(x)=e^x-\log(x)$：

1. 计算导数： $f'(x)=e^x-\frac1x$。
2. 迭代更新： 从 $x_0$ 开始，令 $x_1=x_0-\alpha f'(x_0)$，其中 $\alpha$ 是学习率。

导数的符号指示单变量情形下应向左还是向右移动。

挑战与对策

解析求解困难

方程 $e^x=\frac1x$ 难以直接解析求解，正是梯度下降适用的场景。

学习率 $\alpha$

• 学习率决定迭代步长，过大会越过最小值，过小则收敛缓慢。
• 自适应学习率尝试根据优化进度动态调整 $\alpha$，但不存在通用的最优策略。

局部极小值

• 梯度下降可能收敛到局部而非全局极小值。
• 从多个初始点分别运行可以提高接近全局极小值的概率。

实际实现

1. 选择起点与学习率。
2. 反复应用 $x_k=x_{k-1}-\alpha f'(x_{k-1})$。
3. 检查导数大小、目标值下降、定义域和迭代上限。仅凭 $x$ 变化很小，不能判断已接近最优解。

对于 $f(x)=e^x-\log(x)$，每轮在当前点计算导数并按学习率更新， 无需直接解出导数等于零的位置。

在定义域内安全计算

这里 $\log$ 是自然对数，定义域为 $x>0$。由于 $f''(x)=e^x+1/x^2>0$，函数严格凸；而且当 $x\to0^+$ 或 $x\to\infty$ 时，函数都趋于无穷大，所以它有唯一全局最小点。解 $xe^x=1$ 得 $x_*\approx0.567143$，也记作 $W(1)$。这个例子不存在多个局部极小值之间的竞争。

从 $x_0=1$ 出发，取 $\alpha=0.1$，有 $g_0=e-1$、$x_1\approx0.828172$，函数值从 $2.718282$ 降至 $2.477665$。但若从 $x_0=2$ 出发取 $\alpha=1$，下一点为负数，对数无定义。因此要先检查候选点是否可行，再计算目标值。下面的回溯线搜索不断将步长减半，直到满足 Armijo 下降条件；达到迭代或试探上限时报告失败，不冒充收敛。

from math import exp, log, isfinite

def f(x):
    return exp(x) - log(x)

x = 1.0
for iteration in range(10000):
    g = exp(x) - 1 / x
    if abs(g) <= 1e-7:
        break
    alpha = 1.0
    for trial in range(60):
        candidate = x - alpha * g
        if candidate > 0 and isfinite(candidate):
            try:
                value = f(candidate)
            except OverflowError:
                value = float("inf")
            if isfinite(value) and value <= f(x) - 1e-4 * alpha * g * g:
                break
        alpha *= 0.5
    else:
        raise RuntimeError("line search failed")
    x = candidate
else:
    raise RuntimeError("iteration limit reached")
print(round(x, 6), round(f(x), 6))

输出为 0.567143 2.330366。导数容差在这里表明近似驻点；严格凸性进一步说明唯一驻点就是全局最小点。非凸问题中的小导数也可能对应鞍点或极大点。

可用 $f(x)=x^2$ 检验步长：$x_{k+1}=(1-2\alpha)x_k$。从非零点出发，收敛要求 $0<\alpha<1$；$\alpha=1$ 时振荡，大于 $1$ 时发散。反过来，$\alpha$ 极小时，即使 $|f'(x)|$ 很大，迭代变化也可能很小。若包含这一步的区间内满足 $|f'(u)-f'(v)|\le L|u-v|$，即梯度为 $L$-Lipschitz，则 $f(x-\alpha g)\le f(x)-\alpha(1-L\alpha/2)g^2$，所以 $0<\alpha<2/L$ 可在 $g\ne0$ 时保证下降。对数例子在整个 $(0,\infty)$ 上没有统一的有限 $L$；回溯法无需假定这样的全局常数。

我的阅读 · 打开过的笔记会记在当前浏览器里。