Introduction to linear optimization 阅读笔记（一）

首先从单纯形法开始说起。这本书前面的内容将放在后面说。

单纯形法是得名于拓扑概念单纯形，它是三角形和四面体概念的泛化，k 维单纯形指的是包含 k+1 个节点的多面体。单纯形法最早是有著名运筹科学家 Dantzig（知名运筹学专家、冯诺依曼奖获得者叶荫宇的老师）于 1947 年提出的，他随后在 1963 年在一个课题中将其正式简化成易于理解的文字。

单纯形法被用来解决线性规划问题，它大大缩小了搜索占用的内存空间和时间。下面我将逐步介绍这一方法的由来和原理。

一个经典的线性规划的标准形式是这样表述的：

$\begin{array}{cl}{\operatorname{minimize}} & {\mathbf{c}^{\prime} \mathbf{x}} \\ {\text { subject to }} & {\mathbf{A x}=\mathbf{b}} \\ {\mathbf{x} \geq \mathbf{0}}\end{array}$

那么我们要求这样一个线性规划的最优可行解实际上要保证两点，第一，这个解是满足限制条件的，也就是说它是可行的，第二，这个解释所有的可行解中最好的，也就是满足最优解。

定义 3.1 令 $x$ 成为一个多面集 $P$ 中的一个元素。向量 $d\in R^{n}$ 叫做 $x$ 处的可行方向，如果存在一个正数，使得 $x+\theta d \in P$

规定 $x$ 是该问题标准形式的基可行解， $B=[A_{B(1)}...A_{B(m)}]$ 为对应的基矩阵。

根据 $A（x+\theta d）=b \\ Ax=b$

我们可以反算出 $d_B=-B^{-1}A_j$ ,其中 $d_B$ 是可行方向中对应基矩阵的部分。

下面文章中简单介绍了两种情况，也就是 x 是非退化和 x 是退化的情况，实际上，在fig1图中，就是是否 x 到达了边界，如果对于 $x_B>0,x_B+\theta d_B \geq 0$ ,说明解仍然可行，当 $\theta$ 足够小的时候，也就是说 d 仍然是可行方向。如果 $x_B=0,d_B=-B^{-1}A_j < 0$ ,那么，在这种情况下,非负的限制就会被打破，就成为了非可行解。

fig1

定义 3.2 令 $x$ 成为一个基础解，令 $B$ 成为相关基矩阵，令 $c_B$ 成为这些基变量的代价函数的系数向量。对于每个 j，我们定义一个变量 $x_j$ 的reduced cost $\bar{c_j}$ ，也就是公式：

$\bar{c}_j=c_{j}-\mathbf{c}_{B}^{\prime} \mathbf{B}^{-1} \mathbf{A}_{j}$

定理 3.1 考虑一个基础可行解 x 以及对应的基础矩阵 B，令 $\bar{c }$ 成为对应的reduced cost的系数向量。

（a）若 $\bar{c } \ge 0$ ,x到达最优

（b）若 x 最优且非退化，则 $\bar{ c} \ge 0$

定义 3.3 一个基础矩阵 B 被称为最优的，如果：

（a） $B^{-1}b \ge 0$ ,

(b) $\overline{\mathrm{c}}^{\prime}=\mathbf{c}^{\prime}-\mathbf{c}_{B}^{\prime} \mathbf{B}^{-1} \mathbf{A} \geq \mathbf{0}$

定理 3.2 （a）列 $A_B(i),i \neq l$ ，并且 $A_j$ 是线性无关，因此 $\bar{ B }$ 是基础矩阵。（b）向量 $y=x+\theta^{*}d$ 是对应基础矩阵 $\bar{ B}$ 的基可行解。

由此我们可以得到一个单纯形法的计算方法（simplex method）：

1、首先找到一组基础列 $A_{B(1)},...,A_{B(m)}$ 组成基底,以及对应基础可行解 x

2、然后计算 reduced cost， $\bar{c}_j=c_{j}-\mathbf{c}_{B}^{\prime} \mathbf{B}^{-1} \mathbf{A}_{j}$ ，如果所有 reduced cost 均为非负，则解为最优解，否则，挑选出使reduced cost 为负的 j

3、计算 $u=B^{-1}A_j$ ,如果 u没有部分是正的，那么我们就有 $\theta^*=\infty$ ,最优成本函数是 $-\infty$ ,算法停止。

4、如果 u 一部分是正的，令 $\theta^*=\underset{\{i=1,...m\vert u_i>0\}}{min}{\frac{x_{B(i)}}{u_i} }$

5、找到满足条件的 $l$ ，将 $A_j$ 替换为 $A_{B(l)}$ ，如果 y 是新的基可行解，那么这个新的基础变量的值是 $y_j=\theta^*,y_{B(i)}=x_{B(i)}-\theta^*u_i,i \neq l$

定理 3.3 假设可行集合是非空的并且每个基础可行解是非退化的。那么，单纯形法在有限次的循环后终止。终止后，解集有两种可能性。

