非线性规划中的序列线性互补问题(SLCP)算法基础题 题目描述： 考虑非线性规划问题： 最小化 f(x) = (x₁ - 2)² + (x₂ - 1)² 满足约束条件： g₁(x) = x₁ + x₂ - 2 ≤ 0 g₂(x) = x₁² - x₂ ≤ 0 x₁ ≥ 0, x₂ ≥ 0 使用序列线性互补问题(SLCP)方法求解该问题，初始点x⁰ = (0, 0)，收敛容差ε = 0.001。 解题过程： 1. 算法基本原理 SLCP方法将非线性规划问题转化为一系列线性互补问题来求解。每个迭代步骤中： 在当前点对目标函数和约束条件进行线性化 求解得到的线性互补问题 将解作为下一个迭代点 重复直到收敛 2. 第一次迭代（k=0） 步骤2.1：计算当前点函数值和梯度 当前点：x⁰ = (0, 0) 目标函数梯度： ∇f(x) = [ 2(x₁ - 2), 2(x₂ - 1) ] ∇f(x⁰) = [ 2(0-2), 2(0-1)] = [ -4, -2 ] 约束函数梯度： ∇g₁(x) = [ 1, 1 ]（常数） ∇g₂(x) = [ 2x₁, -1 ] ∇g₂(x⁰) = [ 0, -1 ] 函数值： f(x⁰) = (0-2)² + (0-1)² = 4 + 1 = 5 g₁(x⁰) = 0 + 0 - 2 = -2 g₂(x⁰) = 0² - 0 = 0 步骤2.2：构建线性化子问题 在x⁰处线性化： 最小化 f(x⁰) + ∇f(x⁰)ᵀ(x - x⁰) = 5 + [ -4, -2]·[ x₁, x₂ ]ᵀ = 5 - 4x₁ - 2x₂ 约束条件线性化： g₁(x⁰) + ∇g₁(x⁰)ᵀ(x - x⁰) ≤ 0 ⇒ -2 + [ 1,1]·[ x₁,x₂ ]ᵀ ≤ 0 ⇒ x₁ + x₂ ≤ 2 g₂(x⁰) + ∇g₂(x⁰)ᵀ(x - x⁰) ≤ 0 ⇒ 0 + [ 0,-1]·[ x₁,x₂ ]ᵀ ≤ 0 ⇒ -x₂ ≤ 0 ⇒ x₂ ≥ 0 x₁ ≥ 0, x₂ ≥ 0 步骤2.3：转化为线性互补问题 引入松弛变量s₁, s₂ ≥ 0，将不等式约束转化为等式： x₁ + x₂ + s₁ = 2 -x₂ + s₂ = 0 互补条件： s₁·λ₁ = 0, s₂·λ₂ = 0（λ₁, λ₂为拉格朗日乘子） 步骤2.4：求解线性互补问题 该问题可写为：求w, z ≥ 0，使得w = Mz + q，且wᵀz = 0 通过求解得到：x¹ = (1, 1)，λ = (2, 0) 3. 第二次迭代（k=1） 步骤3.1：计算当前点函数值和梯度 当前点：x¹ = (1, 1) ∇f(x¹) = [ 2(1-2), 2(1-1)] = [ -2, 0 ] ∇g₂(x¹) = [ 2×1, -1] = [ 2, -1 ] 函数值： f(x¹) = (1-2)² + (1-1)² = 1 + 0 = 1 g₁(x¹) = 1 + 1 - 2 = 0 g₂(x¹) = 1² - 1 = 0 步骤3.2：构建线性化子问题 在x¹处线性化： 最小化 1 + [ -2, 0]·[ x₁-1, x₂-1 ]ᵀ = 1 - 2(x₁-1) = 3 - 2x₁ 约束条件线性化： g₁线性化：0 + [ 1,1]·[ x₁-1,x₂-1 ]ᵀ ≤ 0 ⇒ x₁ + x₂ ≤ 2 g₂线性化：0 + [ 2,-1]·[ x₁-1,x₂-1 ]ᵀ ≤ 0 ⇒ 2(x₁-1) - (x₂-1) ≤ 0 ⇒ 2x₁ - x₂ ≤ 1 x₁ ≥ 0, x₂ ≥ 0 步骤3.3：求解线性互补问题 求解得到：x² = (1, 1)，与x¹相同 4. 收敛性检验 步骤4.1：检查迭代点变化 ‖x² - x¹‖ = 0 < ε = 0.001 步骤4.2：检查KKT条件 在x² = (1, 1)处： 原始可行性：g₁(x²) = 0 ≤ 0（满足），g₂(x²) = 0 ≤ 0（满足） 梯度条件：∇f(x²) + λ₁∇g₁(x²) + λ₂∇g₂(x²) = [ -2,0] + λ₁[ 1,1] + λ₂[ 2,-1 ] = 0 解得：λ₁ = 2, λ₂ = 0 互补松弛条件：λ₁g₁(x²) = 2×0 = 0, λ₂g₂(x²) = 0×0 = 0 对偶可行性：λ₁ = 2 ≥ 0, λ₂ = 0 ≥ 0 所有KKT条件满足，算法收敛。 5. 结果分析 最优解：x* = (1, 1) 最优值：f(x* ) = 1 拉格朗日乘子：λ* = (2, 0) SLCP方法通过序列求解线性互补问题，有效处理了非线性约束，在两次迭代后收敛到满足KKT条件的最优解。