最优化问题包括可行决策的集合,以及给每个决策一个数值的目标函数。导数可提出候选点;可行集合与函数的形状则决定候选点有什么意义。凸性的好处是两个可行点之间的线段仍然可行,函数值也不高于端点值的线性插值。因此局部信息可推出全局结论。
凸集合与凸函数
定义 1.1.1
(凸集)
若对所有 及 ,均有 ,则 称为凸集。
空集和单点集都是凸集。凸集的交仍是凸集:交集内两点的连线位于每个集合内。仿射等式 与半空间 都是凸集,故由有限个这样的集合相交得到的多面体也是凸集。凸集的并却未必是凸集;例如 不含零。
定义 1.1.2
(凸函数与严格凸函数)
设 为凸集。若
对所有 和 成立,则 称为凸函数。若当 、 时不等式都严格成立,则称 严格凸。
概念视角几何
函数的凸性即集合的凸性
上境图 是凸集,当且仅当 是凸函数:由函数不等式可证上境图是凸集;反过来取上境图中的点 与 即得函数不等式。因此函数不等式就是高一维的集合定义,凸集的封闭性质也变成凸函数的封闭性质。同一图像说明每个下水平集 都是凸集。逆命题不成立,例如 在 上的下水平集都是区间,函数却不是凸的。
一阶与二阶判别
对可微函数,可用切平面判别凸性;对二阶可微函数,则可用曲率判别。
定理 1.1.3
(凸性的一阶与二阶刻画)
设 是开凸集, 在 上可微。则 是凸函数当且仅当
若 在 上二阶连续可微,则它是凸函数当且仅当每一点 的 Hessian 半正定。
证明
(先用差商,再限制到直线)
必要性:凸性给出对 有 ;令 即得结果。充分性:取 ,分别在 处对 和 使用不等式,再乘以 和 后相加;线性项抵消,得到凸性的定义。
至于二阶判别,沿线段令 ,其二阶导数为 。若 Hessian 半正定,则 单调不减,故 ,这正是一阶不等式。反过来,把凸函数限制在经过 、方向为 的直线上,得到开区间上的一元凸函数,其二阶导数 非负。
因此切平面是全局下界,而不只是在切点附近的近似。处处正定的 Hessian 蕴含严格凸,但并非必要: 严格凸,却有 。
局部、全局及存在性
可行点 若不大于其附近任何可行点的目标值,便是局部最小点;若对所有可行点都成立,便是全局最小点。凸集上凸函数的局部最小点必为全局最小点。否则存在更好的可行点 ;沿 至 的线段取足够靠近 的点 ,由凸性其值不超过 ,矛盾。
命题 1.1.4
(严格凸性与唯一性)
凸可行集上的严格凸函数至多有一个全局最小点。若函数连续,而可行集非空且紧致,则恰有一个。
证明
(以中点证唯一,以紧致性证存在)
若 是两个值为 的全局最小点,则中点可行,而严格凸性使其值小于 ,矛盾。若可行集非空且紧致而 连续,最值定理给出最小点,它于是是唯一的最小点。
存在和唯一是不同的结论: 在 上严格凸,下确界为零但没有最小点。紧致性是充分而非必要条件: 在非紧致的实数轴上仍有最小值。另一常用条件是闭可行集上的连续函数具有强制性,即沿任何满足 的可行序列有 。取极小化序列,它最终位于有界的下水平集内;闭性与连续性提供收敛子列,其可行极限取到下确界。
对可微凸目标,一个不等式就能证明受约束最小点。
定理 1.1.5
(凸可行集上的全局证书)
设非空凸集 包含于开凸定义域,而 在该定义域上可微且凸。 在 上最小化 ,当且仅当对所有 ,。
证明
(可行线段证必要性,切平面证充分性)
设 是最小点,。由 是凸集,点 ()都可行,所以 满足 。因此零处的右导数 非负。反过来,若不等式成立,一阶刻画给出对每个 有 。
证明透视
两种凸性假设各用在哪一步
两个方向用的是不同的假设。必要性只用可微性及可行集的凸性:后者保证由 指向 的整条线段可行;目标函数的凸性在此不起作用。充分性只用目标函数的凸性,经由切平面下界;它完全不沿线段移动。正因为切平面是全局下估计, 处的局部一阶信息已经足够,每个可行点一个不等式便完成论证。若 ,可同时在 与 处检验,不等式便化为 。
每个假设都是使用它的那个方向所必需的。
反例模式
去掉集合或目标函数的凸性
断言:对任何可行集上的任何可微目标,方向不等式都刻画最小点。必要性方面,令 ,。两个可行点都是全局最小点,但在 ,指向 的位移给出 ;目标函数是凸的,使线段论证失效的是非凸可行集。充分性方面,在 上取 。在 ,对每个可行 有 ,但 。修正后的表述就是上述定理:必要性需要凸可行集,充分性需要凸目标函数。
边界处梯度可以非零:在 上最小化 ,最小点为零,所有可行位移与梯度的内积都非负。
例子:受约束二次函数
例题 1.1.6
(以方向不等式证明的边界最小点)
最小化 ,约束为 。无约束最小点 不可行。考虑边界点 ;其梯度为 ,而对每个可行 ,
一阶条件证明它全局最优。Hessian 为 ,严格凸性保证唯一;最小值是 。这个证书比只看图像或检查几个边界点更有说服力。
强凸性与二次增长
严格凸性能区分不同点的函数值,却没有量化差距。要作数值估计,就需要一个正常数。
定义 1.1.7
(强凸性)
设 。若 在凸集 上是凸函数,则称 在 上为 -强凸。
在开定义域上可微时,对这个差函数使用一阶不等式并展开平方,可得
最后一项把强凸与一般凸性区分开来。若凸可行集上存在最小点 ,方向最优条件使中间项对每个可行 非负。因此目标值与最优值之差至少是 。若另有最优值的下界,便可由目标差距估计到最优点的距离,这可用来解释停止准则。严格凸未必有固定的正二次下界: 在零附近趋于零。
例题:检查假设
例题 1.1.8
(有平坦方向的二次函数)
考虑 上的 。其 Hessian 为 ,二次型为 ,故函数是凸的。直线 上每点的值都为零,因此有无穷多个最小点。Hessian 在方向 上奇异,严格凸性不成立。半正定性证明凸性,并不保证唯一。
例题 1.1.9
(投影到区间)
在 上最小化 。取 ,导数为 ,每个可行 满足 ,所以 。一阶证书证明 全局最优,严格凸性保证唯一。导数非零与最优并不矛盾,因为向右移动不可行。直接计算也可见整个区间上 ,故最小值为 。
例题 1.1.10
(驻点本身并不足够)
设 ,原点处梯度为零,但非零 满足 而 。因此原点的每个邻域都有较大和较小的值,它是鞍点而不是最小点。Hessian 不定。这说明梯度为零后仍须检查曲率或其他全局条件。
如何使用证书
实际证明应指出定义域、确认候选点可行、建立凸性,再检查方向不等式。无约束时先解 ,然后用支撑平面不等式证明;边界问题则应确定可行方向及其与梯度的内积。若题目要求唯一解,还须另外说明严格凸性或其他唯一性理由。
开凸域上的二阶可微函数若在某一点 Hessian 不定便不是凸的;但单点半正定不能说明其他点。Hessian 判别中的“每一点”不可省略。可行集即使由非凸函数描述,也可能本身是凸集;反之,凸目标函数在不连通的可行集上未必有“局部最小即全局最小”的性质。
线性组合、复合及注意事项
若 在同一凸定义域上是凸函数,且 ,则 是凸函数。只需将各函数的凸性不等式乘以非负系数后相加。负系数一般会使不等式反向,故此证明不适用于任意带符号的和。加上仿射函数会保持凸性,因为仿射函数在线段上取等号,减去它也不影响结果。
有限个凸函数的逐点最大值也是凸函数:对每个 ,;再对 取最大值即可。例如 是凸函数,虽然它在零处不可微。因此可微的一阶判别只适用于其假设所涵盖的函数,并非所有凸函数的定义。
次梯度接替切平面的角色,无约束的证书变成零属于次梯度集合。
通往推广的路径
目标函数有尖点时,什么取代梯度?
次梯度接替切平面的角色,无约束的证书变成零属于次梯度集合。
对 上的凸函数 ,若对所有 有 ,则称 为 在 处的次梯度;这就是去掉梯度唯一性的切平面不等式。上面充分性的论证于是变成: 是全局最小点,当且仅当 是 处的次梯度。 在零点的次梯度构成 ,其中包含零。有约束时, 的法锥会进入条件,而把它与次梯度结合需要某种规范条件。
另设 是凸函数,而 在包含 值域的区间上凸且单调不减,则 是凸函数:先用单调性将 作用于 的线段上界,再用 的凸性。单调性不可省略。外函数 虽是凸的,却不在整个实数轴上单调不减;若 ,复合函数 在零处的值大于它在 和 处的平均值,所以不是凸的。
这些封闭性质有助于建模。仿射残差的平方和是凸的,因为每个仿射函数的平方都是凸的,而非负组合保持凸性。例如 的 Hessian 为 ,其二次型为 。若 列满秩,每个非零 的二次型严格为正,故函数严格凸且最小二乘解唯一。若 有非零零空间向量,沿该方向移动不改变目标值;一旦最小点存在,便不唯一。曲率的几何性质因此联系到矩阵的秩。
常见错误
常见错误
(只在几点或图像上检查凸性)
凸性涉及定义域内每一对点;检查几个例子,或在小范围内画出图像,都不能证明无界定义域上的凸性。相反,一个反例就足以否定凸性,练习中 在 上的例子正是如此。
常见错误
(强求边界最小点的梯度为零)
驻点要在相应的凸性假设下才可证明为全局最优,边界最小点也不必满足无约束的零梯度条件。在投影例题中,最小点 有 ;正确的检验是对可行位移的方向不等式。
常见错误
(把曲率或唯一性当作存在)
半正定曲率支持凸性,却未必给出严格凸性或唯一性,平坦方向的例题已说明这一点。没有存在性证明的唯一性论证,只说明解至多有一个: 严格凸,却没有最小点。
总结
用可行线段理解集合的几何,用支撑平面将可微性转化为全局下界,再用方向不等式证明受约束最小点。存在和唯一需要分开证明。当可行集由具体的等式及不等式描述时,这些工具将引向乘子证书。
练习
快速检查
(证明 有唯一全局最小点,并求出它。)
配方。
解答 · 答案
配方得 ,唯一最小点为 ,值为 。
快速检查
( 在 上是凸函数吗?直接给出违反定义不等式的反例。)
试取区间左半部分的两点。
解答 · 答案
不是。取 、、,左边为 ,大于右边 ,违反凸性不等式。
快速检查
(在 上最小化 ;为何答案处的导数不必为零?)
找出最小点处的可行方向。
解答 · 答案
最小点为 ,因为整个区间上 。虽然 ,左端点处的可行位移非负,故对每个可行 有 ,方向条件成立。