非线性规划中的修正牛顿法
我们来详细讲解“非线性规划中的修正牛顿法”。我会把这个方法的基本思想、数学基础、核心修正技术、算法步骤及其优势循序渐进地讲清楚。
第一步：牛顿法回顾与问题的提出
修正牛顿法是牛顿法在求解无约束非线性规划问题时的一种重要改进。为了理解“修正”什么，我们先回顾标准牛顿法：
- 目标： 求解无约束优化问题：\(\min_{x \in \mathbb{R}^n} f(x)\)，其中 \(f\) 是二阶连续可微的函数。
- 基本思想： 在当前迭代点 \(x_k\) 处，用 \(f\) 的二阶泰勒展开式来近似 \(f\)。这个近似函数是一个二次函数：\(m_k(p) = f(x_k) + \nabla f(x_k)^T p + \frac{1}{2} p^T \nabla^2 f(x_k) p\)。这里的 \(p\) 是搜索方向。
- 牛顿步： 通过最小化这个二次模型 \(m_k(p)\) 来得到搜索方向。如果海森矩阵（Hessian matrix）\(\nabla^2 f(x_k)\) 是正定的，那么模型有唯一极小点，解方程 \(\nabla m_k(p) = 0\) 得到牛顿方向：\(p_k^N = -[\nabla^2 f(x_k)]^{-1} \nabla f(x_k)\)。
- 迭代格式： \(x_{k+1} = x_k + p_k^N\)。
- 牛顿法的问题： 牛顿法虽然具有局部二阶收敛速度，但它有三个主要缺陷：
- 海森矩阵可能不正定： 在非凸区域，\(\nabla^2 f(x_k)\) 可能含有负特征值，此时牛顿方向 \(p_k^N\) 可能不是下降方向（即 \(\nabla f(x_k)^T p_k^N \ge 0\)），会导致算法失败。
- 需要求解线性方程组： 每一步都需要计算海森矩阵的逆或求解一个 \(n \times n\) 的线性方程组 \([\nabla^2 f(x_k)] p_k = -\nabla f(x_k)\)，当 \(n\) 很大时计算成本高。
3. 缺乏全局收敛性保证： 标准的牛顿步长固定为1，当初始点远离最优解时，迭代可能不收敛。
“修正牛顿法”的核心目标，就是通过修正海森矩阵来解决第一个问题（不正定），并通常结合线搜索或信赖域框架来解决第三个问题（全局收敛）。
第二步：核心修正技术——如何获得一个“好”的海森矩阵
修正牛顿法的关键在于，当海森矩阵 \(G_k = \nabla^2 f(x_k)\) 不正定时，构造一个与之相近的正定矩阵 \(B_k\) 来替代它，从而保证搜索方向 \(p_k = -B_k^{-1} \nabla f(x_k)\) 是一个下降方向。主要修正技术有：
-
特征值修正法：
-
思想： 对 \(G_k\) 进行特征值分解 \(G_k = Q \Lambda Q^T\)，其中 \(\Lambda = \text{diag}(\lambda_1, \dots, \lambda_n)\) 是特征值对角阵。通过修改所有非正的特征值，构造一个新矩阵。一种常见的方法是令 \(\hat{\lambda}_i = \max(|\lambda_i|, \delta)\) 或 \(\hat{\lambda}_i = \max(\lambda_i, \delta)\)，其中 \(\delta > 0\) 是一个小的正数（如 \(10^{-6}\)）。修正后的矩阵为 \(B_k = Q \hat{\Lambda} Q^T\)，其中 \(\hat{\Lambda} = \text{diag}(\hat{\lambda}_1, \dots, \hat{\lambda}_n)\)。这保证了 \(B_k\) 是正定的。
-
优点： 能精确控制修正量，得到的矩阵 \(B_k\) 是距离 \(G_k\) 在谱范数下最近的正定矩阵。
- 缺点： 需要计算完整的特征值分解，对于大规模问题计算成本高昂。
-
对角摄动法（或称“Levenberg-Marquardt”型修正）：
-
思想： 在 \(G_k\) 上直接加上一个正定对角矩阵，通常是 \(B_k = G_k + \mu_k I\)，其中 \(I\) 是单位阵，\(\mu_k > 0\) 是一个修正参数。
-
如何选取 \(\mu_k\)： 从一个小值（如 \(\mu_k = 0\)）开始，不断增大 \(\mu_k\)，直到 \(B_k = G_k + \mu_k I\) 正定。这等价于让 \(B_k\) 的所有特征值 \(\lambda_i(G_k) + \mu_k\) 都大于零。在实践中，可以利用矩阵的Cholesky分解来动态调整 \(\mu_k\)：尝试对 \(G_k + \mu I\) 进行Cholesky分解（\(LL^T\)），如果分解失败（出现非正对角元），就增大 \(\mu\) 重试，直到成功。
-
解释： 当 \(\mu_k\) 很大时，方向 \(p_k = -(G_k + \mu_k I)^{-1} \nabla f(x_k) \approx -\frac{1}{\mu_k} \nabla f(x_k)\)，近似为最速下降方向。当 \(\mu_k = 0\) 且 \(G_k\) 正定时，就是标准牛顿方向。因此，这个修正方法在牛顿方向和最速下降方向之间做了一个平滑的插值，也称为“正则化”。
-
优点： 实现相对简单，与信赖域方法有紧密联系，并且修正参数 \(\mu_k\) 可以通过算法自动选择。
-
对称秩一修正与拟牛顿法思想：
-
虽然拟牛顿法（如BFGS、DFP）通常被视为独立的方法，但其思想也可以看作是对海森矩阵的一种“修正”。它们不计算精确的 \(G_k\)，而是用一个正定矩阵 \(B_k\) 来近似它，并通过迭代公式利用梯度信息更新 \(B_k\)，使其满足割线方程 \(B_{k+1}(x_{k+1} - x_k) = \nabla f(x_{k+1}) - \nabla f(x_k)\)。拟牛顿法天然保证了 \(B_k\) 的正定性（在适当的条件下）。
第三步：修正牛顿法的算法框架与步骤
一个结合了线搜索的修正牛顿法（采用对角摄动）的标准步骤如下：
- 初始化： 给定初始点 \(x_0\)，收敛精度 \(\epsilon > 0\)，令 \(k = 0\)。
- 循环直至收敛（例如， \(\|\nabla f(x_k)\| < \epsilon\)）：
a. 计算梯度： 计算当前点的梯度 \(g_k = \nabla f(x_k)\)。
b. 计算并修正海森矩阵： 计算海森矩阵 \(G_k = \nabla^2 f(x_k)\)。尝试对其进行Cholesky分解 \(G_k = L_k L_k^T\)。
- 如果分解成功，则设 \(B_k = G_k\)，牛顿方向 \(p_k^N = -B_k^{-1} g_k\) 通过回代求解 \(L_k L_k^T p = -g_k\) 得到。
- 如果分解失败，则选择一个初始修正量 \(\mu_k > 0\)。循环：令 \(B_k = G_k + \mu_k I\)，尝试对其做Cholesky分解。若失败，则增大 \(\mu_k\)（例如乘以一个固定因子 \(\beta > 1\)），重复尝试，直到成功分解。然后求解 \((G_k + \mu_k I) p_k = -g_k\) 得到修正牛顿方向 \(p_k\)。
c. 确定搜索方向： 上一步得到的 \(p_k\) 即为本次迭代的搜索方向。由于 \(B_k\) 正定，保证了 \(p_k\) 是下降方向（因为 \(g_k^T p_k = -g_k^T B_k^{-1} g_k < 0\)）。
d. 线搜索： 沿着方向 \(p_k\) 执行不精确线搜索（如Armijo、Wolfe条件），确定步长 \(\alpha_k > 0\)，使得目标函数有充分的下降：\(f(x_k + \alpha_k p_k) \le f(x_k) + c_1 \alpha_k g_k^T p_k\)。
e. 更新迭代点： \(x_{k+1} = x_k + \alpha_k p_k\)。
f. 令 \(k = k+1\)。
第四步：修正牛顿法的性质与小结
- 收敛性： 在标准的线搜索框架下（如Wolfe条件），修正牛顿法具有全局收敛性，即从任意初始点出发，算法产生的迭代点序列至少有一个聚点是稳定点（梯度为零的点）。在最优解 \(x^*\) 附近，如果修正参数 \(\mu_k \to 0\) 且海森矩阵 \(\nabla^2 f(x^*)\) 正定，那么算法最终会采用标准的牛顿步（\(\alpha_k = 1\)），从而恢复局部二阶收敛速度。
- 与信赖域方法的关系： 修正牛顿法与信赖域方法在数学上是等价的。求解信赖域子问题 \(\min_p m_k(p) \text{ s.t. } \|p\| \le \Delta_k\) 的全局解，等价于求解 \((\nabla^2 f(x_k) + \lambda I) p = -\nabla f(x_k)\) 且 \((\nabla^2 f(x_k) + \lambda I)\) 半正定，其中 \(\lambda \ge 0\) 是拉格朗日乘子。这里的 \(\lambda I\) 就扮演了修正项的角色。
- 优势总结：
- 克服了牛顿法的主要缺点： 通过修正保证了搜索方向是下降方向，使算法稳定可靠。
- 继承了牛顿法的优点： 在最优解附近，修正量趋于零，能快速达到局部二阶收敛速度。
- 灵活性： 可以与不同的修正技术（特征值修正、对角摄动）和全局化策略（线搜索、信赖域）结合。
总之，修正牛顿法是牛顿法的一个鲁棒性增强版本。它通过在海森矩阵上增加一个适当的正定修正项（通常是单位阵的倍数），确保每次迭代的搜索方向是下降方向，从而能在整个求解过程中稳定工作，并在接近解时展现出牛顿法快速的收敛特性。它是求解中大规模无约束优化问题的一个非常核心和有效的算法。