（a）我们得到了一个最优基B 和一个相关的最优基可行解

（b）我们找到了一个向量 d满足 $Ad=0，d \ge 0$ ,并且 $c ^\prime d <0$ ,最优成本为 $-\infty$

上面讨论的单纯形方法适用于非退化的基可行解，如果是退化的可行解，那么有两种情况。

第一种，目前的基可行解是退化的，而 $\theta^*=0$ ，在这种情况下，我们可以通过使这些等于 0 的 $x_{B(l)}$ 的对应向量 $A_{B(l)}$ 出基，从而使得定理 3.2成立。

第二种， $\theta^*>0$ ,多于一个原始基础变量成为 0，考虑到它们中只有一个出基，其他基变量仍然在0 位置，新的基可行解是退化的。

fig2

在 fig2 中，我们其实可以很明显看出， $x=（x_1,x_2,x_3,x_4,x_5）$ 是退化解，因为 $x_4,x_5$ 是冗余的约束，因此此时的f,g 方向上的 $\theta^*=0$ ,但当我们将基底换为 $x_4,x_1,x_2,x_3$ ，就可以继续找到可行方向和最优解了。

那么问题来了，如何选择入基向量和出基向量？这样一个选择的规则，我们把它叫做 pivoting rule。下面有两种方法可以选择：

（1）选择一个 $\bar{c }_{j}<0$ ,使其 reduced cost绝对值最大，然而，这样的方式并不能保证最快的移动，因为实际的 cost 需要考虑移动的距离。于是我们有了第二个方法。

（2）选择一个 $\bar{c }_{j}<0$ ，使其对应的 $\theta \vert \bar{c }_{j}\vert$ 最大，这项规则使得 reduced cost 在最短的周期下达到最优，但是这带来一个问题，那就是每次都需要计算出所有 $\bar{c }_{j}<0$ 对应的 $\theta^*$ ,根据经验，第二种方法相对于第一种并没有优势。

对于大型的计算问题，甚至第一种办法也不是很好，因为它需要计算出所有的 reduced cost。事实上，我们采取更简单的策略，那就是选择最小的 j 使得 $\bar{c }_{j}<0$ ，这种方法被称为最小角标法，这种方法还能很有效的避免循环。还有一些方法被用来降低运行时间，比如说 Devex （Harris，1973）以及 steepest edge rule（Goldfarb and Reid,1977）最后，还有一些方法是基于候选表（candidate list），有许多不同的方法来维护候选表。

对于单纯形的实施，我们介绍三种方法，依次是原始方法（naive implementation），修正单纯形方法（revised simplex method）以及全列表方法（the full tableau implementation）。

原始法的做法很简单，就是先计算 $\bar{c}_j=c_{j}-\mathbf{c}_{B}^{\prime} \mathbf{B}^{-1} \mathbf{A}_{j}$ ，然后从中选出入基向量和出基向量，然后计算 $u=B^{-1}A_j$ 从而得到新的基可行解。

修正单纯形法相比于原始法保留了上一个基础矩阵的部分信息。

定义 3.4 给定一个矩阵，不一定是方阵，对其中一行乘以一个常数再加到同一行或其他行的操作叫做基础行操作（elementary row operation）

一个修正单纯形方法的循环包括以下步骤：

1、在一个经典的循环中，我们开始于一个基础列矩阵 $A_{B(1)},...,A_{B(m)}$ 以及相关的基础可行解 x和基础矩阵的逆 $B^{-1}$

2、计算reduced cost $\bar{c}_j=c_{j}-\mathbf{c}_{B}^{\prime} \mathbf{B}^{-1} \mathbf{A}_{j}$ ,如果它们全部是非负的，那么当前的基可行解就是最优解，算法停止，如果不是，选择使得 reduced cost 小于0 的 j 进入候选表

3、计算 $u=B^{-1}A_j$ 。如果u 的部分没有正数，那么最优成本是 $-\infty$ ，算法停止。

4、如果有一部分是正的，那么令 $\theta^*=\underset{\{i=1,...m\vert u_i>0\}}{min}{\frac{x_{B(i)}}{u_i} }$

5、找到使上式成立的 $l$ ，用 $A_l$ 代替 $A_{B(l)}$ ，计算出新的基可行解。

6、形成 $m\times （m+1）$ 维矩阵 $[B^{-1} \vert u]$ ,同时计算出新的基础矩阵 $\bar{B }^{-1}$

今天就先写到这里，未完待续……

Introduction to linear optimization 阅读笔记（一）

定义 3.1 令成为一个多面集中的一个元素。向量叫做处的可行方向，如果存在一个正数，使得

定义 3.2 令成为一个基础解，令成为相关基矩阵，令成为这些基变量的代价函数的系数向量。对于每个 j，我们定义一个变量的reduced cost ，也就是公式：

定理 3.1 考虑一个基础可行解 x 以及对应的基础矩阵 B，令成为对应的reduced cost的系数向量。

（a）若,x到达最优

（b）若 x 最优且非退化，则