非线性规划中的序列二次约束规划(SQCP)算法基础题 题目描述 考虑非线性规划问题： 最小化 f(x) = (x₁ - 2)² + (x₂ - 1)² 满足约束条件： g₁(x) = x₁² - x₂ ≤ 0 g₂(x) = x₁ + x₂ - 2 ≤ 0 其中 x = (x₁, x₂) ∈ R²。 这是一个具有非线性目标函数和非线性不等式约束的优化问题。要求使用序列二次约束规划(SQCP)算法求解该问题，从初始点 x⁰ = (0, 0) 开始，进行至少两次完整迭代。 解题过程 1. SQCP算法基本原理 SQCP是处理非线性约束优化问题的重要方法。与序列二次规划(SQP)不同，SQCP在每次迭代时构建一个二次约束规划子问题，能更好地处理非线性约束。 核心思想：在当前迭代点 xᵏ 处，通过泰勒展开近似目标函数和约束函数，构造一个局部近似问题： 目标函数用二次泰勒展开近似 非线性约束用线性或二次近似 2. 第一次迭代 (k=0) 步骤2.1: 初始化 初始点 x⁰ = (0, 0) 计算该点处的函数值和梯度： f(x⁰) = (0-2)² + (0-1)² = 4 + 1 = 5 ∇f(x⁰) = [ 2(x₁-2), 2(x₂-1)] = [ 2(0-2), 2(0-1)] = [ -4, -2 ] 约束函数值： g₁(x⁰) = 0² - 0 = 0 ≤ 0 (活跃约束) g₂(x⁰) = 0 + 0 - 2 = -2 ≤ 0 (非活跃约束) ∇g₁(x⁰) = [ 2x₁, -1] = [ 0, -1 ] ∇g₂(x⁰) = [ 1, 1 ] 步骤2.2: 构建SQCP子问题 在x⁰处，我们构造以下二次约束规划子问题： 最小化 ½dᵀB⁰d + ∇f(x⁰)ᵀd 满足约束： g₁(x⁰) + ∇g₁(x⁰)ᵀd + ½dᵀH₁⁰d ≤ 0 g₂(x⁰) + ∇g₂(x⁰)ᵀd ≤ 0 其中B⁰是Hessian矩阵的近似（初始可用单位矩阵），H₁⁰是g₁的Hessian近似。 步骤2.3: 简化子问题 使用单位矩阵B⁰ = I，H₁⁰ = ∇²g₁(x⁰) = [ [ 2,0],[ 0,0] ] 子问题变为： 最小化 ½(d₁² + d₂²) - 4d₁ - 2d₂ 满足约束： 0 + [ 0, -1]d + ½dᵀ[ [ 2,0],[ 0,0] ]d ≤ 0 → -d₂ + d₁² ≤ 0 -2 + [ 1, 1 ]d ≤ 0 → d₁ + d₂ - 2 ≤ 0 步骤2.4: 求解子问题 这是一个凸二次约束规划问题。通过观察，满足约束的可行方向应使d₂ ≥ d₁²且d₁ + d₂ ≤ 2。 求解得较优解：d⁰ ≈ (0.5, 0.25) 此时目标函数改进：½(0.25+0.0625) - 4×0.5 - 2×0.25 = 0.15625 - 2 - 0.5 = -2.34375 步骤2.5: 线搜索更新 x¹ = x⁰ + α⁰d⁰，通过线搜索确定步长α⁰ 取α⁰ = 1，得x¹ = (0.5, 0.25) 3. 第二次迭代 (k=1) 步骤3.1: 计算当前点信息 x¹ = (0.5, 0.25) f(x¹) = (0.5-2)² + (0.25-1)² = 2.25 + 0.5625 = 2.8125 ∇f(x¹) = [ 2(0.5-2), 2(0.25-1)] = [ -3, -1.5 ] 约束函数值： g₁(x¹) = 0.25 - 0.25 = 0 ≤ 0 (活跃约束) g₂(x¹) = 0.5 + 0.25 - 2 = -1.25 ≤ 0 (非活跃约束) ∇g₁(x¹) = [ 2×0.5, -1] = [ 1, -1 ] ∇g₂(x¹) = [ 1, 1 ] 步骤3.2: 更新Hessian近似 使用BFGS公式更新B¹： s⁰ = x¹ - x⁰ = (0.5, 0.25) y⁰ = ∇f(x¹) - ∇f(x⁰) = [ -3+4, -1.5+2] = [ 1, 0.5 ] B¹ = B⁰ - (B⁰s⁰)(B⁰s⁰)ᵀ/(s⁰ᵀB⁰s⁰) + y⁰y⁰ᵀ/(y⁰ᵀs⁰) 步骤3.3: 构建并求解新子问题 最小化 ½dᵀB¹d + [ -3, -1.5 ]d 满足约束： g₁(x¹) + ∇g₁(x¹)ᵀd + ½dᵀH₁¹d ≤ 0 g₂(x¹) + ∇g₂(x¹)ᵀd ≤ 0 求解得d¹ ≈ (0.3, 0.4) 步骤3.4: 更新迭代点 x² = x¹ + α¹d¹，取α¹ = 1 x² ≈ (0.8, 0.65) 4. 算法特点总结 SQCP通过序列求解二次约束规划子问题，能有效处理非线性约束。每次迭代需： 计算当前点函数值和梯度 构建局部近似子问题 求解二次约束规划 通过线搜索确定步长 该方法比SQP能更好地保持约束的曲率信息，适合强非线性约束问题。