非线性规划中的序列仿射尺度信赖域反射混合算法基础题
题目描述
考虑非线性规划问题：
\[\min f(x) = (x_1 - 2)^2 + (x_2 - 1)^2 \]
满足约束：
\[g_1(x) = x_1^2 - x_2 \leq 0, \quad g_2(x) = x_1 + x_2 - 2 \leq 0 \]
初始点为 \(x^{(0)} = (0.5, 0.5)\)，信赖域半径初始值 \(\Delta_0 = 0.5\)。要求使用序列仿射尺度信赖域反射混合算法求解该问题，并详细解释迭代过程。
解题过程
1. 算法框架概述
该算法结合了仿射尺度变换（Affine Scaling）、信赖域法（Trust Region）和反射技术（Reflection）。核心思想是：
- 通过仿射尺度变换将约束条件线性化，将非线性约束问题转化为一系列子问题；
- 在信赖域内求解子问题，确保迭代步长合理；
- 若子问题解不可行，使用反射技术调整搜索方向，保持可行性。
2. 第一次迭代（k=0）
步骤1：计算当前点函数值及约束
当前点 \(x^{(0)} = (0.5, 0.5)\)：
\[f(x^{(0)}) = (0.5-2)^2 + (0.5-1)^2 = 2.25 + 0.25 = 2.5 \]
约束值：
\[g_1(x^{(0)}) = 0.25 - 0.5 = -0.25 \leq 0, \quad g_2(x^{(0)}) = 0.5 + 0.5 - 2 = -1 \leq 0 \]
两个约束均满足，当前点可行。
步骤2：构造仿射尺度变换
对不等式约束 \(g_i(x) \leq 0\)，定义尺度矩阵 \(D_k\) 为约束违反度的对角矩阵：
\[D_k = \text{diag}\left( \frac{1}{|g_1(x^{(k)})|}, \frac{1}{|g_2(x^{(k)})|} \right) \]
代入 \(g_1 = -0.25, g_2 = -1\)：
\[D_0 = \text{diag}(4, 1) \]
变换后的约束近似为线性形式： \(D_k \nabla g_i(x^{(k)})^T d \leq -g_i(x^{(k)})\)，其中 \(d\) 为搜索方向。
步骤3：构建信赖域子问题
子目标函数为二阶近似：
\[m_k(d) = f(x^{(k)}) + \nabla f(x^{(k)})^T d + \frac{1}{2} d^T B_k d \]
梯度计算：
\[\nabla f(x) = [2(x_1 - 2), 2(x_2 - 1)] \Rightarrow \nabla f(x^{(0)}) = [-3, -1] \]
海森矩阵 \(B_k\) 用单位矩阵近似（拟牛顿法）： \(B_0 = I\)。
子问题为：
\[\min_d \, -3d_1 - d_2 + \frac{1}{2}(d_1^2 + d_2^2) \]
约束条件：
- 线性化约束：
\[\nabla g_1(x^{(0)}) = [2x_1, -1] = [1, -1], \quad \nabla g_2(x^{(0)}) = [1, 1] \]
\[4 \cdot [1, -1] d \leq 0.25 \Rightarrow 4d_1 - 4d_2 \leq 0.25 \]
\[1 \cdot [1, 1] d \leq 1 \Rightarrow d_1 + d_2 \leq 1 \]
- 信赖域约束： \(\|d\|_2 \leq \Delta_0 = 0.5\)。
步骤4：求解子问题
子问题为凸二次规划，使用拉格朗日法或数值工具求解。
解得 \(d^{(0)} \approx (0.3, 0.2)\)，函数下降量 \(m_k(0) - m_k(d^{(0)}) \approx 1.1\)。
步骤5：接受性检验与反射调整
试探点 \(x^{(1)}_{\text{try}} = x^{(0)} + d^{(0)} = (0.8, 0.7)\)。
计算实际下降量：
\[\Delta f_{\text{actual}} = f(x^{(0)}) - f(x^{(1)}_{\text{try}}) = 2.5 - 1.69 = 0.81 \]
预测下降量 \(\Delta f_{\text{pred}} = 1.1\)，比值 \(\rho = 0.81 / 1.1 \approx 0.74\)。
若 \(\rho > 0.25\)，接受该点；否则缩小信赖域。此处接受 \(x^{(1)} = (0.8, 0.7)\)。
约束检查：
\[g_1(x^{(1)}) = 0.64 - 0.7 = -0.06 \leq 0, \quad g_2(x^{(1)}) = 0.8 + 0.7 - 2 = -0.5 \leq 0 \]
点可行，无需反射。
3. 第二次迭代（k=1）
步骤1：更新尺度矩阵与子问题
\(x^{(1)} = (0.8, 0.7)\)，约束值 \(g_1 = -0.06, g_2 = -0.5\)：
\[D_1 = \text{diag}(1/0.06, 1/0.5) \approx \text{diag}(16.7, 2) \]
梯度 \(\nabla f(x^{(1)}) = [-2.4, -0.6]\)，子问题：
\[\min_d \, -2.4d_1 - 0.6d_2 + \frac{1}{2}(d_1^2 + d_2^2) \]
线性化约束：
\[\nabla g_1(x^{(1)}) = [1.6, -1] \Rightarrow 16.7(1.6d_1 - d_2) \leq 0.06 \]
\[\nabla g_2(x^{(1)}) = [1, 1] \Rightarrow 2(d_1 + d_2) \leq 0.5 \]
信赖域半径保持 \(\Delta_1 = 0.5\)。
步骤2：求解与检验
解得 \(d^{(1)} \approx (0.2, 0.05)\)，试探点 \(x^{(2)}_{\text{try}} = (1.0, 0.75)\)。
实际下降量 \(\Delta f_{\text{actual}} \approx 0.3\)，预测下降量 \(\Delta f_{\text{pred}} \approx 0.5\)，比值 \(\rho = 0.6 > 0.25\)，接受点 \(x^{(2)} = (1.0, 0.75)\)。
约束检查： \(g_1 = 1 - 0.75 = 0.25 > 0\)（违反约束！）。
步骤3：反射调整
因 \(g_1(x^{(2)}) > 0\)，需反射。沿约束边界 \(g_1(x) = 0\) 的梯度方向反射：
反射方向 \(r = -\nabla g_1(x^{(2)}) = [-2, 1]\)，归一化后步长调整，得到新点 \(x^{(2)}_{\text{ref}} = (0.9, 0.81)\)。
重新检验约束： \(g_1 \approx 0, g_2 = -0.29\)，点可行。
4. 后续迭代与收敛
重复上述过程，更新尺度矩阵、求解子问题，并结合反射技术处理约束违反。
经过数次迭代后，点收敛至近似最优解 \(x^* \approx (1.0, 1.0)\)，对应 \(f(x^*) = 1.0\)，约束 \(g_1 = 0, g_2 = 0\) 活跃。
算法在约束边界附近通过仿射尺度变换和反射机制高效逼近最优解。