内点法的原理

Question

如题所述

Answer 1

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

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

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

是原始函数的梯度，且是的梯度。
除了原始变量，我们还引入了拉格朗日乘子（有时也称松弛变量）：

（4）有时被称为扰动互补条件，类似于KKT条件中的互补松弛。我们试图找到那些使得惩罚函数梯度为0的。
对比（3）与（4）我们容易得到一个关于梯度的等式：

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

其中，是的黑塞矩阵，是的的对角矩阵。
因为（1）和（4），所以在每次迭代时都必须满足，所以可以通过选择合适的来计算：