非线性规划中的序列二次规划-代理模型-信赖域混合算法基础题 题目描述 考虑非线性规划问题： min f(x) = (x₁ - 2)² + (x₂ - 1)² s.t. c₁(x) = x₁² - x₂ ≤ 0 c₂(x) = x₁ + x₂ - 2 ≤ 0 其中 x = [ x₁, x₂]ᵀ ∈ ℝ²。要求使用序列二次规划-代理模型-信赖域混合算法求解该问题，从初始点 x⁰ = [ 0, 0 ]ᵀ 开始，详细展示计算过程。 解题过程 1. 算法概述 该混合算法结合三种技术： 序列二次规划(SQP)：通过求解二次规划子问题获得搜索方向 代理模型：用简化模型近似原问题函数，降低计算成本 信赖域：限制步长范围，保证迭代稳定性 2. 初始化 设置初始点 x⁰ = [ 0, 0 ]ᵀ，初始信赖域半径 Δ₀ = 0.5，容许误差 ε = 10⁻⁶ 计算初始函数值：f(x⁰) = (0-2)² + (0-1)² = 4 + 1 = 5 约束违反度：c₁(x⁰) = 0² - 0 = 0，c₂(x⁰) = 0 + 0 - 2 = -2 → 最大违反度 = 0 3. 第一次迭代 (k=0) 3.1 构建代理模型 在 x⁰ 处构建二次代理模型： 梯度 ∇f(x⁰) = [ 2(x₁-2), 2(x₂-1)]ᵀ = [ -4, -2 ]ᵀ Hessian 近似 B₀ = I（单位矩阵） 代理模型：m₀(p) = f(x⁰) + ∇f(x⁰)ᵀp + ½pᵀB₀p = 5 + [ -4, -2 ]p + ½pᵀIp 3.2 构建约束线性化 ∇c₁(x⁰) = [ 2x₁, -1]ᵀ = [ 0, -1 ]ᵀ ∇c₂(x⁰) = [ 1, 1 ]ᵀ 线性化约束： c₁(x⁰) + ∇c₁(x⁰)ᵀp ≤ 0 → 0 + [ 0, -1 ]p ≤ 0 → -p₂ ≤ 0 c₂(x⁰) + ∇c₂(x⁰)ᵀp ≤ 0 → -2 + [ 1, 1 ]p ≤ 0 → p₁ + p₂ ≤ 2 3.3 求解信赖域约束的QP子问题 min m₀(p) = 5 - 4p₁ - 2p₂ + ½(p₁² + p₂²) s.t. -p₂ ≤ 0 p₁ + p₂ ≤ 2 ‖p‖ ≤ Δ₀ = 0.5 3.4 求解过程 忽略约束求解无约束极小点：∇m₀(p) = 0 → [ -4 + p₁, -2 + p₂] = [ 0, 0] → p* = [ 4, 2 ]ᵀ 但 ‖p* ‖ = √(4² + 2²) = √20 ≈ 4.47 > Δ₀ = 0.5 因此在信赖域边界上求解。由于约束较松，主要受信赖域限制。 通过拉格朗日法：min 5 - 4p₁ - 2p₂ + ½(p₁² + p₂²) + μ(‖p‖² - Δ₀²) 得 p₁ = 4/(1+2μ), p₂ = 2/(1+2μ)，代入 ‖p‖² = Δ₀² 解得 μ ≈ 3.8，p₀ ≈ [ 0.447, 0.224 ]ᵀ 3.5 实际下降与预测下降比较 实际下降：ared = f(x⁰) - f(x⁰ + p₀) x¹ = x⁰ + p₀ = [ 0.447, 0.224 ]ᵀ f(x¹) = (0.447-2)² + (0.224-1)² ≈ 2.41 + 0.60 = 3.01 ared = 5 - 3.01 = 1.99 预测下降：pred = m₀(0) - m₀(p₀) = 0 - (-4×0.447 - 2×0.224 + ½(0.447²+0.224²)) ≈ 2.236 - 0.128 = 2.108 比值 ρ₀ = ared/pred = 1.99/2.108 ≈ 0.944 > 0.75（接受步长） 3.6 更新 接受步长：x¹ = [ 0.447, 0.224 ]ᵀ 由于 ρ₀ > 0.75，扩大信赖域：Δ₁ = 1.5×Δ₀ = 0.75 4. 第二次迭代 (k=1) 4.1 更新代理模型 ∇f(x¹) = [ 2(0.447-2), 2(0.224-1)] ≈ [ -3.106, -1.552 ]ᵀ 使用BFGS更新Hessian近似： s₀ = x¹ - x⁰ = [ 0.447, 0.224 ]ᵀ y₀ = ∇f(x¹) - ∇f(x⁰) ≈ [ 0.894, 0.448 ]ᵀ B₁ = B₀ - (B₀s₀s₀ᵀB₀)/(s₀ᵀB₀s₀) + (y₀y₀ᵀ)/(y₀ᵀs₀) ≈ [ [ 1.2, 0.1], [ 0.1, 1.1] ] 4.2 约束线性化 c₁(x¹) ≈ -0.200, ∇c₁(x¹) ≈ [ 0.894, -1 ]ᵀ c₂(x¹) ≈ -1.329, ∇c₂(x¹) = [ 1, 1 ]ᵀ 4.3 求解QP子问题 min m₁(p) = 3.01 + [ -3.106, -1.552 ]p + ½pᵀB₁p s.t. -0.200 + [ 0.894, -1 ]p ≤ 0 → 0.894p₁ - p₂ ≤ 0.200 -1.329 + [ 1,1 ]p ≤ 0 → p₁ + p₂ ≤ 1.329 ‖p‖ ≤ Δ₁ = 0.75 4.4 迭代继续 重复上述过程，每次迭代都会： 更新代理模型（函数近似） 线性化约束 在信赖域内求解QP子问题 根据实际下降效果调整信赖域半径 经过约5-6次迭代后，算法会收敛到最优解 x* ≈ [ 1, 1]ᵀ，f(x* ) = 1。 5. 收敛性分析 该混合算法结合了SQP的快速收敛性、代理模型的计算效率、信赖域的全局收敛保证，特别适合计算代价高的实际问题。