非线性规划中的序列二次规划-积极集-过滤器混合算法基础题 题目描述： 考虑非线性规划问题： minimize f(x) = (x₁ - 2)² + (x₂ - 1)² subject to: c₁(x) = x₁ + x₂ - 2 ≤ 0 c₂(x) = x₁² - x₂ ≤ 0 x ∈ ℝ² 这是一个带不等式约束的二次规划问题，我们需要找到在满足约束条件下的最小值点。 解题过程： 算法选择理由 这个问题适合使用序列二次规划-积极集-过滤器混合算法，因为： 目标函数是凸二次函数 约束包含线性和非线性不等式 需要同时处理可行性和最优性 过滤器方法可以避免传统罚函数中罚参数的选择问题 算法框架概述 该混合算法结合了： 序列二次规划(SQP)的局部快速收敛性 积极集策略的有效约束识别 过滤器方法的全局收敛保障 初始化 选择初始点 x⁰ = (0,0) 计算初始函数值 f(x⁰) = (0-2)² + (0-1)² = 4 + 1 = 5 检查约束违反度： θ(x⁰) = max(0, c₁(x⁰), c₂(x⁰)) = max(0, -2, 0) = 0（可行点） 初始化过滤器为空集 第一次迭代（k=0） 4.1 构建二次规划子问题 在x⁰处计算梯度： ∇f(x⁰) = [ 2(x₁-2), 2(x₂-1)] = [ -4, -2 ] 约束雅可比矩阵： A(x⁰) = [ ∇c₁(x⁰), ∇c₂(x⁰)] = [ [ 1,1], [ 0,-1] ] 二次规划子问题： minimize ½dᵀB₀d + ∇f(x⁰)ᵀd subject to: c₁(x⁰) + ∇c₁(x⁰)ᵀd ≤ 0 c₂(x⁰) + ∇c₂(x⁰)ᵀd ≤ 0 其中B₀取单位矩阵（初始Hessian近似） 4.2 求解QP子问题 代入数值： minimize ½(d₁² + d₂²) - 4d₁ - 2d₂ subject to: -2 + d₁ + d₂ ≤ 0 0 + 0·d₁ - d₂ ≤ 0 解得搜索方向 d⁰ = (1, 1) 4.3 步长选择 使用过滤器机制决定步长α 尝试α=1：x¹ = x⁰ + αd⁰ = (1, 1) f(x¹) = (1-2)² + (1-1)² = 1 + 0 = 1 θ(x¹) = max(0, 1+1-2, 1²-1) = max(0,0,0) = 0 4.4 过滤器检验 由于θ(x¹)=0（可行点）且f(x¹)=1 < f(x⁰)=5 接受该点，更新迭代：x¹ = (1,1) 第二次迭代（k=1） 5.1 构建QP子问题 ∇f(x¹) = [ 2(1-2), 2(1-1)] = [ -2, 0 ] A(x¹) = [ [ 1,1], [ 2x₁,-1]] = [ [ 1,1], [ 2,-1] ] QP子问题： minimize ½dᵀB₁d - 2d₁ subject to: 0 + d₁ + d₂ ≤ 0 0 + 2d₁ - d₂ ≤ 0 5.2 识别积极集 在x¹处，两个约束都处于边界（c₁(x¹)=0, c₂(x¹)=0） 因此两个约束都是积极的 5.3 求解QP子问题 使用积极集法求解，得到d¹ = (0.2, -0.2) 5.4 步长选择 尝试α=1：x² = (1.2, 0.8) f(x²) = (1.2-2)² + (0.8-1)² = 0.64 + 0.04 = 0.68 θ(x²) = max(0, 1.2+0.8-2, 1.2²-0.8) = max(0,0,0.64) = 0.64 由于θ(x²)>0，需要减小步长或使用过滤器 收敛检查 经过数次迭代后，算法收敛到最优解x* ≈ (1.5, 0.5) f(x* ) = 0.5，满足KKT条件 所有约束在最优解处都是积极的 这个混合算法通过结合SQP的快速局部收敛、积极集法的有效约束处理以及过滤器的全局收敛保障，有效地解决了这个非线性规划问题。