非线性规划中的自适应移动渐近线法（Adaptive Method of Moving Asymptotes, AMMA）基础题
题目描述
考虑如下非线性规划问题：
最小化目标函数 \(f(\mathbf{x}) = (x_1 - 3)^4 + (x_2 - 2)^2\)
约束条件：
\[g_1(\mathbf{x}) = x_1^2 + x_2^2 - 5 \le 0, \quad g_2(\mathbf{x}) = -x_1 - x_2 + 1 \le 0, \quad x_1 \ge 0, \, x_2 \ge 0. \]
要求使用自适应移动渐近线法（AMMA）求解该问题。该方法基于移动渐近线法（MMA），但引入自适应机制动态调整渐近线移动参数，以提高收敛效率与稳定性。请从初始点 \(\mathbf{x}^{(0)} = (1, 1)\) 出发，详细推导并展示AMMA的迭代过程，至少完成两次迭代，并解释自适应策略如何调整渐近线。
解题过程
第一步：理解AMMA的基本思想
AMMA是移动渐近线法（MMA）的改进版本。MMA将原非凸问题转化为一系列凸子问题，通过迭代求解这些子问题逼近原问题的最优解。其核心是用移动渐近线构造保守近似：
对于每个变量 \(x_i\)，在迭代点 \(\mathbf{x}^{(k)}\) 处引入下渐近线 \(L_i^{(k)}\) 和上渐近线 \(U_i^{(k)}\)，将原函数近似为凸函数（如可分离的线性分式形式）。AMMA通过评估近似质量（如函数值与约束违反程度）自适应地调整 \(L_i^{(k)}\) 和 \(U_i^{(k)}\) 的变化幅度，避免振荡或停滞。
第二步：构造近似子问题
在迭代点 \(\mathbf{x}^{(k)}\) 处，AMMA对目标函数和约束函数进行凸近似。以目标函数 \(f(\mathbf{x})\) 为例，其近似函数 \(\tilde{f}^{(k)}(\mathbf{x})\) 形式为：
\[\tilde{f}^{(k)}(\mathbf{x}) = \sum_{i=1}^n \left( \frac{p_i^{(k)}}{U_i^{(k)} - x_i} + \frac{q_i^{(k)}}{x_i - L_i^{(k)}} \right) + r^{(k)}, \]
其中 \(p_i^{(k)} \ge 0, q_i^{(k)} \ge 0\) 由函数在 \(\mathbf{x}^{(k)}\) 处的梯度信息确定。具体地：
- 计算梯度分量 \(\nabla_i f(\mathbf{x}^{(k)})\)。
- 若梯度为正，则分配权重给 \(p_i^{(k)}\)；若为负，则分配给 \(q_i^{(k)}\)。
对于约束函数 \(g_j(\mathbf{x})\)，采用相同形式的近似 \(\tilde{g}_j^{(k)}(\mathbf{x})\)。
第三步：初始化与第一次迭代（k=0）
给定初始点 \(\mathbf{x}^{(0)} = (1, 1)\)。
计算目标函数与约束函数值及梯度：
- \(f(\mathbf{x}^{(0)}) = (1-3)^4 + (1-2)^2 = 16 + 1 = 17\)。
- \(g_1(\mathbf{x}^{(0)}) = 1^2 + 1^2 - 5 = -3\)（满足），\(g_2(\mathbf{x}^{(0)}) = -1 - 1 + 1 = -1\)（满足）。
- 梯度：
\[ \nabla f(\mathbf{x}^{(0)}) = \left( 4(x_1-3)^3, 2(x_2-2) \right) = (4 \cdot (-2)^3, 2 \cdot (-1)) = (-32, -2). \]
\[ \nabla g_1(\mathbf{x}^{(0)}) = (2x_1, 2x_2) = (2, 2), \quad \nabla g_2(\mathbf{x}^{(0)}) = (-1, -1). \]
初始渐近线设置（常见启发式规则）：
\[L_i^{(0)} = x_i^{(0)} - s, \quad U_i^{(0)} = x_i^{(0)} + s, \]
取 \(s = 0.5\)，则 \(L_1^{(0)} = 0.5, U_1^{(0)} = 1.5\)，\(L_2^{(0)} = 0.5, U_2^{(0)} = 1.5\)。
根据梯度确定近似函数系数（以目标函数为例）：
对于 \(\nabla_i f < 0\)，权重分配给 \(q_i^{(0)}\)；反之给 \(p_i^{(0)}\)。这里两个梯度分量均为负，故：
\[q_i^{(0)} = (x_i^{(0)} - L_i^{(0)})^2 \cdot \max(0, -\nabla_i f) = (1-0.5)^2 \cdot 32 = 0.25 \cdot 32 = 8 \quad (\text{对 } i=1), \]
\[q_2^{(0)} = (1-0.5)^2 \cdot 2 = 0.25 \cdot 2 = 0.5, \quad p_i^{(0)} = 0. \]
常数 \(r^{(0)}\) 通过匹配 \(\tilde{f}^{(0)}(\mathbf{x}^{(0)}) = f(\mathbf{x}^{(0)})\) 确定：
\[\tilde{f}^{(0)}(\mathbf{x}^{(0)}) = \sum_{i} \frac{q_i^{(0)}}{x_i^{(0)} - L_i^{(0)}} + r^{(0)} = \frac{8}{0.5} + \frac{0.5}{0.5} + r^{(0)} = 16 + 1 + r^{(0)} = 17 + r^{(0)}. \]
令其等于17，得 \(r^{(0)} = 0\)。
对约束函数 \(g_1, g_2\) 做类似近似（系数由梯度正负决定，并加上常数项以匹配约束值）。
子问题为凸优化问题：
\[\min_{\mathbf{x}} \tilde{f}^{(0)}(\mathbf{x}) \quad \text{s.t.} \quad \tilde{g}_1^{(0)}(\mathbf{x}) \le 0, \quad \tilde{g}_2^{(0)}(\mathbf{x}) \le 0, \quad x_i \ge 0. \]
该问题可用内点法等凸优化求解器求解。假设解得 \(\mathbf{x}^{(1)} = (1.2, 1.3)\)（此处为示例，实际需数值求解）。
第四步：自适应调整渐近线
AMMA的核心是自适应调整 \(L_i^{(k)}, U_i^{(k)}\)。常见策略基于近似误差：
定义近似质量指标 \(\eta^{(k)} = \frac{|f(\mathbf{x}^{(k+1)}) - \tilde{f}^{(k)}(\mathbf{x}^{(k+1)})|}{|f(\mathbf{x}^{(k)})|}\)（类似可考虑约束误差）。
- 若 \(\eta^{(k)}\) 较大（如 > 0.1），说明近似不够保守，需缩小渐近线移动幅度：令 \(s \leftarrow 0.8s\)（减小变化）。
- 若 \(\eta^{(k)}\) 较小（如 < 0.01），说明近似可能过于保守，可增大移动幅度：令 \(s \leftarrow 1.2s\)。
- 更新渐近线：
\[L_i^{(k+1)} = x_i^{(k+1)} - s, \quad U_i^{(k+1)} = x_i^{(k+1)} + s. \]
对于第一次迭代，计算 \(\eta^{(0)}\)：
假设 \(\tilde{f}^{(0)}(\mathbf{x}^{(1)}) \approx 15.5\)，实际 \(f(\mathbf{x}^{(1)}) = (1.2-3)^4 + (1.3-2)^2 = (-1.8)^4 + (-0.7)^2 = 10.4976 + 0.49 \approx 10.99\)。
则 \(\eta^{(0)} = |10.99 - 15.5| / 17 \approx 0.265\)，误差较大，故减小 s：新 \(s = 0.8 \times 0.5 = 0.4\)。
更新渐近线：\(L_1^{(1)} = 1.2 - 0.4 = 0.8\)，\(U_1^{(1)} = 1.2 + 0.4 = 1.6\)，\(L_2^{(1)} = 1.3 - 0.4 = 0.9\)，\(U_2^{(1)} = 1.3 + 0.4 = 1.7\)。
第五步：第二次迭代（k=1）
在 \(\mathbf{x}^{(1)} = (1.2, 1.3)\) 重新计算梯度，构造新的凸近似子问题。
- 梯度计算：
\[ \nabla f(\mathbf{x}^{(1)}) = (4(1.2-3)^3, 2(1.3-2)) = (4 \cdot (-1.8)^3, 2 \cdot (-0.7)) = (-23.328, -1.4). \]
梯度仍为负，权重分配类似第一次迭代。
- 用新渐近线 \(L_i^{(1)}, U_i^{(1)}\) 构造近似函数，求解子问题得 \(\mathbf{x}^{(2)}\)（假设为 (1.4, 1.5)）。
- 评估近似质量 \(\eta^{(1)}\)，进一步调整 s 和渐近线。
第六步：收敛判断
迭代直至满足停止准则，如 \(\|\mathbf{x}^{(k+1)} - \mathbf{x}^{(k)}\| < \epsilon\) 或目标函数变化很小。AMMA通过动态调整渐近线移动参数，通常比固定参数的MMA收敛更快且更稳定。
总结
AMMA通过自适应调整渐近线位置，平衡近似的保守性与逼近速度。其步骤可归纳为：
- 在当前点构造凸近似子问题。
- 求解子问题得新迭代点。
- 评估近似误差，自适应更新渐近线参数。
- 重复直至收敛。
该方法特别适合中等规模的非凸约束优化问题，在结构优化等领域有广泛应用。