线性子空间只是约束的一种。可行向量也可能必须具有非负坐标,或位于超平面的某一侧。此时从最近点出发的残差一般不与所有可行方向正交:有些方向不允许移动。正确的替代条件是一个不等式,它还引出了约束最小化的迭代方法。
定义 4.2.1
(凸集及其投影)
全文令 为实 Hilbert 空间。若 且 时都有 ,则称 为凸集。当 非空、闭且凸时,其投影 表示 中离 最近的唯一点;其存在性与唯一性正是下面定理的一部分。
最近点与一个不等式
定理 4.2.2
(到闭凸集的投影)
设 非空、闭且凸。对每个 ,存在唯一 满足 。 是这个最近点当且仅当
证明
(极小化序列与单侧导数)
令 ,选取 使 。由凸性,,故它到 的距离至少为 。平行四边形恒等式给出
右侧趋于零,因此 是 Cauchy 序列。完备性给出极限 ,闭性保证 ;由范数连续性,其距离为 。
对 ,当 时线段上的点 可行。在 取得最小值得
除以 并令 ,得到 (1)。反之,(1) 蕴含
所以 最近,且任何不同的 不可能同样近。特别地,第一段找到的最近点就是满足 (1) 的唯一点。
证明透视
为什么两个假设都重要
证明分为存在性和刻画两半,两者以不同方式使用假设。存在性只用一次凸性:中点 属于 ,所以其距离至少为 ;平行四边形恒等式于是把两点都接近最优转化为两点彼此接近。 的完备性给出极限, 的闭性使极限仍然可行。刻画部分第二次使用凸性,但方式不同:整条线段 留在 中,却只限于 。这种单侧性是关键一步,也是一阶条件是不等式而非等式的原因:除以 保持符号,而负的 不可用。反方向得以完成,是因为 的展开式恰好含有 (1) 所控制的项,剩下的 直接给出唯一性,无须另行论证。
若 是闭线性子空间,对每个 和 都有 。在 (1) 中分别取 与 ,得到 ,于是恢复熟悉的正交投影。其余两个假设确实不可缺少,实数轴上的两个子集就能说明。
反例模式
缺少闭性或缺少凸性
断言:每个非空凸集,或每个非空闭集,对每个 都恰有一个最近点。在 中,凸集 满足 ,但没有 使 ,所以没有离 最近的点。闭但非凸的集合 有 ,所以 有两个最近点。定理两个假设都需要:闭性保证存在,凸性保证唯一(以及 Cauchy 论证)。
常见错误
(把不等式换成正交条件)
对一般闭凸集,残差 不一定与 正交。取 、,则 ,而 在 时为负,并非零。只有当每个可行方向都可以反向时(例如子空间),才有正交性;在凸集的边界点上只能用不等式 (1)。
例题 4.2.3
(到闭单位球的投影)
令 。若 ,则 。否则令 ,于是 ,且 ,其中 。对 ,Cauchy–Schwarz 给出 ,因此
由 (1),。在边界情形 ,两个公式都给出 。
投影的稳定性
命题 4.2.4
(投影的坚定非扩张性)
对非空闭凸集 及所有 ,
特别地,。
证明
(把两个变分不等式相加)
令 、。在 处以 应用 (1),得 ;在 处以 应用 (1),得 。两式相加,
整理即得 (2)。Cauchy–Schwarz 不等式把 (2) 的右边控制为 ; 时约去 ,得 , 时此估计显然成立。
因而输入的微小改变不会放大投影之间的距离。此不等式强于连续性,但并不声称严格压缩。
例题 4.2.5
(到半空间的投影)
固定非零 和 ,令 。若 ,则 。否则令 、。则 ,所以 位于边界上,且对每个 ,
由 (1) 得 。例如在 中, 到 的投影使用 、、,结果为 。
约束二次问题与迭代
令 有界、自伴,并假设存在常数 ,使得
对固定的 ,在非空闭凸集 上最小化 。
定理 4.2.6
(约束二次最小化)
在上述假设下, 在 上有唯一最小点 ,它由变分不等式刻画:
对 及任意 ,投影迭代 满足 ,其中 。
证明
(不动点解出变分不等式的压缩映射)
若 ,一切显然。否则定义 。由 (2)(特别是非扩张性)及自伴性,
当 非零时,Cauchy–Schwarz 不等式给出 ,所以 ,且 。步长条件使它严格小于一,因而 属于 。完备空间 上的压缩映射定理给出唯一不动点 ,且迭代满足 。对点 应用 (1),方程 表示对所有 有 ;由于 ,这恰为 (3)。
对任意 ,令 ,利用自伴性得
因此 是唯一最小点。反过来,若 在 上最小化 ,对于 , 在 处的单侧导数为 且非负,于是得到 (3)。
常见错误
(压缩来自梯度步,而非投影)
投影本身不是压缩映射:对 及输入 和 ,两者的投影都是自身,。证明中的因子 来自 ,用到了强制常数 。 的非扩张性只保证投影不会抵消这个收益。
对 的估计只是充分条件,并非断言更大的步长一定失败;但步长必须有某种限制。
反例模式
步长过长
断言:投影迭代对每个步长 都收敛。取 、(闭且凸)、、,于是 ,。迭代为 。取 得 ;从 出发,迭代在 之间交替,永不收敛。取 ,绝对值每步加倍。对每个初值都收敛恰好当 ,即 ,在此例中它恰好与保证范围 相同。
例题 4.2.7
(有限步内到达起作用的约束)
取 、、、,于是 。无约束驻点解 ,即 ,它不可行。此处 满足 (3),因为对每个 都有 。由 ,保证范围是 ;取 。则 ,所以
从 出发得到 、、,之后迭代停在 。约束在解处起作用,正是投影阻止了迭代沿梯度走向 。
练习
快速检查
(求 并验证 (1)。)
离负数最近的非负数是一个边界点。
解答 · 答案
投影为 。对每个 ,,所以 (1) 成立。
快速检查
(若 闭且凸,证明 。这是否意味着 线性?)
中的点到自身的距离为零。
解答 · 答案
已属于 ,故它在 中的唯一最近点是它自己。投影未必线性:对 ,。
快速检查
(在 上最小化 ,并验证 (3)。)
把 写成 的形式。
解答 · 答案
此处 、。候选点为 :对 ,,所以 (3) 成立。最小值为 。
快速检查
(对 ,说明非扩张估计对两个不同输入可以取等号。)
选取本身已经可行的输入。
解答 · 答案
对 、,两者的投影都是自身,所以 。