非线性规划中的可行顺序线性规划(FSLP)算法基础题 题目描述 ： 考虑非线性规划问题： 最小化 f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² 满足约束条件： g₁(x) = x₁² - x₂ ≤ 0 g₂(x) = -x₁ ≤ 0 g₃(x) = -x₂ ≤ 0 初始点 x⁰ = [ 0, 1 ]ᵀ，使用可行顺序线性规划(FSLP)算法求解该问题。 解题过程 ： 1. 算法基本原理 可行顺序线性规划(FSLP)是一种序列线性规划方法，通过在当前迭代点对目标函数和约束函数进行线性化，求解线性规划子问题来获得搜索方向。关键特点是始终维持解的可行性。 2. 初始化 初始点：x⁰ = [ 0, 1 ]ᵀ 验证初始点可行性： g₁(x⁰) = 0² - 1 = -1 ≤ 0 ✓ g₂(x⁰) = -0 = 0 ≤ 0 ✓ g₃(x⁰) = -1 = -1 ≤ 0 ✓ 初始点可行，目标函数值 f(x⁰) = (0-2)⁴ + (0-2×1)² = 16 + 4 = 20 3. 第一次迭代 (k=0) 3.1 计算梯度 目标函数梯度： ∇f(x) = [ 4(x₁ - 2)³ + 2(x₁ - 2x₂), -4(x₁ - 2x₂) ]ᵀ ∇f(x⁰) = [ 4(0-2)³ + 2(0-2), -4(0-2)] = [ 4×(-8) + 2×(-2), -4×(-2)] = [ -32 -4, 8] = [ -36, 8 ]ᵀ 约束函数梯度： ∇g₁(x) = [ 2x₁, -1]ᵀ, ∇g₁(x⁰) = [ 0, -1 ]ᵀ ∇g₂(x) = [ -1, 0]ᵀ, ∇g₂(x⁰) = [ -1, 0 ]ᵀ ∇g₃(x) = [ 0, -1]ᵀ, ∇g₃(x⁰) = [ 0, -1 ]ᵀ 3.2 构建线性规划子问题 在当前点 x⁰ 处线性化： min d ∇f(x⁰)ᵀd = -36d₁ + 8d₂ 满足： g₁(x⁰) + ∇g₁(x⁰)ᵀd ≤ 0 ⇒ -1 + [ 0, -1][ d₁,d₂ ]ᵀ ≤ 0 ⇒ -1 - d₂ ≤ 0 g₂(x⁰) + ∇g₂(x⁰)ᵀd ≤ 0 ⇒ 0 + [ -1, 0][ d₁,d₂ ]ᵀ ≤ 0 ⇒ -d₁ ≤ 0 g₃(x⁰) + ∇g₃(x⁰)ᵀd ≤ 0 ⇒ -1 + [ 0, -1][ d₁,d₂ ]ᵀ ≤ 0 ⇒ -1 - d₂ ≤ 0 信任域约束：||d||∞ ≤ Δ₀ = 0.5 3.3 求解线性规划 化简约束： d₂ ≥ -1 (来自 g₁) d₁ ≥ 0 (来自 g₂) d₂ ≥ -1 (来自 g₃) -0.5 ≤ d₁ ≤ 0.5, -0.5 ≤ d₂ ≤ 0.5 (信任域) 目标函数：-36d₁ + 8d₂ 为最小化目标，应使 d₁ 最大，d₂ 最小 最优解：d₁ = 0.5, d₂ = -0.5 目标函数值：-36×0.5 + 8×(-0.5) = -18 - 4 = -22 3.4 线搜索确定步长 x⁰ + αd = [ 0, 1] + α[ 0.5, -0.5] = [ 0.5α, 1 - 0.5α ] 使用Armijo条件进行线搜索，确保可行性并充分下降。 4. 收敛性分析 FSLP算法通过序列求解线性规划子问题，在满足约束条件下逐步逼近最优解。当搜索方向 d 的范数小于预设容差时，算法终止，当前点即为KKT点的近似。 5. 算法特点 始终保持迭代点的可行性 通过线性化处理非线性问题 需要信任域约束防止线性化误差过大 收敛到满足KKT条件的稳定点 通过多次迭代，算法将收敛到近似最优解 x* ≈ [ 1.695, 0.848]ᵀ，对应目标函数值 f(x* ) ≈ 0.089。