线性规划

单纯形法

步骤

找到一个初始的基本可行解
不断的进行旋转（pivot）操作
重复2直到结果不能改进为止

退化

在旋转的过程中，可能会存在保持目标值不变的情况，这种现象称为退化。

如何避免退化？一个方法就是使用Bland规则：

在选择替入变量和替出变量的时候，我们总是选择满足条件的下标最小值。

替入变量xe：目标条件中，系数为负数的第一个作为替入变量
替出变量xl：对所有的约束条件中，选择对xe约束最紧的第一个

另一个方法是加入随机扰动

时间复杂度

最坏情况下是非多项式的，而是指数复杂度，即$O(2^n-1)$，但是绝大多数情况下或者说实际运行过程中是多项式时间（$O(kMN)$, $k: 算法中翻转的次数, M: 约束条件数，N：变量个数$)

整體而言, 單形法的表現相當不錯。對於一個有n個變數及m個約束的線性規劃問題,平均起來, 單形法只需要移動經過大約$m^{0.9522} × n^{0.3109}$這麼多個頂點, 便能求得最佳解。但是 G. Minty 和 V. Klee 兩位學者在1971年提出實例來驗證單形法在最差情況下的表現非常不好, 對於一個n維空間裡的特殊線性規劃問題, 單形法要移動經過 $2^n −1$個頂點才能到達最佳解。因為$2^n$這個數目隨著n的增長而做指數式成長, 所以成長速度相當快, 要用單形法來解決超大型的線性規劃確實有值得憂慮之處

其他

给定一个线性规划L，就只有如下三种情形：

有一个有限目标值的最优解
不可行
无界

椭球法

是线性规划的第一个多项式时间算法，但是实际中运行缓慢。（《算法导论》）

内点法

也是多项式时间算法。与单纯形法相比，这类算法在可行区域的内部移动。对大规模的输入，内点算法的性能与单纯形法相当，有时甚至更快。（《算法导论》）

时间复杂度

$O(n^2m) 其中m\gg n$

$m$是变量数，$n$是约束数

线性规划的应用

最短路径问题
最大流
最小费用流

整数规划

可以证明（《算法导论》练习34. 5-3），整数规划是一个NP问题，没有多项式时间算法能解决整数规划。

分枝定界法

Branch and Bound Algorithm (B&B)是整数规划的精确算法。

时间复杂度 $O(2^n)$

空间复杂度 $O(2^n)$

0-1整数规划

隐枚举法

0-1整数规划一般解法为隐枚举法。

原则：

用试探法，求出一个可行解，以它的目标值作为当前最好值$Z^0$。
增加过滤条件$Z \ge Z^0$。
将$x_i$按$c_i$由小到大排列。

凸函数

凸函数的定义：

$f(\theta x+(1-\theta)y)\le \theta f(x) + (1-\theta)f(y)$

注意图片中的函数如果倒过来就不是凸函数了，凸函数上每个点都比这个点的切线上的点大。

对多元函数，如果他是凸函数，则其Hessian矩阵为半正定矩阵。如果Hessian矩阵是正定的，则函数是严格凸函数。

参考资料：

https://www.hrwhisper.me/introduction-to-simplex-algorithm/
https://web.math.sinica.edu.tw/math_media/d171/17104.pdf
https://web.math.sinica.edu.tw/math_media/d171/17104.pdf
《算法导论》