序列二次规划-积极集-过滤器混合算法基础题 题目描述 ： 考虑非线性约束优化问题： minimize f(x) = (x₁ - 2)² + (x₂ - 1)² subject to: c₁(x) = x₁ - 2x₂ + 1 = 0 c₂(x) = -x₁²/4 - x₂² + 1 ≥ 0 初始点 x⁰ = (2, 2)。请使用序列二次规划-积极集-过滤器混合算法求解该问题。 解题过程 ： 1. 算法基本原理 该算法结合了SQP、积极集法和过滤器法的优点： SQP：通过求解二次规划子问题逼近原问题 积极集法：有效处理不等式约束的激活状态 过滤器法：避免传统罚函数中权重系数的选择困难 2. 算法初始化 设置初始点 x⁰ = (2, 2)，初始拉格朗日乘子 λ⁰ = (0, 0)，初始Hessian近似 B₀ = I（单位矩阵），过滤器 F = ∅。 计算初始函数值： f(x⁰) = (2-2)² + (2-1)² = 1 约束违反度：θ(x⁰) = |c₁(x⁰)| + max(0, -c₂(x⁰)) = |2-4+1| + max(0, -(-1-4+1)) = 1 + max(0, 4) = 5 3. 第一次迭代（k=0） 3.1 构建二次规划子问题 梯度计算： ∇f(x⁰) = [ 2(x₁-2), 2(x₂-1)]ᵀ = [ 0, 2 ]ᵀ ∇c₁(x⁰) = [ 1, -2 ]ᵀ ∇c₂(x⁰) = [ -x₁/2, -2x₂]ᵀ = [ -1, -4 ]ᵀ 二次规划子问题： minimize ½dᵀB₀d + ∇f(x⁰)ᵀd subject to: ∇c₁(x⁰)ᵀd + c₁(x⁰) = 0 ∇c₂(x⁰)ᵀd + c₂(x⁰) ≥ 0 代入数值： minimize ½(d₁² + d₂²) + 0·d₁ + 2·d₂ subject to: d₁ - 2d₂ + (-1) = 0 ⇒ d₁ - 2d₂ = 1 -d₁ - 4d₂ + (-1) ≥ 0 ⇒ -d₁ - 4d₂ ≥ 1 3.2 求解二次规划子问题 使用积极集法求解。初始积极集包含等式约束，检查不等式约束在解处的符号。 解得：d⁰ = (-1.4, -1.2)，拉格朗日乘子 μ⁰ = (0.8, 0) 3.3 过滤器接受检验 候选点：x₁ = x⁰ + αd⁰，尝试 α=1 x₁ = (2-1.4, 2-1.2) = (0.6, 0.8) f(x₁) = (0.6-2)² + (0.8-1)² = 1.96 + 0.04 = 2.0 θ(x₁) = |0.6-1.6+1| + max(0, -(-0.09-0.64+1)) = |0| + max(0, -0.27) = 0 检查是否被过滤器支配：∀(f,θ)∈F，需满足 f < 2.0 或 θ < 0（不成立） ∴ x₁ 可被过滤器接受，更新过滤器 F = F ∪ {(2.0, 0)} 4. 第二次迭代（k=1） 4.1 更新Hessian近似 使用BFGS公式更新 B₁： s = x₁ - x⁰ = (-1.4, -1.2) y = ∇L(x₁,μ⁰) - ∇L(x⁰,μ⁰) ≈ [ ∇f(x₁)+μ₁∇c₁(x₁)] - [ ∇f(x⁰)+μ₁∇c₁(x⁰) ] 计算得 B₁ = [ 1.2 0.3; 0.3 1.1 ]（近似值） 4.2 构建新二次规划子问题 ∇f(x₁) = [ -2.8, -0.4 ]ᵀ ∇c₁(x₁) = [ 1, -2 ]ᵀ ∇c₂(x₁) = [ -0.3, -1.6 ]ᵀ 子问题： minimize ½dᵀB₁d + [ -2.8, -0.4 ]d subject to: d₁ - 2d₂ + 0 = 0 -0.3d₁ - 1.6d₂ + 0.27 ≥ 0 4.3 求解并接受新点 解得 d¹ = (0.2, 0.1)，x₂ = (0.8, 0.9) f(x₂) = 1.69，θ(x₂) = 0.01 被过滤器接受，更新 F 5. 收敛检验 经过数次迭代后，x* ≈ (0.822, 0.911)，f(x* ) ≈ 1.393 约束满足度：|c₁(x* )| ≈ 0.000，c₂(x* ) ≈ 0.000 KKT条件满足，算法收敛。 6. 结果分析 最终解在可行域边界上，两个约束都处于活动状态。过滤器机制成功避免了罚函数权重的选择问题，同时保证了收敛性。