非线性规划中的序列凸近似(SCP)算法基础题 题目描述： 考虑非线性规划问题： minimize f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² subject to: g₁(x) = x₁² - x₂ ≤ 0 g₂(x) = -x₁ ≤ 0 g₃(x) = -x₂ ≤ 0 其中初始点 x⁰ = [ 0, 1 ]ᵀ。请使用序列凸近似(SCP)算法求解该问题，迭代3次。 解题过程： 算法原理介绍 序列凸近似(SCP)通过在当前迭代点对非凸函数进行凸近似，将原问题转化为一系列凸子问题。对于目标函数和约束中的非凸部分，我们使用一阶泰勒展开进行线性化。 第一次迭代 (k=0) 初始点：x⁰ = [ 0, 1 ]ᵀ 计算梯度： ∇f(x) = [ 4(x₁-2)³ + 2(x₁-2x₂), -4(x₁-2x₂) ]ᵀ ∇g₁(x) = [ 2x₁, -1 ]ᵀ 在x⁰处计算： f(x⁰) = (0-2)⁴ + (0-2)² = 16 + 4 = 20 ∇f(x⁰) = [ 4(-2)³ + 2(-2), -4(-2)] = [ 4×(-8) - 4, 8] = [ -32-4, 8] = [ -36, 8 ]ᵀ ∇g₁(x⁰) = [ 0, -1 ]ᵀ g₁(x⁰) = 0 - 1 = -1 构建凸子问题： minimize f̂(x) = f(x⁰) + ∇f(x⁰)ᵀ(x-x⁰) = 20 + [ -36, 8]·[ x₁, x₂-1 ]ᵀ subject to: ĝ₁(x) = g₁(x⁰) + ∇g₁(x⁰)ᵀ(x-x⁰) ≤ 0 即：-1 + [ 0, -1]·[ x₁, x₂-1 ]ᵀ ≤ 0 → -1 - (x₂-1) ≤ 0 → -x₂ ≤ 0 加上原始边界约束：x₁ ≥ 0, x₂ ≥ 0 求解该线性规划，得到x¹ = [ 0, 0 ]ᵀ 第二次迭代 (k=1) 当前点：x¹ = [ 0, 0 ]ᵀ 计算： f(x¹) = (0-2)⁴ + (0-0)² = 16 + 0 = 16 ∇f(x¹) = [ 4(-2)³ + 2(0), -4(0)] = [ -32, 0 ]ᵀ ∇g₁(x¹) = [ 0, -1 ]ᵀ g₁(x¹) = 0 - 0 = 0 构建凸子问题： minimize f̂(x) = 16 + [ -32, 0]·[ x₁, x₂ ]ᵀ subject to: ĝ₁(x) = 0 + [ 0, -1]·[ x₁, x₂ ]ᵀ ≤ 0 → -x₂ ≤ 0 加上边界约束：x₁ ≥ 0, x₂ ≥ 0 求解得x² = [ 0, 0 ]ᵀ（与x¹相同） 第三次迭代 (k=2) 当前点：x² = [ 0, 0 ]ᵀ 计算值与第二次迭代相同，构建相同的凸子问题，解得x³ = [ 0, 0 ]ᵀ 结果分析 经过3次迭代，算法收敛到点[ 0, 0]ᵀ。验证可行性：g₁(0,0)=0≤0，满足约束。该点是KKT点，因为∇f(0,0)=[ -32,0]ᵀ，∇g₁(0,0)=[ 0,-1 ]ᵀ，存在乘子λ=32使-32+λ×0=0，0+λ×(-1)=0。