线性规划

只谈一点自认为比较深刻的。

线性规划的可行解构成一个凸集或者说单纯形，而最大化的目标是一个去截这个凸集的超平面。

simplex所做的事情就是每次尝试沿着一个维度向增大目标的方向推动这个超平面，直到目标的所有系数变成负的，此时我们必然找到了那个截的位置。但是很遗憾，我们在推动它的过程中，会受到各约束的限制，而约束

ipm，或者说内点法

考虑我们用一个牛逼函数，它在可行域内是$0$，在可行域外是$-\infty$，来代替限制，然后直接梯度下降或者牛迭。

但是这个函数不光滑，所以不好求导。考虑使用一个称为对数障碍的技术，我们考虑$c\ln(x)$这样的东西，其中$x$是一个$\geq 0$的约束。钦点这个约束的值$<0$的时候，它的值是$+\infty$，这不影响它的光滑。在接近$0$的时候，对数障碍会陡然变大，从而限制出可行域。

于是我们取一个非常接近$0$的$c$，就可以直接求导之后牛迭了。可以证明如果要达到$\epsilon$的精度，只需要迭代不超过$O(\sqrt{n}\log\frac{1}{\epsilon})$轮，所以我们就有了$\tilde{O}(n^{3.5})$的复杂度。

可以感觉到内点法没有引入到OI是因为实现复杂，并且对精度要求比较高。

• Previous
  一轮省集
• Next
  7月5日闲话 : 读x义x《食盐》