为什么存在性需要另外证明
在凸优化问题中,一阶最优性条件可以证明某点是最小点;例如,无约束可微凸函数在梯度为零的点取得最小值,但这个条件本身不能保证这样的点存在。即使函数连续且凸,它的下确界也可能永远取不到。尚待处理的是逃逸问题:一列目标值越来越好的可行点,会不会走到任意远的地方?渐退方向描述一条直线路径:沿此方向平移整个凸可行集,仍不会离开该集。当可行集无界、不能一开始就假设紧致性时,这个概念特别有用。
下文所有空间均为有限维欧氏空间。一个集合若包含在某个半径有限的球内,就称为有界。最小点是取得下确界的可行点;仅有有限下确界,并不保证最小点存在。有关渐退方向的结论,需要所述的闭性与凸性假设,不能仅凭一幅无界集合的图像就断定。
由一条射线推出整个集合可平移
对非空闭凸集 ,定义其渐退锥为
零向量一定属于这个锥。它是一个闭凸锥:定义中的每个条件对 都是闭条件;乘以非负标量只会改变参数 ;而若 都属于锥,凸性保证 属于 ,再用 代替 ,就知道 也属于锥。更一般地,任意非负线性组合都属于它。
定理 5.3.1
(一条射线就能确定渐退方向)
设 非空、闭且凸。若存在一点 ,使每个 都有 ,则 。此外, 有界当且仅当 。
证明
(收缩的凸组合与取极限)
固定 及 。对每个足够大而满足 的整数 ,凸性给出
这些点收敛到 ;由于 是闭集,极限也属于 。这就证明了第一项结论。若 有界,非零渐退方向会产生一条无界射线,因此其渐退锥只能含零向量。
反过来,假设 无界,选取 及 ,使 。单位球面的紧致性保证 有一个子序列收敛到某单位向量 。固定 后,最终有 ,所以凸组合 属于 。由闭性得到 。这对每个固定的 均成立,再用第一项结论,就知道非零向量 是渐退方向。
证明透视
闭性如何把射线转移到每个起点
闭性用了两次,每次都在最后一步。在第一项结论中,凸组合 对每个足够大的 都属于 ,只有闭性才能把误差项 去掉。不显然的一步是把远点 向外推,同时把其权重 缩小,使从 出发的位移除该误差外总是 。凸性保证每个中间点都可行。在反方向中,单位球面的紧致性从一列无界序列造出候选方向,闭性再次让我们取极限,第一项结论则把从 出发的射线提升为渐退方向。
取极限这一步不能省略,下面的集合说明了这一点。
反例模式
一条射线的定理不能省略闭性
设 是 中射线 与点 的凸包。因此 包含 ,但其中第二个坐标为 的点只有 。定义
集合 是凸的:边界部分内的线段仍在 中;若线段有一端的 为正,则除了另一端可能例外,线段上点的 都为正。这个集合不是闭集。从 出发、方向为 的整条射线都在 中,可是 不在其中。因此 不属于 。证明中的取极限步骤确实使用了闭性。
线性约束及最小值取得的定量判据
设 ,并假设 非空。则
事实上, 保证对所有可行的 及 ,均有 。反过来,若 的某一个分量为正,则对任何可行起点 ,沿 移动时,相应的不等式最终都会失效。等式约束 同理带来条件 。因此,只要已知可行集非空,渐退锥就由约束的法向量决定,而与右端项无关。
定理 5.3.2
(线性目标取得最小值的充分条件)
设 非空、闭且凸,并令 。若每个非零 都满足 ,则 在 上取得最小值,且其最小点集合非空且紧致。
证明
(紧致的次水平集)
任取 ,并令 。这个非空集合是闭且凸的。若它无界,前面的定理就给出一个非零 。因为 ,射线 位于 中,所以 ;而定义 的上界也迫使 ,矛盾。因此 紧致。 的连续性保证它在 上取得最小值,而 以外的点,其目标值都大于 的目标值,所以这也是 上的最小值。最小点集合是 的闭子集,因此也紧致。
严格不等式是取得最小值的充分条件,并非必要条件。若某个渐退方向满足 ,则沿该方向从任意可行点出发,目标值均趋向 。若某个非零渐退方向满足 ,沿该方向移动就不改变目标值;假如最小点存在,这会使最小点集合不紧致,却不会仅凭这一点就阻止最小值取得。余下的一种情况是下确界有限,却没有最小点;即使可行集闭且凸、目标为线性函数,这仍可能发生,下面的例子会展示这一点。
例题 5.3.3
(同一个无界集合上的三个目标)
设 。它的渐退锥正是 本身。对 ,每个非零 均有 ,所以定理保证最小点集合紧致;直接检查可知唯一最小点是 。对 ,方向 的目标变化率为零。最小值仍然取得,所有 对应的 都是最小点,因此最小点集合无界。对 ,方向 的目标变化率为负,所以下确界是 。每个非零渐退方向上的变化率均为正,保证最小点集合紧致;负变化率迫使下确界为 ;非零渐退方向上的零变化率,则在最小点存在时排除最小点集合的紧致性。 取得最小值,是由直接检查得知的。
例题 5.3.4
(多面体可行集)
设 ,并最小化 。把约束写成 ,渐退锥由 、 及 给出;最后一项是多余条件,所以 是非负象限。对每个非零锥中向量,目标变化率 均为正,所以定理证明最小值取得。为求最小点,固定 :最小的可行 是 。当 ,目标值至少为 ;当 ,则至少为 。只有 取等号,所以它是唯一最小点,最小值为 。右端项 对渐退锥毫无影响,只用来确定最小点的位置。
反例模式
可行集闭、下确界有限,却没有最小点
设 ,并最小化线性目标 。由于 连续且凸,其上图集闭且凸。每个可行点都有 ,但 可行,且其目标值趋向零。因此下确界为零,却取不到。这里 是目标变化率为零的渐退方向。此例否定了“闭且凸加上有限下确界,就能推出最小值取得”的推论,也说明零变化率的渐退方向本身不能判定最小值能否取得。
非线性目标与次水平集
同样的紧致性推理不需要线性假设。
命题 5.3.5
(有界次水平集给出最小点)
设 非空且闭, 连续。若某个非空次水平集 有界,则 在 上取得最小值,而且最小点集合紧致。
证明
(限制在次水平集上)
是 在闭集上连续函数下的原像,所以是闭集;它又有界,因此紧致。非空紧致集上的连续函数取得最小值,设在 取得。 以外的点,其函数值大于 ,所以 是 在整个 上的最小点。最小点集合 是 的闭子集,因此紧致。这个存在性论证并不需要凸性。
一个有用的充分假设是在 上的强制性:对每个满足 的序列 ,都有 。此条件使每个次水平集都有界。强制性是充分而非必要条件: 上的常数零函数处处取得最小值,却不具强制性。另一个不同的条件——严格凸性——则保证唯一性:若 凸,且 在 上严格凸,两个不同最小点的中点就会有严格更小的函数值。严格凸性本身不保证存在性: 在 上严格凸,却只会趋近零而不取到零。
常见错误
(强制性要在 上检验,而不是在 上)
取 及 。在 上它不具强制性,因为 而 ;但当 时这些点并不可行。对于满足 的可行序列,有 ,所以 ,从而 。因此 在 上具强制性,其最小点集合 紧致。若在整个空间检验强制性,就会错失一个有效的存在性论证。
例题 5.3.6
(有存在性而无唯一性)
设 ,定义在 上。它连续且具强制性,因为当 时 。其次水平集 非空且紧致,所以命题保证最小点存在。由 ,候选点为 及 ,而 、。因此最小值是 ,在 及 同时取得。存在性不需要凸性;唯一性失效,是因为 不凸: 大于 与 的平均值 。
概念视角几何
存在性与唯一性回答不同问题
非空紧致次水平集包含一个最小点,并让我们选取一列有界的最小化序列。严格凸性则阻止两个不同点同时具有最低函数值。两个条件互不蕴含: 上的 同时具有两种性质;常数函数取得最小值,但最小点不唯一; 则严格凸,却不取得最小值。
练习与解答
快速检查
(在 上最小化 。求最小点,并判断最小点集合是否紧致。目标函数在 上是否具强制性?)
沿方向 观察。
解答 · 答案
由于 ,最小值是 ,并在所有 对应的 取得。这个集合闭但无界,因此不紧致。沿 ,范数趋向无穷,但目标值保持为 ,所以目标在 上不具强制性。然而它仍然取得最小值。这里没有把线性目标的定理用于 。
快速检查
(在 上最小化 。求下确界,并判断它能否取得。次水平集命题的哪个假设不成立?)
追踪序列 。
解答 · 答案
下确界为零,因为 时的 趋向零,但每个可行的 都有 。虽然可行集及其次水平子集均有界,但这里每个非空次水平集都是区间 或 ,不是 中的闭集,因此不紧致。特别地,序列 没有可行极限。由于 不是闭集,命题不适用。
快速检查
(设 。证明 是渐退方向。对 、 及 ,分别求下确界,并判断它能否取得。)
对 ,不要只考虑直线射线。
解答 · 答案
加上 只会增加 而不改变 ,所以对所有 均保持可行。对 ,有 ,且只在 取等号,所以最小值为零。对 ,可行射线 使目标值趋向 。对 ,可行点 使目标值趋向 。竖直方向对 的变化率为零,说明一个零变化率方向既不能排除沿弯曲序列逃逸,也不能证明下确界有限。事实上,这里的渐退锥只有向上的竖直射线:非零水平分量会使 随 二次增长,而 只会线性增长。若 且 ,则 最终会低于固定的 。