非线性规划中的自适应移动限界框架(Adaptive Move-Limits Framework)算法进阶题
题目描述
考虑一个非线性规划问题：
最小化 \(f(x) = (x_1 - 2)^4 + (x_1 - 2x_2)^2\)
约束条件为
\[\begin{aligned} g_1(x) &= x_1^2 - x_2 \leq 0, \\ g_2(x) &= x_1 + x_2 - 2 \leq 0, \\ x_1, x_2 &\geq 0. \end{aligned} \]
初始点 \(x^{(0)} = (0, 0)\)，初始移动限界半径 \(\delta^{(0)} = 0.5\)，收缩因子 \(\beta = 0.7\)，扩张因子 \(\gamma = 1.2\)，收敛阈值 \(\epsilon = 10^{-4}\)。要求使用自适应移动限界框架（Adaptive Move-Limits Framework, AML）求解，并详细展示迭代过程。
解题过程
自适应移动限界框架是一种序列线性规划方法，通过动态调整移动限界半径来控制线性近似的精度，平衡收敛速度和稳定性。以下是逐步求解过程：
步骤1: 理解自适应移动限界框架的核心思想
- 移动限界的作用：在每次迭代中，将非线性函数在当前点 \(x^{(k)}\) 处线性化，但限制优化变量在信任区域 \(\|x - x^{(k)}\| \leq \delta^{(k)}\) 内变化，避免线性近似误差过大。
- 自适应调整：根据线性化模型的预测改进与实际改进的比值 \(\rho^{(k)}\)，动态调整限界半径 \(\delta^{(k)}\)：
- 若 \(\rho^{(k)}\) 接近1（模型拟合好），则扩张限界（\(\delta^{(k+1)} = \gamma \delta^{(k)}\)）；
- 若 \(\rho^{(k)}\) 很小（模型拟合差），则收缩限界（\(\delta^{(k+1)} = \beta \delta^{(k)}\)）；
- 否则保持限界不变。
- 线性化方法：目标函数和约束函数在 \(x^{(k)}\) 处作一阶泰勒展开，转化为线性规划子问题。
步骤2: 第一次迭代（k=0）
- 当前点：\(x^{(0)} = (0, 0)\)，限界半径 \(\delta^{(0)} = 0.5\)。
- 线性化子问题：
目标函数线性化：
\[ f(x) \approx f(x^{(0)}) + \nabla f(x^{(0)})^T (x - x^{(0)}) = 16 + [-4(0-2)^3 + 2(0-0)] x_1 + [0] x_2 = 16 - 32x_1. \]
约束线性化：
\[ \begin{aligned} g_1(x) &\approx g_1(0) + \nabla g_1(0)^T x = 0 + [0, -1] x = -x_2 \leq 0, \\ g_2(x) &\approx g_2(0) + \nabla g_2(0)^T x = -2 + [1, 1] x \leq 0. \end{aligned} \]
子问题为：
\[ \begin{aligned} \min_{x} &\quad -32x_1 \\ \text{s.t.} &\quad -x_2 \leq 0, \\ &\quad x_1 + x_2 \leq 2, \\ &\quad x_1, x_2 \geq 0, \\ &\quad \|x - (0,0)\|_\infty \leq 0.5 \quad (\text{移动限界约束}). \end{aligned} \]
- 求解子问题：
目标函数系数为负，需最大化 \(x_1\)。在移动限界内，\(x_1 \leq 0.5\)，且约束 \(x_1 + x_2 \leq 2\) 宽松。最优解为 \(x^{(1)} = (0.5, 0)\)。 - 计算改进比：
实际改进：
\[ \Delta f_{\text{actual}} = f(x^{(0)}) - f(x^{(1)}) = 16 - [(0.5-2)^4 + (0.5-0)^2] = 16 - [5.0625 + 0.25] = 10.6875. \]
预测改进（线性模型改进）：
\[ \Delta f_{\text{pred}} = -32 \times 0.5 - 16 = -16 - 16 = -32 \quad (\text{错误，需修正}). \]
修正：线性化目标函数值为 \(16 - 32x_1\)，在 \(x^{(0)}\) 处为16，在 \(x^{(1)}\) 处为 \(16 - 32 \times 0.5 = 0\)，故预测改进为 \(16 - 0 = 16\)。
改进比：
\[ \rho^{(0)} = \frac{\Delta f_{\text{actual}}}{\Delta f_{\text{pred}}} = \frac{10.6875}{16} \approx 0.668. \]
- 调整限界半径：
由于 \(\rho^{(0)} \in [0.25, 0.75)\)，限界半径保持不变：\(\delta^{(1)} = \delta^{(0)} = 0.5\)。
步骤3: 第二次迭代（k=1）
- 当前点：\(x^{(1)} = (0.5, 0)\)，限界半径 \(\delta^{(1)} = 0.5\)。
- 线性化子问题：
梯度计算：
\[ \nabla f(x) = \left[4(x_1-2)^3 + 2(x_1-2x_2), -4(x_1-2x_2)\right]. \]
在 \(x^{(1)}\) 处：
\[ \nabla f(0.5, 0) = [4(-1.5)^3 + 2(0.5), -4(0.5)] = [-13.5 + 1, -2] = [-12.5, -2]. \]
目标线性化：
\[ f(x) \approx f(0.5,0) + [-12.5, -2] (x - (0.5,0)) = 5.3125 -12.5(x_1-0.5) -2x_2. \]
约束线性化：
\[ \begin{aligned} g_1(x) &\approx g_1(0.5,0) + [2x_1, -1]_{(0.5,0)} (x - (0.5,0)) = 0.25 + [1, -1] (x_1-0.5, x_2) \leq 0, \\ g_2(x) &\approx -1.5 + [1,1] (x_1-0.5, x_2) \leq 0. \end{aligned} \]
子问题为：
\[ \begin{aligned} \min_{x} &\quad -12.5x_1 - 2x_2 \quad (\text{忽略常数项}) \\ \text{s.t.} &\quad x_1 - x_2 \leq 0.25, \\ &\quad x_1 + x_2 \leq 2, \\ &\quad x_1, x_2 \geq 0, \\ &\quad \|x - (0.5, 0)\|_\infty \leq 0.5. \end{aligned} \]
- 求解子问题：
移动限界内 \(x_1 \in [0, 1]\)，目标函数系数为负，需最大化 \(x_1\) 和 \(x_2\)。最优解为 \(x^{(2)} = (1, 0)\)（在限界内且满足约束）。 - 计算改进比：
实际改进：
\[ \Delta f_{\text{actual}} = f(0.5,0) - f(1,0) = 5.3125 - [(1-2)^4 + (1-0)^2] = 5.3125 - [1 + 1] = 3.3125. \]
预测改进：线性模型在 \(x^{(1)}\) 处值为 \(5.3125\)，在 \(x^{(2)}\) 处为 \(5.3125 -12.5(1-0.5) -2(0) = 5.3125 - 6.25 = -0.9375\)，改进为 \(5.3125 - (-0.9375) = 6.25\)。
改进比：
\[ \rho^{(1)} = \frac{3.3125}{6.25} \approx 0.53. \]
- 调整限界半径：
\(\rho^{(1)} \in [0.25, 0.75)\)，限界半径不变：\(\delta^{(2)} = 0.5\).
步骤4: 后续迭代与收敛
重复以上过程，每次迭代后：
- 若 \(\rho^{(k)} > 0.75\)，则扩张限界（\(\delta^{(k+1)} = 1.2 \delta^{(k)}\)）；
- 若 \(\rho^{(k)} < 0.25\)，则收缩限界（\(\delta^{(k+1)} = 0.7 \delta^{(k)}\)）；
- 否则保持限界。
当连续两次迭代的 \(\|x^{(k+1)} - x^{(k)}\| < \epsilon\) 时停止。最终解将接近真实最优解 \(x^* \approx (1, 1)\)（满足 \(g_1(x^*) = 0\) 且梯度条件）。
关键点总结
- 移动限界框架通过线性化简化问题，但需限界控制误差。
- 自适应机制根据模型拟合度调整限界，提高效率。
- 改进比 \(\rho^{(k)}\) 是调整限界的核心指标。
- 初始点和限界半径影响收敛路径，需合理选择。