非线性规划中的序列二次规划-积极集-乘子法-过滤器-信赖域-自适应屏障混合算法基础题
题目描述：
考虑非线性规划问题：
minimize f(x) = (x₁ - 2)² + (x₂ - 1)²
subject to:
c₁(x) = x₁² - x₂ ≤ 0
c₂(x) = x₁ + x₂ - 2 ≤ 0
x ∈ ℝ²
要求使用序列二次规划-积极集-乘子法-过滤器-信赖域-自适应屏障混合算法求解该问题。该算法结合了SQP的局部收敛性、积极集法的约束处理效率、乘子法的全局收敛性、过滤器法的可行性控制、信赖域法的全局收敛保证以及自适应屏障法的内点特性。
解题过程：
步骤1：算法框架理解
该混合算法的核心思想是：
- 使用SQP生成搜索方向
- 用积极集法识别有效约束
- 用乘子法处理约束（将约束惩罚融入目标函数）
- 用过滤器判断步长接受性（同时考虑目标函数和约束违反度）
- 用信赖域控制步长大小
- 用自适应屏障法处理不等式约束（内点特性）
步骤2：初始化
设初始点x⁰ = (0, 0)，初始乘子估计λ⁰ = (0, 0)，初始信赖域半径Δ₀ = 0.5，初始屏障参数μ₀ = 1.0，过滤器F = ∅。
计算初始函数值：
f(x⁰) = (0-2)² + (0-1)² = 4 + 1 = 5
约束违反度：c₁(x⁰) = 0² - 0 = 0，c₂(x⁰) = 0 + 0 - 2 = -2
违反度θ(x⁰) = max(0, c₁(x⁰)) + max(0, c₂(x⁰)) = 0 + 0 = 0
步骤3：构建增广拉格朗日函数（乘子法）
L(x, λ, μ) = f(x) + Σλᵢcᵢ(x) + (μ/2)Σcᵢ(x)² - μΣln(-cᵢ(x))（屏障项）
在x⁰处：
L(x⁰, λ⁰, μ₀) = 5 + 0×0 + 0×(-2) + 0.5×(0²+(-2)²) - 1×ln(2) = 5 + 2 - 0.693 = 6.307
步骤4：构建二次规划子问题（SQP）
在x⁰处计算梯度：
∇f(x⁰) = [2(x₁-2), 2(x₂-1)] = [-4, -2]
∇c₁(x⁰) = [2x₁, -1] = [0, -1]
∇c₂(x⁰) = [1, 1]
Hessian近似（使用BFGS更新或单位矩阵）：
B⁰ = I（单位矩阵）
二次规划子问题：
minimize 0.5dᵀB⁰d + ∇f(x⁰)ᵀd
subject to:
c₁(x⁰) + ∇c₁(x⁰)ᵀd ≤ 0 → 0 + [0, -1]d ≤ 0 → -d₂ ≤ 0
c₂(x⁰) + ∇c₂(x⁰)ᵀd ≤ 0 → -2 + [1, 1]d ≤ 0 → d₁ + d₂ ≤ 2
步骤5：积极集识别
在x⁰处：
c₁(x⁰) = 0（临界有效）
c₂(x⁰) = -2 < 0（非有效）
积极集A = {1}
只考虑有效约束c₁的线性化。
步骤6：求解QP子问题
简化问题：
minimize 0.5(d₁² + d₂²) - 4d₁ - 2d₂
subject to: -d₂ ≤ 0
拉格朗日函数：L = 0.5(d₁² + d₂²) - 4d₁ - 2d₂ + μ(-d₂)
KKT条件：
∂L/∂d₁ = d₁ - 4 = 0 → d₁ = 4
∂L/∂d₂ = d₂ - 2 - μ = 0
μ(-d₂) = 0, μ ≥ 0, -d₂ ≤ 0
解得：d₁ = 4, d₂ = 0, μ = -2（不可行，违反μ≥0）
重新求解（考虑约束边界）：
在d₂ = 0时，目标函数：0.5d₁² - 4d₁
最小化得d₁ = 4
但需检查可行性：d₁ + d₂ = 4 + 0 = 4 > 2（违反c₂约束）
需同时考虑两个约束：
求解系统：
d₁ - 4 + λ₂ = 0
d₂ - 2 + λ₁(-1) + λ₂ = 0
-d₂ ≤ 0, d₁ + d₂ ≤ 2
λ₁ ≥ 0, λ₂ ≥ 0
λ₁(-d₂) = 0, λ₂(d₁ + d₂ - 2) = 0
解得：在d₁ + d₂ = 2边界上，λ₁ = 0, λ₂ = 2, d₁ = 2, d₂ = 0
步骤7：过滤器判断
试探点x₁ = x⁰ + d = (0+2, 0+0) = (2, 0)
f(x₁) = (2-2)² + (0-1)² = 0 + 1 = 1
θ(x₁) = max(0, 2²-0) + max(0, 2+0-2) = max(0,4) + 0 = 4
与当前点(f=5, θ=0)比较：
Δf = 1-5 = -4（目标改善）
Δθ = 4-0 = 4（违反度增加）
检查过滤器接受条件：
如果(f₁, θ₁)不被F中任何点支配，且满足充分下降条件，则接受。
步骤8：信赖域调整
实际改善：ΔL = L(x⁰) - L(x₁) = 6.307 - [1 + 0 + 0.5×16 - 1×ln(4)] = 6.307 - (1+8-1.386) = -1.307
预测改善：Δq = q(0) - q(d) = 0 - [0.5×(4+0) - 8 - 0] = -(-6) = 6
比值ρ = ΔL/Δq = -1.307/6 = -0.218 < 0.25
比值小于0.25，拒绝步长，缩小信赖域：Δ₁ = 0.5×Δ₀ = 0.25
步骤9：重新求解QP（缩小信赖域后）
增加信赖域约束：‖d‖ ≤ 0.25
重新求解：
minimize 0.5(d₁² + d₂²) - 4d₁ - 2d₂
subject to:
-d₂ ≤ 0
d₁ + d₂ ≤ 2
d₁² + d₂² ≤ 0.0625
在信赖域边界上寻找解，得d ≈ (0.2, 0.15)
步骤10：迭代继续
重复步骤7-9，逐步逼近解点x* = (1, 1)，其中f(x*) = 1，约束满足c₁(x*) = 0，c₂(x*) = 0。
经过多次迭代，算法会收敛到最优解，同时保持全局收敛性和约束可行性。