好的，根据你提供的庞大历史列表，我为你随机生成一个尚未出现过的算法题目。
题目：非线性规划中的自适应移动渐近线法（Adaptive Method of Moving Asymptotes, AMMA）基础题
题目描述：
考虑一个标准的非线性规划问题：
最小化 \(f(x)\)
约束条件为 \(g_j(x) \leq 0, \quad j = 1, ..., m\)
以及 \(x_i^L \leq x_i \leq x_i^U, \quad i = 1, ..., n\)。
其中，目标函数 \(f(x)\) 和约束函数 \(g_j(x)\) 是光滑但可能高度非线性和非凸的。移动渐近线法（MMA）是一种著名的序列凸近似（SCA）算法，它通过巧妙地构造凸可分（convex and separable）的近似子问题来逼近原问题。然而，经典MMA中近似函数的曲率参数（即移动渐近线的位置）更新策略相对固定。
本题要求你理解并实现一种自适应移动渐近线法（AMMA）。其核心思想是：根据当前迭代点函数的行为（如梯度信息、约束违反度等），自适应地调整每次迭代中为每个变量 \(x_i\) 构建近似函数时所使用的渐近线移动参数（\(L_i^k, U_i^k\)），而不仅仅是根据经验公式更新。目标是使近似模型在全局收敛性和局部收敛速度之间取得更好的平衡。
我们用一个具体问题来演示：
最小化 \(f(x) = x_1^4 + x_2^4 - 4x_1x_2\)
约束条件为 \(g_1(x) = x_1^2 + x_2^2 - 1 \leq 0\)
初始点 \(x^0 = (0.5, 0.5)\)，变量范围 \(-2 \leq x_1, x_2 \leq 2\)。
解题过程详解：
我们将循序渐进地讲解AMMA的求解步骤。
步骤1：回顾经典MMA近似子问题的构建
在迭代点 \(x^k\)，MMA为原函数 \(f(x)\) 和 \(g_j(x)\) 构造凸可分的近似函数 \(\tilde{f}^k(x)\) 和 \(\tilde{g}_j^k(x)\)。对于函数 \(F(x)\)（代表 \(f\) 或 \(g_j\)），其近似形式为：
\[\tilde{F}^k(x) = 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) \]
其中，\(L_i^k\) 和 \(U_i^k\) 是当前迭代的“移动渐近线”，满足 \(L_i^k < x_i^k < U_i^k\)。系数 \(p_i^k, q_i^k\) 由函数在 \(x^k\) 处的梯度 \(\nabla_i F(x^k)\) 决定：
\[\text{若 } \nabla_i F(x^k) > 0, \text{ 则 } p_i^k = (U_i^k - x_i^k)^2 \nabla_i F(x^k), \quad q_i^k = 0 \]
\[ \text{若 } \nabla_i F(x^k) < 0, \text{ 则 } p_i^k = 0, \quad q_i^k = -(x_i^k - L_i^k)^2 \nabla_i F(x^k) \]
关键参数 \(L_i^k, U_i^k\) 控制了近似函数的“弯曲”程度和保守性。经典MMA通常使用如下经验更新：
\[L_i^k = x_i^k - s_{low}(x_i^U - x_i^L)， \quad U_i^k = x_i^k + s_{up}(x_i^U - x_i^L) \]
其中 \(s_{low}, s_{up} \in (0, 1)\) 是固定缩放因子，后续迭代可能会根据收敛情况缩小它们。
步骤2：理解自适应的核心思想
固定参数 \(s_{low}, s_{up}\) 的问题在于：它们无法根据当前点的局部函数特性进行调整。
- 当函数变化剧烈（梯度大）时，我们希望近似更“保守”（即 \(L_i^k\) 更接近 \(x_i^k\) 的下方，\(U_i^k\) 更接近 \(x_i^k\) 的上方），使近似子问题的可行域更小，避免因近似误差过大而导致迭代发散或不稳定。
- 当函数变化平缓（梯度小）时，我们可以采用更“激进”的近似（即 \(L_i^k\) 离 \(x_i^k\) 更远一些，\(U_i^k\) 离 \(x_i^k\) 更远一些），使近似子问题的可行域更大，从而允许单次迭代走更长的步长，加速收敛。
因此，AMMA 的核心就是根据梯度大小等信息，动态计算缩放因子 \(s_{low}^k, s_{up}^k\)。
步骤3：设计自适应策略
一种简单有效的自适应策略是利用梯度信息。定义当前迭代对所有函数（目标+有效约束）的梯度敏感度：
\[\gamma_i^k = \alpha |\nabla_i f(x^k)| + \beta \sum_{j \in \mathcal{A}^k} |\nabla_i g_j(x^k)| \]
其中 \(\mathcal{A}^k\) 是当前点的有效约束集（通常包括所有违反或接近边界的约束），\(\alpha, \beta\) 是权重系数（例如 \(\alpha=1, \beta=1\)）。\(\gamma_i^k\) 反映了变量 \(x_i\) 在当前位置对总体优化问题的敏感度。
然后，我们将敏感度映射到缩放因子上：
\[s_{i, low}^k = s_{min} + (s_{max} - s_{min}) \cdot \exp(-\eta \cdot \gamma_i^k) \]
\[ s_{i, up}^k = s_{min} + (s_{max} - s_{min}) \cdot \exp(-\eta \cdot \gamma_i^k) \]
这里 \(s_{min}, s_{max}\) 是缩放因子的下限和上限（例如0.1和0.5），\(\eta > 0\) 是一个衰减参数（例如1.0）。
- 高敏感度（\(\gamma_i^k\) 大）：\(\exp(-\eta \cdot \gamma_i^k)\) 小，\(s_{i, low}^k\) 和 \(s_{i, up}^k\) 接近 \(s_{min}\)，产生保守近似（移动渐近线靠近当前点）。
- 低敏感度（\(\gamma_i^k\) 小）：\(\exp(-\eta \cdot \gamma_i^k)\) 接近1，\(s_{i, low}^k\) 和 \(s_{i, up}^k\) 接近 \(s_{max}\)，产生激进近似（移动渐近线远离当前点）。
最后更新移动渐近线：
\[L_i^k = x_i^k - s_{i, low}^k \cdot (x_i^U - x_i^L) \]
\[ U_i^k = x_i^k + s_{i, up}^k \cdot (x_i^U - x_i^L) \]
并确保 \(L_i^k < x_i^k < U_i^k\) 且不超出全局变量边界太多（可施加额外截断）。
步骤4：应用于例题的迭代过程（第1次迭代演示）
- 初始化：\(x^0 = (0.5, 0.5)\)，设 \(s_{min}=0.1, s_{max}=0.5, \eta=1.0, \alpha=\beta=1\)。
- 计算梯度和约束：
- \(\nabla f(x^0) = [4x_1^3 - 4x_2, 4x_2^3 - 4x_1] = [4*0.125 - 2, 4*0.125 - 2] = [-1.5, -1.5]\)
- \(g_1(x^0) = 0.25+0.25-1 = -0.5\)（满足，非有效约束），故 \(\mathcal{A}^0\) 为空集。
- 计算自适应敏感度：\(\gamma_1^0 = 1*| -1.5 | + 1*0 = 1.5\)，同理 \(\gamma_2^0 = 1.5\)。
- 计算自适应缩放因子：
- \(\exp(-1.0 * 1.5) \approx 0.223\)
- \(s_{1, low}^0 = s_{2, low}^0 = s_{1, up}^0 = s_{2, up}^0 = 0.1 + (0.5 - 0.1)*0.223 \approx 0.189\)
- 对比：若用经典固定因子 \(s_{low}=s_{up}=0.3\)，则新方法（0.189）更保守，因为初始梯度较大。
- 计算移动渐近线：变量范围跨度 \(x_i^U - x_i^L = 4\)。
- \(L_1^0 = 0.5 - 0.189*4 = 0.5 - 0.756 = -0.256\)
- \(U_1^0 = 0.5 + 0.189*4 = 0.5 + 0.756 = 1.256\)
- 同理 \(L_2^0 = -0.256, U_2^0 = 1.256\)。
- 构建近似子问题：对于 \(f(x)\) 和 \(g_1(x)\) 分别计算 \(p_i^k, q_i^k\)。
- 目标函数 \(f(x)\)：梯度分量均为负，所以 \(p_i^0=0\)，\(q_i^0 = -(x_i^0 - L_i^0)^2 * \nabla_i f(x^0) = -(0.5 - (-0.256))^2 * (-1.5) = -(0.756)^2 * (-1.5) \approx 0.857\)。近似函数 \(\tilde{f}^0(x) = f(x^0) + \sum_{i=1}^2 \frac{0.857}{x_i - (-0.256)}\)。
- 约束函数 \(g_1(x)\)：由于当前约束非有效（\(g_1(x^0) < 0\)），在子问题中有时可以忽略或宽松处理，但为演示我们仍构造。\(\nabla g_1(x^0) = [2x_1, 2x_2] = [1, 1] > 0\)，所以 \(p_i^0 = (U_i^0 - x_i^0)^2 * 1 = (1.256-0.5)^2 = 0.572\)，\(q_i^0=0\)。近似函数 \(\tilde{g}_1^0(x) = g_1(x^0) + \sum_{i=1}^2 \frac{0.572}{1.256 - x_i}\)。
- 求解子问题：求解凸可分近似子问题（最小化 \(\tilde{f}^0(x)\)，约束为 \(\tilde{g}_1^0(x) \leq 0\) 和变量边界）。这通常可以通过对偶法或专门的凸优化求解器高效求解。假设我们求解得到新点 \(x^1\)。（实际数值求解略，这里理解流程）
- 迭代与收敛判断：用 \(x^1\) 重复步骤2-7，直到满足收敛条件（如 \(||x^{k+1}-x^k||\) 和约束违反度足够小）。
步骤5：总结与对比
AMMA通过引入梯度敏感度 \(\gamma_i^k\) 来自适应调整移动渐近线的位置。与经典固定参数MMA相比：
- 优点：在函数变化剧烈的区域自动收紧近似，增强算法鲁棒性，防止振荡或发散；在平缓区域放松近似，加快收敛速度。这种动态调整使其能更好地处理高度非线性的问题。
- 缺点：引入了额外的参数（\(\alpha, \beta, \eta, s_{min}, s_{max}\)），需要根据问题经验调整。计算量略有增加（需计算梯度敏感度）。
通过这个例题，你理解了自适应移动渐近线法（AMMA）如何改进经典MMA，并掌握了其构建自适应近似子问题并进行迭代求解的核心流程。