非线性规划中的自适应移动限界框架(Adaptive Move-Limits Framework)算法基础题 题目描述： 考虑非线性规划问题： 最小化 f(x) = (x₁ - 3)⁴ + (x₂ - 2)² 满足约束条件： g₁(x) = x₁² + x₂² - 4 ≤ 0 g₂(x) = x₁ + x₂ - 3 ≤ 0 -1 ≤ x₁ ≤ 3, 0 ≤ x₂ ≤ 4 请使用自适应移动限界框架(AMLF)算法求解该问题，初始点设为x⁰ = [ 0, 0 ]，初始移动限界δ⁰ = 0.5，收缩因子β = 0.7，扩张因子γ = 1.2，收敛容差ε = 10⁻³。 解题过程： 1. 算法基本原理 自适应移动限界框架是一种序列近似优化方法，通过在每次迭代中构建原问题的近似子问题，并自适应调整移动限界（信任域）来控制步长。核心思想是： 在当前点构建线性或二次近似模型 设置移动限界约束|x - xᵏ| ≤ δᵏ 求解近似子问题得到候选点 根据目标函数改进情况自适应调整移动限界大小 2. 第一次迭代（k=0） 步骤2.1：构建近似模型 在当前点x⁰ = [ 0, 0 ]处构建线性近似： f̃(x) ≈ f(x⁰) + ∇f(x⁰)ᵀ(x - x⁰) g̃₁(x) ≈ g₁(x⁰) + ∇g₁(x⁰)ᵀ(x - x⁰) g̃₂(x) ≈ g₂(x⁰) + ∇g₂(x⁰)ᵀ(x - x⁰) 计算梯度： ∇f(x) = [ 4(x₁-3)³, 2(x₂-2)] ⇒ ∇f(0,0) = [ 4(-3)³, 2(-2)] = [ -108, -4 ] ∇g₁(x) = [ 2x₁, 2x₂] ⇒ ∇g₁(0,0) = [ 0, 0 ] ∇g₂(x) = [ 1, 1] ⇒ ∇g₂(0,0) = [ 1, 1 ] 函数值： f(0,0) = 81 + 4 = 85 g₁(0,0) = -4 ≤ 0 g₂(0,0) = -3 ≤ 0 步骤2.2：构建子问题 最小化 f̃(x) = 85 - 108x₁ - 4x₂ 满足： g̃₁(x) = -4 ≤ 0 g̃₂(x) = -3 + x₁ + x₂ ≤ 0 -1 ≤ x₁ ≤ 3, 0 ≤ x₂ ≤ 4 |x₁ - 0| ≤ 0.5, |x₂ - 0| ≤ 0.5 步骤2.3：求解子问题 由于g̃₁始终满足，g̃₂要求x₁ + x₂ ≤ 3，移动限界要求x₁, x₂ ∈ [ -0.5, 0.5 ] 目标函数系数为负，应取尽可能大的x₁和x₂ 最优解：x₁* = 0.5, x₂* = 0.5 f̃(x* ) = 85 - 108×0.5 - 4×0.5 = 85 - 54 - 2 = 29 步骤2.4：计算实际改进 实际函数值：f(0.5,0.5) = (0.5-3)⁴ + (0.5-2)² = (-2.5)⁴ + (-1.5)² = 39.0625 + 2.25 = 41.3125 预测改进：Δf̃ = f̃(x⁰) - f̃(x* ) = 85 - 29 = 56 实际改进：Δf = f(x⁰) - f(x* ) = 85 - 41.3125 = 43.6875 步骤2.5：计算改进比率 ρ = Δf/Δf̃ = 43.6875/56 ≈ 0.78 步骤2.6：调整移动限界 由于ρ = 0.78 ∈ [ 0.25, 0.75 ]，改进尚可接受，保持移动限界不变 δ¹ = δ⁰ = 0.5 接受新点：x¹ = [ 0.5, 0.5 ] 3. 第二次迭代（k=1） 步骤3.1：构建近似模型 在x¹ = [ 0.5, 0.5 ]处： ∇f(0.5,0.5) = [ 4(-2.5)³, 2(-1.5)] = [ 4×(-15.625), -3] = [ -62.5, -3 ] ∇g₁(0.5,0.5) = [ 1, 1 ] ∇g₂(0.5,0.5) = [ 1, 1 ] 函数值： f(0.5,0.5) = 41.3125 g₁(0.5,0.5) = 0.25 + 0.25 - 4 = -3.5 ≤ 0 g₂(0.5,0.5) = 0.5 + 0.5 - 3 = -2 ≤ 0 步骤3.2：构建子问题 最小化 f̃(x) = 41.3125 - 62.5(x₁-0.5) - 3(x₂-0.5) 满足： g̃₁(x) = -3.5 + (x₁-0.5) + (x₂-0.5) ≤ 0 ⇒ x₁ + x₂ ≤ 4.5 g̃₂(x) = -2 + (x₁-0.5) + (x₂-0.5) ≤ 0 ⇒ x₁ + x₂ ≤ 3 移动限界：|x₁-0.5| ≤ 0.5, |x₂-0.5| ≤ 0.5 步骤3.3：求解子问题 在移动限界内x₁, x₂ ∈ [ 0, 1 ]，g̃₂要求x₁ + x₂ ≤ 3自动满足 目标函数系数为负，应取尽可能大的x₁和x₂ 最优解：x₁* = 1.0, x₂* = 1.0 f̃(x* ) = 41.3125 - 62.5×0.5 - 3×0.5 = 41.3125 - 31.25 - 1.5 = 8.5625 步骤3.4：计算实际改进 f(1.0,1.0) = (1-3)⁴ + (1-2)² = 16 + 1 = 17 Δf̃ = 41.3125 - 8.5625 = 32.75 Δf = 41.3125 - 17 = 24.3125 ρ = 24.3125/32.75 ≈ 0.74 步骤3.5：调整移动限界 ρ = 0.74 ∈ [ 0.25, 0.75 ]，保持移动限界不变 δ² = δ¹ = 0.5 接受新点：x² = [ 1.0, 1.0 ] 4. 后续迭代与收敛 继续迭代过程，算法将逐步向最优解[ 2, 1]靠近。当移动限界足够小且目标函数改进很小时，满足收敛条件‖xᵏ⁺¹ - xᵏ‖ < ε，算法终止。 5. 算法特点总结 自适应调整移动限界平衡收敛速度与稳定性 适用于中等规模非线性规划问题 对函数凸性要求不高，实用性较强 移动限界调整策略影响算法性能