搜索失败也可以有证书
求解 、 看似要在无穷多个候选向量中搜索。Farkas 择一原理把不成功的搜索转化成可检查的见证:找出向量 ,使它与 的每个列向量的内积都非负,却与 的内积为负。这些列向量的非负组合不可能与 有负内积。这个分离原理也解释了最优性条件中乘子的来源,以及乘子证书实际证明了什么。
以下都在有限维欧氏空间中讨论,、,向量不等式按分量理解。允许约束集合为空;特别地,没有生成向量的锥定义为 。内积和范数都采用欧氏形式。
有限生成锥的几何性质
定义 2.2.1
(有限生成锥)
把 的列向量记作 。它们生成的锥为
是凸集,而且当 、 时 。闭性值得证明:闭集在连续映射下的像不一定是闭集。
引理 2.2.2
(有限生成锥是闭集)
由 中有限多个向量生成的锥 是闭集。
证明
(化为线性无关的生成向量,再用紧致性)
每个 都能用线性无关的列向量表示。先取任一表示并删去零系数。若剩下的向量线性相关,取非零关系 ;必要时把 换成 ,使某个 。令 ,以 代替 。系数仍非负、至少一个变成零,而表示的向量不变。重复这一步,直至剩下的向量线性无关。
现在令 收敛至 。线性无关的列向量子集只有有限多个,故可取子序列,使它们都使用同一子集 。若 为空,这些向量都为零。否则映射 是单射,因而存在 使 :只需在紧致的单位球面上取 的最小值。因此对应的系数向量有界。再取子序列使之收敛至非负向量 ,便得 。在欧氏空间中,序列闭性即给出闭性。
择一原理
定理 2.2.3
(Farkas 择一原理)
以下两个系统恰有一个有解:
- 且 ;
- 且 。
证明
(把 b 投影到锥上)
两者不能同时成立,因为 。反之,若第一个系统无解,则 。取 在非空闭凸锥 上的最近点 。投影性质给出对每个 都有 。分别代入 和 ,得 。因此令 ,每个 都满足 ,而
每个列向量都属于 ,所以 。
证明透视
闭性与锥性质用在哪里
容易的一半只用到 和 。困难的一半有三步。第一, 的闭性保证最近点 存在且属于 ;由于 ,便有 及正的间距 ,有限生成正是在这里用到。第二, 是锥,所以 和 都是可用的检验点;对一般凸集,投影不等式只给出仿射分离 ,锥性质则把它变成齐次的 ,并有 。第三,在生成向量本身处检验,便把这个结论变成 。 的严格性则来自正交关系 与 。
例题 2.2.4
(用简短证书取代搜索)
考虑 ,其中 。方程给出 、,所以此系统不可行。证书为 :它与两个列向量的内积分别是 、,但 。检查这三个内积无须依赖上面的解方程过程。
常见错误
(放宽证书中的严格不等式)
严格不等式不能放宽为 :即使第一个系统可行, 也会满足第二个系统。此证书证明的是不可行,不是近似解。
不等式形式
同一择一原理也可以对线性不等式组表述。
推论 2.2.5
(不等式形式的 Farkas 择一原理)
对 及 ,以下两个系统恰有一个有解:
证明
(拆分自由变量并加入松弛变量)
写 ,其中 ,再加入松弛变量 ,把择一原理应用于 。所得见证 满足 、 及 ,即 、,并有 。反过来,若两个系统同时有解,用非负的 乘 便得到 ,矛盾。
这个形式清楚地展示了如何把不等式相加以得到矛盾。
例题 2.2.6
(把两个不等式相加得到矛盾)
单变量系统 、 有 、。向量 非负,,且 ,所以系统不可行。具体而言,把两个不等式相加便得 。生成集为空的边界情形也一样:若 ,则 ;对 ,向量 就是证书,因为条件 自动成立,而 。
从线性化下降方向到乘子
在光滑约束问题的可行点,把活跃的不等式约束的梯度排列为矩阵 的行,把等式约束的梯度排列为矩阵 的行,并记 。线性化方向满足 和 。有没有这样的方向使目标严格下降,即 ?由于正数倍不改变齐次条件,这等价于以下系统可行:
定理 2.2.7
(不存在线性化下降方向的证书)
以下两者恰有一个成立:(i) 存在 使 、 及 ;(ii) 存在 和不受符号限制的 ,使
证明
(对归一化系统应用不等式形式的择一原理)
把 写成 和 。若上述归一化的下降系统不可行,不等式形式的择一原理给出 ,使
因此 ;除以 并令 。反过来,若上述乘子方程和严格下降方向同时存在,与 作内积便得到
与严格下降矛盾。等式乘子不受符号限制:它是两个非负乘子之差。
对约束为 、 的最优化问题,给不活跃的不等式约束赋零乘子,上述证书便是 KKT 条件中的驻点、乘子符号和互补松弛部分。它来自不存在线性化下降方向,而非仅仅来自可行性。在局部最小点,要另用 MFCQ 等约束规范条件证明这类方向不存在:它把线性化方向与实际可行曲线联系起来。
常见错误
(把 KKT 证书当作最小点证书)
对一般非凸问题,KKT 证书本身不能证明最小;还要检查凸性或其他充分条件。上述定理只排除了该点的严格线性化下降方向。
例题 2.2.8
(从方向检验求乘子)
在 、 下最小化 。在 ,活跃约束的梯度为 、,而 。线性化约束给出 和 ,所以 ,不可能严格线性化下降。驻点方程 给出 、。此例中,可行性本身给出 ,另外证明了全局最优。
实际方向和线性化方向的区别很重要;没有约束规范条件时,即使在真正的最小点,乘子结论也可能失效。
反例模式
没有乘子的全局最小点
断言:光滑问题的每个局部最小点都有满足驻点条件的乘子。考虑在 下最小化 。唯一可行点是 ,因而它是全局最小点。但该处活跃约束的梯度为 ,故每个 都是线性化可行方向,而 给出 :存在严格线性化下降方向,没有乘子能满足 。修正后的表述须加上约束规范条件。此处 MFCQ 不成立,因为没有 满足 ;在 MFCQ 下,局部最优排除了线性化下降方向,上述定理便提供乘子。
练习与解答
快速检查
(令 、。找出 、 的不可行证书。)
一个数 就足够。
解答 · 答案
取 ,则 且 。
快速检查
(令 、、。求乘子证书,并解释为何没有严格线性化下降方向。)
先解驻点方程,再与方向条件对照。
解答 · 答案
驻点方程 给出 、。也可直接看出 给出 , 给出 ,所以 。
快速检查
(在反例 中, 能否是通过 的可行曲线的导数?为什么?)
先描述可行集。
解答 · 答案
不能。可行集只有 ,所以每条可行曲线恒为零,其导数也是零。没有适当的正则性时,线性化方向不一定是实际的可行速度。