内点法_求解线性规划或非线性凸优化问题的算法

内点法

求解线性规划或非线性凸优化问题的算法

内点法(Interior Point Method)是一种求解线性规划或非线性凸优化问题的算法。

基本介绍

任何凸优化问题都可转化成凸集上的线性目标函数问题。早在19世纪60年代，就有人在研究非线性规划时，试图通过设计惩罚函数来描述可行区域。

1972年，V.Klee和G.Minty给出一个例子，他们构造一个线性规划问题，用单纯形方法求解，需要的计算时间为。这个例子表明，单纯形算法虽然在实际应用中非常有效，至今占有绝对优势，但在理论上它还不是多项式算法。于是产生这样的问题：对于线性规划，能否找到多项式算法？

1979年，前苏联数学家第一个给出了求解线性规划的多项式算法，这就是所谓的椭球算法。它的计算复杂性为，其中n是变量的维数，L是输入长度。这个算法在理论上是重要的，但是计算结果很不理想，远不及单纯形方法有效。

算法上突破性的进展和当代科学技术发展的需要，又给人们提出进一步的问题：能否找到实用上也确实有效的多项式时间算法？正是在这样的背景下，产生了内点法，它的计算复杂性是。

原理

内点法中有一个惩罚函数，用于描述凸集。与单纯形法不同，它通过遍历内部可行区域来搜索最优解。

与（1）对应的对数型惩罚函数为：

这里是一个小的正参数，常被称作“惩罚因子”。当趋近于0时，将趋近于（1）的解。

惩罚函数的梯度为：

是原始函数的梯度，且是的梯度。

除了原始变量，我们还引入了拉格朗日乘子（有时也称松弛变量）：

（4）有时被称为扰动互补条件，类似于KKT条件中的互补松弛。我们试图找到那些使得惩罚函数梯度为0的。

对比（3）与（4）我们容易得到一个关于梯度的等式：

其中，是限制条件的雅克比矩阵。

（5）式意味着的梯度应该位于限制条件梯度所张成的子空间中。对（4）和（5）应用牛顿法我们得到：

其中，是的黑塞矩阵，是的的对角矩阵。

因为（1）和（4），所以在每次迭代时都必须满足，所以可以通过选择合适的来计算：

应用

参考资料

最新修订时间：2023-09-11 11:42

条目作者

概述

基本介绍

参考资料