非线性规划中的自适应信赖域序列二次规划(Adaptive Trust Region SQP)算法进阶题

问题描述
考虑非线性规划问题：
min f(x)
s.t. cᵢ(x) = 0, i∈ε
  cᵢ(x) ≥ 0, i∈ℐ
其中f(x)和cᵢ(x)均为二阶连续可导函数。现有标准信赖域序列二次规划(TR-SQP)在迭代过程中采用固定信赖域半径更新策略，导致在非光滑区域收敛缓慢。现要求设计自适应信赖域半径更新策略，在迭代中根据模型近似精度动态调整半径，并给出完整算法流程。

解题过程

1. 构造拉格朗日函数与二次规划子问题
   定义拉格朗日函数：
   L(x,λ) = f(x) - ∑λᵢcᵢ(x)
   在第k次迭代点xₖ处，求解二次规划子问题：
   min ∇fₖᵀd + ½dᵀBₖd
   s.t. cᵢ(xₖ) + ∇cᵢ(xₖ)ᵀd = 0, i∈ε
     cᵢ(xₖ) + ∇cᵢ(xₖ)ᵀd ≥ 0, i∈ℐ
     ‖d‖ ≤ Δₖ
   其中Bₖ为拉格朗日函数Hessian近似，Δₖ为当前信赖域半径。

2. 计算实际下降量与预测下降量比值
   定义实际下降量：
   Aredₖ = f(xₖ) - f(xₖ + dₖ) + ∑μᵢ|cᵢ(xₖ) - cᵢ(xₖ + dₖ)|
   预测下降量：
   Predₖ = -∇fₖᵀdₖ - ½dₖᵀBₖdₖ + ∑μᵢ|cᵢ(xₖ)|
   其中μᵢ为罚参数。计算比值：
   ρₖ = Aredₖ / Predₖ

3. 设计自适应半径更新策略
   传统方法采用固定比例调整：
   Δₖ₊₁ = { ½Δₖ, ρₖ < 0.25; 2Δₖ, ρₖ > 0.75 }
   改进为自适应策略：

   • 当ρₖ < 0.1时，说明模型近似差，取Δₖ₊₁ = 0.5‖dₖ‖
   • 当0.1 ≤ ρₖ < 0.5时，采用插值调整：Δₖ₊₁ = (0.5 + ρₖ)‖dₖ‖
   • 当ρₖ ≥ 0.5时，若‖dₖ‖ = Δₖ则取Δₖ₊₁ = 2Δₖ，否则保持Δₖ₊₁ = Δₖ

4. 引入曲率感知机制
   计算条件数估计值κ(Bₖ)，当κ(Bₖ) > 10⁶时判定为病态问题，此时：

   • 在半径更新中引入修正因子η = min(1, 10³/κ(Bₖ))
   • 实际更新公式修正为Δₖ₊₁ = η·Δₖ₊₁

5. 算法实现步骤
   (1) 初始化x₀, Δ₀ > 0, B₀ = I, 容差ε
   (2) 循环直到‖∇Lₖ‖ < ε：
    a. 求解当前QP子问题得dₖ
    b. 计算ρₖ = Aredₖ/Predₖ
    c. 采用自适应策略更新Δₖ₊₁
    d. 若ρₖ > 0.1则接受步长xₖ₊₁ = xₖ + dₖ
    e. 用BFGS公式更新Bₖ₊₁

6. 收敛性分析
   在自适应策略下需证明：

   • 当迭代点远离最优解时，Δₖ有下界防止过早收缩
   • 在最优解附近时，Δₖ趋于零保证超线性收敛
     关键引理：存在常数δ>0，使得当‖dₖ‖ < δ时必有ρₖ > 0.5

算法特点

1. 通过ρₖ的连续值进行插值调整，比传统三区间策略更平滑
2. 曲率感知机制避免病态问题下的震荡
3. 收敛速度从传统超线性提升至二阶收敛（当Bₖ精确计算Hessian时）