原始-对偶方法与最短路算法

之前，我们学习了求解线性规划的单纯形法与对偶单纯形法，单纯形法在满足解可行的条件下不断优化目标函数，事实上是逐渐让对偶问题可行；对偶单纯形法则是在保证对偶可行的条件下使解逐渐可行。从凸优化中的知识我们知道，线性规划一定满足强对偶定理，因此，一定同时 (即目标函数值相等)存在对偶问题与原问题的可行解，此时得到最优值。

但单纯形法与对偶单纯形法的计算都较为复杂，于是提出了原始-对偶方法。原始-对偶方法的主要思想是从一个对偶可行解 $y$ 出发，逐渐优化可行解 $y$ ，希望得到一个原问题的解 $x$ 与 $y$ 满足互补松弛条件，且 $x$ 可行，此时便得到了原问题与对偶问题的最优解。

原始-对偶方法

考虑原问题(P) 为：

\[ \min\limits_x c^Tx \\ \text{s.t.} Ax = b \ge 0 \\ x \ge 0 \]

对偶问题 (DP)为

\[ \max\limits_x b^Ty \\ \text{s.t.} A^Ty \le c \]

首先假设我们得到了对偶问题的一个可行解 $y$。由互补松弛条件我们知道，当原问题的可行解 $x$ 与 $y$ 满足

\[ (c^T-y^TA)x = 0\\ (Ax-b)y = 0 \]

$x$ , $y$ 分别是原问题与对偶问题的最优解。由于 $x$ 是原问题的可行解，满足等式约束，因此互补松弛条件的第二条满足。我们只需考虑第一个条件，有两种满足的方式：

当 $c_j^T - y^TA_j = 0$, 即 $A^T_jy \le c_j$ 的约束取等号，$x$ 无约束
当 $c^T_j - y^TA_j \neq 0$, 即 $A_j^Ty \le c_j$ 的约束不紧， $x = 0$

我们记集合 $J$ 为紧的约束的集合： \[ J = \{j\vert A_j^Ty = c_j\}\]，此时，我们希望找到原问题的解满足

\[ Ax = b\\ x\ge 0, j \in J\\ x = 0, j \notin J \]

因此，我们考虑新的规划问题：限制规划问题（RP）

\[ \min \sum_{i = 0}^m\overline{x_i}\\ \left[ \begin{array}{} A& E \end{array} \right] \left[ \begin{array}{} x\\ \overline{x} \end{array} \right] = b\\ x\ge 0, j \in J\\ x = 0, j \notin J \]

类似于两阶段法的思想，对于新的规划问题，若目标函数最优解为 0，则得到了满足互补松弛条件的可行解。

考虑限制规划问题的对偶问题（DRP）

\[ \max b^Ty\\ A_j^Ty\le 0, j \in J\\ y_i\le 1,i = 1,...,m \]

可以看到 $y = 0$ 是一个可行解，因此目标函数 $\max y^Tb\ge 0$。设 $\overline{y}$ 是DRP的最优解

若目标函数最优值为0，根据强对偶定理，RP的最优值也为0，因此存在原问题的解 $x $ 满足上面的三个条件，即存在满足互补松弛定理的可行解，因此 $y$ 是对偶问题的最优解
若目标函数最优值大于0，根据上面的推论，不存在满足互补松弛定理的可行解。而线性规划对于最优解强对偶定理一定成立，互补松弛条件也一定成立，因此 $y$ 不是对偶问题的最优解

此时，我们需要对原对偶问题的可行解 $y$ 进行改进。一个简单的思想是使对偶问题的目标函数值更大，而我们发现DRP问题目标函数值的最优解大于0，因此，如果把DRP的最优解加入 $y$ 中，一定可以对它进行优化。能加多少呢？为了使收敛更快，我们应该加到约束恰好变紧，也就是使一个约束取等号。即

\[ y' = y +\theta \overline{y}, \theta>0\\ \]

$y'$ 比原来的解更优： \[y'^Tb = y^Tb +\theta \overline{y}^Tb>y^Tb\]

$y'$ 满足约束 $A^Ty' \le c$:

