非线性规划中的修正牛顿法（Modified Newton’s Method）

字数 3220 2025-12-07 18:51:32

非线性规划中的修正牛顿法（Modified Newton’s Method）

非线性规划中的修正牛顿法是求解无约束或有约束优化问题的一种重要迭代算法，它针对经典牛顿法的缺陷进行了改进，使其在更广泛的条件下稳定收敛。下面我将分步讲解其背景、原理、修正策略及算法流程。

第一步：经典牛顿法及其局限性

牛顿法的基本思想：对于二阶连续可微的函数 \(f: \mathbb{R}^n \to \mathbb{R}\)，寻找其极小点。在迭代点 \(x^k\)，利用二次泰勒展开近似 \(f\)：

\[ f(x^k + d) \approx q(d) = f(x^k) + \nabla f(x^k)^T d + \frac{1}{2} d^T \nabla^2 f(x^k) d. \]

通过最小化这个二次模型 \(q(d)\) 来确定搜索方向 \(d^k\)，即求解方程：

\[ \nabla^2 f(x^k) d = -\nabla f(x^k). \]

这个方程的解 \(d^k\) 称为牛顿方向。迭代格式为：

\[ x^{k+1} = x^k + d^k. \]

经典牛顿法的优点：在初始点足够靠近极小点，且目标函数的海森矩阵（Hessian matrix）\(\nabla^2 f(x^*)\) 正定、条件数良好时，算法具有局部二次收敛速率，即收敛非常快。
经典牛顿法的主要问题：

海森矩阵非正定：当 \(\nabla^2 f(x^k)\) 非正定时，二次模型 \(q(d)\) 无有界极小值，牛顿方向 \(d^k\) 可能不是下降方向（即 \(\nabla f(x^k)^T d^k \geq 0\)），导致迭代发散。
需要求解线性方程组：每次迭代需计算并求解 \(\nabla^2 f(x^k) d = -\nabla f(x^k)\)，当维度 \(n\) 很大时，计算和存储海森矩阵的成本高昂。
3. 依赖初始点：只有初始点在解的小邻域内才能保证快速收敛，全局收敛性没有保证。

第二步：修正牛顿法的核心思路

修正牛顿法的核心目标是在保持牛顿法快速局部收敛性的同时，克服其全局收敛性问题。其主要修正策略围绕保证搜索方向是下降方向和引入线搜索来实现。

策略一：修正海森矩阵（Hessian Modification）
当 \(\nabla^2 f(x^k)\) 非正定时，直接对其添加一个修正矩阵 \(E^k\)，构造一个新的正定矩阵 \(B^k = \nabla^2 f(x^k) + E^k\)。然后用 \(B^k\) 替代 \(\nabla^2 f(x^k)\) 来求解搜索方向：

\[ B^k d = -\nabla f(x^k). \]

由于 \(B^k\) 正定，可以保证 \(d^k\) 是下降方向（因为 \(\nabla f(x^k)^T d^k = -\nabla f(x^k)^T (B^k)^{-1} \nabla f(x^k) < 0\)）。
* 常见的修正技术：

特征值修正：计算 \(\nabla^2 f(x^k)\) 的特征值，将负的特征值替换为一个小的正数 \(\delta > 0\)。
加上单位矩阵倍数：\(B^k = \nabla^2 f(x^k) + \mu I\)，其中 \(\mu > 0\) 足够大使 \(B^k\) 正定。这类似于岭回归或信赖域方法的思想，当 \(\mu\) 很大时，方向趋近于最速下降方向。
策略二：结合线搜索（Line Search）
即使有了下降方向 \(d^k\)，步长也不一定为1。引入线搜索，迭代格式变为：

\[ x^{k+1} = x^k + \alpha^k d^k, \]

其中步长 \(\alpha^k > 0\) 通过线搜索（如Armijo、Wolfe条件）确定，以保证每次迭代目标函数值充分下降（\(f(x^{k+1}) < f(x^k)\)）。这确保了算法的全局收敛性，即从任意初始点出发，至少能收敛到一个稳定点（梯度为零的点）。

策略三：使用海森矩阵的近似（拟牛顿法）
为了避免直接计算和存储海森矩阵，拟牛顿法（如BFGS、DFP、SR1）用另一个正定矩阵 \(B^k\) 来近似 \(\nabla^2 f(x^k)\)，并通过梯度信息在迭代中更新 \(B^k\)。这可以看作另一种“修正”，侧重于降低计算成本。拟牛顿法本身是修正牛顿法的一个重要分支。

第三步：算法流程与收敛性

一个典型的（基于海森矩阵修正的）修正牛顿法步骤如下：

初始化：给定初始点 \(x^0\)，设定收敛精度 \(\epsilon > 0\)，置 \(k = 0\)。
循环直至收敛：
a. 计算梯度：计算当前梯度 \(g^k = \nabla f(x^k)\)。
b. 检查收敛：如果 \(\| g^k \| \leq \epsilon\)，则停止，输出 \(x^k\) 为近似解。
c. 计算/修正海森矩阵：

