非线性规划中的牛顿法基础题
题目描述
考虑一个无约束非线性规划问题：
最小化函数 \(f(x) = x_1^4 + 2x_2^2 - x_1x_2 + 3x_1\)，其中 \(x = [x_1, x_2]^T\)。
使用牛顿法找到该函数的局部极小值点，初始点设为 \(x^{(0)} = [1, 1]^T\)，迭代两次（即计算 \(x^{(1)}\) 和 \(x^{(2)}\)），并分析结果。
解题过程
牛顿法通过迭代公式 \(x^{(k+1)} = x^{(k)} - [H_f(x^{(k)})]^{-1} \nabla f(x^{(k)})\) 寻找极小值，其中 \(\nabla f\) 是梯度，\(H_f\) 是Hessian矩阵（二阶导数矩阵）。以下是详细步骤：
- 计算梯度 \(\nabla f(x)\)
对 \(f(x)\) 求偏导：
\[ \frac{\partial f}{\partial x_1} = 4x_1^3 - x_2 + 3, \quad \frac{\partial f}{\partial x_2} = 4x_2 - x_1. \]
梯度向量为：
\[ \nabla f(x) = \begin{bmatrix} 4x_1^3 - x_2 + 3 \\ 4x_2 - x_1 \end{bmatrix}. \]
- 计算Hessian矩阵 \(H_f(x)\)
求二阶偏导：
\[ \frac{\partial^2 f}{\partial x_1^2} = 12x_1^2, \quad \frac{\partial^2 f}{\partial x_1 \partial x_2} = -1, \quad \frac{\partial^2 f}{\partial x_2^2} = 4. \]
Hessian矩阵为：
\[ H_f(x) = \begin{bmatrix} 12x_1^2 & -1 \\ -1 & 4 \end{bmatrix}. \]
- 第一次迭代（k=0）
- 初始点 \(x^{(0)} = [1, 1]^T\)。
- 梯度：
\[ \nabla f(x^{(0)}) = \begin{bmatrix} 4(1)^3 - 1 + 3 \\ 4(1) - 1 \end{bmatrix} = \begin{bmatrix} 6 \\ 3 \end{bmatrix}. \]
- Hessian矩阵：
\[ H_f(x^{(0)}) = \begin{bmatrix} 12(1)^2 & -1 \\ -1 & 4 \end{bmatrix} = \begin{bmatrix} 12 & -1 \\ -1 & 4 \end{bmatrix}. \]
- 求逆矩阵：
\[ H_f^{-1} = \frac{1}{(12)(4) - (-1)(-1)} \begin{bmatrix} 4 & 1 \\ 1 & 12 \end{bmatrix} = \frac{1}{47} \begin{bmatrix} 4 & 1 \\ 1 & 12 \end{bmatrix}. \]
- 更新点：
\[ x^{(1)} = \begin{bmatrix} 1 \\ 1 \end{bmatrix} - \frac{1}{47} \begin{bmatrix} 4 & 1 \\ 1 & 12 \end{bmatrix} \begin{bmatrix} 6 \\ 3 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \end{bmatrix} - \frac{1}{47} \begin{bmatrix} 27 \\ 42 \end{bmatrix} \approx \begin{bmatrix} 0.4255 \\ 0.1064 \end{bmatrix}. \]
- 第二次迭代（k=1）
- 当前点 \(x^{(1)} \approx [0.4255, 0.1064]^T\)。
- 梯度：
\[ \nabla f(x^{(1)}) \approx \begin{bmatrix} 4(0.4255)^3 - 0.1064 + 3 \\ 4(0.1064) - 0.4255 \end{bmatrix} \approx \begin{bmatrix} 3.008 \\ 0.0001 \end{bmatrix}. \]
- Hessian矩阵：
\[ H_f(x^{(1)}) \approx \begin{bmatrix} 12(0.4255)^2 & -1 \\ -1 & 4 \end{bmatrix} \approx \begin{bmatrix} 2.173 & -1 \\ -1 & 4 \end{bmatrix}. \]
- 求逆矩阵：
\[ H_f^{-1} \approx \frac{1}{(2.173)(4) - (-1)(-1)} \begin{bmatrix} 4 & 1 \\ 1 & 2.173 \end{bmatrix} \approx \frac{1}{7.692} \begin{bmatrix} 4 & 1 \\ 1 & 2.173 \end{bmatrix}. \]
- 更新点：
\[ x^{(2)} \approx \begin{bmatrix} 0.4255 \\ 0.1064 \end{bmatrix} - \frac{1}{7.692} \begin{bmatrix} 4 & 1 \\ 1 & 2.173 \end{bmatrix} \begin{bmatrix} 3.008 \\ 0.0001 \end{bmatrix} \approx \begin{bmatrix} 0.4255 \\ 0.1064 \end{bmatrix} - \begin{bmatrix} 1.564 \\ 0.391 \end{bmatrix} \approx \begin{bmatrix} -1.1385 \\ -0.2846 \end{bmatrix}. \]
- 结果分析
- 两次迭代后，点从 \([1,1]\) 移动到 \([-1.1385, -0.2846]\)。
- 梯度在 \(x^{(1)}\) 的第二个分量接近零，但第一次迭代后Hessian矩阵的条件数较大（约7.69），导致第二次迭代步长过大，可能发散。
- 牛顿法需Hessian矩阵正定才能保证收敛，此处初始点选择可能导致问题。实际应用中常引入步长因子或改用拟牛顿法。