对于 $j\in J$, 即 $A_j^Ty = c_j$, $A_j^T\overline{y}\le 0$, 因此，$A_j^Ty' \le c_j$
对于 $j\notin J$, 为了使满足约束且收敛最快，取恰好有约束变紧的时候
\[ \theta = \min_{j\notin J, A_j^T\overline{y}>0}\frac{c_j-A_j^Ty}{A^T_j\overline{y}} \]

如果 $\theta$ 可以无限增大，说明对偶问题没有有限最优解，那么原问题无可行解。

将 $y$ 调整为 $y'$ 之后，确定新的 $J$ (考虑多个约束同时满足的情况) ,进入下一轮迭代继续调整，直到 DRP 目标函数值的最优解为 0，此时的 $y$ 就是对偶问题的最优解。

最短路问题

我们考虑有向图上的最短路问题，起点为 $s$，终点为 $t$。对有向图定义关联矩阵，这个矩阵中每列对应一条边，每行对应一个顶点。若一条边是一个顶点的出边，那么矩阵对应元素为 1；若一条边是一个顶点的入边，那么矩阵对应元素为 -1。设 $w_i$ 表示第 $i$ 条边的长度，$x_i$ 表示第 $i$ 条边是否在最短路上，那么最短路问题就是解如下线性规划问题

\[ \min\limits_x w^Tx \\ \text{s.t.} Ax = v \\ x \ge 0 \]

其中

\[ v_i = \begin{cases} 1 & i = s \\ -1 & i = t \\ 0 & \text{otherwise} \end{cases} \]

在整数规划中，我们知道了由于 $A$ 是全幺模矩阵，线性规划的最优解也是整数解，即问题的最优解。

根据关联矩阵的定义，把 $A$ 的每一行加起来，最后会获得都是 0 的一行，也就是说 $A$ 中的行向量是线性相关的。那么不妨从 $A$ 中去掉代表终点 $t$ 的那一行，得到新矩阵 $\bar{A}$。最短路问题就变为

\[ \min\limits_x w^Tx \\ \text{s.t.} \overline{A}x = v \\ x \ge 0 \]

其中

\[ v_i = \begin{cases} 1 & i = s \\ 0 & \text{otherwise} \end{cases} \]

这个问题的对偶问题

\[ \max y_s \\ \text{s.t.} y_i - y_j \le w_e ,\forall e = (i, j) \in E,j\neq t \\ y_i \le w_e, \forall e = (i, t) \in E \]

我们知道，由于删去了 $t$ 的一行，对偶问题的约束中应该与 $t$ 没有关系。此时我们令 $y_t = 0$ 再加入对偶问题中，与对偶问题等价：

\[ \max y_s \\ \text{s.t.} y_i - y_j \le w_e ,\forall e = (i, j) \in E \\y_t= 0 \]

所以这么做的目的是什么呢？

我们可以得到原问题的对偶问题为：

\[ \max y_s-y_t \\ \text{s.t.} y_i - y_j \le w_e ,\forall e = (i, j) \in E \]

毫无疑问这比我们变化后的对偶问题复杂。事实上，由于目标函数是两个变量的差，而约束也是对不同的两个变化差值的约束，我们可以认为这个变化通过将 $y_t$ 的值固定，将变量的范围限定，从而使问题简化，且不会改变目标函数的最优值。

变化后的对偶问题的可行解很容易得到，即 $y = 0$。

它的DRP问题为

\[ \max y_s \\ \text{s.t.} y_i - y_j \le 0 , \forall (i, j) \in J \\ y_i \le 1 \\ y_t = 0 \]

我们模拟一下前两次递归：

DP 的解为 $y_s=0$, DRP 的最优解为 $\overline{y_s} = 1, J =\emptyset$

根据 \[\theta = \min_{j\notin J, A_j^T\overline{y}>0}\frac{c_j-A_j^Ty}{A^T_j\overline{y}}\] , 而 $A_j^Ty_i$ 当边$j$ 从点 $i$ 出发时为 1，其他为0或-1，我们发现，$\theta$ 表示的是从点 $s$ 出发的最短的边，将其加入 $J$
DP 的解为 $y_s=\theta \overline{y_s}$, DRP 的最优解为 $\overline{y_s} =\overline{y_1} = 1, J =\{j_1\}$

再求 $\theta$, 我们发现它表示的是从DRP 的最优解中为1的点出发的最短的边，将其加入 $J$