非线性规划中的修正牛顿法基础题
题目描述
考虑非线性规划问题：
最小化 \(f(x) = x_1^4 + 2x_2^4 + x_1^2 x_2^2 - 5x_1\)
初始点 \(x^{(0)} = [1, 1]^T\)，使用修正牛顿法求解该问题。要求说明修正牛顿法与标准牛顿法的区别，并详细展示迭代过程。
解题过程
1. 修正牛顿法的核心思想
标准牛顿法直接使用目标函数的Hessian矩阵（二阶导数矩阵）的逆来更新迭代点：
\[x^{(k+1)} = x^{(k)} - [\nabla^2 f(x^{(k)})]^{-1} \nabla f(x^{(k)}) \]
但若Hessian矩阵非正定，搜索方向可能不是下降方向，导致算法失效。修正牛顿法通过强制Hessian矩阵正定来解决此问题，常用方法是：
- 对Hessian矩阵 \(H_k\) 进行修正 \(H_k + \mu I\)（\(\mu > 0\)），使 \(H_k + \mu I\) 正定。
- 修正后的迭代公式：
\[x^{(k+1)} = x^{(k)} - [H_k + \mu I]^{-1} \nabla f(x^{(k)}) \]
2. 计算梯度与Hessian矩阵
给定 \(f(x) = x_1^4 + 2x_2^4 + x_1^2 x_2^2 - 5x_1\)：
- 梯度：
\[\nabla f(x) = \begin{bmatrix} 4x_1^3 + 2x_1 x_2^2 - 5 \\ 8x_2^3 + 2x_1^2 x_2 \end{bmatrix} \]
- Hessian矩阵：
\[\nabla^2 f(x) = \begin{bmatrix} 12x_1^2 + 2x_2^2 & 4x_1 x_2 \\ 4x_1 x_2 & 24x_2^2 + 2x_1^2 \end{bmatrix} \]
3. 初始点检查与修正
初始点 \(x^{(0)} = [1, 1]^T\)：
- 梯度：
\[\nabla f(x^{(0)}) = [4 \cdot 1^3 + 2 \cdot 1 \cdot 1^2 - 5,\ 8 \cdot 1^3 + 2 \cdot 1^2 \cdot 1]^T = [1,\ 10]^T \]
- Hessian矩阵：
\[H_0 = \begin{bmatrix} 12 \cdot 1^2 + 2 \cdot 1^2 & 4 \cdot 1 \cdot 1 \\ 4 \cdot 1 \cdot 1 & 24 \cdot 1^2 + 2 \cdot 1^2 \end{bmatrix} = \begin{bmatrix} 14 & 4 \\ 4 & 26 \end{bmatrix} \]
检查正定性：Hessian矩阵的特征值需全为正。
特征方程：
\[\det(H_0 - \lambda I) = (14-\lambda)(26-\lambda) - 16 = \lambda^2 - 40\lambda + 348 = 0 \]
解得特征值 \(\lambda_1 \approx 12.34, \lambda_2 \approx 28.66\)（均正），故 \(H_0\) 正定，无需修正。但为演示方法，我们仍展示修正步骤。
4. 修正牛顿法迭代步骤（以 \(\mu = 0.1\) 为例）
若Hessian非正定，需添加修正项 \(\mu I\)。此处假设需修正：
\[\tilde{H}_0 = H_0 + 0.1I = \begin{bmatrix} 14.1 & 4 \\ 4 & 26.1 \end{bmatrix} \]
- 求逆：
\[\tilde{H}_0^{-1} = \frac{1}{14.1 \cdot 26.1 - 4 \cdot 4} \begin{bmatrix} 26.1 & -4 \\ -4 & 14.1 \end{bmatrix} \approx \frac{1}{360.21} \begin{bmatrix} 26.1 & -4 \\ -4 & 14.1 \end{bmatrix} \]
- 计算搜索方向 \(d^{(0)} = -\tilde{H}_0^{-1} \nabla f(x^{(0)})\)：
\[d^{(0)} \approx -\frac{1}{360.21} \begin{bmatrix} 26.1 \cdot 1 + (-4) \cdot 10 \\ -4 \cdot 1 + 14.1 \cdot 10 \end{bmatrix} = -\frac{1}{360.21} \begin{bmatrix} -13.9 \\ 137 \end{bmatrix} \approx \begin{bmatrix} 0.0386 \\ -0.380 \end{bmatrix} \]
- 更新迭代点（步长 \(\alpha = 1\)）：
\[x^{(1)} = x^{(0)} + d^{(0)} \approx [1.0386,\ 0.620]^T \]
5. 第二次迭代
- 梯度 \(\nabla f(x^{(1)})\)：
\[x_1 = 1.0386,\ x_2 = 0.620 \\ \nabla f \approx [4(1.0386)^3 + 2(1.0386)(0.620)^2 - 5,\ 8(0.620)^3 + 2(1.0386)^2(0.620)]^T \approx [0.203,\ 3.823]^T \]
- Hessian矩阵：
\[H_1 \approx \begin{bmatrix} 12(1.0386)^2 + 2(0.620)^2 & 4(1.0386)(0.620) \\ 4(1.0386)(0.620) & 24(0.620)^2 + 2(1.0386)^2 \end{bmatrix} \approx \begin{bmatrix} 13.50 & 2.57 \\ 2.57 & 9.87 \end{bmatrix} \]
- 检查正定性：特征值 \(\lambda_1 \approx 8.24, \lambda_2 \approx 15.13\)（正定），无需修正。
- 直接牛顿方向：
\[d^{(1)} = -H_1^{-1} \nabla f(x^{(1)}) \approx - \begin{bmatrix} 0.077 & -0.020 \\ -0.020 & 0.105 \end{bmatrix} \begin{bmatrix} 0.203 \\ 3.823 \end{bmatrix} \approx \begin{bmatrix} 0.027 \\ -0.394 \end{bmatrix} \]
- 更新点：
\[x^{(2)} \approx [1.0656,\ 0.226]^T \]
6. 收敛判断
重复迭代直到梯度范数 \(\|\nabla f(x^{(k)})\| < \epsilon\)（例如 \(\epsilon = 10^{-3}\)）。
- 修正牛顿法保证每次搜索方向为下降方向，且收敛到局部极小点。
- 本例中，经过数次迭代后梯度趋近于零，最优解约在 \(x^* \approx [1.08, 0]^T\) 附近。
关键区别总结
- 标准牛顿法：直接使用Hessian矩阵，若非正定可能失败。
- 修正牛顿法：通过 \(H_k + \mu I\) 强制正定，鲁棒性更强，但需选择参数 \(\mu\)。