为什么需要资格条件
在约束最小点处,目标函数的负梯度可能由约束梯度平衡。但即使可行集很简单,描述它的约束梯度也可能毫无作用: 描述单点集 ,其梯度在零点却是零。在此集合上最小化 ,零点是最小点,但没有任何乘子能使驻点方程 成立。因此,断言乘子存在之前,我们需要的是对约束表示方式的条件,而不仅是对可行集的条件。
设 和 在可行点 附近连续可微;不等式写作 ,等式写作 。令 ,。非活跃不等式已经严格成立,在附近仍然严格成立。
定义 4.2.1
(Mangasarian–Fromovitz 约束资格条件)
若下列两项成立,称 处满足 Mangasarian–Fromovitz 约束资格条件(MFCQ):
- 的行向量线性无关;并且
- 存在向量 ,使 ,并对所有 有 。
若 为空,第二项自动成立,取 即可;若没有等式,第一项自动成立。MFCQ 要求有一个方向,一阶上不违反等式,并走向所有活跃不等式的严格一侧。它比要求所有等式及活跃不等式梯度线性无关(LICQ)更弱。
命题 4.2.2
(LICQ 推出 MFCQ)
若梯度 及 ()线性无关,则 处成立 MFCQ。
证明
(指定方向导数)
的各行都在这组线性无关的梯度之中,所以线性无关。把所列梯度依次排成矩阵 的各行。各行线性无关意味着 行满秩,故对任何右端 , 都有解。取 在等式行为零、在每个活跃不等式行为 。所得的解满足 ,且对 有 。
反过来不一定成立,下面重复约束的例子会说明这一点。
由线性化方向得到乘子
定义线性化锥
定理 4.2.3
(MFCQ 与 KKT 条件)
若 是局部最小点且满足 MFCQ,则存在 和 ,使
此外,这些乘子对的集合有界而且闭,因此是紧致集;它不一定只有一个元素。
证明
(推入严格一侧,再归一化)
任取 及一个 MFCQ 方向 。对每个 , 满足 ,并使每个活跃不等式的一阶变化严格为负。由于 行满秩,隐函数定理给出满足等式的曲线 ,其中 为充分小的正数。对每个活跃约束,;非活跃约束仍然严格成立。局部最小性给出 。令 ,得到对所有 都有 。
有限维 Farkas 择一定理于是给出 ,其中 。把非活跃乘子设为零,便得到驻点条件及互补条件。
要证明有界性,反设有一列乘子对的范数趋于无穷。用各自的范数除驻点方程,并取归一化乘子对的收敛子列。其极限 的范数为一,活跃乘子非负,而且
与 作内积:等式项消失,而每个 都严格为负,所以所有 都为零。 行满秩再推出 ,与范数为一矛盾。乘子集合由闭的等式和不等式定义,因此是闭集。
证明透视
一个方向做两件事
MFCQ 方向 用了两次,目的不同。在存在性部分,它把任意线性化方向 倾斜成 ,使之严格指向每个活跃不等式的内侧;只有这样,隐函数曲线才保持可行,而 行满秩正是使该定理适用于等式的条件。不等式 是闭条件,所以可令 。在有界性部分,关键一步是归一化:除以发散的范数会消去 ,只剩非零异常乘子的齐次方程。把该方程与 配对,就证明这样的乘子不存在,因为剩下的每个系数都有严格的符号。行满秩第二次用于消去 。没有 MFCQ,齐次方程可以有非零解;下面的反例说明乘子集合此时会变得无界。
关键是排除了上述齐次方程的非零异常乘子。这里的有界性针对固定点及固定表示方式;它本身不保证数值算法收敛,也不保证邻近问题的乘子连续变化。
概念视角代数
把 MFCQ 看作不存在异常乘子
MFCQ 有一个等价的对偶形式:它成立当且仅当
的唯一解是 、。有界性证明用了其中一个方向:与 作内积迫使 ,行满秩再迫使 。反方向来自一个 Farkas 型的择一定理。原始形式靠给出 来确认;对偶形式则只要给出一个异常乘子就被否定,正如下面的反例。
例:重复约束
例题 4.2.4
(一整段乘子)
在 、 下最小化 。唯一最小点是 。两个活跃梯度 和 线性相关,故 LICQ 失败;取 ,两个内积分别是 和 ,所以 MFCQ 成立。驻点条件要求
所有 ()都是乘子对。集合有界但乘子不唯一:相同的支撑作用可以分配给冗余的描述。
常见错误
(把乘子当作可行集的性质)
约束重新缩放会改变乘子的数值,尽管可行集不变:在上例中,把 换成 ,系数 就变成 。乘子属于约束的某种表示方式,只有在 LICQ 之类的资格条件下才唯一。
约束梯度线性无关时,乘子便被确定。
例题 4.2.5
(一个等式与一个活跃不等式)
在 及 下最小化 。可行点为 ,,而 ,所以 是最小点。此时 ,。取 ,则 且 ,故 MFCQ 成立。驻点条件为
即 及 。因此 、。两个梯度线性无关,所以 LICQ 也成立,乘子对唯一。
定义的边界情形,是没有任何活跃约束的点。
例题 4.2.6
(没有活跃不等式)
在 下最小化 。最小点 满足 ,所以 为空,也没有等式;取 即满足 MFCQ。互补条件迫使 ,驻点条件 于是化为无约束条件。乘子集合是单点 ,正如定理所说是紧致集。
资格条件失败时
在单点问题“最小化 ,满足 ”中,活跃梯度为零,没有方向能使其一阶严格减少。MFCQ 失败,而且如上所见不存在 KKT 乘子。
反例模式
没有 MFCQ 时乘子集合可以无界
保留约束 ,但把目标改为 。最小点仍是 ,该处 MFCQ 仍然失败。驻点条件为 ,在 处对每个 都成立。所以 KKT 乘子存在,但乘子集合是整条射线 ,并非有界。事实上 满足齐次方程 :它是异常乘子,正是 MFCQ 所排除的。定理的有界性结论需要资格条件。
这个例子也说明,MFCQ 失败不代表 KKT 必定失败。资格条件保证有用的结论;个别问题即使没有它,仍可能存在证书。
练习与解答
快速检查
(在 、 下最小化 。验证原点处的 MFCQ,并按 的约定求乘子。)
解答 · 答案
写成 、,方向 与两个梯度的内积都为 ,故 MFCQ 成立。驻点方程 给出 。所有可行点都有 ,因此原点确实是全局最小点。
快速检查
(在 及 下最小化 。在 处验证 MFCQ 并求乘子;LICQ 是否成立?)
解答 · 答案
,活跃不等式梯度是 。取 ,则 且 。驻点方程 给出 、。两个梯度线性无关,LICQ 也成立。等式把可行集化为 ,所以 是全局最小点。
快速检查
(某可行点没有等式约束,活跃不等式梯度是 、。MFCQ 能否成立?不需假设目标函数。)
解答 · 答案
不能。严格下降同时要求 及 ,互相矛盾。这是该点约束表示方式的性质,与目标函数无关;它不排除某个特定目标仍有 KKT 乘子。