非线性规划中的序列二次约束二次规划(SQCQP)算法基础题 题目描述 考虑非线性规划问题： 最小化 f(x) = (x₁ - 2)² + (x₂ - 1)² 满足约束条件： c₁(x) = x₁ + x₂ - 2 ≤ 0 c₂(x) = x₁² - x₂ ≤ 0 其中 x = (x₁, x₂) ∈ R²。 这是一个具有二次目标函数和非线性约束的优化问题。我们将使用序列二次约束二次规划(SQCQP)算法求解该问题。 解题过程 1. 算法基本原理 SQCQP算法是序列二次规划(SQP)的扩展，特别适用于约束条件包含非线性项的问题。基本思想是：在每次迭代中，在当前点xₖ处构造一个二次规划(QP)子问题，该子问题通过线性化约束来近似原问题。但与标准SQP不同，SQCQP对高度非线性的约束会采用二次近似，从而提高收敛性。 2. 算法步骤详解 步骤1：初始化 选择初始点x₀ = (0, 0)，初始拉格朗日乘子估计λ₀ = (0, 0)，收敛容差ε = 10⁻⁶，设置迭代计数器k = 0。 验证初始点可行性： c₁(x₀) = 0 + 0 - 2 = -2 ≤ 0 ✓ c₂(x₀) = 0 - 0 = 0 ≤ 0 ✓ 初始点可行。 步骤2：构造二次规划子问题 在当前点xₖ = (x₁ₖ, x₂ₖ)处，我们需要构造QP子问题。 首先计算目标函数和约束函数的梯度： ∇f(x) = [ 2(x₁ - 2), 2(x₂ - 1) ]ᵀ ∇c₁(x) = [ 1, 1 ]ᵀ ∇c₂(x) = [ 2x₁, -1 ]ᵀ 在x₀ = (0, 0)处： ∇f(x₀) = [ -4, -2 ]ᵀ ∇c₁(x₀) = [ 1, 1 ]ᵀ ∇c₂(x₀) = [ 0, -1 ]ᵀ QP子问题为： 最小化 ∇f(xₖ)ᵀd + ½dᵀBₖd 满足约束： c₁(xₖ) + ∇c₁(xₖ)ᵀd ≤ 0 c₂(xₖ) + ∇c₂(xₖ)ᵀd ≤ 0 其中Bₖ是拉格朗日函数的海森矩阵近似，初始可用单位矩阵B₀ = I。 代入数值： 最小化 [ -4, -2 ]d + ½dᵀId 满足： -2 + [ 1, 1 ]d ≤ 0 0 + [ 0, -1 ]d ≤ 0 步骤3：求解QP子问题 简化后的QP问题： 最小化 -4d₁ - 2d₂ + ½(d₁² + d₂²) 满足： d₁ + d₂ ≤ 2 -d₂ ≤ 0 这是一个凸二次规划问题，可用拉格朗日法求解。得到解d₀ = (d₁, d₂) ≈ (1.0, 1.0)。 步骤4：更新迭代点 x₁ = x₀ + d₀ = (0, 0) + (1.0, 1.0) = (1.0, 1.0) 步骤5：检查收敛性 计算当前点的约束违反度和最优性条件： c₁(x₁) = 1 + 1 - 2 = 0 c₂(x₁) = 1² - 1 = 0 约束满足。 梯度条件：∇f(x₁) = [ 2(1-2), 2(1-1)] = [ -2, 0 ] 拉格朗日乘子估计：通过QP子问题的对偶变量得到λ₁ ≈ (1.0, 1.0) 最优性误差：‖∇f(x₁) + λ₁₁∇c₁(x₁) + λ₁₂∇c₂(x₁)‖ = ‖[ -2,0] + 1×[ 1,1] + 1×[ 2,-1]‖ = ‖[ 1,0 ]‖ = 1 > ε 未收敛，继续迭代。 步骤6：更新海森矩阵近似 使用BFGS公式更新Bₖ： B₁ = B₀ + (y yᵀ)/(yᵀs) - (B₀ s sᵀ B₀)/(sᵀ B₀ s) 其中s = x₁ - x₀ = (1, 1)，y = ∇L(x₁,λ₁) - ∇L(x₀,λ₀) 步骤7：第二次迭代 在x₁ = (1, 1)处重复步骤2-3构造并求解QP子问题，得到新的搜索方向d₁。 经过几次迭代后，算法会收敛到最优解x* ≈ (1, 1)，此时f(x* ) = 1，满足所有约束条件。 3. 算法特点 SQCQP通过序列求解二次规划子问题来逼近原问题解 对于非线性约束，相比纯线性化有更好的局部收敛性 需要合适的海森矩阵近似和步长控制策略 在约束 Qualification 条件下具有局部超线性收敛性 这个简单例子展示了SQCQP算法的基本流程和原理，实际应用中还需要考虑步长控制、约束规格验证等细节。