非线性规划中的序列二次规划-乘子法-积极集-过滤器-信赖域-自适应屏障-代理模型-梯度投影混合算法基础题

题目描述
考虑非线性约束优化问题：
minimize f(x) = (x₁ - 2)² + (x₂ - 1)²
subject to:
c₁(x) = x₁² - x₂ ≤ 0
c₂(x) = x₁ + x₂ - 2 ≤ 0
其中 x ∈ ℝ²。要求设计一种混合算法，结合序列二次规划（SQP）、乘子法、积极集策略、过滤器方法、信赖域框架、自适应屏障函数、代理模型和梯度投影技术，在初始点 x⁰ = (0, 0) 处开始迭代，逐步收敛到满足约束的局部最优解。

解题过程

1. 初始化

   • 设置初始点 x⁰ = (0, 0)，拉格朗日乘子 λ⁰ = (0, 0)，信赖域半径 Δ₀ = 0.5，屏障参数 μ₀ = 1.0，过滤器集合 F 为空。
   • 计算初始目标函数值 f(x⁰) = (0-2)² + (0-1)² = 5，约束违反度 θ(x⁰) = max(0, c₁(x⁰), c₂(x⁰)) = max(0, 0, -2) = 0。

2. 构建代理模型

   • 在当前点 xᵏ 处，利用一阶泰勒展开近似目标函数和约束：
     f̃(d) ≈ f(xᵏ) + ∇f(xᵏ)ᵀd
     c̃₁(d) ≈ c₁(xᵏ) + ∇c₁(xᵏ)ᵀd
     c̃₂(d) ≈ c₂(xᵏ) + ∇c₂(xᵏ)ᵀd
     其中 d = x - xᵏ 为搜索方向。
   • 例如在 x⁰ 处：
     ∇f(x⁰) = (2(0-2), 2(0-1)) = (-4, -2)
     ∇c₁(x⁰) = (2×0, -1) = (0, -1)
     ∇c₂(x⁰) = (1, 1)
     故 f̃(d) = 5 - 4d₁ - 2d₂, c̃₁(d) = 0 + 0·d₁ - 1·d₂, c̃₂(d) = -2 + d₁ + d₂。

3. 定义自适应屏障函数

   • 将约束转化为屏障项：
     B(x; μ) = f(x) - μ∑ᵢ ln(-cᵢ(x))
     但仅对违反约束或接近边界的约束使用屏障（自适应选择），其他约束保留在积极集中。

4. 求解子问题（混合策略）

   • 积极集识别：检查约束违反度，若 |cᵢ(xᵏ)| < ε（如 ε=0.01），则标记为积极约束。
   • 乘子更新：对非积极约束，使用乘子法松弛；对积极约束，在子问题中严格满足。
   • 信赖域框架：求解以下二次规划子问题：
     minimize ∇f(xᵏ)ᵀd + ½dᵀHᵏd
     subject to:
     cᵢ(xᵏ) + ∇cᵢ(xᵏ)ᵀd = 0（积极约束）
     cᵢ(xᵏ) + ∇cᵢ(xᵏ)ᵀd ≤ 0（非积极约束）
     ||d|| ≤ Δᵏ
     其中 Hᵏ 为拉格朗日函数 Hessian 的近似（初始设为单位矩阵）。

5. 过滤器判断

   • 计算 trial 点 xᵗʳᵅᶦˡ = xᵏ + d。
   • 若 (f(xᵗʳᵅᶦˡ), θ(xᵗʳᵅᶦˡ)) 不被过滤器 F 中的任何点支配（即不同时有 f ≥ fⱼ 且 θ ≥ θⱼ 对所有 j 成立），则接受该点，并加入过滤器。
   • 否则，缩小信赖域半径 Δᵏ 或调整屏障参数 μ，重新求解子问题。

6. 梯度投影修正

   • 若 trial 点违反约束，沿约束边界投影：
     xᵏ⁺¹ = P(xᵗʳᵅᶦˡ) = xᵗʳᵅᶦˡ - Aᵀ(AAᵀ)⁻¹(Axᵗʳᵅᶦˡ - b)
     其中 A 为积极约束的梯度矩阵，b 为对应边界值。

7. 参数更新

   • 若迭代成功，更新乘子 λ 和屏障参数 μ（如 μᵏ⁺¹ = 0.7μᵏ）。
   • 调整信赖域半径：根据实际下降与预测下降的比率 ρ 扩大或缩小 Δ。

8. 收敛检查

   • 重复步骤 2–7 直至 ||∇L(xᵏ, λᵏ)|| < 1e-6 且 θ(xᵏ) < 1e-6。

示例迭代（第一轮）

• 在 x⁰ = (0,0)，求解 QP 子问题得 d ≈ (0.3, 0.3)，xᵗʳᵅᶦˡ = (0.3, 0.3)。
• θ(xᵗʳᵅᶦˡ) = max(0, 0.09-0.3, 0.3+0.3-2) = 0，f 下降至 4.42，被过滤器接受。
• 更新乘子，进入下一轮迭代，最终收敛至最优解 x* ≈ (1, 1)。