非线性规划中的逐步线性规划（SLP）算法进阶题 我将为您详细讲解逐步线性规划（Sequential Linear Programming, SLP）算法在非线性规划中的应用。这是一个重要的序列近似优化方法。 题目描述 考虑非线性规划问题： 最小化 f(x) = x₁² + x₂² - 4x₁ - 2x₂ 约束条件： g₁(x) = x₁ + x₂ - 2 ≤ 0 g₂(x) = x₁² - x₂ ≤ 0 x₁ ≥ 0, x₂ ≥ 0 初始点 x⁰ = [ 1, 1 ]ᵀ，信赖域半径 Δ₀ = 0.5，收敛容差 ε = 0.001。 解题过程详解 第一步：理解SLP算法基本原理 SLP算法的核心思想是将非线性规划问题在当前迭代点附近线性化，通过求解一系列线性规划子问题来逼近原问题的最优解。 对于当前迭代点 xᵏ，我们构建线性化子问题： 目标函数线性化：∇f(xᵏ)ᵀd 约束线性化：gᵢ(xᵏ) + ∇gᵢ(xᵏ)ᵀd ≤ 0 添加信赖域约束：‖d‖∞ ≤ Δₖ 其中 d = x - xᵏ 是搜索方向。 第二步：计算初始点的梯度和函数值 在初始点 x⁰ = [ 1, 1 ]ᵀ： 目标函数梯度： ∇f(x) = [ 2x₁ - 4, 2x₂ - 2 ]ᵀ ∇f(x⁰) = [ 2×1 - 4, 2×1 - 2]ᵀ = [ -2, 0 ]ᵀ 约束函数值： g₁(x⁰) = 1 + 1 - 2 = 0 g₂(x⁰) = 1² - 1 = 0 约束梯度： ∇g₁(x) = [ 1, 1 ]ᵀ ∇g₂(x) = [ 2x₁, -1 ]ᵀ ∇g₂(x⁰) = [ 2, -1 ]ᵀ 第三步：构建第一个线性规划子问题 在 x⁰ 处，线性规划子问题为： 最小化 ∇f(x⁰)ᵀd = -2d₁ + 0d₂ 约束条件： g₁(x⁰) + ∇g₁(x⁰)ᵀd ≤ 0 → 0 + 1d₁ + 1d₂ ≤ 0 g₂(x⁰) + ∇g₂(x⁰)ᵀd ≤ 0 → 0 + 2d₁ - 1d₂ ≤ 0 信赖域约束：|d₁| ≤ 0.5, |d₂| ≤ 0.5 变量界限：x₁⁰ + d₁ ≥ 0, x₂⁰ + d₂ ≥ 0 第四步：求解线性规划子问题 将约束条件具体化： d₁ + d₂ ≤ 0 2d₁ - d₂ ≤ 0 -0.5 ≤ d₁ ≤ 0.5 -0.5 ≤ d₂ ≤ 0.5 d₁ ≥ -1, d₂ ≥ -1 目标函数为 -2d₁，要最小化此函数，我们希望 d₁ 尽可能大。 分析约束： 从 d₁ + d₂ ≤ 0 得 d₂ ≤ -d₁ 从 2d₁ - d₂ ≤ 0 得 d₂ ≥ 2d₁ 结合得：2d₁ ≤ d₂ ≤ -d₁，这要求 2d₁ ≤ -d₁，即 3d₁ ≤ 0，所以 d₁ ≤ 0 但目标函数要最小化 -2d₁，需要 d₁ 尽可能大，产生矛盾。 检查可行域顶点： 顶点1：d₁ = 0, d₂ = 0，目标值 = 0 顶点2：d₁ = -0.5, d₂ = 0.5，检查约束：-0.5 + 0.5 = 0 ≤ 0 ✓，2×(-0.5) - 0.5 = -1.5 ≤ 0 ✓ 目标值 = -2×(-0.5) = 1.0 顶点3：d₁ = 0, d₂ = -0.5，目标值 = 0 顶点4：d₁ = -0.5, d₂ = -0.5，约束：-0.5 + (-0.5) = -1 ≤ 0 ✓，2×(-0.5) - (-0.5) = -0.5 ≤ 0 ✓ 目标值 = -2×(-0.5) = 1.0 最优解为 d₁ = 0, d₂ = 0，目标值 = 0 第五步：判断收敛性和更新迭代点 由于搜索方向 d = [ 0, 0 ]ᵀ，说明当前点是一个稳定点。 检查KKT条件： 在 x⁰ = [ 1, 1 ]ᵀ 处： ∇f(x⁰) = [ -2, 0 ]ᵀ ∇g₁(x⁰) = [ 1, 1 ]ᵀ ∇g₂(x⁰) = [ 2, -1 ]ᵀ KKT条件：∇f(x) + λ₁∇g₁(x) + λ₂∇g₂(x) = 0 即：[ -2, 0]ᵀ + λ₁[ 1, 1]ᵀ + λ₂[ 2, -1]ᵀ = [ 0, 0 ]ᵀ 得到方程组： -2 + λ₁ + 2λ₂ = 0 0 + λ₁ - λ₂ = 0 解得：λ₁ = λ₂，代入第一式：-2 + λ₁ + 2λ₁ = 0 → 3λ₁ = 2 → λ₁ = 2/3, λ₂ = 2/3 由于 λ₁ > 0, λ₂ > 0，且 g₁(x⁰) = 0, g₂(x⁰) = 0，满足互补松弛条件。 因此 x⁰ = [ 1, 1 ]ᵀ 确实是KKT点，算法收敛。 第六步：验证最优性 原问题的最优解可以通过解析方法验证： 拉格朗日函数：L(x,λ) = x₁² + x₂² - 4x₁ - 2x₂ + λ₁(x₁ + x₂ - 2) + λ₂(x₁² - x₂) KKT条件： ∂L/∂x₁ = 2x₁ - 4 + λ₁ + 2λ₂x₁ = 0 ∂L/∂x₂ = 2x₂ - 2 + λ₁ - λ₂ = 0 λ₁(x₁ + x₂ - 2) = 0 λ₂(x₁² - x₂) = 0 x₁ + x₂ - 2 ≤ 0 x₁² - x₂ ≤ 0 λ₁ ≥ 0, λ₂ ≥ 0 在 x = [ 1, 1 ]ᵀ 处，如前计算，λ₁ = 2/3, λ₂ = 2/3 满足所有条件。 算法特点总结 SLP算法的关键要素： 线性化逼近：在当前点对非线性函数进行一阶泰勒展开 信赖域机制：控制步长保证线性近似的有效性 序列求解：通过一系列线性规划问题逼近原问题解 收敛判断：基于搜索方向范数或KKT条件 当线性化子问题无改进时，需要收缩信赖域半径；当线性近似质量好时，可扩张信赖域半径。