线性规划的原始对偶算法

假设有如下原始问题和对偶问题：

如果我们能够找到一个x,一个y，满足根据互补松弛定理，即使得：

那么这个x,y就是原始问题和对偶问题的最优解。
可是，直接这样找，相当于穷举，大海捞针，我们希望给出一个算法来找到。

算法思路：我们首先找到对偶问题的一个可行解 $y$，并尝试找到一个原问题的可行解 $x$，使得 $x$ 和 $y$ 满足互补松弛定理。如果我们找到了这样的 $x$，那么 $x$ 和 $y$ 就分别是原问题和对偶问题的最优解；否则我们就需要调整 $y$，让它变得更好，继续尝试，直到找到最优解为止。

限制的原问题 (RP) 与限制的对偶问题 (DRP)

算法开始了：

假设我们有了一个对偶问题的可行解 $y$，现在我们需要寻找一个新原问题的可行解 $x$ 满足互补松弛定理。

先来个定义：

设 $A_j$ 表示矩阵 $A$ 的第 $j$ 列，定义 J = { j ∣ A j T y = c j } J = \{ j | A_j^Ty = c_j \} J={j∣AjT​y=cj​}（称 $J$ 为允许指标集，简单来说 $J$ 就是以 $y$ 作为对偶可行解时，对偶问题中那些成为紧约束的编号）。根据原问题的定义和互补松弛定理，我们有（1）

$$\begin{gathered} Ax=b \\ {x}_j=0\forall j\notin J \\ {x}_j\ge 0\forall j\in J \end{gathered}$$

如果我们能找到一个 $x$ 满足上面三个条件，$x$ 和 $y$ 就能满足互补松弛定理。

令$x_j=0,j\notin J$，我们为了求解$x_j,j\in J$,构造一个优化问题，称为限制的原问题（restricted primal，RP）

min ⁡ ∑ i = 1 m x ˉ i s.t. ∑ j ∈ J a i j x j + x ˉ i = b i x j ≥ 0 , x ˉ i ≥ 0

$$\begin{matrix} \min & \sum\limits_{i=1}^m \bar{x}_i \\ \text{s.t.} & \sum\limits_{j\in J} a_{ij}x_j + \bar{x}_i = b_i \\ & x_j \ge 0, \bar{x}_i \ge 0 \end{matrix}$$ mins.t.​i=1∑m​xˉi​j∈J∑​aij​xj​+xˉi​=bi​xj​≥0,xˉi​≥0​

如果RP的最优解为0，则说明每一个松弛$\bar{x}$都为0，此时(1)中的3个条件都满足，是最优解，找到了$x,y$。

注：上面的$Q$是$J$,$w^{(0)}$是$y$。

考虑 RP 的对偶问题，称为限制的对偶问题（DRP） max ⁡ b T y s.t. A j T y ≤ 0 ∀ j ∈ J y i ≤ 1 ∀ i ∈ { 1 , 2 , … , m }

$$\begin{matrix} \max & b^Ty \\ \text{s.t.} & A^T_jy \le 0 & \forall j \in J \\ & y_i \le 1 & \forall i \in \{1, 2, \dots, m\} \end{matrix}$$ maxs.t.​bTyAjT​y≤0yi​≤1​∀j∈J∀i∈{1,2,…,m}​

注意，$w^{(0)}$是初始选的那个$y$，$p_j$是原始问题中的那个系数矩阵A中的第$j$列。下面我们要判断，新构造的$w$代入对偶规划的约束中的$y$，查看能否满足。若可以满足，则新构造了一个对偶问题的可行解。



即想要负数+非负数=非正数，那么就让这个负数减去(一个很小的正数乘以这个非负数），那么结果肯定就会非正数$\le 0$了。

貌似为了找到下一个$y$，费了这么大的劲，竟然还求了一个DRP。我们当然会有疑惑，为什么这样求新$y$,我告诉你，这个新$y$代入到对偶问题中去，你会发现目标函数值比旧$y$更大，对偶是求最大，这不正是我们想要的吗？
设新$y$为$y^{\ast }$：

我们处在更新$y$的过程，所以$\theta >0,b^T\bar{y}>0$。

其实，我们生成一个新的$y$的过程中有了一个现象，虽然不影响我们生成新的$y$，但是如果我们发现这个新的现象，可以不用生成新$y$了，直接停止算法，因为原问题没有可行解，你是找不到最优解$\bar{y}$的。
那么这个现象是什么呢？来看看把。

由于RP与DRP是对偶，所以DRP最优值就是RP最优值，而此种情况下RP最优值大于0。等于0的情况早就排除了，在前面。

所以总结就是：如果RP中的最优值不是0，那么就看看是不是上述的情况，如果是，算法终止，如果不是就构造新的$y$进入下一轮迭代继续调整，直接确定新的 $J$ 和新的 DRP 即可（RP也不需要了，DRP和RP是一样的，RP最优值大于0，那么DRP也是），直到 DRP 的最优解让目标函数值为 0，此时的 $y$ 就是对偶问题的最优解。

其完整流程如下：

最后一个问题，送佛送到西，如何构造第一个对偶可行解。

从而问题变为：

这个方法非常类似于大M法。