非线性规划中的序列凸近似信赖域法进阶题 题目描述： 考虑非线性规划问题： 最小化 f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² 满足约束条件： g₁(x) = x₁² - x₂ ≤ 0 g₂(x) = -x₁ ≤ 0 g₃(x) = -x₂ ≤ 0 要求使用序列凸近似信赖域法求解该问题，初始点x⁽⁰⁾ = [ 0, 1 ]，初始信赖域半径Δ₀ = 0.5，收敛容差ε = 10⁻⁶。 解题过程： 第一步：理解序列凸近似信赖域法的基本原理 序列凸近似信赖域法结合了两种重要思想： 序列凸近似：在每次迭代中，将非凸函数在当前点附近用凸函数近似 信赖域：限制步长大小，确保近似模型在局部区域内有效 算法流程： 在当前点构造原问题的凸近似 在信赖域内求解近似子问题 根据实际下降量与预测下降量的比值调整信赖域半径 重复直到收敛 第二步：第一次迭代（k=0） 初始点：x⁽⁰⁾ = [ 0, 1 ] 初始信赖域半径：Δ₀ = 0.5 2.1 计算函数值和梯度 目标函数f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² 梯度∇f(x) = [ 4(x₁ - 2)³ + 2(x₁ - 2x₂), -4(x₁ - 2x₂) ] 在x⁽⁰⁾处： f(x⁽⁰⁾) = (0-2)⁴ + (0-2×1)² = 16 + 4 = 20 ∇f(x⁽⁰⁾) = [ 4(0-2)³ + 2(0-2), -4(0-2)] = [ 4×(-8) + 2×(-2), 8] = [ -32 - 4, 8] = [ -36, 8 ] 约束函数： g₁(x) = x₁² - x₂，梯度∇g₁(x) = [ 2x₁, -1 ] g₂(x) = -x₁，梯度∇g₂(x) = [ -1, 0 ] g₃(x) = -x₂，梯度∇g₃(x) = [ 0, -1 ] 在x⁽⁰⁾处： g₁(x⁽⁰⁾) = 0² - 1 = -1 ≤ 0（满足） g₂(x⁽⁰⁾) = -0 = 0 ≤ 0（边界） g₃(x⁽⁰⁾) = -1 = -1 ≤ 0（满足） 2.2 构造凸近似子问题 使用一阶泰勒展开构造线性近似： f̃(d) ≈ f(x⁽⁰⁾) + ∇f(x⁽⁰⁾)ᵀd = 20 + [ -36, 8]·[ d₁, d₂ ] = 20 - 36d₁ + 8d₂ 约束的线性近似： g̃₁(d) ≈ g₁(x⁽⁰⁾) + ∇g₁(x⁽⁰⁾)ᵀd = -1 + [ 0, -1]·[ d₁, d₂ ] = -1 - d₂ ≤ 0 g̃₂(d) ≈ g₂(x⁽⁰⁾) + ∇g₂(x⁽⁰⁾)ᵀd = 0 + [ -1, 0]·[ d₁, d₂ ] = -d₁ ≤ 0 g̃₃(d) ≈ g₃(x⁽⁰⁾) + ∇g₃(x⁽⁰⁾)ᵀd = -1 + [ 0, -1]·[ d₁, d₂ ] = -1 - d₂ ≤ 0 信赖域约束：‖d‖₂ ≤ Δ₀ = 0.5 2.3 求解凸近似子问题 子问题为线性规划： 最小化 20 - 36d₁ + 8d₂ 满足： -d₂ ≤ 1 -d₁ ≤ 0 -d₂ ≤ 1 d₁² + d₂² ≤ 0.25 由于目标函数中d₁系数为负且绝对值大，应使d₁尽可能大，d₂尽可能小。 在信赖域约束下，最优解在边界上：d₁ = 0.5, d₂ = 0 验证约束：-d₂ = 0 ≤ 1 ✓，-d₁ = -0.5 ≤ 0 ✓，-d₂ = 0 ≤ 1 ✓ 2.4 计算实际下降比 候选点：x⁽ᶜᵃⁿᵈ⁾ = x⁽⁰⁾ + d = [ 0, 1] + [ 0.5, 0] = [ 0.5, 1 ] 实际函数值：f(x⁽ᶜᵃⁿᵈ⁾) = (0.5-2)⁴ + (0.5-2)² = (-1.5)⁴ + (-1.5)² = 5.0625 + 2.25 = 7.3125 实际下降：ared = f(x⁽⁰⁾) - f(x⁽ᶜᵃⁿᵈ⁾) = 20 - 7.3125 = 12.6875 预测下降：pred = f(x⁽⁰⁾) - f̃(d) = 20 - (20 - 36×0.5 + 8×0) = 20 - (20 - 18) = 18 下降比：ρ = ared/pred = 12.6875/18 ≈ 0.705 2.5 更新迭代点和信赖域半径 由于ρ > 0.25，接受该步：x⁽¹⁾ = x⁽ᶜᵃⁿᵈ⁾ = [ 0.5, 1 ] 由于ρ ≈ 0.705 ∈ [ 0.25, 0.75 ]，保持信赖域半径：Δ₁ = Δ₀ = 0.5 第三步：第二次迭代（k=1） 当前点：x⁽¹⁾ = [ 0.5, 1 ] 3.1 计算函数值和梯度 f(x⁽¹⁾) = 7.3125（已计算） ∇f(x⁽¹⁾) = [ 4(0.5-2)³ + 2(0.5-2), -4(0.5-2)] = [ 4×(-1.5)³ + 2×(-1.5), 6] = [ 4×(-3.375) - 3, 6] = [ -13.5 - 3, 6] = [ -16.5, 6 ] 约束函数值： g₁(x⁽¹⁾) = 0.5² - 1 = 0.25 - 1 = -0.75 ≤ 0 g₂(x⁽¹⁾) = -0.5 = -0.5 ≤ 0 g₃(x⁽¹⁾) = -1 = -1 ≤ 0 3.2 构造凸近似子问题 f̃(d) ≈ 7.3125 + [ -16.5, 6]·[ d₁, d₂ ] = 7.3125 - 16.5d₁ + 6d₂ 约束近似： g̃₁(d) ≈ -0.75 + [ 1, -1]·[ d₁, d₂ ] = -0.75 + d₁ - d₂ ≤ 0 g̃₂(d) ≈ -0.5 + [ -1, 0]·[ d₁, d₂ ] = -0.5 - d₁ ≤ 0 g̃₃(d) ≈ -1 + [ 0, -1]·[ d₁, d₂ ] = -1 - d₂ ≤ 0 信赖域约束：‖d‖₂ ≤ 0.5 3.3 求解凸近似子问题 最小化 7.3125 - 16.5d₁ + 6d₂ 满足： d₁ - d₂ ≤ 0.75 -d₁ ≤ 0.5 -d₂ ≤ 1 d₁² + d₂² ≤ 0.25 目标函数中d₁系数为负，应使d₁尽可能大。约束分析表明d₁最大可取0.5，此时d₂=0满足所有约束。 最优解：d = [ 0.5, 0 ] 3.4 计算实际下降比 候选点：x⁽ᶜᵃⁿᵈ⁾ = [ 0.5, 1] + [ 0.5, 0] = [ 1, 1 ] 实际函数值：f(x⁽ᶜᵃⁿᵈ⁾) = (1-2)⁴ + (1-2)² = 1 + 1 = 2 实际下降：ared = 7.3125 - 2 = 5.3125 预测下降：pred = 7.3125 - (7.3125 - 16.5×0.5 + 6×0) = 16.5×0.5 = 8.25 下降比：ρ = 5.3125/8.25 ≈ 0.644 3.5 更新迭代点和信赖域半径 接受该步：x⁽²⁾ = [ 1, 1 ] 保持信赖域半径：Δ₂ = 0.5 第四步：后续迭代和收敛分析 继续迭代过程，算法将向最优解[ 2, 1 ]收敛。在最优解处： 目标函数值f* = (2-2)⁴ + (2-2)² = 0 约束g₁(2,1) = 4-1=3>0（违反），但其他约束满足 实际最优解在约束边界上，需要通过拉格朗日乘子法确定 收敛条件：当‖d‖ < ε 或 |f(x⁽ᵏ⁺¹⁾) - f(x⁽ᵏ⁾)| < ε 时停止。 序列凸近似信赖域法通过交替进行凸近似和信赖域搜索，能有效处理非凸约束优化问题，保证全局收敛性。