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

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

但单纯形法与对偶单纯形法的计算都较为复杂，于是提出了原始-对偶方法。原始-对偶方法的主要思想是从一个对偶可行解 $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$

是不是有一点熟悉? 事实上这就是我们熟悉的 Dijkstra 算法的过程。其中 $J$ 表示以及选中的边, DRP 的最优解中为 1 表示已经到达的点, $\theta $ 表示每次选取的最短边, 而DP中的可行解 $y_s$ 一直在累加,因此表示现在到最远的点的最短距离。

当 $J$ 中包含的边到达了 $t$ , 由DRP的约束条件, DRP的最优解为全 0, 因此算法结束,对偶问题达到最优解, 此时的 $y_s$表示到 t 点的最短距离。