序列凸近似信赖域反射混合算法基础题
题目描述
考虑非线性规划问题：
\[\min f(x) = (x_1 - 2)^2 + (x_2 - 1)^2 \]
满足约束：
\[g_1(x) = x_1^2 - x_2 \le 0, \quad g_2(x) = x_1 + x_2 - 2 \le 0 \]
初始点为 \(x^{(0)} = (0, 0)\)，使用序列凸近似（SCA）结合信赖域反射（Trust Region Reflection）的混合算法，进行两次迭代，并分析收敛性。
解题过程
步骤1: 序列凸近似（SCA）原理
SCA的核心思想是将非凸问题在当前迭代点 \(x^{(k)}\) 处进行凸近似，构造一个凸子问题，通过求解子问题更新迭代点。具体步骤：
- 线性化非凸约束：对非凸约束 \(g_1(x) = x_1^2 - x_2\) 在 \(x^{(k)}\) 处进行一阶泰勒展开：
\[ \tilde{g}_1(x; x^{(k)}) = (x_1^{(k)})^2 + 2x_1^{(k)}(x_1 - x_1^{(k)}) - x_2 \]
化简后为：
\[ \tilde{g}_1(x; x^{(k)}) = 2x_1^{(k)}x_1 - x_2 - (x_1^{(k)})^2 \]
注意：目标函数 \(f(x)\) 本身是凸函数，无需近似。
2. 构建凸子问题：在信赖域 \(\|x - x^{(k)}\| \le \Delta_k\) 内求解凸近似问题。
步骤2: 信赖域反射（Trust Region Reflection）机制
若子问题的解使得约束违反度或目标函数恶化，信赖域反射通过调整搜索方向或缩小信赖域半径 \(\Delta_k\) 确保收敛。具体规则：
- 定义实际下降量 \(\text{ared}(k) = f(x^{(k)}) - f(x^{(k+1)})\) 和预测下降量 \(\text{pred}(k)\)（子问题目标函数下降值）。
- 若 \(\text{ared}(k) / \text{pred}(k) < \eta\)（如 \(\eta = 0.1\)），则缩小信赖域；否则保持或扩大信赖域。
步骤3: 第一次迭代（k=0）
初始点 \(x^{(0)} = (0, 0)\)，初始信赖域半径 \(\Delta_0 = 0.5\)。
- 凸近似子问题：
- 目标函数：\(f(x) = (x_1 - 2)^2 + (x_2 - 1)^2\)（保持不变）。
- 近似约束：
\[ \tilde{g}_1(x; x^{(0)}) = 2 \cdot 0 \cdot x_1 - x_2 - 0^2 = -x_2 \le 0 \quad \Rightarrow \quad x_2 \ge 0 \]
\[ g_2(x) = x_1 + x_2 - 2 \le 0 \quad \text{（线性约束，无需近似）} \]
- 信赖域约束：\(x_1^2 + x_2^2 \le 0.5^2\)。
-
求解子问题：
子问题为凸二次规划，可用拉格朗日法或数值工具求解。在信赖域内，目标函数最小值在约束边界上。通过分析：- 约束 \(g_2\) 要求 \(x_1 + x_2 \le 2\)，但信赖域半径小，优先考虑目标函数梯度方向 \(-\nabla f(0,0) = (4, 2)\)。
- 结合约束 \(x_2 \ge 0\) 和信赖域，得解 \(x^{(1)} = (0.4, 0.3)\)（数值近似）。
-
接受性与信赖域调整：
- 计算实际下降量：
\[ \text{ared} = f(0,0) - f(0.4, 0.3) = 5 - 3.25 = 1.75 \]
- 预测下降量（子问题目标函数下降）约为 1.8。
- 比率 \(\rho = 1.75 / 1.8 \approx 0.97 > \eta\)，接受 \(x^{(1)}\)，并扩大信赖域至 \(\Delta_1 = 0.8\)。
步骤4: 第二次迭代（k=1）
当前点 \(x^{(1)} = (0.4, 0.3)\)，信赖域半径 \(\Delta_1 = 0.8\)。
- 凸近似子问题：
- 线性化 \(g_1\) 在 \(x^{(1)}\) 处：
\[ \tilde{g}_1(x; x^{(1)}) = 2 \cdot 0.4 \cdot x_1 - x_2 - (0.4)^2 = 0.8x_1 - x_2 - 0.16 \le 0 \]
- 其他约束与信赖域不变。
-
求解子问题：
在信赖域内最小化 \(f(x)\)，满足 \(0.8x_1 - x_2 \le 0.16\) 和 \(x_1 + x_2 \le 2\)。
通过数值求解得 \(x^{(2)} = (0.7, 0.5)\)。 -
接受性与收敛判断：
- 实际下降量：\(f(0.4,0.3) - f(0.7,0.5) = 3.25 - 2.34 = 0.91\)
- 预测下降量约为 0.95，比率 \(\rho \approx 0.96 > \eta\)，接受 \(x^{(2)}\)。
- 检查约束违反度：
\[ g_1(0.7,0.5) = 0.49 - 0.5 = -0.01 \le 0, \quad g_2(0.7,0.5) = 1.2 \le 0 \]
满足约束，且目标函数下降显著，算法继续。
步骤5: 收敛性分析
- 理论保证：SCA的凸近似误差随迭代缩小，信赖域反射确保全局收敛到局部最优。
- 本题趋势：迭代点向可行域内最优解 \((1, 1)\) 靠近，约束违反度逐渐减少，目标函数单调下降，符合收敛预期。
关键点总结
- SCA通过线性化非凸约束构造凸子问题。
- 信赖域反射控制步长，避免无效移动。
- 混合算法平衡收敛速度与稳定性，适用于中等规模非凸问题。