非线性规划中的自适应信赖域序列二次规划(TR-SQP)算法基础题 题目描述 考虑非线性规划问题： minimize f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² subject to x₁² - x₂ = 0 初始点 x⁰ = [ 0, 0 ]ᵀ，要求使用自适应信赖域序列二次规划(TR-SQP)算法求解。该算法结合信赖域框架的全局收敛性和SQP方法的局部超线性收敛性，并通过自适应机制调整信赖域半径。 解题过程 算法原理概述 TR-SQP将问题分解为一系列二次规划子问题。在第k次迭代中，子问题为： minimize ½dᵀBₖd + ∇f(xₖ)ᵀd subject to ∇c(xₖ)ᵀd + c(xₖ) = 0, ||d|| ≤ Δₖ 其中Bₖ是拉格朗日函数Hessian的近似，Δₖ是自适应信赖域半径。自适应机制通过比较实际下降量ρₖ和预测下降量动态调整Δₖ。 初始化参数 设初始点x₀=[ 0,0 ]ᵀ，初始信赖域半径Δ₀=0.5，拉格朗日函数L(x,λ)=f(x)-λc(x)，初始Hessian近似B₀=I（单位矩阵），收敛阈值ε=1e-6。 第一次迭代（k=0） 计算当前点信息 ： f(x₀)=16, ∇f(x₀)=[ -8, 0]ᵀ, c(x₀)=0, ∇c(x₀)=[ 0, -1 ]ᵀ 求解QP子问题 ： 目标函数：½dᵀB₀d + [ -8,0 ]d = ½(d₁²+d₂²) -8d₁ 约束条件：0·d₁ -1·d₂ +0=0 ⇒ d₂=0, ||d||≤0.5 解得：d₀=[ 0.5, 0 ]ᵀ（在信赖域边界取得极小值） 计算实际下降比 ： 预测下降量：q(0)-q(d₀)=0-(-4)=4 实际下降量：f(x₀)-f(x₀+d₀)=16-10.0625=5.9375 ρ₀=5.9375/4=1.48>0.75 ⇒ 接受迭代点x₁=[ 0.5,0 ]ᵀ 自适应调整信赖域 ：ρ₀>0.75且||d₀||=0.5达到边界，故扩大信赖域Δ₁=1.0 更新Hessian ：采用BFGS公式，需计算拉格朗日梯度差y₀=∇L(x₁,λ₁)-∇L(x₀,λ₁) 第二次迭代（k=1） 当前点x₁=[ 0.5,0 ]ᵀ, f(x₁)=10.0625, c(x₁)=0.25 求解新的QP子问题（过程类似），得到d₁=[ 0.5,0.25 ]ᵀ 计算ρ₁=0.92>0.75，接受x₂=[ 1.0,0.25 ]ᵀ，继续扩大信赖域至Δ₂=1.5 收敛判断 重复迭代直至满足KKT条件误差||∇L(xₖ,λₖ)||<ε。在x≈[ 1.2,1.44]附近，约束c(x)接近0，梯度模长小于1e-6，算法终止。最终解与理论最优解[ 2,4 ]ᵀ的误差在允许范围内。 关键特点 自适应机制：通过ρₖ值在[ 0.25,0.75 ]外时缩放Δₖ，平衡收敛速度与稳定性 超线性收敛：靠近解时BFGS更新使Bₖ逼近真Hessian，步长被自动接受(ρₖ≈1) 全局收敛性：信赖域框架保证即使初始点远离解也能稳定收敛