自适应移动渐近线法（Adaptive Method of Moving Asymptotes, AMMA）基础题
题目描述
考虑一个二维非线性约束优化问题：
最小化目标函数 f(x₁, x₂) = (x₁ - 4)⁴ + (x₂ - 3)² + 5
满足约束：
g₁(x₁, x₂) = x₁² + x₂² - 5 ≤ 0
g₂(x₁, x₂) = -x₁ + 1 ≤ 0
g₃(x₁, x₂) = -x₂ + 1 ≤ 0
初始点 x⁰ = (2.0, 2.0)。
该问题为具有非线性不等式约束的非凸规划。你将通过自适应移动渐近线法（AMMA） 进行求解。你需要理解移动渐近线法的核心思想，并掌握其自适应机制（自适应更新移动渐近线参数、自适应移动限界等）。本题重点在于用AMMA构造序列凸近似子问题，逐步逼近原问题的最优解。
解题过程
1. 移动渐近线法（MMA）的基本思想
移动渐近线法是一种序列凸近似方法。其核心是：在当前点 \(x^k\) 处，对原目标函数和约束函数分别构建凸可分的近似函数（通常为线性分式形式或线性化形式），从而得到一个凸子问题，求解该子问题得到新的迭代点。近似函数的构造依赖于“移动渐近线”参数 \(L_i^k\) 和 \(U_i^k\)，它们随着迭代自适应调整，以控制近似的精度和稳定性。
凸可分近似的一般形式（对函数 \(f(x)\)）：
\[\tilde{f}(x; x^k, L, U) = f(x^k) + \sum_{i=1}^{n} \left[ \frac{p_i^k}{U_i^k - x_i} + \frac{q_i^k}{x_i - L_i^k} \right] \]
其中 \(p_i^k, q_i^k\) 由梯度信息决定，使得近似函数在 \(x^k\) 处与原函数一阶匹配。
优点：通过调整渐近线 \(L_i^k, U_i^k\) 可控制近似函数的曲率，保证子问题凸且可分，易于求解。
2. 对本题的AMMA具体构造
设当前迭代点为 \(x^k = (x_1^k, x_2^k)\)。我们采用一种更常用的简化形式（基于一阶泰勒展开与移动限界）来构造凸近似：
步骤1：构造近似目标函数
对目标函数 \(f(x)\) 在 \(x^k\) 处做一阶泰勒展开，但引入移动限界（移动渐近线的简化版本）来限制变量变化范围：
\[\tilde{f}(x) = f(x^k) + \nabla f(x^k)^T (x - x^k) + \frac{1}{2} \sum_{i=1}^{2} \alpha_i^k (x_i - x_i^k)^2 \]
其中 \(\alpha_i^k\) 是自适应曲率系数，用于保证近似函数的凸性和近似质量。在实际MMA中，这种形式可通过选择合适的 \(L_i^k, U_i^k\) 来实现。
为简化，本题使用如下凸可分近似（基于倒变量替换）：
令
\[y_i = \frac{1}{U_i^k - x_i}, \quad z_i = \frac{1}{x_i - L_i^k} \]
但更常用的是对目标函数直接线性化，对约束函数采用特殊凸近似。
这里我们采用标准MMA的近似形式（对任意函数 \(\phi(x)\)）：
\[\tilde{\phi}(x) = \phi(x^k) + \sum_{i=1}^{n} \left( \frac{p_i^k}{U_i^k - x_i} + \frac{q_i^k}{x_i - L_i^k} \right) \]
其中：
\[p_i^k = \begin{cases} (U_i^k - x_i^k)^2 \frac{\partial \phi}{\partial x_i}(x^k) & \text{if } \frac{\partial \phi}{\partial x_i}(x^k) > 0 \\ 0 & \text{otherwise} \end{cases} \]
\[ q_i^k = \begin{cases} 0 & \text{if } \frac{\partial \phi}{\partial x_i}(x^k) > 0 \\ (x_i^k - L_i^k)^2 \left| \frac{\partial \phi}{\partial x_i}(x^k) \right| & \text{otherwise} \end{cases} \]
且 \(L_i^k < x_i^k < U_i^k\)。
3. 计算当前迭代点处的梯度
初始点 \(x^0 = (2.0, 2.0)\)。
目标函数梯度：
\[\nabla f(x) = \begin{bmatrix} 4(x_1 - 4)^3 \\ 2(x_2 - 3) \end{bmatrix} \]
在 \(x^0\) 处：
\[\nabla f(x^0) = [4(2-4)^3, 2(2-3)] = [4 \cdot (-8), -2] = [-32, -2] \]
约束函数梯度：
\[\nabla g_1(x) = [2x_1, 2x_2] = [4, 4] \quad \text{at } x^0 \]
\[ \nabla g_2(x) = [-1, 0] \]
\[ \nabla g_3(x) = [0, -1] \]
约束函数值：
\[g_1(x^0) = 2^2 + 2^2 - 5 = 3 > 0 \quad (\text{违反}) \]
\[ g_2(x^0) = -2 + 1 = -1 \le 0 \quad (\text{满足}) \]
\[ g_3(x^0) = -2 + 1 = -1 \le 0 \quad (\text{满足}) \]
4. 初始化移动渐近线参数
设置初始渐近线：
常用启发式：令 \(L_i^0 = x_i^0 - s\), \(U_i^0 = x_i^0 + s\)，其中 \(s > 0\) 为初始范围，如 \(s = 0.5\)。
但为了稳定性，通常让渐近线距离当前点一定距离，避免分母接近零。
取 \(s = 1.0\)：
\[L_1^0 = 1.0, \quad U_1^0 = 3.0 \]
\[ L_2^0 = 1.0, \quad U_2^0 = 3.0 \]
检查：\(L_i^0 < x_i^0 < U_i^0\) 成立。
5. 构造第一个凸子问题（k=0）
目标函数近似：
对 \(f(x)\) 在 \(x^0\) 处使用MMA近似公式。
计算 \(p_i^0, q_i^0\) 对于 \(f\)：
对 \(i=1\)：\(\frac{\partial f}{\partial x_1} = -32 < 0\)，所以：
\[p_1^0 = 0, \quad q_1^0 = (x_1^0 - L_1^0)^2 \cdot 32 = (2.0 - 1.0)^2 \cdot 32 = 32 \]
对 \(i=2\)：\(\frac{\partial f}{\partial x_2} = -2 < 0\)：
\[p_2^0 = 0, \quad q_2^0 = (2.0 - 1.0)^2 \cdot 2 = 2 \]
于是近似目标函数：
\[\tilde{f}(x) = f(x^0) + \frac{32}{x_1 - 1.0} + \frac{2}{x_2 - 1.0} \]
其中 \(f(x^0) = (2-4)^4 + (2-3)^2 + 5 = 16 + 1 + 5 = 22\)。
约束函数近似：
对 \(g_1(x)\)：梯度分量为正（4, 4 > 0），所以：
对 \(i=1\)：\(p_{1,1}^0 = (U_1^0 - x_1^0)^2 \cdot 4 = (3.0 - 2.0)^2 \cdot 4 = 4\)，\(q_{1,1}^0 = 0\)
对 \(i=2\)：\(p_{1,2}^0 = (3.0 - 2.0)^2 \cdot 4 = 4\)，\(q_{1,2}^0 = 0\)
于是：
\[\tilde{g}_1(x) = g_1(x^0) + \frac{4}{3.0 - x_1} + \frac{4}{3.0 - x_2} \]
其中 \(g_1(x^0) = 3\)。
对 \(g_2(x)\)：梯度为 \([-1, 0]\)，第一个分量为负，第二个分量为零。
对 \(i=1\)：\(\frac{\partial g_2}{\partial x_1} = -1 < 0\)，所以 \(p_{2,1}^0 = 0\), \(q_{2,1}^0 = (2.0 - 1.0)^2 \cdot 1 = 1\)
对 \(i=2\)：梯度为0，则 \(p_{2,2}^0 = 0, q_{2,2}^0 = 0\)
于是：
\[\tilde{g}_2(x) = g_2(x^0) + \frac{1}{x_1 - 1.0} \]
其中 \(g_2(x^0) = -1\)。
对 \(g_3(x)\)：梯度为 \([0, -1]\)，类似有：
对 \(i=1\)：梯度0 → p=q=0
对 \(i=2\)：梯度-1 → p=0, q = (2.0 - 1.0)^2 \cdot 1 = 1
\[\tilde{g}_3(x) = g_3(x^0) + \frac{1}{x_2 - 1.0} \]
其中 \(g_3(x^0) = -1\)。
子问题（k=0）：
\[\begin{aligned} \min_{x} \quad & 22 + \frac{32}{x_1 - 1.0} + \frac{2}{x_2 - 1.0} \\ \text{s.t.} \quad & 3 + \frac{4}{3.0 - x_1} + \frac{4}{3.0 - x_2} \le 0 \\ & -1 + \frac{1}{x_1 - 1.0} \le 0 \\ & -1 + \frac{1}{x_2 - 1.0} \le 0 \\ & L_i^0 < x_i < U_i^0 \quad (i=1,2) \end{aligned} \]
注意：子问题中自变量还需满足 \(L_i^0 < x_i < U_i^0\)，即 \(1.0 < x_1 < 3.0, 1.0 < x_2 < 3.0\)。
6. 求解子问题
该子问题是凸可分规划（目标函数和约束均为凸可分函数），可用凸优化求解器或简单的一维搜索（因可分）求解。这里为展示，我们手动分析。
约束 \(-1 + \frac{1}{x_i - 1.0} \le 0\) 等价于 \(\frac{1}{x_i - 1.0} \le 1\)，即 \(x_i - 1.0 \ge 1\)，所以 \(x_i \ge 2.0\)。结合 \(x_i < 3.0\) 得 \(2.0 \le x_i < 3.0\)。
第一个约束：\(3 + \frac{4}{3.0 - x_1} + \frac{4}{3.0 - x_2} \le 0\)。
由于 \(3.0 - x_i > 0\)，左边每项 \(\frac{4}{3.0 - x_i} > 0\)，要使总和 ≤ 0 很困难。实际上在 \(2.0 \le x_i < 3.0\) 范围内，该约束很难满足。这说明初始近似可能太松，需要调整。
自适应机制：当近似约束无法满足时，可调整渐近线参数，使近似更保守（更接近原约束）。一种自适应策略是：如果子问题解对应的原约束违反度大，则缩小渐近线范围（让 \(L_i^k\) 更靠近 \(x_i^k\)，\(U_i^k\) 也更靠近 \(x_i^k\)），以增加近似的局部性。
7. 自适应调整渐近线
常用自适应规则（简化）：
- 如果当前迭代后原约束违反度大，则减小 \(s^{k+1} = 0.7 s^k\)（缩小渐近线间隔）。
- 如果满足约束且进展顺利，可适当增大 \(s^{k+1}\) 以加速。
这里初始子问题可能不可行，可先尝试放松子问题（如允许约束违反），或直接调整渐近线。
为简单起见，我们重新初始化更紧的渐近线，比如 \(s = 0.2\)：
\[L_i^0 = x_i^0 - 0.2 = 1.8, \quad U_i^0 = x_i^0 + 0.2 = 2.2 \]
然后重新构造子问题，过程类似，此时分母区间变小，近似更局部，约束近似更接近真实值，更可能可行。
8. 迭代步骤
一般AMMA迭代流程：
- 在当前点 \(x^k\)，根据当前渐近线 \(L_i^k, U_i^k\) 构造凸可分近似子问题。
- 求解子问题得到候选点 \(x^{k+1}\)。
- 计算原问题目标函数和约束在 \(x^{k+1}\) 处的值，判断是否接受该点（如使用滤子法或罚函数判断）。
- 根据接受情况与近似质量，自适应更新渐近线参数 \(L_i^{k+1}, U_i^{k+1}\)（如：如果近似误差大，则缩小渐近线间隔；如果迭代顺利，可适当放大）。
- 更新迭代点，重复直到收敛。
收敛准则：当 \(\|x^{k+1} - x^k\|\) 小于给定容差，且约束违反度足够小，停止。
9. 本题的预期求解轨迹
从初始点 (2,2) 开始，目标函数梯度指向 (4,3) 方向（最小值大约在 (4,3) 附近，但需满足约束 \(x_1^2 + x_2^2 \le 5\)）。
通过AMMA逐步构造凸子问题，解会从 (2,2) 移向可行域内部，最终逼近约束边界 \(x_1^2 + x_2^2 = 5\) 上的最优点。可验证最优解大约在 (1.581, 1.581) 附近（通过拉格朗日乘子法可解），目标函数值比无约束最小值大。
总结
自适应移动渐近线法（AMMA）通过构造序列凸可分近似子问题，将原非凸问题转化为一系列凸问题求解。关键是通过调整移动渐近线参数控制近似的局部性和保守性，以保证收敛性和数值稳定性。本题展示了如何基于梯度信息构造近似、如何自适应调整参数，以及如何迭代直到满足约束并优化目标。