动机
线性规划的一个可行解给出最优值的一个界,其对偶规划的一个可行解则给出另一个方向的界。近似算法常利用由此得到的证书,把离散解与线性规划松弛进行比较。但为什么这两个最好的界会重合呢?回答这个问题需要假设条件:不可行的规划没有原问题最优解,无界的规划则没有可与之匹配的有限最优值。
我们将针对一种具体而常用的标准形式证明强对偶性。证明的做法是从不等式中逐个消去变量,同时记录每个新不等式是由哪个非负组合产生的。目标函数最终得到的一个上界就成为对偶解。这样既建立了存在性,也建立了等式;它并不只是观察到两种算法恰好给出相同的数值。
定义与弱对偶
定义 4.2.1
(原问题与对偶问题)
设 ,,。原问题与对偶问题分别为
不等式均按坐标分量理解。可行点是满足所列全部约束的点。若存在可行点实际取得某个有限最优值,则称该有限最优值被取到。变量集或约束集为空的情形,可按通常的空和约定来解释;当原问题可行且有界时,主要证明在这些情形下同样成立。
定理 4.2.2
(弱对偶性)
若 是原问题的可行点、 是对偶问题的可行点,则 。
证明
(以两个受符号控制的不等式连锁)
对任意可行的 ,有
第一个不等号用到 与 ;最后一个不等号用到 与 。这就是弱对偶性:每个对偶可行点都是每个原问题可行目标值的上界。
定理
定理 4.2.3
(带有可达性的强对偶定理)
若原问题可行且其目标函数有上界,则两个规划都取得有限最优值,且最优值相等。
定理 4.2.4
(一个实变量的精确消去)
对于关于 的有限个非严格线性不等式组,可以构造出关于 的有限个非严格不等式,使得它们成立当且仅当存在实数 满足原不等式组。所构造的每个不等式都是原不等式的非负线性组合。
证明
消去引理的证明
证明
(配对下界与上界)
将每个含 的不等式改写成上界 或下界 :两边除以 系数的正绝对值,必要时反转不等号方向。 的系数为零的不等式原样保留。对每一对下界与上界,加入不等式 。它由两个原不等式的正数倍相加得到,因此是非负组合。若没有下界或没有上界,则不加入任何配对不等式。
原不等式组的每个解都满足所构造的不等式组。反之,若所构造的不等式组成立,则所有下界都不超过所有上界。当两类界都非空时,在它们的有限最大值与有限最小值之间取 。若只出现下界,则取 不小于这些下界的最大值;若只出现上界,则取 不大于这些上界的最小值。若两者都不出现,则取任意实数 。保持不变的那些不等式同样成立。于是存在相容的 ,精确性得证。
重复消去会保持证书性质:由本身已是原不等式组非负组合的那些不等式再作非负组合,仍然是原不等式组的非负组合。不等式的个数可能迅速增长,所以这个证明是存在性论证,并不表明它是高效的线性规划算法。
强对偶性的证明
证明
(投影目标并读出对偶解)
引入实的目标变量 ,考虑不等式组
利用引理消去 的全部坐标,得到只含单个变量 的有限个不等式。精确投影说明:实数 满足这个不等式组,当且仅当存在某个原问题可行点使得 。
投影集非空,因为原问题可行。它有上界,因为原问题的目标函数有上界。因此至少有一个投影后的不等式中 的系数为正:否则所有不等式都只是下界或常数,那么这个非空集合将向上无限延伸。把每个 系数为正的不等式规范化为 ,并令 为这有限多个上界中最小的一个。每个可行的 都不超过 。
投影集也是闭集,因为它由有限个非严格不等式描述。它含有某个值 ,并包含 以下的每个数:同一个原问题见证点对更小的 同样适用。它的正系数不等式以 为上界,而它的下界型不等式在 处成立,因为 。因此 本身满足整个投影不等式组。由精确性得到原问题可行点 使 ;上界迫使等号成立。于是原问题的最优值在 处被取到。
取一个达到最小值的导出不等式 。它是原不等式的非负组合。设它对 、、 的乘子分别为 、、。该组合中 的系数恰为 ,因为只有最后一个原不等式含 。由于所选不等式已规范化为系数为一,故 。其 的系数全部消去,给出
于是 ,所以 是对偶可行解,其目标值为 。由弱对偶性,任何对偶可行点的值都不可能更小,证明完成。
证明透视
最后的不等式记得自己的来源
的乘子在规范化后必须为一。其余乘子非负,并且抵消 的系数。这种抵消恰好就是对偶约束;其右端恰好就是原问题的最优值。
例题详解
例题 4.2.5
(一个变量与一个被取到的证书)
在 与 的条件下最大化 。原问题的最优值为 ,在 处取得。对偶问题在 与 的条件下最小化 ,所以 的值同样是 。将 乘以三,再加上 ,得到 。
例题 4.2.6
(一个冗余的界)
在 、、 的条件下最大化 。对偶问题在 与 的条件下最小化 。取 即证明原问题的最优值为二。较松的约束可以取乘子为零;对偶性并不要求每个约束都发挥作用。
例题 4.2.7
(最优值为负的可行规划)
在 与 的条件下最大化 。其可行域为 ,最优值为 。对偶问题在 、 的条件下最小化 ,所以 ,而 取得 。系数为负与最优值为负都是允许的。
例题 4.2.8
(零目标函数)
对任意非空可行域及 ,每个可行的 的目标值都为零。对偶点 可行且目标值为零,即使原问题的可行域无界也是如此。目标函数有界与可行域有界是不同的。
常见错误
反例模式
丢掉假设条件
仅在 的条件下最大化 。目标函数无上界。其对偶将要求不可能成立的不等式 ,所以不存在有限的对偶最优值。强对偶性并不是说每一对语法上合法的规划都有两个有限最优值。
常见错误
(两个界还不是最优值)
仅凭弱对偶性不能证明等式。例如,原问题可行点的值为二、对偶可行点的值为十,给出的是一个正确的区间,但不是最优性证书。若两个值相等,则弱对偶性立刻证明两者都是最优的。强对偶性保证在所述假设下存在一对相等的解;如何高效地找到它则是另一个算法问题。
常见错误
(不检验就照搬符号)
弱对偶性的乘法推导中,符号约束至关重要。若 的某个坐标可以为负,用它去乘一个按坐标成立的不等式就可能使不等号反向。含无约束变量的规划,可以把每个自由变量写成两个非负变量之差而化为标准形式,但所得对偶的符号必须从这一转换中推导,而不能不加检验地照搬。
投影证明提供了什么、没有提供什么
消去法的证明表明,即使可行多面体本身延伸到无穷远,有限的上界仍然被取到。这来自投影后的目标集的有限闭描述,而不是来自原可行域的紧致性。一个变量的负最优值例子与零目标函数例子说明了这两种可能。
导出的乘子是在所给实数据之上的精确证书。对有理数输入,消去只用到有理数的加、乘、除,因此原则上得到有理数见证。中间不等式的个数与比特长度可能迅速增长。这里的论证并不说明某个具体线性规划求解器的多项式运行时间,也不说明浮点输出的数值可靠性。计算得到的证书应当在适当的精确或经认证的算术模型下,对照原不等式加以检验。
常见错误
(线性规划对偶不能消除整数性间隙)
对于整数优化,即使线性规划的最优值是精确的,也可能严格大于整数解上的最优值。强对偶性使两个连续的线性规划值相等;它不会消除整数性间隙。近似性证明仍然可以把线性规划最优值当作界来用,前提是其舍入或原始—对偶分析单独考虑了这个间隙。
跟随一个消去步骤
考虑 、 与 。写成关于 的界,即 、 与 。将唯一的上界与两个下界配对,得到 与 。将后者规范化后,投影得到的限制为 。这个证书中目标不等式的系数,要在 乘以三之后才变为一。在由此得到的原不等式组合中, 的乘子是三,恰好就是对偶最优解 ,其目标值 与原问题最优值相等。
多个上界可以产生若干个投影不等式。其中最小的右端控制最大目标值,其余的仍然有效但是较弱的界。若两个界相等,则任何一个都可以提供对偶证书;这就是为什么一个最优值可能对应不止一个对偶解的原因之一。冗余的中间不等式可以保留而不改变投影,尽管它们会使消去过程大得多。
对于任意一对目标值相等的可行点,该证书也解释了互补松弛性。在弱对偶的链式不等式中,间隙分解为
两项都是非负乘积之和。若目标值相等,则两个和中的每个乘积都为零:正的对偶乘子迫使其对应的原问题不等式取等,正的原问题变量迫使对应的对偶不等式取等。反之,可行点满足这些乘积为零的条件时,目标值相等,从而证明最优性。这些条件并不要求每个取等的约束都有正的乘子。
概念视角几何
目标是活动约束法向量的组合
由于 ,有 ,其中 是 的第 行。依互补松弛性,只有在最优解 处取等号的约束才带正权重。所以 落在活动约束的外法向量所生成的锥内:在 处没有任何可行方向能使目标增大。
作为具体检验,在冗余界的例子中,第一个乘子为一,其界 取等;第二个乘子为零,其界 有三的松弛量。原问题变量为正,且对偶不等式 取等。这些是间隙为零的推论,而不是强对偶性所需的额外假设。
总结
从有限个非严格不等式中消去变量,既保持精确的可行性,又记录非负组合。将原问题目标投影到一维,得到一个被取到的有限上界。产生该上界的乘子构成一个值相同的对偶可行解。弱对偶性随即证明两个解都是最优的。
练习
快速检查
(在 与 的条件下最大化 。给出原问题与对偶问题的最优解及其共同的值。)
先写出对偶问题。
解答 · 答案
原问题点 的值为六。对偶问题在 与 的条件下最小化 ; 的值为六。弱对偶性证明两者都是最优的。
快速检查
(从 与 中消去 。对哪些 存在相容的 ?)
比较两个界。
解答 · 答案
这一对不等式相容,当且仅当 ,即 。对这样的 ,取 即同时满足两个不等式。
快速检查
(某个原问题可行点的值为七,某个对偶可行点的值也为七。说明为什么两者都不能再改进。)
对两个方向都使用弱对偶性。
解答 · 答案
弱对偶性使每个原问题的值以七为上界,每个对偶问题的值以七为下界。所给的两个可行点恰好取到这两个界。
快速检查
(在 与 的条件下最大化 。该定理适用吗?请说明理由。)
先检查定理的假设。
解答 · 答案
这些约束互相矛盾,所以原问题不可行。这里所述的强对偶定理假设原问题可行,因此不适用。