非线性规划中的序列二次规划-代理模型-信赖域混合算法基础题
题目描述
考虑以下非线性规划问题：
最小化 \(f(x) = (x_1 - 2)^4 + (x_1 - 2x_2)^2\)
满足约束：
\(g_1(x) = x_1^2 - x_2 \leq 0\)
\(g_2(x) = x_1^2 + x_2^2 - 1 \leq 0\)
初始点 \(x^{(0)} = (0.5, 0.5)\)，信赖域半径初始值 \(\Delta_0 = 0.5\)。
本题要求使用序列二次规划-代理模型-信赖域混合算法求解。该算法的核心思想是：在每次迭代中，基于当前点构造原问题的近似二次模型（代理模型）作为子问题，在信赖域约束下求解该子问题，根据实际下降量与预测下降量的比率来调整信赖域半径和迭代点。
解题过程
步骤1：算法框架理解
序列二次规划-代理模型-信赖域混合算法结合了SQP（通过二次模型近似目标函数和线性化约束）、代理模型（简化约束处理）和信赖域（控制步长可靠性）三大组件。基本迭代格式为：
- 在当前点 \(x^{(k)}\) 构造近似二次规划子问题
- 在信赖域 \(\|d\| \leq \Delta_k\) 内求解子问题得试探步 \(d^{(k)}\)
- 计算实际下降量 \(\text{ared}\) 与预测下降量 \(\text{pred}\)
- 根据比率 \(\rho_k = \text{ared} / \text{pred}\) 决定是否接受试探步并更新信赖域半径
步骤2：第一次迭代（k=0）
初始点 \(x^{(0)} = (0.5, 0.5)\)，初始信赖域半径 \(\Delta_0 = 0.5\)。
-
计算梯度和Hessian：
目标函数梯度 \(\nabla f(x) = [4(x_1-2)^3 + 2(x_1-2x_2), -4(x_1-2x_2)]\)，在 \(x^{(0)}\) 处：
\(\nabla f(x^{(0)}) = [4(0.5-2)^3 + 2(0.5-1), -4(0.5-1)] = [4(-1.5)^3 + 2(-0.5), -4(-0.5)] = [-13.5 -1, 2] = [-14.5, 2]\)
为简化计算，采用单位矩阵作为Hessian近似（最速下降方向）：\(B_0 = I\) -
约束线性化：
\(g_1(x) \approx g_1(x^{(0)}) + \nabla g_1(x^{(0)})^T d = (0.25-0.5) + [2x_1, -1]^T d = -0.25 + [1, -1]^T d\)
\(g_2(x) \approx g_2(x^{(0)}) + \nabla g_2(x^{(0)})^T d = (0.25+0.25-1) + [2x_1, 2x_2]^T d = -0.5 + [1, 1]^T d\) -
构造子问题：
最小化 \(m_k(d) = f(x^{(0)}) + \nabla f(x^{(0)})^T d + \frac{1}{2} d^T B_0 d\)
代入数值：\(f(x^{(0)}) = (0.5-2)^4 + (0.5-1)^2 = (-1.5)^4 + (-0.5)^2 = 5.0625 + 0.25 = 5.3125\)
\(m_k(d) = 5.3125 + [-14.5, 2]^T d + \frac{1}{2} d^T I d\)
约束：\(-0.25 + d_1 - d_2 \leq 0\)，\(-0.5 + d_1 + d_2 \leq 0\)，\(\|d\| \leq 0.5\) -
求解子问题：
由于信赖域较小，约束可能不起作用。求解无约束最速下降方向 \(d = -\nabla f(x^{(0)}) = [14.5, -2]\)，范数为 \(\sqrt{14.5^2 + (-2)^2} \approx 14.64 > 0.5\)，需缩放至信赖域内：
\(d^{(0)} = -0.5 \times \frac{\nabla f(x^{(0)})}{\|\nabla f(x^{(0)})\|} = -0.5 \times [-14.5, 2]/14.64 \approx [0.495, -0.068]\) -
计算实际比率：
新点 \(x^{(1)} = x^{(0)} + d^{(0)} \approx (0.995, 0.432)\)
实际下降 \(\text{ared} = f(x^{(0)}) - f(x^{(1)})\)
\(f(x^{(1)}) = (0.995-2)^4 + (0.995-2\times0.432)^2 \approx (-1.005)^4 + (0.131)^2 \approx 1.020 + 0.017 = 1.037\)
\(\text{ared} = 5.3125 - 1.037 = 4.2755\)
预测下降 \(\text{pred} = -(\nabla f(x^{(0)})^T d^{(0)} + \frac{1}{2} (d^{(0)})^T d^{(0)})\)
\(\nabla f(x^{(0)})^T d^{(0)} \approx [-14.5, 2]^T [0.495, -0.068] = -7.1775 - 0.136 = -7.3135\)
\(\text{pred} = -(-7.3135) + 0.5 \times (0.5^2) = 7.3135 + 0.125 = 7.4385\)（注：标准预测下降应为 \(-[\nabla f^T d + \frac{1}{2} d^T B d]\)，这里B=I）
\(\rho_0 = 4.2755 / 7.4385 \approx 0.575\) -
更新信赖域：
比率 \(\rho_0 \approx 0.575\) 属于中等接受范围（通常 \(\rho > 0.25\) 可接受），接受 \(x^{(1)}\)。由于 \(\rho < 0.75\)，信赖域半径保持 \(\Delta_1 = \Delta_0 = 0.5\)
步骤3：第二次迭代（k=1）
当前点 \(x^{(1)} \approx (0.995, 0.432)\)
-
计算梯度：
\(\nabla f(x^{(1)}) = [4(0.995-2)^3 + 2(0.995-0.864), -4(0.995-0.864)] \approx [4(-1.005)^3 + 2(0.131), -4(0.131)] \approx [4(-1.015) + 0.262, -0.524] = [-4.06 + 0.262, -0.524] = [-3.798, -0.524]\) -
构造子问题：
采用BFGS更新Hessian近似（略去复杂更新过程，假设 \(B_1\) 仍接近I），子问题：
最小化 \(m_1(d) = f(x^{(1)}) + [-3.798, -0.524]^T d + \frac{1}{2} d^T d\)
约束线性化：\(g_1 \approx (0.990-0.432) + [1.99, -1]^T d = 0.558 + [1.99, -1]^T d \leq 0\)
\(g_2 \approx (0.990+0.187-1) + [1.99, 0.864]^T d = 0.177 + [1.99, 0.864]^T d \leq 0\)
信赖域 \(\|d\| \leq 0.5\) -
求解子问题：
无约束最速下降方向 \(d = -[-3.798, -0.524] = [3.798, 0.524]\)，范数 \(\approx 3.834 > 0.5\)，缩放得 \(d^{(1)} \approx [0.495, 0.068]\) -
计算比率：
\(x^{(2)} = x^{(1)} + d^{(1)} \approx (1.49, 0.5)\)
\(f(x^{(2)}) = (1.49-2)^4 + (1.49-1)^2 = (-0.51)^4 + (0.49)^2 \approx 0.068 + 0.240 = 0.308\)
\(\text{ared} = 1.037 - 0.308 = 0.729\)
\(\text{pred} \approx -([-3.798, -0.524]^T [0.495, 0.068]) + 0.5 \times 0.25 \approx -(-1.879 - 0.036) + 0.125 = 1.915 + 0.125 = 2.04\)
\(\rho_1 = 0.729 / 2.04 \approx 0.357\) -
更新：
接受 \(x^{(2)}\)，\(\rho_1 > 0.25\) 但 \(< 0.75\)，保持 \(\Delta_2 = 0.5\)
步骤4：收敛判断
经过数次迭代后，点列将趋近约束边界 \(g_2(x) = 0\)（单位圆）附近的最优解。实际应用中，当梯度范数小于阈值（如 \(10^{-6}\)）或迭代点变化很小时停止。本例经过有限步即可接近最优解 \(x^* \approx (1, 0.5)\) 附近（满足 \(g_2(x)=0\) 且目标函数较小）。
关键点总结
- 代理模型用二次函数近似目标，线性函数近似约束
- 信赖域保证每次迭代的可靠性
- 比率 \(\rho_k\) 决定步长接受与半径调整
- 混合策略平衡收敛速度与稳定性