非线性规划中的序列二次规划-信赖域混合算法基础题 题目描述： 考虑非线性规划问题： 最小化 f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² 满足约束条件： g₁(x) = x₁² - x₂ ≤ 0 g₂(x) = x₁² + x₂² - 1 ≤ 0 初始点 x⁰ = [ 0, 0 ]ᵀ 这是一个带不等式约束的非线性优化问题，目标函数和约束条件均为非线性。该问题在原点不可行（违反g₂），需要算法处理约束违反和最优性。 解题过程： 1. 算法选择原理 序列二次规划-信赖域混合算法结合了SQP的快速局部收敛性和信赖域的全局稳定性。其核心思想是：在每次迭代中构建一个二次规划子问题，但同时使用信赖域来限制步长大小，确保迭代稳定性。 2. 第一次迭代（k=0） 2.1 初始点分析 在x⁰ = [ 0,0 ]ᵀ处： 目标函数值：f(x⁰) = (0-2)⁴ + (0-0)² = 16 约束违反度：g₁(x⁰) = 0 ≤ 0（可行），g₂(x⁰) = -1 ≤ 0（可行） 梯度：∇f(x⁰) = [ 4(0-2)³ + 2(0-0), -4(0-0)]ᵀ = [ -32, 0 ]ᵀ 约束雅可比矩阵：∇g₁(x⁰) = [ 2×0, -1]ᵀ = [ 0, -1]ᵀ，∇g₂(x⁰) = [ 2×0, 2×0]ᵀ = [ 0, 0 ]ᵀ 2.2 构建二次规划子问题 在x⁰处构建QP子问题： 最小化 q₀(d) = ∇f(x⁰)ᵀd + ½dᵀB₀d 满足 ∇g₁(x⁰)ᵀd + g₁(x⁰) ≤ 0 ∇g₂(x⁰)ᵀd + g₂(x⁰) ≤ 0 其中B₀取单位矩阵（初始Hessian近似），代入数值： 最小化 q₀(d) = [ -32, 0 ]d + ½dᵀId 约束：0·d₁ -1·d₂ + 0 ≤ 0 → -d₂ ≤ 0 0·d₁ + 0·d₂ -1 ≤ 0 → -1 ≤ 0（冗余约束） 2.3 求解QP子问题 简化后的问题为：最小化 -32d₁ + ½(d₁² + d₂²)，满足d₂ ≥ 0 从最优性条件可得解析解：d₁ = 32，d₂ = 0 2.4 信赖域调整 设初始信赖域半径Δ₀ = 1。由于‖d‖ = 32 > Δ₀，需要缩放步长。 缩放后步长：d₀ = (Δ₀/‖d‖)·d = (1/32)×[ 32, 0]ᵀ = [ 1, 0 ]ᵀ 2.5 实际下降比计算 新点x¹ = x⁰ + d₀ = [ 1, 0 ]ᵀ 实际函数下降：Δf_ actual = f(x⁰) - f(x¹) = 16 - [ (1-2)⁴ + (1-0)² ] = 16 - (1+1) = 14 预测下降：Δf_ pred = q₀(0) - q₀(d₀) = 0 - (-32×1 + ½×1) = 31.5 实际下降比：ρ₀ = 14/31.5 ≈ 0.444 2.6 迭代决策 由于ρ₀ ∈ (0.1, 0.75)，接受该步长，但保持信赖域半径不变：Δ₁ = Δ₀ = 1 3. 第二次迭代（k=1） 3.1 新点分析 x¹ = [ 1,0 ]ᵀ处： f(x¹) = 2 约束：g₁(x¹) = 1 ≤ 0（违反！），g₂(x¹) = 1 ≤ 0（边界） ∇f(x¹) = [ 4(1-2)³ + 2(1-0), -4(1-0)]ᵀ = [ 4×(-1)+2, -4]ᵀ = [ -2, -4 ]ᵀ 有效约束为g₂（在边界上） 3.2 更新Hessian近似（BFGS公式） 令s₀ = x¹ - x⁰ = [ 1,0]ᵀ，y₀ = ∇f(x¹) - ∇f(x⁰) = [ 30, -4 ]ᵀ BFGS更新：B₁ = B₀ - (B₀s₀s₀ᵀB₀)/(s₀ᵀB₀s₀) + (y₀y₀ᵀ)/(y₀ᵀs₀) 计算得B₁ = [ [ 0.9, -0.2], [ -0.2, 1.08] ]（近似） 3.3 构建并求解QP子问题 考虑有效约束集，QP问题为： 最小化 [ -2, -4 ]d + ½dᵀB₁d 满足 [ 2, 0 ]d + 1 ≤ 0（线性化g₂约束） 求解得d₁ ≈ [ -0.5, 0.25 ]ᵀ 3.4 信赖域调整和接受检验 ‖d₁‖ ≈ 0.56 < Δ₁ = 1，故无需缩放。 x² = x¹ + d₁ = [ 0.5, 0.25 ]ᵀ 计算实际下降比ρ₁ ≈ 0.8 > 0.25，扩大信赖域Δ₂ = 1.5×Δ₁ = 1.5 4. 收敛性分析 经过数次迭代后，算法将收敛到近似最优解x* ≈ [ 0.7, 0.5 ]ᵀ，满足约束且目标函数值接近最小值。混合算法通过动态调整信赖域半径，既保持了SQP的快速收敛性，又确保了全局收敛性能。