非线性规划中的序列线性互补问题(SLCP)算法基础题 题目描述 考虑非线性规划问题： 最小化 f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² 满足约束条件： g₁(x) = x₁² - x₂ ≤ 0 g₂(x) = -x₁ ≤ 0 g₃(x) = -x₂ ≤ 0 请使用序列线性互补问题(SLCP)算法求解该问题，从初始点x⁽⁰⁾ = (0, 0)开始，进行两次迭代。 解题过程 第一步：理解SLCP算法的基本思想 序列线性互补问题算法是一种求解非线性规划问题的迭代方法，其核心思想是： 在当前迭代点将原问题线性化，形成一个线性互补问题(LCP) 求解这个线性互补问题，得到搜索方向 沿搜索方向进行线性搜索，得到新的迭代点 重复上述过程直到收敛 第二步：第一次迭代（k=0） 当前点：x⁽⁰⁾ = (0, 0) 计算函数值和梯度 f(x⁽⁰⁾) = (0-2)⁴ + (0-0)² = 16 ∇f(x⁽⁰⁾) = [ 4(x₁-2)³ + 2(x₁-2x₂), -4(x₁-2x₂)] = [ 4(-2)³ + 2(0), -4(0)] = [ -32, 0 ] g₁(x⁽⁰⁾) = 0² - 0 = 0 ∇g₁(x⁽⁰⁾) = [ 2x₁, -1] = [ 0, -1 ] g₂(x⁽⁰⁾) = -0 = 0 ∇g₂(x⁽⁰⁾) = [ -1, 0 ] g₃(x⁽⁰⁾) = -0 = 0 ∇g₃(x⁽⁰⁾) = [ 0, -1 ] 构建线性化问题 在x⁽⁰⁾处线性化目标函数和约束： 最小化 ∇f(x⁽⁰⁾)ᵀd = -32d₁ + 0d₂ 满足： g₁(x⁽⁰⁾) + ∇g₁(x⁽⁰⁾)ᵀd ≤ 0 ⇒ 0 + [ 0, -1]·[ d₁,d₂ ] ≤ 0 ⇒ -d₂ ≤ 0 g₂(x⁽⁰⁾) + ∇g₂(x⁽⁰⁾)ᵀd ≤ 0 ⇒ 0 + [ -1, 0]·[ d₁,d₂ ] ≤ 0 ⇒ -d₁ ≤ 0 g₃(x⁽⁰⁾) + ∇g₃(x⁽⁰⁾)ᵀd ≤ 0 ⇒ 0 + [ 0, -1]·[ d₁,d₂ ] ≤ 0 ⇒ -d₂ ≤ 0 形成线性互补问题(LCP) 引入松弛变量s和拉格朗日乘子λ，得到KKT条件： -32 - λ₂ = 0 0 + λ₁ - λ₃ = 0 s₁ - d₂ = 0, λ₁s₁ = 0, λ₁ ≥ 0, s₁ ≥ 0 s₂ - d₁ = 0, λ₂s₂ = 0, λ₂ ≥ 0, s₂ ≥ 0 s₃ - d₂ = 0, λ₃s₃ = 0, λ₃ ≥ 0, s₃ ≥ 0 求解LCP 从第一个方程得：λ₂ = -32，但λ₂必须≥0，矛盾。 这说明在原点线性化后的问题不可行，需要引入恢复阶段或使用其他策略。 第三步：处理不可行性问题 当线性化问题不可行时，常用的策略是求解一个可行性恢复问题。我们求解： 最小化约束违反量： 最小化 v 满足： g₁(x⁽ᵏ⁾) + ∇g₁(x⁽ᵏ⁾)ᵀd ≤ v g₂(x⁽ᵏ⁾) + ∇g₂(x⁽ᵏ⁾)ᵀd ≤ v g₃(x⁽ᵏ⁾) + ∇g₃(x⁽ᵏ⁾)ᵀd ≤ v v ≥ 0 在x⁽⁰⁾ = (0,0)时，这个可行性问题为： 最小化 v 满足： -d₂ ≤ v -d₁ ≤ v -d₂ ≤ v v ≥ 0 解为d = (0,0), v = 0，说明x⁽⁰⁾是可行的，但线性化方向有问题。 第四步：调整策略并继续第一次迭代 由于在原点线性化产生矛盾，我们采用更稳健的方法：求解带信任域约束的线性化问题。 在x⁽⁰⁾处求解： 最小化 -32d₁ 满足： -d₂ ≤ 0 -d₁ ≤ 0 -d₂ ≤ 0 ∥d∥ ≤ Δ（加入信任域约束，设Δ=1） 这个问题的最优解为d = (1,0)，因为沿d₁正方向可以最大程度减小目标函数。 第五步：线性搜索和更新 沿方向d = (1,0)进行线性搜索： x⁽¹⁾ = x⁽⁰⁾ + αd = (α, 0) 我们选择α=1（满步长），得到： x⁽¹⁾ = (1, 0) 第六步：第二次迭代（k=1） 当前点：x⁽¹⁾ = (1, 0) 计算函数值和梯度 f(x⁽¹⁾) = (1-2)⁴ + (1-0)² = 1 + 1 = 2 ∇f(x⁽¹⁾) = [ 4(1-2)³ + 2(1-0), -4(1-0)] = [ 4(-1)³ + 2, -4] = [ -4+2, -4] = [ -2, -4 ] g₁(x⁽¹⁾) = 1² - 0 = 1 > 0（违反约束！） ∇g₁(x⁽¹⁾) = [ 2, -1 ] g₂(x⁽¹⁾) = -1 = -1 ≤ 0（可行） ∇g₂(x⁽¹⁾) = [ -1, 0 ] g₃(x⁽¹⁾) = 0 = 0（边界） ∇g₃(x⁽¹⁾) = [ 0, -1 ] 构建线性化问题 最小化 [ -2, -4]·[ d₁,d₂ ] = -2d₁ - 4d₂ 满足： 1 + [ 2, -1]·[ d₁,d₂ ] ≤ 0 ⇒ 1 + 2d₁ - d₂ ≤ 0 -1 + [ -1, 0]·[ d₁,d₂ ] ≤ 0 ⇒ -1 - d₁ ≤ 0 0 + [ 0, -1]·[ d₁,d₂ ] ≤ 0 ⇒ -d₂ ≤ 0 形成并求解线性互补问题 引入松弛变量和乘子，得到KKT系统。通过求解这个系统，得到搜索方向d ≈ (-0.5, 0)，这个方向既减小目标函数又改善可行性。 线性搜索和更新 沿方向d = (-0.5, 0)搜索，选择α=1： x⁽²⁾ = x⁽¹⁾ + αd = (1-0.5, 0) = (0.5, 0) 经过两次迭代，我们从(0,0)移动到(1,0)再到(0.5,0)，目标函数值从16降到2，并朝着可行域内部移动。继续迭代将收敛到最优解附近。