非线性规划中的序列线性规划方法 序列线性规划方法是求解非线性规划问题的一类重要算法。其核心思想是通过一系列线性规划子问题来逐步逼近原非线性规划问题的最优解。让我们逐步深入理解这个方法。 首先考虑一个一般的非线性规划问题： min f(x) s.t. g_ i(x) ≤ 0, i = 1,...,m h_ j(x) = 0, j = 1,...,p 其中f(x), g_ i(x), h_ j(x)都是非线性函数。 第一步：线性化过程 在当前迭代点x_ k处，我们对所有非线性函数进行一阶泰勒展开： f(x) ≈ f(x_ k) + ∇f(x_ k)^T(x - x_ k) g_ i(x) ≈ g_ i(x_ k) + ∇g_ i(x_ k)^T(x - x_ k) h_ j(x) ≈ h_ j(x_ k) + ∇h_ j(x_ k)^T(x - x_ k) 这样就将原非线性规划问题转化为一个线性规划问题。 第二步：信赖域策略 由于线性近似只在当前点的小邻域内有效，我们需要引入信赖域约束： ||x - x_ k|| ≤ Δ_ k 其中Δ_ k > 0是信赖域半径，控制着线性近似的适用范围。这个约束确保了我们在模型可信的区域内求解。 第三步：子问题构建 在每一步迭代中，我们需要求解如下线性规划子问题： min [ f(x_ k) + ∇f(x_ k)^T(x - x_ k) ] s.t. g_ i(x_ k) + ∇g_ i(x_ k)^T(x - x_ k) ≤ 0, i = 1,...,m h_ j(x_ k) + ∇h_ j(x_ k)^T(x - x_ k) = 0, j = 1,...,p ||x - x_ k|| ≤ Δ_ k 这个子问题是标准的线性规划问题，可以用单纯形法等成熟算法求解。 第四步：接受性检验 设x_ {k+1}是子问题的解，我们定义实际下降量： Ared_ k = f(x_ k) - f(x_ {k+1}) 和预测下降量： Pred_ k = [ f(x_ k) + ∇f(x_ k)^T(x_ k - x_ k)] - [ f(x_ k) + ∇f(x_ k)^T(x_ {k+1} - x_ k) ] = -∇f(x_ k)^T(x_ {k+1} - x_ k) 然后计算比值： r_ k = Ared_ k / Pred_ k 这个比值反映了线性近似的准确程度。 第五步：信赖域半径调整 根据比值r_ k来调整信赖域半径： 如果r_ k接近1，说明线性近似很好，可以增大信赖域半径 如果r_ k接近0，说明近似效果差，需要减小信赖域半径 如果r_ k在某个阈值之间，保持当前信赖域半径 常用的调整策略是： 如果 r_ k < 0.25，则 Δ_ {k+1} = 0.5Δ_ k 如果 r_ k > 0.75，则 Δ_ {k+1} = 2Δ_ k 否则，Δ_ {k+1} = Δ_ k 第六步：收敛性分析 序列线性规划方法具有局部超线性收敛性。在适当的正则性条件下，当迭代点充分接近最优解时，算法会接受全步长，即信赖域约束不再起作用，此时收敛速度是超线性的。 这个方法的主要优势在于它只需要一阶导数信息，且每个子问题都是线性规划，计算相对简单。然而，其收敛性严重依赖于初始点的选择，且需要合理控制信赖域半径。