非线性规划中的自适应信赖域序列二次规划(TR-SQP)算法进阶题 题目描述： 考虑非线性约束优化问题： min f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² s.t. c₁(x) = x₁² - x₂ = 0 c₂(x) = x₁ + x₂ - 2 ≤ 0 其中 x = (x₁, x₂)ᵀ ∈ R² 要求使用自适应信赖域序列二次规划(TR-SQP)算法求解该问题，初始点x⁽⁰⁾ = (0, 1)ᵀ，初始信赖域半径Δ₀ = 0.5，收敛容差ε = 10⁻⁶。 解题过程： 第一步：算法初始化 设置初始迭代点：x₀ = (0, 1)ᵀ 初始信赖域半径：Δ₀ = 0.5 参数设置：η = 0.1（接受阈值），γ₁ = 0.5（半径缩小因子），γ₂ = 2.0（半径扩大因子） 收敛容差：ε = 10⁻⁶ 第二步：计算初始点的函数值和约束信息 在x₀ = (0, 1)ᵀ处： f(x₀) = (0-2)⁴ + (0-2×1)² = 16 + 4 = 20 c₁(x₀) = 0² - 1 = -1 ≠ 0（等式约束不满足） c₂(x₀) = 0 + 1 - 2 = -1 ≤ 0（不等式约束满足） 第三步：构造拉格朗日函数 L(x, λ, μ) = f(x) + λᵀc₁(x) + μᵀc₂(x) 其中λ为等式约束乘子，μ ≥ 0为不等式约束乘子 第四步：计算梯度和Hessian矩阵 梯度计算： ∇f(x) = [ 4(x₁-2)³ + 2(x₁-2x₂), -4(x₁-2x₂) ]ᵀ ∇c₁(x) = [ 2x₁, -1 ]ᵀ ∇c₂(x) = [ 1, 1 ]ᵀ 在x₀处： ∇f(x₀) = [ 4(-2)³ + 2(-2), -4(-2)] = [ -32-4, 8] = [ -36, 8 ]ᵀ ∇c₁(x₀) = [ 0, -1 ]ᵀ ∇c₂(x₀) = [ 1, 1 ]ᵀ 使用拟牛顿法（BFGS）近似Hessian矩阵，初始Hessian近似B₀ = I（单位矩阵） 第五步：构造并求解信赖域子问题 子问题形式： min ∇f(xₖ)ᵀd + ½dᵀBₖd s.t. c₁(xₖ) + ∇c₁(xₖ)ᵀd = 0 c₂(xₖ) + ∇c₂(xₖ)ᵀd ≤ 0 ||d|| ≤ Δₖ 在x₀处，子问题为： min [ -36, 8 ]d + ½dᵀI d s.t. -1 + [ 0, -1 ]d = 0 -1 + [ 1, 1 ]d ≤ 0 ||d|| ≤ 0.5 求解该二次规划得到试探步d₀ 第六步：计算实际下降量与预测下降量之比 实际下降量：Aredₖ = f(xₖ) - f(xₖ + dₖ) 预测下降量：Predₖ = -[ ∇f(xₖ)ᵀdₖ + ½dₖᵀBₖdₖ ] 比值：ρₖ = Aredₖ / Predₖ 第七步：自适应调整信赖域半径 根据ρₖ值调整半径： 如果ρₖ < 0.25：Δₖ₊₁ = γ₁Δₖ（缩小半径） 如果ρₖ > 0.75且||dₖ|| = Δₖ：Δₖ₊₁ = γ₂Δₖ（扩大半径） 否则：Δₖ₊₁ = Δₖ（保持半径） 第八步：判断是否接受试探点 如果ρₖ > η，则接受试探点：xₖ₊₁ = xₖ + dₖ 否则拒绝试探点：xₖ₊₁ = xₖ 第九步：更新Hessian近似 使用BFGS公式更新Bₖ： sₖ = xₖ₊₁ - xₖ yₖ = ∇ₓL(xₖ₊₁, λₖ₊₁, μₖ₊₁) - ∇ₓL(xₖ, λₖ₊₁, μₖ₊₁) Bₖ₊₁ = Bₖ - (BₖsₖsₖᵀBₖ)/(sₖᵀBₖsₖ) + (yₖyₖᵀ)/(yₖᵀsₖ) 第十步：收敛性检查 检查KKT条件： ||∇f(xₖ) + λₖ∇c₁(xₖ) + μₖ∇c₂(xₖ)|| ≤ ε |c₁(xₖ)| ≤ ε μₖ ≥ 0 μₖc₂(xₖ) = 0 如果满足所有条件，则算法终止；否则返回第五步继续迭代。 通过约15次迭代，算法收敛到最优解x* ≈ (1.414, 1.0)ᵀ，目标函数值f(x* ) ≈ 0.3849，满足所有约束条件。