计算海森矩阵 \(H^k = \nabla^2 f(x^k)\)。
检查 \(H^k\) 的正定性。如果 \(H^k\) 不正定，对其进行修正，得到正定矩阵 \(B^k\)（例如，通过Cholesky分解调整，或添加 \(\mu I\) 直至正定）。
d. 求解线性方程组：求解 \(B^k d^k = -g^k\) 得到搜索方向 \(d^k\)。
e. 线搜索：沿方向 \(d^k\) 执行线搜索，确定满足充分下降条件的步长 \(\alpha^k > 0\)。
f. 更新迭代点：\(x^{k+1} = x^k + \alpha^k d^k\)。
g. 更新迭代次数：\(k = k + 1\)。
收敛性分析：
全局收敛：由于每一步的搜索方向 \(d^k\) 都通过修正保证了是下降方向，并且结合了线搜索，在适当条件下（如 \(f\) 下有界、梯度Lipschitz连续），算法可以保证梯度序列 \(\{ \nabla f(x^k) \}\) 收敛到零，即收敛到一个稳定点。
局部收敛：如果迭代点最终进入解 \(x^*\) 的一个邻域，其中 \(\nabla^2 f(x^*)\) 正定，且修正量 \(E^k\) 趋近于零（或采用拟牛顿更新且满足一定的拟牛顿方程），那么算法可以恢复牛顿法的超线性收敛速率。如果修正策略得当，甚至可能保持二次收敛。

第四步：修正牛顿法的扩展与总结

扩展到约束问题：在约束优化（如等式约束）中，修正牛顿法思想可用于求解KKT系统的牛顿方程。当KKT矩阵（包含拉格朗日函数的Hessian和约束的雅可比矩阵）非正定或奇异时，也需要类似的正定性修正（如惯性指标控制、正则化）来保证迭代方向是下降方向并能求解。
与信赖域方法的关系：信赖域方法在每次迭代中求解一个带信赖域半径约束的二次模型子问题。当子问题的海森矩阵非正定时，其解通常位于信赖域边界上，这天然地提供了一种“修正”机制。因此，信赖域方法也被视为一种能自动处理不定海森矩阵的、更稳健的牛顿型方法。
总结：修正牛顿法通过海森矩阵修正确保搜索方向的下降性，结合线搜索保证全局收敛，并尽量保持牛顿法在解附近的快速收敛特性。它是经典牛顿法在鲁棒性和实用性上的重要增强，是现代非线性优化软件包（如MATLAB的fminunc，带有Hessian选项）中求解中小规模、光滑问题的核心算法之一。

