非线性规划中的序列二次约束二次规划(SQCQP)算法基础题 题目描述： 考虑非线性规划问题： 最小化 f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² 满足约束条件： g₁(x) = x₁² - x₂ ≤ 0 g₂(x) = x₁² + x₂² - 4 ≤ 0 其中 x = (x₁, x₂) ∈ ℝ²。 这是一个具有非线性目标函数和非线性不等式约束的优化问题。我们需要使用序列二次约束二次规划(SQCQP)方法求解该问题。 解题过程： SQCQP方法基本原理 SQCQP是序列二次规划(SQP)的扩展，特别适用于处理非线性约束。其核心思想是：在每次迭代中，在当前点xₖ处构造一个二次规划(QP)子问题，该子问题近似原问题，但将非线性约束进行二次近似（而不仅仅是线性近似）。 构建SQCQP子问题 在当前迭代点xₖ处，我们构建如下二次规划子问题： 最小化 ∇f(xₖ)ᵀd + (1/2)dᵀBₖd 满足约束： gᵢ(xₖ) + ∇gᵢ(xₖ)ᵀd + (1/2)dᵀ∇²gᵢ(xₖ)d ≤ 0, i=1,2 其中d是搜索方向，Bₖ是Hessian矩阵的近似。 计算梯度和Hessian矩阵 首先计算目标函数和约束函数的梯度： ∇f(x) = [ 4(x₁-2)³ + 2(x₁-2x₂), -4(x₁-2x₂) ] ∇g₁(x) = [ 2x₁, -1 ] ∇g₂(x) = [ 2x₁, 2x₂ ] 然后计算二阶导数： ∇²f(x) = [ [ 12(x₁-2)² + 2, -4], [ -4, 8] ] ∇²g₁(x) = [ [ 2, 0], [ 0, 0] ] ∇²g₂(x) = [ [ 2, 0], [ 0, 2] ] 选择初始点并开始迭代 我们选择可行初始点x₀ = (1, 1)，验证可行性： g₁(1,1) = 1 - 1 = 0 ≤ 0 ✓ g₂(1,1) = 1 + 1 - 4 = -2 ≤ 0 ✓ 第一次迭代（k=0） 在x₀ = (1,1)处计算： f(x₀) = (1-2)⁴ + (1-2)² = 1 + 1 = 2 ∇f(1,1) = [ 4(-1)³ + 2(-1), -4(-1)] = [ -4-2, 4] = [ -6, 4 ] 约束函数值： g₁(1,1) = 0, ∇g₁(1,1) = [ 2, -1 ] g₂(1,1) = -2, ∇g₂(1,1) = [ 2, 2 ] Hessian矩阵： ∇²f(1,1) = [ [ 12(1) + 2, -4], [ -4, 8]] = [ [ 14, -4], [ -4, 8] ] ∇²g₁(1,1) = [ [ 2, 0], [ 0, 0] ] ∇²g₂(1,1) = [ [ 2, 0], [ 0, 2] ] 使用单位矩阵作为初始B₀ = I，构建QP子问题： 最小化 [ -6,4 ]d + (1/2)dᵀId 满足： 0 + [ 2,-1]d + (1/2)dᵀ[ [ 2,0],[ 0,0] ]d ≤ 0 -2 + [ 2,2]d + (1/2)dᵀ[ [ 2,0],[ 0,2] ]d ≤ 0 求解QP子问题 这是一个二次约束二次规划问题，可以使用专门算法求解。假设我们得到解d₀ = (-0.2, 0.1)。 线搜索确定步长 使用Armijo条件进行线搜索，找到步长α₀使得： f(x₀ + α₀d₀) ≤ f(x₀) + cα₀∇f(x₀)ᵀd₀ 同时确保新点满足约束或使用罚函数处理约束违反。 假设找到α₀ = 0.5，则新点： x₁ = (1,1) + 0.5×(-0.2,0.1) = (0.9,1.05) 更新Hessian近似 使用BFGS公式更新Bₖ： s₀ = x₁ - x₀ = (-0.1,0.05) y₀ = ∇f(x₁) - ∇f(x₀) B₁ = B₀ - (B₀s₀s₀ᵀB₀)/(s₀ᵀB₀s₀) + (y₀y₀ᵀ)/(y₀ᵀs₀) 收敛性检查 检查‖∇L(x₁)‖ < ε（其中L是拉格朗日函数）和约束违反度。如果不满足收敛条件，返回步骤5继续迭代。 最终结果 经过若干次迭代后，算法会收敛到近似最优解x* ≈ (1.2, 1.4)，对应的目标函数值f(x* ) ≈ 0.2，满足所有约束条件。 SQCQP方法通过更精确的约束近似（二次而非线性）通常能获得更好的收敛性能，特别是对于高度非线性的约束问题。