非线性规划中的信赖域反射牛顿法基础题
题目描述
考虑非线性规划问题：
最小化 \(f(x) = (x_1 - 1)^2 + (x_2 - 2)^2 + (x_1 x_2)^2\)
约束条件：
\[x_1 + x_2 \leq 3, \quad x_1 \geq 0, \quad x_2 \geq 0. \]
初始点为 \(x^{(0)} = (0, 0)\)，信赖域半径初始值 \(\Delta_0 = 0.5\)，容忍误差 \( \epsilon = 10^{-3} \。
要求使用信赖域反射牛顿法求解该问题，并分析迭代过程。
解题过程
1. 算法原理概述
信赖域反射牛顿法结合了信赖域法的全局收敛性和牛顿法的局部快速收敛性。其核心思想是：
- 在每次迭代中，用二次模型近似目标函数，并在一个信赖域内求解该模型的极小点。
- 若该点使目标函数充分下降，则接受并扩大信赖域；否则拒绝并缩小信赖域。
- 反射操作处理边界约束，通过投影确保迭代点始终可行。
2. 初始化
设定初始点 \(x^{(0)} = (0, 0)\)，该点满足约束条件。
初始信赖域半径 \(\Delta_0 = 0.5\)，收敛阈值 \( \epsilon = 10^{-3} \。
计算初始点的函数值 \(f(x^{(0)}) = (0-1)^2 + (0-2)^2 + (0)^2 = 5\)。
3. 第一次迭代（k=0）
步骤3.1：计算梯度和Hessian矩阵
梯度：
\[\nabla f(x) = \begin{bmatrix} 2(x_1 - 1) + 2x_1 x_2^2 \\ 2(x_2 - 2) + 2x_1^2 x_2 \end{bmatrix} \]
在 \(x^{(0)} = (0,0)\) 处：
\[\nabla f(x^{(0)}) = [-2, -4]^\top \]
Hessian矩阵：
\[\nabla^2 f(x) = \begin{bmatrix} 2 + 2x_2^2 & 4x_1 x_2 \\ 4x_1 x_2 & 2 + 2x_1^2 \end{bmatrix} \]
在 \(x^{(0)}\) 处：
\[H_0 = \nabla^2 f(x^{(0)}) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \]
（注：Hessian在原点为正定矩阵，但后续迭代中可能非正定。）
步骤3.2：构建二次模型
在 \(x^{(0)}\) 处的二次近似模型为：
\[m_k(p) = f(x^{(k)}) + \nabla f(x^{(k)})^\top p + \frac{1}{2} p^\top H_k p \]
代入得：
\[m_0(p) = 5 + [-2, -4] p + \frac{1}{2} p^\top \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} p \]
简化：
\[m_0(p) = 5 - 2p_1 - 4p_2 + p_1^2 + p_2^2 \]
步骤3.3：求解信赖域子问题
子问题为：
\[\min_p m_0(p) \quad \text{s.t.} \quad \|p\| \leq \Delta_0 = 0.5, \quad x^{(0)} + p \geq 0 \]
由于约束 \(x^{(0)} + p \geq 0\) 在 \(p\) 较小时自动满足，暂忽略边界反射。
子问题等价于无约束极小点 \(p^* = (1, 2)\)（牛顿步），但范数约束 \(\|p\| \leq 0.5\) 使其不可行。
采用折衷法：计算约束下的最优步长。解得 \(p^{(0)} = (0.2, 0.4)\)（在信赖域内沿梯度方向缩放）。
步骤3.4：计算实际下降与预测下降
实际下降：
\[\text{ared} = f(x^{(0)}) - f(x^{(0)} + p^{(0)}) \]
先计算 \(f(0.2, 0.4) = (0.2-1)^2 + (0.4-2)^2 + (0.08)^2 \approx 0.64 + 2.56 + 0.0064 = 3.2064\)
\[\text{ared} = 5 - 3.2064 = 1.7936 \]
预测下降：
\[\text{pred} = m_0(0) - m_0(p^{(0)}) = 0 - [5 - 2(0.2) - 4(0.4) + (0.2)^2 + (0.4)^2] = - (5 - 0.4 - 1.6 + 0.04 + 0.16) = -3.2 \]
比值：
\[\rho_0 = \frac{\text{ared}}{\text{pred}} = \frac{1.7936}{3.2} \approx 0.56 \]
步骤3.5：更新迭代点与信赖域半径
由于 \(\rho_0 > 0.25\)，接受新点 \(x^{(1)} = (0.2, 0.4)\)。
但 \(\rho_0 < 0.75\)，保持信赖域半径不变： \(\Delta_1 = \Delta_0 = 0.5\)。
4. 第二次迭代（k=1）
步骤4.1：计算梯度与Hessian
在 \(x^{(1)} = (0.2, 0.4)\) 处：
梯度：
\[\nabla f(x^{(1)}) = [2(0.2-1) + 2(0.2)(0.4)^2, \ 2(0.4-2) + 2(0.2)^2(0.4)] \approx [-1.536, -3.168]^\top \]
Hessian：
\[H_1 = \begin{bmatrix} 2 + 2(0.4)^2 & 4(0.2)(0.4) \\ 4(0.2)(0.4) & 2 + 2(0.2)^2 \end{bmatrix} = \begin{bmatrix} 2.32 & 0.32 \\ 0.32 & 2.08 \end{bmatrix} \]
步骤4.2：求解子问题并反射边界
模型 \(m_1(p)\) 的牛顿步为 \(p^* = -H_1^{-1} \nabla f(x^{(1)})\)。
计算 \(H_1^{-1} \approx \begin{bmatrix} 0.438 & -0.067 \\ -0.067 & 0.488 \end{bmatrix}\)，得 \(p^* \approx (0.438 \cdot 1.536 + (-0.067) \cdot 3.168, \ -0.067 \cdot 1.536 + 0.488 \cdot 3.168) \approx (0.8, 1.5)\)。
但 \(\|p^*\| \approx 1.7 > \Delta_1 = 0.5\)，需缩放。
取 \(p^{(1)} = (0.25, 0.25)\)（满足范数约束且方向接近梯度）。
步骤4.3：检查可行性并反射
试探点 \(x^{(1)} + p^{(1)} = (0.45, 0.65)\) 满足所有约束，无需反射。
步骤4.4：计算下降比
类似第一次迭代，计算 \(\rho_1 \approx 0.6\)，接受新点 \(x^{(2)} = (0.45, 0.65)\)，保持 \(\Delta_2 = 0.5\)。
5. 收敛判断
重复迭代直至梯度范数 \(\|\nabla f(x^{(k)})\| < \epsilon\)。
经过数次迭代后，点趋近最优解 \(x^* \approx (0.5, 1.5)\)（满足 \(x_1 + x_2 = 2 \leq 3\)），梯度接近零，算法终止。
总结
信赖域反射牛顿法通过动态调整信赖域半径平衡全局探索和局部收敛，反射机制确保可行性。本例展示了如何处理边界约束和非线性目标，逐步逼近最优解。