非线性规划中的序列线性化方法(SLM)基础题 题目描述： 考虑非线性规划问题： 最小化 f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² 满足约束条件： h(x) = x₁² - x₂ = 0 x₁ + x₂ ≤ 2 x₁, x₂ ≥ 0 请使用序列线性化方法(SLM)求解该问题，从初始点 x⁰ = (0, 1) 开始，进行两次完整迭代。 解题过程： 第一步：理解序列线性化方法(SLM)的基本思想 序列线性化方法是一种解决非线性规划问题的迭代算法，其核心思想是： 在当前迭代点处，将非线性目标函数和约束函数进行一阶泰勒展开，得到线性近似 求解这个线性规划子问题，得到搜索方向 沿搜索方向进行线搜索，确定新的迭代点 重复上述过程直到收敛 第二步：第一次迭代（k=0） 初始点：x⁰ = (0, 1) 2.1 计算函数值和梯度 目标函数 f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² 在 x⁰ = (0, 1) 处： f(x⁰) = (0-2)⁴ + (0-2×1)² = 16 + 4 = 20 梯度计算： ∂f/∂x₁ = 4(x₁-2)³ + 2(x₁-2x₂) ∂f/∂x₂ = -4(x₁-2x₂) 在 x⁰ 处： ∇f(x⁰) = [ 4(0-2)³ + 2(0-2), -4(0-2)] = [ 4×(-8) + 2×(-2), -4×(-2)] = [ -32-4, 8] = [ -36, 8 ] 等式约束 h(x) = x₁² - x₂ 在 x⁰ 处：h(x⁰) = 0² - 1 = -1 梯度：∇h(x⁰) = [ 2x₁, -1] = [ 0, -1 ] 不等式约束 g(x) = x₁ + x₂ - 2 ≤ 0 在 x⁰ 处：g(x⁰) = 0 + 1 - 2 = -1 ≤ 0（满足） 梯度：∇g(x⁰) = [ 1, 1 ] 2.2 构建线性规划子问题 在 x⁰ 处进行线性化： 目标函数线性化：f(x) ≈ f(x⁰) + ∇f(x⁰)ᵀ(x - x⁰) 约束线性化： h(x) ≈ h(x⁰) + ∇h(x⁰)ᵀ(x - x⁰) = 0 g(x) ≈ g(x⁰) + ∇g(x⁰)ᵀ(x - x⁰) ≤ 0 引入变量 d = x - x⁰，得到线性规划子问题： 最小化 ∇f(x⁰)ᵀd = -36d₁ + 8d₂ 满足： ∇h(x⁰)ᵀd = -h(x⁰) ⇒ 0·d₁ - 1·d₂ = 1 ⇒ d₂ = -1 ∇g(x⁰)ᵀd ≤ -g(x⁰) ⇒ d₁ + d₂ ≤ 1 x⁰ + d ≥ 0 ⇒ d₁ ≥ 0, d₂ ≥ -1 2.3 求解线性规划子问题 代入 d₂ = -1 到约束中： d₁ + (-1) ≤ 1 ⇒ d₁ ≤ 2 d₁ ≥ 0, d₂ = -1 目标函数：-36d₁ + 8×(-1) = -36d₁ - 8 由于系数为负，目标函数随 d₁ 增大而减小，因此取 d₁ 的最大值 d₁ = 2 得到搜索方向：d⁰ = (2, -1) 2.4 线搜索确定步长 新点：x⁰ + αd⁰ = (0+2α, 1-α) = (2α, 1-α) 需要考虑约束可行性： 等式约束：h(x) = (2α)² - (1-α) = 4α² + α - 1 = 0 解方程：α = [ -1 ± √(1+16)]/8 = [ -1 ± √17 ]/8 取正根：α = (-1 + √17)/8 ≈ 0.390 不等式约束：2α + (1-α) - 2 = α - 1 ≤ 0 ⇒ α ≤ 1 边界约束：2α ≥ 0, 1-α ≥ 0 ⇒ α ≤ 1 综合考虑所有约束，最大可行步长 α_ max = 0.390 在此区间内最小化原始目标函数 f(2α, 1-α)，通过一维搜索可得最优步长 α₀ ≈ 0.39 2.5 得到第一次迭代结果 x¹ = x⁰ + α₀d⁰ = (0.78, 0.61) f(x¹) ≈ (0.78-2)⁴ + (0.78-2×0.61)² ≈ 2.32 + 0.03 ≈ 2.35 第三步：第二次迭代（k=1） 当前点：x¹ = (0.78, 0.61) 3.1 计算函数值和梯度 f(x¹) ≈ 2.35 ∇f(x¹) = [ 4(0.78-2)³ + 2(0.78-2×0.61), -4(0.78-2×0.61) ] = [ 4×(-1.22)³ + 2×(-0.44), -4×(-0.44) ] ≈ [ 4×(-1.82) - 0.88, 1.76] ≈ [ -7.28-0.88, 1.76] = [ -8.16, 1.76 ] h(x¹) = 0.78² - 0.61 = 0.608 - 0.61 = -0.002 ≈ 0 ∇h(x¹) = [ 2×0.78, -1] = [ 1.56, -1 ] g(x¹) = 0.78 + 0.61 - 2 = -0.61 ≤ 0 ∇g(x¹) = [ 1, 1 ] 3.2 构建线性规划子问题 最小化 ∇f(x¹)ᵀd = -8.16d₁ + 1.76d₂ 满足： ∇h(x¹)ᵀd = -h(x¹) ⇒ 1.56d₁ - d₂ ≈ 0 ∇g(x¹)ᵀd ≤ -g(x¹) ⇒ d₁ + d₂ ≤ 0.61 x¹ + d ≥ 0 ⇒ d₁ ≥ -0.78, d₂ ≥ -0.61 3.3 求解线性规划子问题 由等式约束：d₂ = 1.56d₁ 代入不等式约束：d₁ + 1.56d₁ ≤ 0.61 ⇒ 2.56d₁ ≤ 0.61 ⇒ d₁ ≤ 0.238 目标函数：-8.16d₁ + 1.76×1.56d₁ = -8.16d₁ + 2.75d₁ = -5.41d₁ 系数为负，目标函数随 d₁ 增大而减小，取 d₁ = 0.238 则 d₂ = 1.56×0.238 ≈ 0.371 搜索方向：d¹ = (0.238, 0.371) 3.4 线搜索确定步长 新点：x¹ + αd¹ = (0.78+0.238α, 0.61+0.371α) 约束处理： 等式约束：h(x) = (0.78+0.238α)² - (0.61+0.371α) ≈ 0 边界约束：所有变量非负 通过线搜索确定最优步长 α₁ ≈ 0.8 3.5 得到第二次迭代结果 x² = x¹ + α₁d¹ ≈ (0.78+0.190, 0.61+0.297) ≈ (0.97, 0.91) f(x²) ≈ (0.97-2)⁴ + (0.97-2×0.91)² ≈ 1.07 + 0.72 ≈ 1.79 经过两次迭代，目标函数值从初始的20降低到约1.79，显示出良好的收敛趋势。