梯度步后保持可行
无约束梯度步可能离开可行集。投影梯度法将该步投回集合,并可在适当假设下给出定量的目标界。
令 非空、闭且凸。令 凸且可微,其梯度对某个 为 -Lipschitz。假设最小点 存在。
定义 8.1.1
(欧氏投影与投影梯度法)
对 ,投影 是 中在欧氏范数下唯一最接近 的点。对 和固定步长 ,投影梯度法令
闭性和凸性保证最近点存在且唯一;约束是最优化问题的一部分,并非事后补充。
投影与三点估计
投影由一条不等式而不是公式刻画。
引理 8.1.2
(投影的变分不等式)
设 、。则 当且仅当对每个 都有 。
证明
(沿可行线段求导)
设 ,。当 时线段 可行;它到 的距离平方在零点的右导数 不能为负。反过来,若不等式成立,则对每个 ,展开 ,可知 是最近点。
特别地,对可微凸函数 ,可行点 在 上最小,当且仅当对所有 有 。取 ,这正是变分不等式,所以最优性等价于对任意 ,
此条件允许边界处 。
定理 8.1.3
(一次投影步)
对 、 及每个 ,
证明
(三条不等式与一个极化恒等式)
令 、。光滑性不等式及 给出 。凸性给出 。两式之和至多为 。把投影不等式用于点 、投影 和可行点 :
最后利用 。最后的平方项与光滑性项抵消。
证明透视
步长条件用在哪里
证明结合三条不等式,每个假设恰好用一次。光滑性给出 在 处的上界模型;凸性通过在 处的线性化比较 与 ;投影不等式是集合 唯一出场的地方,它之所以适用,是因为比较点 可行。关键一步是极化恒等式:它把投影产生的内积化为到 的平方距离之差,再减去额外一项 。这额外一项抵消光滑性罚项,而罚项不超过 恰好在 时成立; 就用在这里。若步长更长,右边会剩下正的余项 。所得右边是相邻距离之差,正因如此下一个证明才能裂项相消。
有限迭代保证
定理 8.1.4
(目标差距)
对每个整数 ,
证明
(单调性与裂项相消)
在单步不等式中取 得 。取 ,从 加到 ,平方距离相消。由于函数值不增,和中每个目标差距至少为最后的差距;因为 在 上最小,每个差距都非负。除以 即得。
定理限制最后一次迭代的目标差距。它假设最小点可以达到且投影精确。
常见错误
(把收敛率读成多于目标界的结论)
定理没有给出到唯一解距离的相同速率、舍入误差下的停止规则或不精确投影的保证。它计数的也是迭代次数,而不是实际运行时间:投影成本可能主导每次迭代。
例题 8.1.5
(边界上的最小点)
取 、、、。因 ,步长符合条件。未投影步为 ,故 ;下一个未投影步为 ,投影后仍为 。这是约束最小点,即使 ,因为能使 下降的方向不可行。
常见错误
(以为解处梯度必为零)
边界上的约束最小点不一定是 的驻点,上例的 就是如此。正确的判别是不动点条件 ,即对每个可行 有 。以 为停止准则,在这里永远不会停止。
在盒子上,投影按坐标逐个进行,各坐标可在不同时间到达边界。
例题 8.1.6
(投影到盒子)
取 及 ,故 、。用 及 。投影到盒子就是把每个坐标截断到 。
- ,故 。
- ,故 。
- ,未投影点为 ,故 。
点 是约束最小点,;该处 ,所以第一个坐标被边界挡住,第二个坐标则是无约束驻点。核对定理:,界为 ,而实际差距为 及 。
假设的作用
反例模式
闭的可行集未必包含最小点
在 上, 凸且梯度全局 Lipschitz,因为 ;但其下确界为零,没有任何有限的 能达到。故 的闭性及凸性不能推出 存在。另外,非凸集合可能有多个最近点: 时,两点都是原点的投影。
步长条件是充分条件,并非断言所有更大的步长都会失败。
例题 8.1.7
(长于 1/L 的步长)
令 、、,则 且 。取 ,迭代为 ,而 不断增大。取同样违反 的 ,迭代为 ,收敛到最小点 。定理只是没有涵盖这类步长;对这个二次函数,收敛恰好在 时成立。
习题
快速检查
(在边界例子中求 ,并解释为何非零导数不违反约束最优性。)
解答 · 答案
两者都是 。右端点的可行方向不能指向更大的 ,而目标在该方向下降。
快速检查
(若 、、,目标差距界是多少?)
解答 · 答案
至多为 。
快速检查
(为何把 的存在列为假设?)
解答 · 答案
光滑凸的 softplus 例子在闭集 上有有限下确界,但没有最小点。
快速检查
(为何 的凸性对唯一的欧氏投影重要?)
解答 · 答案
加上非空及闭性,凸性给出唯一的最近点; 说明没有凸性时唯一性可能失败。
延伸阅读
MIT 开放课程:投影梯度与镜像下降 讨论投影方法。