非线性规划中的序列二次规划-积极集-乘子法-过滤器-信赖域混合算法基础题 题目描述 考虑非线性规划问题： minimize f(x) = (x₁ - 2)² + (x₂ - 1)² subject to: c₁(x) = x₁² - x₂ ≤ 0 c₂(x) = x₁ + x₂ - 2 ≤ 0 x₀ = (0, 0)ᵀ 这是一个具有二次目标函数和二次/线性不等式约束的优化问题。要求使用序列二次规划-积极集-乘子法-过滤器-信赖域混合算法求解。 算法原理 该混合算法结合了多种技术的优势： 序列二次规划(SQP)提供快速局部收敛 积极集策略有效处理约束 乘子法改善约束违反惩罚 过滤器技术避免罚参数选择困难 信赖域保证子问题可解性和全局收敛 解题步骤 步骤1：算法初始化 设置初始点x₀ = (0, 0)ᵀ，初始乘子估计μ₀ = (0, 0)ᵀ，初始信赖域半径Δ₀ = 0.5，过滤器F = ∅，惩罚参数τ = 10，收敛容忍度ε = 10⁻⁶。 计算初始函数值f(x₀) = (0-2)² + (0-1)² = 5，约束违反度θ(x₀) = max(0, c₁(x₀), c₂(x₀)) = max(0, 0-0, 0+0-2) = 0。 步骤2：构建增广拉格朗日函数 L(x, μ) = f(x) + Σμᵢcᵢ(x) + (τ/2)Σ[ cᵢ(x) ]² 在x₀处，c₁(x₀) = 0，c₂(x₀) = -2，因此： L(x₀, μ₀) = 5 + 0×0 + 0×(-2) + 5×(0² + (-2)²) = 5 + 20 = 25 步骤3：识别积极约束集 A(x) = {i | cᵢ(x) ≥ -ε或μᵢ > 0} 在x₀处，c₁(x₀) = 0 ≥ -10⁻⁶，c₂(x₀) = -2 < -10⁻⁶，因此积极集A = {1}。 步骤4：构建二次规划子问题 min ∇f(x₀)ᵀd + ½dᵀB₀d subject to: ∇c₁(x₀)ᵀd + c₁(x₀) ≤ 0 ∇c₂(x₀)ᵀd + c₂(x₀) ≤ 0 ‖d‖ ≤ Δ₀ 计算∇f(x₀) = (2(x₁-2), 2(x₂-1))|ₓ₌₀ = (-4, -2) ∇c₁(x₀) = (2x₁, -1)|ₓ₌₀ = (0, -1) ∇c₂(x₀) = (1, 1) B₀取单位矩阵I 子问题变为： min (-4, -2)ᵀd + ½dᵀId subject to: (0, -1)ᵀd + 0 ≤ 0 → -d₂ ≤ 0 (1, 1)ᵀd - 2 ≤ 0 → d₁ + d₂ ≤ 2 d₁² + d₂² ≤ 0.25 步骤5：求解二次规划子问题 通过积极集法求解该QP。约束-d₂ ≤ 0意味着d₂ ≥ 0，结合信赖域约束，得到解d₀ ≈ (0.35, 0.35)，在信赖域边界上。 步骤6：过滤器接受检验 计算候选点x₁ = x₀ + d₀ = (0.35, 0.35) f(x₁) = (0.35-2)² + (0.35-1)² ≈ 2.72 + 0.42 = 3.14 θ(x₁) = max(0, 0.35²-0.35, 0.35+0.35-2) = max(0, -0.23, -1.3) = 0 检查(x₁)是否被过滤器F支配：∀(f, θ) ∈ F, f < 3.14或θ < 0。由于F为空，接受该点。 步骤7：更新乘子估计 使用QP子问题的乘子解更新： μ₁ᵏ⁺¹ = max(0, μ₁ᵏ + τc₁(x₁)) = max(0, 0 + 10×(-0.23)) = 0 μ₂ᵏ⁺¹ = max(0, μ₂ᵏ + τc₂(x₁)) = max(0, 0 + 10×(-1.3)) = 0 步骤8：收敛检验 计算KKT条件违反度：‖∇f(x₁) + μ₁∇c₁(x₁) + μ₂∇c₂(x₁)‖ ≈ 3.2 > ε，未收敛。 步骤9：迭代继续 重复步骤2-8，在x₁处构建新的QP子问题，直到满足收敛条件‖∇L(x, μ)‖ < ε且θ(x) < ε。 经过约5次迭代后，算法收敛到最优解x* ≈ (1.0, 1.0)，f(x* ) = 1.0，满足所有约束。