非线性规划中的插值模型优化方法基础题
题目描述
考虑非线性规划问题：
\[\min f(x) = (x_1 - 2)^4 + (x_1 - 2x_2)^2, \quad x \in \mathbb{R}^2. \]
假设当前迭代点为 \(x^{(k)} = (0, 0)\)，目标函数 \(f(x)\) 在 \(x^{(k)}\) 处计算复杂，但可通过局部插值模型近似。试基于二次插值模型（如使用函数值和梯度信息构建），推导下一步迭代点 \(x^{(k+1)}\)，并分析模型与真实函数的误差。
解题过程
1. 构建插值模型
在当前点 \(x^{(k)} = (0, 0)\)，计算函数值 \(f(x^{(k)})\) 和梯度 \(\nabla f(x^{(k)})\)：
\[f(0,0) = (0-2)^4 + (0 - 0)^2 = 16, \]
\[\nabla f(x) = \begin{bmatrix} 4(x_1 - 2)^3 + 2(x_1 - 2x_2) \\ -4(x_1 - 2x_2) \end{bmatrix}, \]
\[\nabla f(0,0) = \begin{bmatrix} 4(-2)^3 + 2(0) \\ -4(0) \end{bmatrix} = \begin{bmatrix} -32 \\ 0 \end{bmatrix}. \]
构建二次插值模型 \(m_k(p)\)，其中 \(p = x - x^{(k)}\)：
\[m_k(p) = f(x^{(k)}) + \nabla f(x^{(k)})^T p + \frac{1}{2} p^T B_k p. \]
这里 \(B_k\) 是Hessian的近似矩阵。由于无额外点信息，假设 \(B_k\) 初始为单位矩阵 \(I\)，则：
\[m_k(p) = 16 + [-32, 0] \begin{bmatrix} p_1 \\ p_2 \end{bmatrix} + \frac{1}{2} (p_1^2 + p_2^2) = 16 - 32p_1 + \frac{1}{2}(p_1^2 + p_2^2). \]
2. 求解模型的最小值
对 \(m_k(p)\) 求梯度并令为零：
\[\frac{\partial m_k}{\partial p_1} = -32 + p_1 = 0 \implies p_1 = 32, \]
\[\frac{\partial m_k}{\partial p_2} = p_2 = 0 \implies p_2 = 0. \]
因此，下一步迭代点为：
\[x^{(k+1)} = x^{(k)} + p = (0, 0) + (32, 0) = (32, 0). \]
3. 分析模型与真实函数的误差
真实函数在 \(x^{(k+1)} = (32, 0)\) 处的值为：
\[f(32, 0) = (32-2)^4 + (32 - 0)^2 = 30^4 + 32^2 = 810000 + 1024 = 811024. \]
插值模型预测值为：
\[m_k(32, 0) = 16 - 32 \times 32 + \frac{1}{2}(32^2 + 0) = 16 - 1024 + 512 = -496. \]
误差极大（\(|811024 - (-496)| \approx 8.11 \times 10^5\)），原因是单位矩阵 \(B_k\) 未能捕捉真实Hessian的曲率。
4. 改进插值模型
通过计算真实Hessian更新 \(B_k\)：
\[\nabla^2 f(x) = \begin{bmatrix} 12(x_1 - 2)^2 + 2 & -4 \\ -4 & 8 \end{bmatrix}, \]
在 \(x^{(k)} = (0,0)\) 处：
\[\nabla^2 f(0,0) = \begin{bmatrix} 12(4) + 2 & -4 \\ -4 & 8 \end{bmatrix} = \begin{bmatrix} 50 & -4 \\ -4 & 8 \end{bmatrix}. \]
用此Hessian更新插值模型：
\[m_k(p) = 16 - 32p_1 + \frac{1}{2} p^T \begin{bmatrix} 50 & -4 \\ -4 & 8 \end{bmatrix} p. \]
求解 \(\nabla_p m_k(p) = 0\)：
\[-32 + 50p_1 - 4p_2 = 0, \quad 0 - 4p_1 + 8p_2 = 0. \]
解得 \(p_2 = 0.5p_1\)，代入第一式：
\[-32 + 50p_1 - 2p_1 = 0 \implies 48p_1 = 32 \implies p_1 = \frac{2}{3}, \quad p_2 = \frac{1}{3}. \]
新迭代点 \(x^{(k+1)} = \left( \frac{2}{3}, \frac{1}{3} \right)\)，真实函数值 \(f \approx 14.6\)，模型预测值 \(m_k \approx 0.89\)，误差显著减小。
5. 结论
插值模型的精度依赖二阶导近似。通过精确Hessian可提升模型可靠性，避免无效迭代。实际中常用拟牛顿法（如BFGS）更新 \(B_k\)，以平衡计算成本与收敛速度。