前面的对偶笔记说明找到乘数后如何核验证书;本节解释这些乘数为什么存在。论证限于有限维线性模型。
动机
未找到可行点并不证明不可行;不断改善界,也不证明某个界会真正等于原始值。择一定理把第一个困难化为两种互斥而穷尽的可能:可行决策,或分离乘数。强对偶则保证有限最优值有取得同值的乘数。
关键是有限线性系统的特殊性:有限个向量生成的锥是闭集。因此锥外一点有最近点,两者位移产生分离线性泛函。我们逐步证明,不把分离当成一张无法核验的几何图。
敏感度也是证书的结果。只改右端时,对偶乘子仍可行,给最小值函数处处适用的下界;原问题的最优乘子才在原右端给出支撑下界;只有相应原始基保持可行,下界才是精确线性公式。活动基改变时,可能同时存在多个支撑斜率,不能直接说成唯一导数。
定义
定义 5.1.1
(等式原始问题、对偶及生成锥)
采用最小化惯例:
等式乘数 不受符号限制。向量 的生成锥为 。择一定理指定两个系统恰有一个可行。
几何证明使用欧氏内积,但可行性结论不依赖算法选哪个范数。零列及空系统也容许。锥含零、凸且对非负倍数封闭;这些代数性质并未证明其拓扑闭性,后者必须另行处理。
令 为可行且下确界有限时的最优值。若在扰动值有限之处都有 ,称 在 支撑此值函数,也称次梯度。支撑向量不必唯一,也未必是通常的导数。
定理/命题
定理 5.1.2
(Farkas 择一定理)
对有限实矩阵 及向量 ,下列恰有一个成立:
第二个向量是第一个系统的不可行证书。
定理 5.1.3
(包括取得性的强对偶)
若 可行且下确界有限,则原始下确界与对偶上确界都取得,且两值相等。对可行 ,目标相等当且仅当
因此原始可行、对偶可行及这些乘积,是可行对同时最优的充要条件。
有限维及有限个线性限制很重要。一般闭凸集上的有限下确界未必取得;任意非线性问题也未必有取得同值的对偶乘子。
证明思路
有限生成锥为闭集
引理 5.1.4
(有限生成锥是闭集)
对向量 ,生成锥 是 的闭子集。
证明
(先缩减到无关支撑,再用连续的逆)
任一锥内点都能用线性无关生成元表示。若某非负表示的正支撑相关,取非零关系 ,必要时反号使某个 。由系数减去 ,其中 是正 所对应的最小 。全部系数仍非负,至少一个正项消失;反复做便剩无关支撑。
固定一组无关列矩阵 ,系数由像向量通过连续公式 唯一恢复。像收敛,非负系数也收敛到非负极限,所以这个子锥闭。无关子集只有有限个,其闭子锥并集由支撑缩减覆盖整个锥。有限闭集并集仍闭,包括空支撑表示的零,故得证。
不能直接假设任意表示的系数都有界。例如生成元一与负一,可以用同时趋向无限的两个相同系数表示零。像保持有界而系数发散,正是天真取极限的漏洞。先缩减到无关支撑,才有连续左逆可控制系数。有限种支撑还保证可以固定其中一种分析极限;无限个闭子集的并集一般并不闭,所以“有限”并非可有可无的修饰。
最近点产生另一个系统
证明
(以最近点把 与锥分开)
取 为 的列锥。若 ,选最近点 。零已是候选,太远的点不可能改善距离,因此可把搜索限在足够大的闭球;闭且有界的交集紧致,最近点存在。令 。沿 至任意 的线段最小化平方距离,得
分别取 ,得 ,所以全部 。令 ,每列均有 ,而 。两系统不可能同时成立,因可行点会使 ,矛盾。
分离向量还可除以负的 的绝对值,归一化成值负一,但仍须逐列检查符号。若右端为零, 已可行,当然不可能有严格负证书。重复生成列也无碍,只需找到一个无关表示。锥本身一般无界;紧致性只用于排除太远候选后的最近点搜索,没有假设锥可行性是有界问题。
原始取得性与最优乘数
证明
(上图锥给出取得性,Farkas 给出乘数)
存在非负 使 的对 ,恰为向量 及 的生成锥,所以闭。取可行目标趋向有限下确界 ,相应对趋向 ,仍在锥内。其表示给出 ,按下确界定义必相等,证明取得。
这里闭的不是任意投影,而是已明确写成有限生成锥的集合。一般闭集的线性像未必闭,不能略去生成元表示便套用同一句话。多出来的生成元最后坐标为一,正好表示容许目标高于某个可行成本的非负余量;没有它,便只描述精确成本对,不是上图集合。这个表示也容许成本系数为负,不曾假设目标本身非负。
取最优 ,令 为零坐标集。我们要证明存在
若没有,以 各列、其负列及 的坐标向量作生成矩阵,右端取 ,套用 Farkas。其替代向量 满足 于 ,且 。
足够小的正 使 非负:零坐标不能下降,正坐标还有余量;等式也因 保持。目标却下降,矛盾。
更明确地,只需看那些正坐标而方向为负的有限个位置;把步长取成小于其正比值的最小值,即能保留全部正坐标。若没有这类位置,任何足够小正步长都可。零坐标由替代系统的符号条件保护,等式由零方向保护,下降由成本内积的严格负号保护。这三项检查分别对应可行性及改善,不能只用“朝较好方向”代替。故所需表示存在,给对偶可行 ,且
弱对偶即证对偶取得及同值。一般可行对的差距为 ,每项非负,等号恰好等价于逐项乘积零,完成证明。
证明透视
乘数存在性用在哪一步?
非负差距恒等式只证充分性,不会自己造出乘数。存在性来自把 Farkas 用在成本向量及活动零坐标锥:若无乘数,分离向量就成为可行改善方向,违反最优性。原始最优值取得则是更早的上图锥论证。分清这两步,才不会假设欲证的证书而循环论证。
例题详解
例题 5.1.5
(明确的不可行乘数)
方程 、 左端相同、右端不同。取 ,有 ,但 。任何非负可行点都会导出 。严格负标量是可核验证书,不是未成功搜索的记录。
例题 5.1.6
(完整求出敏感度函数)
最小化 ,限制 及全部非负。可行需 。当 ,取 ,对偶 ;其限制为 ,双方值为 。
当 ,取 及 ,同样可行且同值 。故
旧乘数超过二仍对偶可行,却只给下界 ;使它精确的原始基已不可行。可行乘数不能无条件当成全局精确价格公式。
例题 5.1.7
(角点有多个支撑斜率)
时, 对每个 都可行且值二,给
负 时最小斜率一给最高下界;正 时最大斜率三给最高下界。左导数一、右导数三,通常导数不存在。对偶不唯一正确记录这个角点,并非计算矛盾。
概念视角分析
值函数是有限个线性函数的最大值
若 有满行秩,对偶多面体 不含直线,所以只有有限个顶点 ,而在其上有上界的线性目标必在某个顶点取得最大值。强对偶于是给出:凡 有限之处,。因此 是凸的分段线性函数。在上例中顶点为 与 ,得 ; 的拐角正是两个顶点同时最优之处。
一般基的参数范围
删冗余等式行后,最优基满足 。只改右端,约化成本不变;原基在 的区域保持可行及最优,值恰为 。这些线性不等式给精确多面参数范围。若基本值全正,连续性给一个开邻域,局部值函数为仿射且梯度为乘数;若已有零基本值,某些方向可立即离开区域,可能出现角点或可行边界。因此同一个基计算既解释平滑的局部价格含义,也解释这种含义的界限,无须预先假设可微。成本扰动则会改约化成本,需要另一套检查,不能直接沿用右端公式。
常见错误
常见错误
(把零值当作不可行证书)
不可行证书需要严格负值, 并未把 分离到锥外。这样的向量或许另有用途,却不能证明系统无解。例如 对任何系统都满足 及 。
常见错误
(照搬另一种惯例的对偶符号)
对偶符号取决于本节最小化等式惯例,不能照抄前节最大化上界形式;两者模型不同。先由可行不等式推弱对偶,才相信记忆中的符号。
闭性不能从最近点论证中删去。目标值能否取得是另一回事;在这一点上,强对偶的多面体假设不能放宽为闭凸。
反例模式
有限下确界不被取得的闭凸集
一个看似合理的说法是:可行集闭凸且下确界有限的凸问题,会像线性规划一样取得下确界。在 上最小化 。 是凸函数 ()图像上方的区域,所以是凸集。尽管描述中有严格不等号,它仍是闭集:若 收敛,则 有界,设上界为 ,于是 ;极限满足 及 ,故属于 。点 的目标值为 ,所以下确界为 ,但 中每点都有 。取得性证明用的是有限生成上图锥的闭性;弯曲的集合没有这种表示,这个例子并不违反多面体情形的取得定理。
总结
有限生成锥闭,最近点给 Farkas,上图锥给原始取得,再一次择一产生最优乘数。敏感度由对偶可行性配原始基可行范围推导。每步回答不同问题,不能把存在、核验及局部变化率混成一句话。
练习
快速检查
(对 给 Farkas 证书。)
解答 · 答案
取标量 ,有 而 。等式虽有自由实数解,却无非负解。
快速检查
(最小化 ,限制 ,求原始、对偶最优及互补乘积。)
解答 · 答案
值六。对偶最大化 ,限制 ,故 取得六。余量 ,乘积为 。正余量与零原始变量完全相容。
快速检查
(求例中 ,比较保留乘数 所给两个界。)
解答 · 答案
值分别 ,旧乘数界为 。第一个精确,第二个严格偏低,因原基候选松弛 已负。
快速检查
(证明任一最优对偶在扰动值有限处支撑 。这足以证可微吗?)
解答 · 答案
对偶可行集不依赖右端,故弱对偶给 ,原最优性给 ,相减即得。不能推出可微; 的支撑斜率区间及不同左右导数已是反例。