支持斜率为什么引出另一种算法
梯度描述可微函数唯一的切平面。在折角处,支持平面可能不止一个,每个都给出有效的全局下界。这种选择很有用:我们可以直接最小化绝对值、仿射损失的最大值,以及这些项的和,无须先把折角平滑化。不过,收敛论证也要改变。负次梯度未必是下降方向,因此不能直接沿用光滑函数的下降引理。
我们先建立假设可以逐一检查的运算规则。在运算部分,所有函数都在整个 上取有限值且为凸函数。这个限制排除了定义域边界的困难;它比一般凸分析定理所需的条件更强。我们会在这个设定下证明和法则,然后展示去掉限制后可能出现的失败。讨论算法时,约束另由非空闭凸集 表示,而目标函数仍在整个空间上取有限值。
几何方面需要欧氏投影,以及上一篇关于分离与强对偶的笔记所用的有限维分离定理:两个不相交的非空开凸集可由一个非零线性泛函分离;开凸集与集外一点之间存在非零的弱分离泛函。以下正是使用这两种分离结果。
次梯度是下界,并非任选的导数
对有限凸函数 ,定义
“对每个 ”这个量词十分重要。只在几个测试点支撑图像,并不足以证明某向量是次梯度。集合 是闭凸集,因为对变量 而言,上式的每一个不等式都定义一个闭半空间。
两个直接推论有助理解定义。首先, 当且仅当 是全局无约束最小点。其次,若 在 可微,则 :把支持不等式用于 ,除以正数 并令 趋于零,再以 重复,便迫使支持斜率等于梯度。凸性则保证梯度本身满足支持不等式。
有限值情况下为什么存在支持斜率
引理 5.2.1
(有限凸函数连续且处处有次梯度)
设 为凸函数。则 连续,而且对每个 , 非空。
证明
(局部上界与支持超平面)
使用开集分离前,需要先知道连续性。以下是一个基本论证。固定 ,取立方体 ,其中 。令 为 在有限个顶点上的最大值。立方体内每一点都是顶点的凸组合,所以整个立方体上都有 ,特别是 。
当 时,令 及 。凸性给出 。对 也有相同上界。再用 ,得到
所以 在每个 连续。这是以固定中心 为准的局部估计,并没有假设全局 Lipschitz 常数。
现在严格上图集 是开凸集,而 不在其中。分离定理及从 趋近该点的极限,给出非零向量对 ,使
令 向上增加,可知 。若 ,则不等式对每个 成立,迫使 ,矛盾。因此 。令 下降至 ,便得 。排除 的一步,确实用到了函数在整个空间取有限值。
附明确条件的运算规则
定理 5.2.2
(有限凸函数的和法则)
设 都是有限凸函数。对每个 ,
右方为 Minkowski 和 。
若 ,则 。若 ,则
把两个支持不等式相加,便证明和法则由右至左的包含关系。正比例及仿射项法则则可直接把定义不等式除以正数或减去仿射项,从两个方向证明。和法则反方向的包含关系需要额外论证;只把不等式相加并不能得到它。
证明
(分离两个开集以拆分斜率)
取 。对 ,记 及 。考虑
这是两个非空开凸集。次梯度不等式给出 ,所以它们不相交。两者的闭包都含 。因此可用非零 把分离不等式写成
由于两个闭包都含原点,共同的分离阈值必为零。 含向上的铅直射线,迫使 。若 ,第一个不等式对所有 成立,因为每个 上方都有 中的点;于是 ,与分离泛函非零矛盾。将系数归一化为 。
分别取极限至两个图像边界,得到
所以 且 。这就证明了缺少的包含关系,从而得到等式。
证明透视
困难的包含关系为何需要分离
把支持不等式相加,只能得到 。反方向的包含要把和的一个支持平面拆成两部分,而不等式 并没有说明如何拆分。证明把问题转成几何: 位于 图像上方, 位于 图像下方,而 的次梯度不等式正好等价于两者不相交。在整个 上取有限值这个假设用了两次:它使 与 连续,两个集合都是开集,从而可用开集分离;它又保证每个 上方都有 的点,迫使 。取 后,分离斜率 是分给 的部分, 则是分给 的部分。下面的反例显示,当某个函数只在半直线上有限时,这样的拆分未必存在。
反复使用便得到有限多项的和法则。系数为零时应直接处理:常数零函数的次微分为 。乘以负数一般不保留凸性。
有限个仿射函数之最大值的精确公式
设
命题 5.2.3
(仿射函数最大值的次微分)
设 及 如上,则对每个 ,
证明
(活跃部分与投影)
每个活跃仿射函数都是全局下界,并在 与 相接。因此它的斜率是次梯度;次梯度的凸组合仍是次梯度。
反过来,假设 不在活跃斜率的凸包 内。该凸包非空、紧致且凸。令 及 。投影不等式给出每个活跃斜率都满足 ,而 。因此 。非活跃仿射函数在 有正的差距,而且函数数目有限,所以对所有充分小的 ,它们在 的值都不超过 。某个达到斜率 的活跃函数恰好取此值,因此 ,与 的支持不等式矛盾。故每个次梯度都在所述凸包内。
概念视角几何
折角同时保留多个活跃线性模型
对 ,零点的活跃斜率为 及 ,其凸包是 。离开零点,只有一个仿射函数活跃。折角处的区间并不表示普通导数可以随意选取;它记录的是所有全局支持直线。
若有限凸函数 对欧氏范数满足全局 -Lipschitz 条件,则每个 都有 。事实上,在 同时使用支持及 Lipschitz 不等式,可得对每个单位向量 及 都有 。当 时,取 即可。若有限个仿射函数的斜率皆有 ,其最大值便有此性质;凸包公式也直接给出次梯度界。
例题 5.2.4
(三条直线最大值的次梯度)
求 的 及全局最小值。
在零点,首两个仿射函数活跃,斜率分别为 及 ;第三个函数的值为 。因此 ,包含零。最小值为 。直接看, 时第一个仿射函数至少为一, 时第二个至少为一。当 时,相应的界为严格不等式,所以零是唯一最小点。
去掉定义域假设后会怎样
反例模式
不加条件的广义值和法则是错的
允许以 把点排除在函数的定义域之外。在定义域内的点,沿用相同的支持不等式来定义次微分;函数值为 的地方,不等式自动成立。在 上定义
这两个函数都是真、下半连续的凸函数;这里“真”指从不取 ,且至少在一点取有限值。在零点,若 ,则对每个 都须有 ,即 。当 下降至零,没有有限 能满足此条件,所以 是空集。另一方面,,而 ,故 。但两个个别次微分的和是空集。
正确做法是使用附有实际假设的和定理。本节在整个 取有限值的定理,是一个充分版本。这里并未证明一般以定义域相对内部为条件的法则。
投影次梯度步骤
设 非空、闭且凸,而 为有限凸函数。选择 、正步长 ,以及任意 ,并令
在这些假设下投影唯一存在。次梯度的选取是算法的一部分:在折角处,不同的合法选择可以产生不同的下一个迭代点。我们假设 在 上存在最小点 ,并记 。单靠 闭并不能保证最小点存在。
为取得定量界,假设实际选取的向量满足 ,其中 已知。全局 -Lipschitz 连续是一个充分条件,但证明只用到所选向量的界。再选已知 ,使 。这些界需要就具体问题证明,并非算法自动提供的数值。
定理 5.2.5
(最佳迭代点与平均点的保证)
对每个整数 ,令
则 ,而 与 都不超过
特别是,若预先固定迭代预算 ,并在该次运行全程取常步长 ,则两个误差都不超过 。
证明
(投影、展开与相消求和)
设 及 。投影不等式 给出
令 及 。展开平方,再使用次梯度不等式,得到
移项后从 加至 ,中间的距离平方互相抵消。舍去最后非负的距离平方,便有
最小的误差不超过这些误差的加权平均。另一方面, 的凸性保证 可行,而 的凸性给出 。所以所求两个误差各自满足同一个上界。对指定的常步长, 且 ,得到 。
证明透视
目标值未必下降,改为消去相邻距离项
次梯度步未必使 下降,所以证明从不直接追踪 ,而是追踪到固定最小点的距离平方。投影到凸集 不会增加到任何可行点的距离,所以约束不带来代价。关键一步是在 的次梯度不等式中取 :它把交叉项 换成目标差距 。唯一的代价是误差项 ,这就是界中把 与 比较的原因。求和使中间的距离项互相抵消,而最后的距离非负,论证就此完成。最后再用一次凸性: 的凸性使 可行, 的凸性则以 的加权平均控制 。
常见错误
(保证并非关于最后一个迭代点)
定理计算的是 ;不能把其中最佳目标值换成 。它也没有比较平均点与最佳迭代点的目标值:两者都有可能较小。这是目标值精确度的界,并非到某个指定最小点的距离界。
若任意固定 ,相同论证给出 。令 趋于无穷后仍留下正的上界,因此此估计不能证明固定非零步长下的精确收敛。在按预算调整的界中,改变 也会改变该次运行所用步长。若 ,则 已是 的全局最小点,算法可以停止,无须计算收敛速率。
例题 5.2.6
(到欧氏球的投影)
证明到欧氏球 的投影公式,其中 。为什么不能改为把每个坐标独立截断到 ?
若 ,投影就是 。否则,对每个可行 ,反三角不等式给出 ,而 取等。由投影的唯一性,。逐坐标截值则是投影到长方盒:在二维会把 留在原位,但该点范数为 ,位于球外。
在两个折角处作完整计算
例题 5.2.7
(合法步骤可以离开精确最小点)
在 上最小化 。和法则与正比例法则给出: 时斜率为 , 时为 , 时为 。在折角处,
当 时,;当 时,;当 时,。由此可见唯一最小点是 ,最小值为 。所有次梯度的范数都不超过 。
取 ,从 出发,作以下合法选择。区间投影就是把数值截断到区间内;本表的试探点都已在区间内,所以投影不改变它们。
| 所选 | |||
|---|---|---|---|
每行都由 得出。从精确最小点走到 的一步使目标值上升。若在最小点选零次梯度,则会留在原位。这两个选择都是合法的次梯度。
另作一次预算为 的运行,同样从 出发,利用已知界 及 ,应取 。定理保证在指定的首 100 个计值点中,最佳点与平均点的误差都不超过 。这是最坏情况保证;上表用的是另一个步长。
反例模式
负次梯度未必指向下降方向
“若非零 ,则沿 走充分短的一步会使 下降”是错的。对 ,在 选 。每个 都给出 。即使是精确最小点,也可以有非零次梯度。
次梯度提供未来函数值的下界,并不提供沿其负方向的上界。因此证明利用距离控制累积的目标误差,而不假设逐步下降。最优性判别是零次梯度存在,并非所有次梯度都为零。
练习及完整解答
快速检查
(求 在 的次微分。 是否存在无约束最小点?)
逐个坐标处理,再加上仿射梯度。
解答 · 答案
在 , 的支持斜率在第一坐标形成 , 的支持斜率在第二坐标形成 。加上仿射梯度 ,得 ,不含零。这只能排除该点为最小点。为判断整个问题,固定 ,令 趋于 :。所以不存在无约束最小点。
快速检查
(设 且 ,直接证明 。)
用一个仿射部分在 的值去估计它在 的值。
解答 · 答案
对每个 ,。对 取最大值,得到 。交换 、 便得反方向的不等式。
快速检查
(假设投影次梯度定理适用,且 、。选择迭代预算与常步长,使目标误差保证不超过 。准确指出保证适用于哪些输出。)
由 解出 。
解答 · 答案
只须 ,因此可选 及 。保证适用于 及 。它没有声称最后更新点 也满足同一界;具体问题仍须符合距离与次梯度的假设。