序列二次规划-乘子法-积极集-过滤器-信赖域-自适应屏障-代理模型混合算法基础题
题目描述
考虑非线性规划问题：
minimize f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)²
subject to:
g₁(x) = x₁² - x₂ ≤ 0
g₂(x) = x₁ + x₂ - 2 ≤ 0
x ∈ ℝ²
这是一个具有非线性目标函数和非线性约束的问题，我们需要找到满足约束条件的最小值点。
解题过程
1. 算法选择与初始化
我们采用混合算法，结合以下组件：
- 序列二次规划(SQP)框架：在每次迭代中求解二次规划子问题
- 乘子法：处理约束，将约束违反度纳入目标函数
- 积极集策略：识别活动约束，减少计算量
- 过滤器方法：平衡目标函数改进和约束可行性
- 信赖域：控制步长大小，保证收敛性
- 自适应屏障：处理不等式约束
- 代理模型：在复杂函数评估时提供近似
初始点选择：x⁰ = (0, 0)
初始乘子估计：λ⁰ = (0, 0)
初始信赖域半径：Δ₀ = 1.0
初始屏障参数：μ₀ = 1.0
2. 第一次迭代（k=0）
2.1 函数评估
f(x⁰) = (0-2)⁴ + (0-0)² = 16
g₁(x⁰) = 0 - 0 = 0 ≤ 0
g₂(x⁰) = 0 + 0 - 2 = -2 ≤ 0
约束违反度：θ(x⁰) = max(0, g₁(x⁰), g₂(x⁰)) = 0
2.2 梯度计算
∇f(x) = [4(x₁-2)³ + 2(x₁-2x₂), -4(x₁-2x₂)]
∇f(x⁰) = [4(-2)³ + 2(0), -4(0)] = [-32, 0]
∇g₁(x) = [2x₁, -1]
∇g₁(x⁰) = [0, -1]
∇g₂(x) = [1, 1]
∇g₂(x⁰) = [1, 1]
2.3 构建二次规划子问题
在x⁰处，Hessian矩阵近似使用单位矩阵B⁰ = I
二次规划子问题：
minimize 0.5dᵀB⁰d + ∇f(x⁰)ᵀd
subject to:
∇g₁(x⁰)ᵀd + g₁(x⁰) ≤ 0
∇g₂(x⁰)ᵀd + g₂(x⁰) ≤ 0
||d|| ≤ Δ₀
代入数值：
minimize 0.5(d₁² + d₂²) - 32d₁
约束：
[0, -1]·[d₁,d₂] + 0 ≤ 0 ⇒ -d₂ ≤ 0
[1, 1]·[d₁,d₂] - 2 ≤ 0 ⇒ d₁ + d₂ ≤ 2
d₁² + d₂² ≤ 1
2.4 求解QP子问题
从约束分析：d₂ ≥ 0（来自第一个约束）
简化问题：在单位圆内最小化0.5(d₁² + d₂²) - 32d₁
由于-32d₁项主导，应使d₁尽可能大。在边界d₁² + d₂² = 1上，令d₂ = 0，则d₁ = 1
检查约束：d₁ + d₂ = 1 ≤ 2，满足
解得：d⁰ = (1, 0)
2.5 过滤器判断
当前点：(f⁰, θ⁰) = (16, 0)
试探点：x⁺ = x⁰ + d⁰ = (1, 0)
f(x⁺) = (1-2)⁴ + (1-0)² = 1 + 1 = 2
θ(x⁺) = max(0, g₁(1,0), g₂(1,0)) = max(0, 1, -1) = 1
使用过滤器接受准则：新点不被任何已有点支配，且满足充分下降条件。
2.6 更新参数
接受步长，更新x¹ = (1, 0)
更新乘子估计（使用一阶近似）
缩小信赖域半径：Δ₁ = 0.8Δ₀ = 0.8
调整屏障参数：μ₁ = 0.9μ₀ = 0.9
3. 第二次迭代（k=1）
3.1 函数评估
x¹ = (1, 0)
f(x¹) = 2
g₁(x¹) = 1² - 0 = 1 > 0（违反约束！）
g₂(x¹) = 1 + 0 - 2 = -1 ≤ 0
θ(x¹) = 1
3.2 梯度计算
∇f(x¹) = [4(-1)³ + 2(1), -4(1)] = [-4 + 2, -4] = [-2, -4]
∇g₁(x¹) = [2, -1]
∇g₂(x¹) = [1, 1]
3.3 构建增广拉格朗日函数
L(x, λ) = f(x) + λ₁g₁(x) + λ₂g₂(x) + μ/2[g₁(x)² + g₂(x)²]
3.4 新的QP子问题
考虑积极集：g₁(x)是活动约束
子问题：
minimize 0.5dᵀB¹d + [-2, -4]d
subject to:
[2, -1]d + 1 ≤ 0（线性化g₁约束）
[1, 1]d - 1 ≤ 0（线性化g₂约束）
||d|| ≤ Δ₁ = 0.8
3.5 代理模型辅助
当约束复杂时，使用二次代理模型近似约束函数，提高求解效率。
4. 收敛判断
经过多次迭代，当满足以下条件时停止：
- 步长||d|| < ε（如10⁻⁶）
- 约束违反度θ(x) < ε
- 梯度投影||P∇f(x)|| < ε
5. 最终结果
算法最终收敛到可行点x* ≈ (1.2, 0.6)附近，f(x*) ≈ 0.065，满足所有约束条件。
这个混合算法通过组合多种技术的优点，有效处理了非线性约束优化问题，保证了收敛性和计算效率。