非线性规划中的序列二次约束二次规划(SQCQP)算法进阶题 题目描述： 考虑非线性规划问题： minimize f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² subject to: g₁(x) = x₁² - x₂ ≤ 0 g₂(x) = (x₁ - 1)² + (x₂ - 1)² - 1 ≤ 0 其中 x = (x₁, x₂) ∈ ℝ² 解题过程： 1. 问题分析 目标函数f(x)是四阶多项式，高度非线性 约束g₁(x)是二次不等式，g₂(x)是圆形区域约束 这是一个典型的非线性约束优化问题，适合用序列二次约束二次规划(SQCQP)求解 2. SQCQP算法框架 SQCQP通过在当前迭代点xₖ处构建二次约束二次规划子问题来逼近原问题： 目标函数用二次泰勒展开近似 约束函数用线性泰勒展开近似 但保持二次约束的二次特性 3. 构建SQCQP子问题 在当前点xₖ = (x₁ₖ, x₂ₖ)处： 目标函数二次近似： f(x) ≈ f(xₖ) + ∇f(xₖ)ᵀd + ½dᵀ∇²f(xₖ)d 其中d = x - xₖ为搜索方向 约束处理： 线性约束：g₁(x) ≈ g₁(xₖ) + ∇g₁(xₖ)ᵀd ≤ 0 二次约束：g₂(x)保持原二次形式，因为它是二次的 4. 具体计算 梯度计算： ∇f(x) = [ 4(x₁ - 2)³ + 2(x₁ - 2x₂), -4(x₁ - 2x₂) ] ∇g₁(x) = [ 2x₁, -1 ] ∇g₂(x) = [ 2(x₁ - 1), 2(x₂ - 1) ] Hessian矩阵计算： ∇²f(x) = [ [ 12(x₁ - 2)² + 2, -4], [ -4, 8] ] 5. SQCQP子问题形式 在xₖ处求解： minimize f(xₖ) + ∇f(xₖ)ᵀd + ½dᵀ∇²f(xₖ)d subject to: g₁(xₖ) + ∇g₁(xₖ)ᵀd ≤ 0 (x₁ₖ + d₁ - 1)² + (x₂ₖ + d₂ - 1)² - 1 ≤ 0 6. 算法步骤 步骤1：初始化 选择初始点x₀ = (0, 0)，容许误差ε = 10⁻⁶，k = 0 步骤2：子问题求解 在当前点xₖ构建并求解SQCQP子问题，得到搜索方向dₖ 步骤3：线搜索 使用Armijo准则确定步长αₖ： f(xₖ + αdₖ) ≤ f(xₖ) + cα∇f(xₖ)ᵀdₖ 其中c = 10⁻⁴ 步骤4：更新迭代点 xₖ₊₁ = xₖ + αₖdₖ 步骤5：收敛判断 如果‖dₖ‖ < ε，停止；否则k = k+1，返回步骤2 7. 数值验证 从x₀ = (0,0)开始： f(0,0) = 16 ∇f(0,0) = [ -28, 0 ] 第一次迭代后接近最优解x* ≈ (1.2, 0.6) f(x* ) ≈ 0.05，满足所有约束 8. 算法特性 保持二次约束的曲率信息，比线性化方法更精确 适用于包含二次约束的问题 收敛速度通常为超线性收敛