非线性规划中的序列凸近似信赖域法进阶题 题目描述 考虑非线性规划问题： 最小化 f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² 满足约束条件： g₁(x) = x₁² - x₂ ≤ 0 g₂(x) = -x₁ ≤ 0 g₃(x) = -x₂ ≤ 0 初始点 x⁰ = [ 0.0, 0.5 ]ᵀ，信赖域半径初始值 Δ₀ = 0.5。请使用序列凸近似信赖域法进行两次迭代，详细展示每次迭代的凸近似子问题构建、求解过程及信赖域调整策略。 解题过程 第一步：理解算法框架 序列凸近似信赖域法（Sequential Convex Approximation Trust Region, SCATR）的核心思想是：在每次迭代点，将原非凸问题用凸函数局部近似，并在信赖域内求解这个凸子问题。关键步骤包括： 构建凸近似模型（目标函数和约束的凸化） 求解凸信赖域子问题 评估近似质量并调整信赖域半径 第二步：第一次迭代（k=0） 1. 当前迭代点与函数值 x⁰ = [ 0.0, 0.5 ]ᵀ f(x⁰) = (0-2)⁴ + (0-2×0.5)² = 16 + (-1)² = 17 g₁(x⁰) = 0² - 0.5 = -0.5 ≤ 0（可行） g₂(x⁰) = -0 = 0 ≤ 0（边界可行） g₃(x⁰) = -0.5 = -0.5 ≤ 0（可行） 2. 计算梯度（用于凸近似） ∇f(x) = [ 4(x₁-2)³ + 2(x₁-2x₂), -4(x₁-2x₂) ]ᵀ ∇f(x⁰) = [ 4(-2)³ + 2(0-1), -4(0-1)]ᵀ = [ 4×(-8) + 2×(-1), 4]ᵀ = [ -32-2, 4]ᵀ = [ -34, 4 ]ᵀ ∇g₁(x) = [ 2x₁, -1 ]ᵀ ∇g₁(x⁰) = [ 0, -1 ]ᵀ 3. 构建凸近似子问题 采用一阶泰勒展开进行凸线性化： 近似目标函数： f̃(x) ≈ f(x⁰) + ∇f(x⁰)ᵀ(x - x⁰) = 17 + [ -34, 4]·[ x₁-0, x₂-0.5 ]ᵀ = 17 -34x₁ + 4(x₂ - 0.5) = 17 -34x₁ + 4x₂ - 2 = 15 -34x₁ + 4x₂ 近似约束（同样线性化）： g̃₁(x) ≈ g₁(x⁰) + ∇g₁(x⁰)ᵀ(x - x⁰) = -0.5 + [ 0, -1]·[ x₁-0, x₂-0.5 ]ᵀ = -0.5 - (x₂ - 0.5) = -0.5 - x₂ + 0.5 = -x₂ g₂(x) = -x₁（本身线性，保持不变） g₃(x) = -x₂（本身线性，保持不变） 凸子问题： 最小化 f̃(x) = 15 -34x₁ + 4x₂ 满足： g̃₁(x) = -x₂ ≤ 0 g₂(x) = -x₁ ≤ 0 g₃(x) = -x₂ ≤ 0 ||x - x⁰||∞ ≤ Δ₀ = 0.5（信赖域约束，∞-范数便于线性化） 4. 求解凸子问题 这是一个线性规划问题： 目标函数系数：x₁系数-34（负，应最大化x₁），x₂系数+4（正，应最小化x₂） 约束分析： g̃₁(x): -x₂ ≤ 0 ⇒ x₂ ≥ 0 g₂(x): -x₁ ≤ 0 ⇒ x₁ ≥ 0 g₃(x): -x₂ ≤ 0 ⇒ x₂ ≥ 0（与g̃₁重复） 信赖域：|x₁-0| ≤ 0.5 ⇒ 0 ≤ x₁ ≤ 0.5 |x₂-0.5| ≤ 0.5 ⇒ 0 ≤ x₂ ≤ 1 最优解：在x₁最大、x₂最小处取得，即x₁ = 0.5, x₂ = 0 候选点 x̂¹ = [ 0.5, 0.0 ]ᵀ 5. 评估近似质量并调整信赖域 实际下降量：Δf_ actual = f(x⁰) - f(x̂¹) f(x̂¹) = (0.5-2)⁴ + (0.5-0)² = (-1.5)⁴ + (0.5)² = 5.0625 + 0.25 = 5.3125 Δf_ actual = 17 - 5.3125 = 11.6875 预测下降量：Δf_ pred = f̃(x⁰) - f̃(x̂¹) f̃(x̂¹) = 15 -34×0.5 + 4×0 = 15 - 17 + 0 = -2 Δf_ pred = 15 - (-2) = 17 近似比率：ρ = Δf_ actual / Δf_ pred = 11.6875 / 17 ≈ 0.6875 信赖域调整： ρ ≈ 0.69 ∈ [ 0.25, 0.75)，近似质量一般，保持信赖域半径不变 Δ₁ = Δ₀ = 0.5 由于ρ > 0，接受该步：x¹ = x̂¹ = [ 0.5, 0.0 ]ᵀ 第三步：第二次迭代（k=1） 1. 当前迭代点与函数值 x¹ = [ 0.5, 0.0 ]ᵀ f(x¹) = 5.3125 g₁(x¹) = 0.5² - 0 = 0.25 > 0（不可行！需要处理） 2. 约束违反处理 由于g₁(x¹) > 0，当前点不可行。序列凸近似法通常要求子问题严格可行，因此需要恢复可行性。 方法：在构建子问题时，对违反的约束进行严格凸化，并添加可行性恢复项或使用过滤法。这里采用保守凸化：对g₁(x)在x¹处线性化，但要求g̃₁(x) ≤ -ε（ε>0小量）确保严格可行。 3. 计算梯度 ∇f(x¹) = [ 4(0.5-2)³ + 2(0.5-0), -4(0.5-0) ]ᵀ = [ 4×(-1.5)³ + 2×0.5, -4×0.5 ]ᵀ = [ 4×(-3.375) + 1, -2 ]ᵀ = [ -13.5 + 1, -2]ᵀ = [ -12.5, -2 ]ᵀ ∇g₁(x¹) = [ 2×0.5, -1]ᵀ = [ 1, -1 ]ᵀ 4. 构建凸近似子问题（含可行性恢复） 目标函数近似： f̃(x) ≈ f(x¹) + ∇f(x¹)ᵀ(x - x¹) = 5.3125 + [ -12.5, -2]·[ x₁-0.5, x₂-0 ]ᵀ = 5.3125 -12.5(x₁-0.5) -2x₂ = 5.3125 -12.5x₁ + 6.25 -2x₂ = 11.5625 -12.5x₁ -2x₂ 约束近似（严格可行化）： g̃₁(x) ≈ g₁(x¹) + ∇g₁(x¹)ᵀ(x - x¹) ≤ -0.1 0.25 + [ 1, -1]·[ x₁-0.5, x₂-0 ]ᵀ ≤ -0.1 0.25 + (x₁-0.5) - x₂ ≤ -0.1 x₁ - x₂ -0.25 ≤ -0.1 x₁ - x₂ ≤ 0.15 其他约束不变： g₂(x) = -x₁ ≤ 0 g₃(x) = -x₂ ≤ 0 ||x - x¹||∞ ≤ Δ₁ = 0.5 5. 求解凸子问题 线性规划： 最小化 11.5625 -12.5x₁ -2x₂ 约束： x₁ - x₂ ≤ 0.15 x₁ ≥ 0, x₂ ≥ 0 0 ≤ x₁ ≤ 1.0, 0 ≤ x₂ ≤ 0.5（信赖域边界） 目标函数系数：x₁系数-12.5，x₂系数-2，都应最大化x₁和x₂ 但受x₁ - x₂ ≤ 0.15限制 最优解在约束边界取得：令x₁ - x₂ = 0.15，且x₁尽可能大 同时x₂ = x₁ - 0.15，需满足x₂ ≥ 0 ⇒ x₁ ≥ 0.15 在信赖域内最大x₁为1.0，此时x₂ = 1.0 - 0.15 = 0.85，但x₂上限为0.5 所以取x₂ = 0.5，则x₁ = 0.5 + 0.15 = 0.65 检查信赖域：|0.65-0.5|=0.15≤0.5, |0.5-0|=0.5≤0.5，可行 x̂² = [ 0.65, 0.5 ]ᵀ 6. 评估近似质量与更新 f(x̂²) = (0.65-2)⁴ + (0.65-2×0.5)² = (-1.35)⁴ + (0.65-1)² = 3.32 + (-0.35)² = 3.32 + 0.1225 = 3.4425 f̃(x̂²) = 11.5625 -12.5×0.65 -2×0.5 = 11.5625 - 8.125 - 1 = 2.4375 Δf_ actual = f(x¹) - f(x̂²) = 5.3125 - 3.4425 = 1.87 Δf_ pred = f̃(x¹) - f̃(x̂²) = 11.5625 - 2.4375 = 9.125 ρ = 1.87 / 9.125 ≈ 0.205 ρ < 0.25，近似质量差，拒绝该步，缩小信赖域： Δ₂ = 0.5 × Δ₁ = 0.25 x² = x¹ = [ 0.5, 0.0 ]ᵀ（保持原迭代点） 算法总结 经过两次迭代，当前最优解为[ 0.5, 0.0 ]ᵀ，函数值5.3125。由于第二次迭代近似质量不佳，信赖域半径缩小至0.25，需要在更小邻域内构建更精确的凸近似。序列凸近似信赖域法通过这种自适应调整机制，能有效平衡收敛速度和近似精度。