非线性规划中的修正牛顿法（Modified Newton’s Method）非线性规划中的修正牛顿法是求解无约束或有约束优化问题的一种重要迭代算法，它针对经典牛顿法的缺陷进行了改进，使其在更广泛的条件下稳定收敛。下面我将分步讲解其背景、原理、修正策略及算法流程。第一步：经典牛顿法及其局限性牛顿法的基本思想：对于二阶连续可微的函数 \( f: \mathbb{R}^n \to \mathbb{R} \)，寻找其极小点。在迭代点 \( x^k \)，利用二次泰勒展开近似 \( f \)： \[ f(x^k + d) \approx q(d) = f(x^k) + \nabla f(x^k)^T d + \frac{1}{2} d^T \nabla^2 f(x^k) d. \] 通过最小化这个二次模型 \( q(d) \) 来确定搜索方向 \( d^k \)，即求解方程： \[ \nabla^2 f(x^k) d = -\nabla f(x^k). \] 这个方程的解 \( d^k \) 称为牛顿方向。迭代格式为： \[ x^{k+1} = x^k + d^k. \] 经典牛顿法的优点：在初始点足够靠近极小点，且目标函数的海森矩阵（Hessian matrix）\( \nabla^2 f(x^* ) \) 正定、条件数良好时，算法具有局部二次收敛速率，即收敛非常快。经典牛顿法的主要问题：海森矩阵非正定：当 \( \nabla^2 f(x^k) \) 非正定时，二次模型 \( q(d) \) 无有界极小值，牛顿方向 \( d^k \) 可能不是下降方向（即 \( \nabla f(x^k)^T d^k \geq 0 \)），导致迭代发散。需要求解线性方程组：每次迭代需计算并求解 \( \nabla^2 f(x^k) d = -\nabla f(x^k) \)，当维度 \( n \) 很大时，计算和存储海森矩阵的成本高昂。依赖初始点：只有初始点在解的小邻域内才能保证快速收敛，全局收敛性没有保证。第二步：修正牛顿法的核心思路修正牛顿法的核心目标是在保持牛顿法快速局部收敛性的同时，克服其全局收敛性问题。其主要修正策略围绕保证搜索方向是下降方向和引入线搜索来实现。策略一：修正海森矩阵（Hessian Modification）当 \( \nabla^2 f(x^k) \) 非正定时，直接对其添加一个修正矩阵 \( E^k \)，构造一个新的正定矩阵 \( B^k = \nabla^2 f(x^k) + E^k \)。然后用 \( B^k \) 替代 \( \nabla^2 f(x^k) \) 来求解搜索方向： \[ B^k d = -\nabla f(x^k). \] 由于 \( B^k \) 正定，可以保证 \( d^k \) 是下降方向（因为 \( \nabla f(x^k)^T d^k = -\nabla f(x^k)^T (B^k)^{-1} \nabla f(x^k) < 0 \)）。常见的修正技术：特征值修正：计算 \( \nabla^2 f(x^k) \) 的特征值，将负的特征值替换为一个小的正数 \( \delta > 0 \)。加上单位矩阵倍数：\( B^k = \nabla^2 f(x^k) + \mu I \)，其中 \( \mu > 0 \) 足够大使 \( B^k \) 正定。这类似于岭回归或信赖域方法的思想，当 \( \mu \) 很大时，方向趋近于最速下降方向。策略二：结合线搜索（Line Search）即使有了下降方向 \( d^k \)，步长也不一定为1。引入线搜索，迭代格式变为： \[ x^{k+1} = x^k + \alpha^k d^k, \] 其中步长 \( \alpha^k > 0 \) 通过线搜索（如Armijo、Wolfe条件）确定，以保证每次迭代目标函数值充分下降（\( f(x^{k+1}) < f(x^k) \)）。这确保了算法的全局收敛性，即从任意初始点出发，至少能收敛到一个稳定点（梯度为零的点）。策略三：使用海森矩阵的近似（拟牛顿法）为了避免直接计算和存储海森矩阵，拟牛顿法（如BFGS、DFP、SR1）用另一个正定矩阵 \( B^k \) 来近似 \( \nabla^2 f(x^k) \)，并通过梯度信息在迭代中更新 \( B^k \)。这可以看作另一种“修正”，侧重于降低计算成本。拟牛顿法本身是修正牛顿法的一个重要分支。第三步：算法流程与收敛性一个典型的（基于海森矩阵修正的）修正牛顿法步骤如下：初始化：给定初始点 \( x^0 \)，设定收敛精度 \( \epsilon > 0 \)，置 \( k = 0 \)。循环直至收敛： a. 计算梯度：计算当前梯度 \( g^k = \nabla f(x^k) \)。 b. 检查收敛：如果 \( \| g^k \| \leq \epsilon \)，则停止，输出 \( x^k \) 为近似解。 c. 计算/修正海森矩阵： * 计算海森矩阵 \( H^k = \nabla^2 f(x^k) \)。 * 检查 \( H^k \) 的正定性。如果 \( H^k \) 不正定，对其进行修正，得到正定矩阵 \( B^k \)（例如，通过Cholesky分解调整，或添加 \( \mu I \) 直至正定）。 d. 求解线性方程组：求解 \( B^k d^k = -g^k \) 得到搜索方向 \( d^k \)。 e. 线搜索：沿方向 \( d^k \) 执行线搜索，确定满足充分下降条件的步长 \( \alpha^k > 0 \)。 f. 更新迭代点：\( x^{k+1} = x^k + \alpha^k d^k \)。 g. 更新迭代次数：\( k = k + 1 \)。收敛性分析：全局收敛：由于每一步的搜索方向 \( d^k \) 都通过修正保证了是下降方向，并且结合了线搜索，在适当条件下（如 \( f \) 下有界、梯度Lipschitz连续），算法可以保证梯度序列 \( \{ \nabla f(x^k) \} \) 收敛到零，即收敛到一个稳定点。局部收敛：如果迭代点最终进入解 \( x^* \) 的一个邻域，其中 \( \nabla^2 f(x^* ) \) 正定，且修正量 \( E^k \) 趋近于零（或采用拟牛顿更新且满足一定的拟牛顿方程），那么算法可以恢复牛顿法的超线性收敛速率。如果修正策略得当，甚至可能保持二次收敛。第四步：修正牛顿法的扩展与总结扩展到约束问题：在约束优化（如等式约束）中，修正牛顿法思想可用于求解 KKT系统的牛顿方程。当KKT矩阵（包含拉格朗日函数的Hessian和约束的雅可比矩阵）非正定或奇异时，也需要类似的正定性修正（如惯性指标控制、正则化）来保证迭代方向是下降方向并能求解。与信赖域方法的关系：信赖域方法在每次迭代中求解一个带信赖域半径约束的二次模型子问题。当子问题的海森矩阵非正定时，其解通常位于信赖域边界上，这天然地提供了一种“修正”机制。因此，信赖域方法也被视为一种能自动处理不定海森矩阵的、更稳健的牛顿型方法。总结：修正牛顿法通过海森矩阵修正确保搜索方向的下降性，结合线搜索保证全局收敛，并尽量保持牛顿法在解附近的快速收敛特性。它是经典牛顿法在鲁棒性和实用性上的重要增强，是现代非线性优化软件包（如MATLAB的 fminunc ，带有Hessian选项）中求解中小规模、光滑问题的核心算法之一。