非线性规划中的序列二次规划-积极集-乘子法混合算法基础题 题目描述 考虑非线性规划问题： minimize f(x) = x₁² + 2x₂² - 2x₁x₂ - 4x₁ subject to: g₁(x) = x₁ + x₂ - 2 ≤ 0 g₂(x) = x₁² + x₂² - 4 ≤ 0 x₁ ≥ 0, x₂ ≥ 0 这是一个具有二次目标函数和二次约束的非线性规划问题。我们将使用序列二次规划(SQP)框架，结合积极集策略处理不等式约束，并引入乘子法改善收敛性。 解题过程 第一步：算法框架理解 SQP-积极集-乘子法混合算法的核心思想是： 在每次迭代中构造一个二次规划子问题 使用积极集策略识别有效约束 引入乘子法增强拉格朗日函数，改善收敛性质 通过求解一系列二次规划问题逼近原问题的最优解 第二步：构造增广拉格朗日函数 对于不等式约束gᵢ(x) ≤ 0，我们引入松弛变量sᵢ ≥ 0，将其转化为等式约束： gᵢ(x) + sᵢ = 0 增广拉格朗日函数为： L(x,λ,μ) = f(x) + ∑λᵢ[ gᵢ(x) + sᵢ] + (μ/2)∑[ gᵢ(x) + sᵢ ]² 其中λ为拉格朗日乘子，μ为惩罚参数。 第三步：当前点初始化 假设初始点x⁰ = [ 1, 1]ᵀ，初始乘子λ⁰ = [ 0, 0 ]ᵀ，惩罚参数μ = 1 计算当前点的函数值和约束值： f(x⁰) = 1² + 2×1² - 2×1×1 - 4×1 = -3 g₁(x⁰) = 1 + 1 - 2 = 0 (边界约束，可能积极) g₂(x⁰) = 1² + 1² - 4 = -2 (非积极约束) 第四步：构造二次规划子问题 在当前点x⁰处，我们需要近似目标函数和约束： 梯度计算： ∇f(x) = [ 2x₁ - 2x₂ - 4, 4x₂ - 2x₁ ]ᵀ ∇f(x⁰) = [ 2×1 - 2×1 - 4, 4×1 - 2×1]ᵀ = [ -4, 2 ]ᵀ Hessian矩阵近似（使用BFGS更新或精确计算）： ∇²f(x) = [ [ 2, -2], [ -2, 4] ] ∇²g₁(x) = 0 ∇²g₂(x) = [ [ 2, 0], [ 0, 2] ] 二次规划子问题： minimize 0.5dᵀHd + ∇f(x⁰)ᵀd subject to: ∇g₁(x⁰)ᵀd + g₁(x⁰) ≤ 0 ∇g₂(x⁰)ᵀd + g₂(x⁰) ≤ 0 x⁰ + d ≥ 0 其中H是拉格朗日函数的Hessian近似。 第五步：积极集识别与子问题求解 在当前点，g₁(x⁰) = 0，因此g₁是积极约束。 积极集为：A = {1} 简化二次规划子问题（只考虑积极约束）： minimize 0.5dᵀHd + [ -4, 2 ]d subject to: ∇g₁(x⁰)ᵀd ≤ 0 （因为g₁(x⁰)=0） 其中∇g₁(x⁰) = [ 1, 1 ]ᵀ 求解该二次规划得到搜索方向d。 第六步：线搜索与乘子更新 沿方向d进行线搜索，确定步长α，使得增广拉格朗日函数充分下降： x¹ = x⁰ + αd 更新乘子： 对于积极约束g₁：λ₁¹ = λ₁⁰ + μ·max(g₁(x¹), -λ₁⁰/μ) 对于非积极约束g₂：λ₂¹ = 0（保持为零） 第七步：收敛判断 检查KKT条件的满足程度： 梯度条件：‖∇f(x) + ∑λᵢ∇gᵢ(x)‖ ≤ ε 互补松弛条件：λᵢgᵢ(x) ≈ 0 可行性条件：gᵢ(x) ≤ ε 如果满足收敛条件，则停止；否则返回第四步继续迭代。 第八步：算法特性分析 该混合算法结合了SQP的快速局部收敛性、积极集方法的约束处理效率以及乘子法的全局收敛保证。通过自适应调整惩罚参数μ，可以在保证收敛性的同时提高计算效率。