梯度下降与牛顿下降

2025年11月17日 1k 字大概 5 分钟

📚牛顿下降法 (Newton’s Method / Newton-Raphson Method)
- 1. 核心公式
  - 1.1 求方程的根 (单变量)
  - 1.2 求函数的极小值 (多变量)
梯度下降法

📚牛顿下降法 (Newton’s Method / Newton-Raphson Method)

用于求方程的根（牛顿迭代法），也可以用于求函数的极小值（牛顿下降法）。

1. 核心公式

1.1 求方程的根 (单变量)

基本思想： 在当前点 $x_k$ 附近，用函数的切线去逼近函数本身。切线与 $x$ 轴的交点 $x_{k+1}$ 就是下一个迭代点。
几何意义： 逼近 $f(x)$ 在 $x_k$ 处的线性近似。

寻找 $f(x)=0$ 的根：

x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}

1.2 求函数的极小值 (多变量)

基本思想： 求解 $\nabla L(\mathbf{x}) = 0$ 的根（即寻找梯度为零的点，通常是极值点）。它通过在当前点使用函数的二次泰勒展开式来近似目标函数，并直接求出近似函数的最小值点作为下一个迭代点。
寻找函数 $L(\mathbf{x})$ 的极小值：

\mathbf{x}_{k+1} = \mathbf{x}_k - \mathbf{H}_k^{-1} \nabla L(\mathbf{x}_k)

其中：

$\nabla L(\mathbf{x}_k)$ ：目标函数 $L(\mathbf{x})$ 在 $\mathbf{x}_k$ 处的**梯度向量**（一阶导数）。
$\mathbf{H}_k$ ：目标函数 $L(\mathbf{x})$ 在 $\mathbf{x}_k$ 处的 **Hessian 矩阵**（二阶导数矩阵）。
$\mathbf{H}_k^{-1}$ ：Hessian 矩阵的逆。

加入步长（阻尼牛顿法）：

\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \mathbf{H}_k^{-1} \nabla L(\mathbf{x}_k)

其中 $\alpha_k$ 是步长（或学习率），通常通过线搜索确定。

简易来讲，求根是让目标函数为0，求极小值是让一阶导数为0

0 = f(x) \approx f(x_k) + f'(x_k) (x_{k+1} - x_k)

0 = f'(x) \approx f'(x_k) + f''(x_k) (x_{k+1} - x_k)


double func(double x) {
    // 任意函数，假设有一个吧
    return x*x + 3*x + exp(x);
}

double getdiff(double x, double (*func)(double)) {
    return (func(x + 1e-6) - func(x)) / 1e-6;
}



// 求根

double newton(double x0, double (*func)(double), double (*getdiff)(double, double (*func)(double))) {
    double func_val = func(x0);
    while (abs(func_val) > 1e-6) { // 检查 f(x) 是否接近 0
        double diff = getdiff(x0, func);
        // 检查分母是否接近 0，防止除零错误
        if (abs(diff) < 1e-12) {
            break; 
        }
        x0 -= func_val / diff; // 牛顿迭代公式：x_k+1 = x_k - f(x_k) / f'(x_k)
        func_val = func(x0);
    }
    return x0;
}

// 求极值
// L_double_prime(x, func) 返回 L''(x) 的值。
// 它通过对 L'(x) 再次求数值差分来实现。
double L_double_prime(double x, double (*func)(double)) {
    const double h = 1e-6; // 步长

    // L''(x) ≈ [ L'(x + h) - L'(x) ] / h
    
    // 计算 L'(x + h)
    // L_prime_value 的第一个参数是 x + h
    double L_prime_at_x_plus_h = L_prime_value(x + h, func);

    // 计算 L'(x)
    // L_prime_value 的第一个参数是 x
    double L_prime_at_x = L_prime_value(x, func);

    // 计算二阶差分
    return (L_prime_at_x_plus_h - L_prime_at_x) / h;
}

// L_prime_value 和 L_double_prime 必须在 newton 函数外部定义

double newton_optimizer(double x0, double (*func)(double)) {
    
    // 1. 计算 L'(x) 的值
    double L_prime_val = L_prime_value(x0, func);
    int max_iter = 100;

    // 2. 循环条件：L'(x) 接近 0 
    while (abs(L_prime_val) > 1e-6 && max_iter-- > 0) {
        
        // 3. 计算 L''(x) 的值
        double L_double_prime_val = L_double_prime(x0, func); 

        if (abs(L_double_prime_val) < 1e-12) {
            std::cerr << "Warning: Second derivative close to zero, stopping." << std::endl;
            break; 
        }

        // 4. 更新公式
        x0 -= L_prime_val / L_double_prime_val;
        
        // 5. 更新 L'(x) 的值，用于下一次循环判断
        L_prime_val = L_prime_value(x0, func); 
    }
    return x0;
}

梯度下降法

从当前位置开始，每一步都沿着负梯度方向（最快下降方向）走一小段距离

\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha \nabla L(\mathbf{x}_k)

局限性：

收敛速度：梯度下降是线性收敛的，在某些地形（如狭长的“山谷”）中会走“锯齿”路线，效率低下。

局部最优：在非凸函数中，它可能陷入不是全局最优的局部最小值。