非线性规划中的自适应信赖域反射牛顿法基础题
题目描述
考虑非线性规划问题：
最小化 \(f(x) = (x_1 - 1)^4 + (x_2 - 2)^2\)
满足约束 \(h(x) = x_1 + x_2 - 3 = 0\)。
要求使用自适应信赖域反射牛顿法，从初始点 \(x^{(0)} = (0, 3)\) 开始，迭代至多 3 步，并分析每次迭代的收敛行为。
解题过程
1. 方法原理简述
自适应信赖域反射牛顿法结合了信赖域法的全局收敛性和牛顿法的局部超线性收敛。其特点包括：
- 利用反射技术处理约束边界（如线性等式约束的可行域）。
- 自适应调整信赖域半径 \(\Delta_k\)，根据实际下降量与预测下降量的比值 \(\rho_k\) 动态更新。
- 在每次迭代中求解信赖域子问题，得到试探步 \(p_k\)，并通过反射操作确保迭代点保持在可行域内。
2. 初始设置
初始点 \(x^{(0)} = (0, 3)\)，满足约束 \(h(x^{(0)}) = 0 + 3 - 3 = 0\)。
初始信赖域半径 \(\Delta_0 = 1\)，容忍误差 \(\epsilon = 10^{-6}\)。
目标函数梯度：
\[\nabla f(x) = \begin{bmatrix} 4(x_1 - 1)^3 \\ 2(x_2 - 2) \end{bmatrix} \]
Hessian 矩阵：
\[\nabla^2 f(x) = \begin{bmatrix} 12(x_1 - 1)^2 & 0 \\ 0 & 2 \end{bmatrix} \]
约束梯度：
\[\nabla h(x) = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \]
3. 第一次迭代（k=0）
步骤 1：计算当前点的梯度和 Hessian
\[\nabla f(x^{(0)}) = \begin{bmatrix} 4(0-1)^3 \\ 2(3-2) \end{bmatrix} = \begin{bmatrix} -4 \\ 2 \end{bmatrix}, \quad \nabla^2 f(x^{(0)}) = \begin{bmatrix} 12(0-1)^2 & 0 \\ 0 & 2 \end{bmatrix} = \begin{bmatrix} 12 & 0 \\ 0 & 2 \end{bmatrix} \]
步骤 2：构造拉格朗日函数及 KKT 系统
拉格朗日函数 \(L(x, \lambda) = f(x) + \lambda h(x)\)。
当前 KKT 系统为：
\[\begin{bmatrix} \nabla^2 f(x^{(0)}) & \nabla h(x^{(0)}) \\ \nabla h(x^{(0)})^\top & 0 \end{bmatrix} \begin{bmatrix} p \\ \lambda \end{bmatrix} = -\begin{bmatrix} \nabla f(x^{(0)}) \\ h(x^{(0)}) \end{bmatrix} \]
代入数值：
\[\begin{bmatrix} 12 & 0 & 1 \\ 0 & 2 & 1 \\ 1 & 1 & 0 \end{bmatrix} \begin{bmatrix} p_1 \\ p_2 \\ \lambda \end{bmatrix} = -\begin{bmatrix} -4 \\ 2 \\ 0 \end{bmatrix} = \begin{bmatrix} 4 \\ -2 \\ 0 \end{bmatrix} \]
步骤 3：求解子问题得试探步 \(p^{(0)}\)
解线性系统：
- 前两行： \(12p_1 + \lambda = 4\), \(2p_2 + \lambda = -2\)
- 第三行： \(p_1 + p_2 = 0\)
解得 \(p_1 = -p_2\), 代入得 \(\lambda = 4 - 12p_1\), \(2(-p_1) + (4 - 12p_1) = -2\)
简化： \(-2p_1 + 4 - 12p_1 = -2\) → \(-14p_1 = -6\) → \(p_1 = \frac{3}{7}\), \(p_2 = -\frac{3}{7}\)
试探步 \(p^{(0)} = \left( \frac{3}{7}, -\frac{3}{7} \right)\)，范数 \(\|p^{(0)}\| \approx 0.606 < \Delta_0 = 1\)，在信赖域内。
步骤 4：反射操作（因约束线性，直接投影）
新点 \(x^{(1)} = x^{(0)} + p^{(0)} = \left( \frac{3}{7}, \frac{18}{7} \right)\)。
检查可行性： \(h(x^{(1)}) = \frac{3}{7} + \frac{18}{7} - 3 = 0\)，满足约束。
步骤 5：计算实际下降比 \(\rho_0\)
实际下降： \(\text{ared} = f(x^{(0)}) - f(x^{(1)})\)
\(f(x^{(0)}) = (0-1)^4 + (3-2)^2 = 1 + 1 = 2\)
\(f(x^{(1)}) = \left( \frac{3}{7}-1 \right)^4 + \left( \frac{18}{7}-2 \right)^2 = \left( -\frac{4}{7} \right)^4 + \left( \frac{4}{7} \right)^2 = \frac{256}{2401} + \frac{16}{49} \approx 0.106 + 0.327 = 0.433\)
\(\text{ared} = 2 - 0.433 = 1.567\)
预测下降：二次模型 \(m(p) = f(x^{(0)}) + \nabla f(x^{(0)})^\top p + \frac{1}{2} p^\top \nabla^2 f(x^{(0)}) p\)
\(\nabla f(x^{(0)})^\top p = (-4, 2) \cdot \left( \frac{3}{7}, -\frac{3}{7} \right) = -\frac{12}{7} - \frac{6}{7} = -\frac{18}{7} \approx -2.571\)
\(p^\top \nabla^2 f(x^{(0)}) p = \left( \frac{3}{7}, -\frac{3}{7} \right) \begin{bmatrix} 12 & 0 \\ 0 & 2 \end{bmatrix} \begin{bmatrix} \frac{3}{7} \\ -\frac{3}{7} \end{bmatrix} = \frac{9}{49} \cdot 12 + \frac{9}{49} \cdot 2 = \frac{108}{49} + \frac{18}{49} = \frac{126}{49} \approx 2.571\)
\(\text{pred} = -\left( -\frac{18}{7} \right) + \frac{1}{2} \cdot 2.571 \approx 2.571 + 1.286 = 3.857\)
\(\rho_0 = \frac{1.567}{3.857} \approx 0.406\)
步骤 6：更新信赖域半径
由于 \(\rho_0 < 0.5\)，缩小信赖域： \(\Delta_1 = 0.5 \Delta_0 = 0.5\)。
4. 第二次迭代（k=1）
当前点 \(x^{(1)} = \left( \frac{3}{7}, \frac{18}{7} \right) \approx (0.429, 2.571)\)。
步骤 1：计算梯度和 Hessian
\[\nabla f(x^{(1)}) = \begin{bmatrix} 4(0.429-1)^3 \\ 2(2.571-2) \end{bmatrix} \approx \begin{bmatrix} 4(-0.571)^3 \\ 2(0.571) \end{bmatrix} = \begin{bmatrix} -0.744 \\ 1.142 \end{bmatrix} \]
\[\nabla^2 f(x^{(1)}) = \begin{bmatrix} 12(0.429-1)^2 & 0 \\ 0 & 2 \end{bmatrix} \approx \begin{bmatrix} 12(0.326) & 0 \\ 0 & 2 \end{bmatrix} = \begin{bmatrix} 3.912 & 0 \\ 0 & 2 \end{bmatrix} \]
步骤 2：求解 KKT 系统
\[\begin{bmatrix} 3.912 & 0 & 1 \\ 0 & 2 & 1 \\ 1 & 1 & 0 \end{bmatrix} \begin{bmatrix} p_1 \\ p_2 \\ \lambda \end{bmatrix} = -\begin{bmatrix} -0.744 \\ 1.142 \\ 0 \end{bmatrix} = \begin{bmatrix} 0.744 \\ -1.142 \\ 0 \end{bmatrix} \]
解方程得：
\(p_1 \approx 0.211\), \(p_2 \approx -0.211\)，范数 \(\|p^{(1)}\| \approx 0.298 < \Delta_1 = 0.5\)，接受该步。
步骤 3：更新迭代点
\(x^{(2)} = x^{(1)} + p^{(1)} \approx (0.640, 2.360)\)，约束满足 \(h(x^{(2)}) = 0\)。
步骤 4：计算 \(\rho_1\)
\(f(x^{(1)}) \approx 0.433\), \(f(x^{(2)}) \approx (0.640-1)^4 + (2.360-2)^2 = (-0.360)^4 + (0.360)^2 \approx 0.017 + 0.130 = 0.147\)
\(\text{ared} = 0.433 - 0.147 = 0.286\)
预测下降：类似计算得 \(\text{pred} \approx 0.350\)，\(\rho_1 \approx 0.817 > 0.75\)，扩大信赖域： \(\Delta_2 = 2 \Delta_1 = 1\)。
5. 第三次迭代（k=2）
当前点 \(x^{(2)} \approx (0.640, 2.360)\)。
步骤 1：计算梯度和 Hessian
\[\nabla f(x^{(2)}) \approx \begin{bmatrix} 4(-0.360)^3 \\ 2(0.360) \end{bmatrix} = \begin{bmatrix} -0.187 \\ 0.720 \end{bmatrix}, \quad \nabla^2 f(x^{(2)}) \approx \begin{bmatrix} 12(0.130) & 0 \\ 0 & 2 \end{bmatrix} = \begin{bmatrix} 1.560 & 0 \\ 0 & 2 \end{bmatrix} \]
步骤 2：求解 KKT 系统
解得 \(p^{(2)} \approx (0.102, -0.102)\)，范数约 0.144 < \(\Delta_2 = 1\)。
新点 \(x^{(3)} \approx (0.742, 2.258)\)，\(f(x^{(3)}) \approx (0.742-1)^4 + (2.258-2)^2 = 0.004 + 0.067 = 0.071\)。
步骤 3：收敛分析
梯度范数 \(\|\nabla f(x^{(3)}) + \lambda \nabla h(x^{(3)})\|\) 已显著减小（具体计算略），接近最优解 \(x^* = (1, 2)\)。
6. 结论
自适应信赖域反射牛顿法通过动态调整 \(\Delta_k\) 和反射操作，在 3 步内稳定逼近约束最优解，体现了其处理等式约束问题的有效性。