只观察可行方向上的曲率
考虑
其中 , 满行秩,且 。这些条件保证每个 都有可行解,却没有要求 正定。约束可能排除负曲率方向;反过来,只有违反约束的方向具有正曲率,并不能保证可行集上有最小值。
取任一可行点 ,令 的列构成 的一组基。每个可行点都能唯一写成 。代入得到
定义 4.3.1
(零空间基与约化 Hessian)
若矩阵 的列构成 的一组基,就称它为约束的零空间基。对称矩阵 称为约化 Hessian,而 称为可行点 处的约化梯度。
的具体元素随基而变,但正定性和半正定性不变: 恰好衡量原目标沿可行方向的曲率。
定理 4.3.2
(完整分类)
问题 (1) 存在最小点,当且仅当 半正定且 。存在时,全部最小点为 ,其中 。最小点唯一,当且仅当 正定。其余情况下,目标函数在可行集上无下界。
证明
(分别检查弯曲方向和平坦方向)
由 (2),只需研究 上的 。若存在 使 ,则 时 。现在假设 。由对称性,。若 不在该值域中,便有 使 ;适当选择 的符号,就有 。
若 在值域中,取 使 。配方得
故 是最小点。对于半正定矩阵,二次型为零等价于向量属于其核,所以其他最小点与 之差恰好属于 ,也就是说它们正是 的解。因此唯一性等价于核为零,即 。
证明透视
两种失败方式从何而来
代入式 (2) 是约束唯一出场的地方;此后问题变成关于 的无约束二次问题, 的满行秩只用来保证存在可行点 。证明接着分开两种失败方式。负曲率由一个满足 的方向揭示,线性项无法补救,因为二次项增长更快。平坦方向更微妙: 的对称性用于 ,把代数条件 转成几何事实,即存在一个平坦方向,约化梯度沿它有非零分量。其余情形的关键一步,是围绕 的解配方,把与每个竞争点的差写成 的二次型。唯一性一步再次用到半正定性:对不定矩阵,二次型为零并不迫使向量落在核中。
常见错误
(检查完整 Hessian 而不是约化 Hessian)
不定并不排除唯一的约束最小点,约束可能去掉所有负曲率方向:对 及约束 ,约化 Hessian 是 。决定分类的只有 ,即沿可行方向的曲率。 正定确实给出 ,但那只是充分条件,而不是判别准则。
乘子与完整算例
在可行点处,沿所有可行方向的一阶导数为零,即 。因为 ,这恰好等价于存在乘子 ,满足
满行秩保证给定驻点的乘子唯一。该系统寻找驻点,不能自动保证最小。它能否唯一确定驻点,同样取决于 。
命题 4.3.3
(KKT 矩阵的可逆性)
在问题 (1) 的假设下,(3) 的系数矩阵可逆,当且仅当约化 Hessian 可逆。
证明
(在零空间坐标中解齐次方程组)
考虑齐次方程组 、。第二式给出 ;由于 ,把第一式左乘 得 。若 可逆,则 ,故 ;再由 单射及 得 。反之,若有非零 使 ,则 与 的每一列正交,故属于 ,可写成 。因 的列线性无关, 是非零齐次解。
例题 4.3.4
(约束改变无约束解)
最小化 ,满足 。取 ,。此时 ,,故 ,,。于是 ,。该点梯度为 ,所以乘子 满足 (3)。因为 ,它是唯一的全局约束最小点,函数值为 。无约束最小点 不可行。
和 的数值与基绑定,最小点却不然。
例题 4.3.5
(换一组零空间基)
改用 重做计算。则 ,,所以 ,而 ,是同一点。把基放大 倍使 乘以 、 乘以 ,但 的符号和解集都不变。
分类的边界情形,是约化 Hessian 奇异却仍有最小点。
例题 4.3.6
(奇异约化 Hessian 与一整条最小点)
最小化 ,满足 。此时
取 ,并以 为 的列。则 奇异,而 。 的解为 ,所以最小点是所有实数 对应的 ,函数值都是 。在每一点 ,且 满足 (3)。KKT 矩阵如命题所料是奇异的,但方程组相容。
反例模式
KKT 矩阵可逆仍可能得到最大点
最小化 ,满足 。此时 ,,,因而 可逆。KKT 方程组唯一解为 ,但 。可逆只保证驻点唯一,不保证它是最小点;分类还需要 。
练习与解答
快速检查
(最小化 ,满足 。写出全部最小点。)
解答 · 答案
每个 都是最小点。取 ,则 且 ,约化目标为常数。
快速检查
(最小化 ,满足 。最小点是否存在?)
解答 · 答案
不存在。,但 不属于其值域 ;可行点 的函数值 。
快速检查
(若 ,约束为 , 的约束最小点唯一吗?)
解答 · 答案
唯一。约化 Hessian 是 ,因此 是唯一最小点,尽管 在整个空间上不定。
满行秩简化了乘子的讨论。冗余方程可以描述同一个可行集,但乘子可能不唯一;使用 (3) 前,应先去掉冗余,或另行说明适用的结果。