原始-对偶算法

《原始-对偶算法》由会员分享，可在线阅读，更多相关《原始-对偶算法（4页珍藏版）》请在金锄头文库上搜索。

1、18.433 组合最优化组合最优化 原始对偶算法 October 28 授课教师：Santosh Vempala 在这一讲中，我们介绍互补松弛性条件并利用它们得到求解线性规划的原始对偶方法。 1 互补松弛性互补松弛性 由前面的强对偶定理我们已经知道， 下面两个线性规划都有可行解时其最优值是相等的， 即利用上面的结论，我们可以验证原始和/或其对偶问提解的最优性。 定理定理 1. 设和 分别是(P)和(D)的可行解，那么和 是最优解当且仅当下面的条件成立： 证 明： 首 先 ， 由 于和是 可 行 解 ， 故且对下标 和 做加和，可得 把上面两式相加并利用强对偶定理，可得， 因此， 不等式(1)和

2、(2)一定为等式。 故结论得证。 2 原始对偶算法原始对偶算法 定理 1 主要蕴含的结论是：如果和是可行解且满足互补松弛性条件，则他们是最优解。 这个结论产生了原始对偶算法：从某个可行解和出发，使之越来越满足互补松弛性条件。 方便起见，我们考虑如下原始和对偶规划： 在这种形式下，互补松弛性条件可简化为： 原始对偶算法步骤如下： 1、 从(D)的一个可行解开始。在多数情况下得到这样的一个可行解要比求解线性规划简单得多。 令 现在我们需要利用(3)得到(P)的一个可行解满足问题是有没有一个满足这种性质的可行解。 2、写出限定原始规划(RP)如下： 事实上，(RP)的可行解即满足上述提到的性质(3)

3、。这里，变量为人工变量。如果为 0，那么即为(P)的最优解。 3、 如果，那么和是最优的。否则，这时我们写 出(RP)的对偶形式，称为(DRP)，并求其解 4、 令来改进（D）的解，其中的取值需满足是可行的，而且由可行性可知， 对有又因为任意均有 所以当时可取任意正数。故取 则满足且是可行的。 又因为且， 注意，在上面的原始对偶算法中，求解(DRP)通常要比求解(P)或(D)简单。实际上，在这 种方法中，(P)和(RP)都是临时规划，我们真正想解的是(D)。为此，我们先解出(DRP)再用 这个解来反复改进。 2.1 实例实例 考虑下面形式的最大流问题： 值得一提的是， 在初始的最大流问题中， 前三组约束为等式。 但是我们将这三组不等式相加， 得到 0=0，这些不等式的弱集蕴涵着等式。我们把上述表示形式作为(D)，取为零向量即 可得到它的一个可行解。现在我们直接给出(DRP): 可以看出(DRP)有如下释义。寻找一条从 到 的路（流值为 1）且路上只能经过下列弧：饱 和的后向弧， 零流的前向弧和任意方向的其它弧。 换句话说， 我们需要在剩余图中找一条路。 这种观察说明最大流算法实际上是一个原始对偶算法。 最后，需要注意，原始对偶算法不一定具有多项式执行时间。