凸优化必备：保凸运算与复合函数凹凸性判断全攻略

在凸优化这个圈子里这个函数是不是凸的几乎是最常见的问题之一。但我发现一个很有意思的现象很多人拿到一个新目标函数第一反应就是掏出纸笔算 Hessian算半天算不出来最后要么放弃要么换个函数硬凑。如果你真正理解保凸运算convexity-preserving operations和复合函数的凹凸性判断规则这类问题的思考方式就完全不一样了——你不会再去傻算二阶导而是先把函数拆成外层函数 内层函数然后查表匹配像搭积木一样把结论推出来。这篇文章把我这些年做优化建模时实际用下来觉得最有价值的内容整理出来三种最常用的保凸运算、一张复合函数凹凸性判定表、大量常见函数族实例以及我踩过的一些反例和定义域陷阱。适合正在学凸优化理论、或者在做机器学习/运筹学建模时需要频繁判断目标函数形状的读者。读完之后你再看那些看起来很吓人的函数脑子里会自动浮现出它的结构拆解图。1. 为什么要专门研究保凸运算而不是直接求导1.1 凸性的价值在于局部最优即全局最优先花两分钟把基础对齐。一个函数 (f:\mathbb{R}^n\to\mathbb{R}) 是凸函数需要满足两个条件定义域是凸集并且对任意 (x,y\in\text{dom}f)、任意 (\theta\in[0,1])都有[ f(\theta x(1-\theta)y)\le \theta f(x)(1-\theta)f(y) ]这个不等式说的是函数图像上任意两点连一条弦弦一定在函数图像上方。生活化的理解是——这是一个单坑函数你往坑里走不管从哪个方向走只要每一步都在下降最后都会到同一个最低点。这保证了绝大多数迭代优化算法梯度下降、牛顿法、内点法等不会陷入局部最优的泥潭。所以凸性不是一个可有可无的数学装饰它直接决定了你选的求解器靠不靠谱、收敛性证明能不能写、实际运行会不会发散。建模时把目标函数和约束条件都确认成凸的等于给整个求解过程上了一道保险。1.2 求导判据的三个致命短板说到判断凸性很多人第一反应是求 Hessian 矩阵并检查半正定性。这个方法在课本上很完美但实际工程中经常失效第一计算量太离谱。目标函数嵌套五六层Hessian 的每个元素都是一大串链式法则求导手算容易错用符号计算工具推导出来的表达式也长得没法看。第二大量常见函数根本不可导。绝对值 (|x|)、逐点最大 (\max{f_1(x),f_2(x)})、范数 (|x|_1)、ReLU 激活函数这些在定义域的某些地方导数不存在二阶判据直接失效。第三很多函数不是单个解析式而是一组函数的上确界或者是对某个变量做最小值运算。这种结构你甚至没法写出 Hessian因为函数本身就不是由初等运算直接组合出来的。因此实际工作中判断凸性要靠结构派打法不关心具体表达式长什么样只关心这个函数是由哪些已知凸函数、通过什么运算拼起来的。这就是保凸运算存在的意义。1.3 两种工具的分工保凸运算和复合规则解决的是两类问题保凸运算告诉你如果已知几个函数是凸的经过某种运算后得到的新函数是否保持凸性。典型例子有非负加权和、仿射复合、逐点最大、逐点上确界、部分最小化等。复合函数凹凸性判断解决的是给定外层函数 (h) 和内层函数 (g)什么条件下 (h(g(x))) 是凸的、凹的或者无法保证。这两套工具叠加起来可以把一个复杂表达式层层拆开每一层单独判断最后拼装出全局结论。下面逐个来。2. 三种最常用的保凸运算加权和、仿射复合、逐点最大2.1 非负加权和简单但约束严格设 (f_1,\dots,f_m) 都是凸函数(\alpha_1,\dots,\alpha_m\ge 0)则[ f(x)\alpha_1 f_1(x)\dots\alpha_m f_m(x) ]仍然是凸函数。证明几乎可以直接从凸性定义出发每一项都满足中点不等式非负系数不会把不等号方向翻转加起来还是满足。关键要求是系数非负。如果某一个 (\alpha_i0)这一项的凹凸方向就反了。举个最直白的例子(f_1(x)x^2) 是凸的但 (-x^2) 是凹的二者相加 (x^2-2x^2-x^2) 当然不是凸函数。这个运算在机器学习里无处不在。带正则化的经验风险最小化目标函数通常是[ \sum_{i1}^N \ell_i(w) \lambda \sum_{j1}^d |w_j| ]只要损失函数 (\ell_i) 是凸的L1 正则项是凸的并且 (\lambda\ge 0)整个目标就是凸的。每一次你往成本函数里加一个正系数的凸惩罚项凸性都不会被破坏这就是加权和运算在背后兜底。2.2 与仿射函数的复合最容易被低估的免费午餐如果 (f) 是凸函数(A) 是 (m\times n) 矩阵(b\in\mathbb{R}^n)那么[ g(x)f(Axb) ]也是凸函数。这里对 (A) 和 (b) 没有任何额外限制不需要 (A) 半正定不需要 (b) 满足什么条件。这背后的道理是仿射函数 (Axb) 本质上只是对自变量做了一次线性搬动缩放、旋转、平移它既不改变函数图像的凹陷方向也不改变凸性界定的本质。你可以把凸函数想象成一张凹面朝上的碗把碗在空间里任意拉伸和平移它依然是碗不会变成山峰。这个运算是所有保凸运算里最常用的。比如 (|x|_2) 是凸的那么 (|Ax-b|_2) 是凸的(\log) 函数在正数域是凹的那么 (\log(a^T xb))在 (a^T xb0) 的定义域内也是凹的。注意一个容易混淆的点仿射复合不需要外层函数满足什么单调性条件。这一点和后面要讲的复合函数规则完全不同。为什么因为仿射函数是既凸又凹的它同时满足两种匹配方向所以外层是凸是凹都能直接套用结论。2.3 逐点最大把多个凸函数叠加成更复杂的凸函数设 (f_1,\dots,f_m) 都是凸函数定义[ f(x)\max{f_1(x),\dots,f_m(x)} ]那么 (f) 也是凸函数。这句话的直观图像是把 (m) 张凸碗叠在一起然后取每一处的最高点得到的曲面虽然可能有棱角但整体凹陷方向保持一致。证明也不难。对任意 (x,y) 和 (\theta\in[0,1])[ \max_i f_i(\theta x(1-\theta)y)f_k(\theta x(1-\theta)y) ]其中 (k) 是在这个点上取得最大值的下标。由于 (f_k) 是凸的[ f_k(\theta x(1-\theta)y)\le \theta f_k(x)(1-\theta)f_k(y) ]而 (f_k(x)\le \max_i f_i(x))(f_k(y)\le \max_i f_i(y))所以[ f_k(\theta x(1-\theta)y)\le \theta \max_i f_i(x)(1-\theta)\max_i f_i(y) ]这就证明了结论。逐点最大能构造出一类重要的凸函数——分段线性凸函数。例如 (f(x)\max{a_1^T xb_1,\dots,a_m^T xb_m}) 是一族线性函数取最大它在不同区域内由不同的线性函数主导形成一个多面体形状的凸函数。这在鲁棒优化、约束规划、支持向量机对偶推导中都频繁出现。还有一个小例子(|x|_\infty\max_i |x_i|\max_i{x_i,-x_i})。绝对值函数本身是 (\max{t,-t})而 (-x_i) 也是线性的所以无穷范数天然就是有限个线性函数取最大当然是凸的。2.4 保凸运算的叠加使用这些运算可以叠加就像搭乐高。比如[ f(x)\max{\alpha_1 f_1(x),\alpha_2 f_2(x)}\beta^T x ]如果 (f_1,f_2) 凸、(\alpha_1,\alpha_2\ge 0)那么第一项由非负加权和 逐点最大保持凸性再加一个线性函数线性函数自身既是凸也是凹整体仍然凸。一个经典的综合示例是[ |x|1\max{s\in{-1,1}^n} s^T x ]把每个符号组合 (s) 看成一个线性函数(|x|_1) 就是 (2^n) 个线性函数的逐点最大。这也是为什么 L1 范数一定是凸的——你根本不需要对每个分量求导从结构上就看出来了。3. 上确界、部分最小化与透视运算三个进阶保凸工具3.1 逐点上确界把最大值推广到无穷集合逐点最大值只能处理有限个函数。但现实中经常会遇到对无限多个函数取上确界的情况。设 (\mathcal{A}) 是任意非空集合不要求有穷甚至不要求是凸集如果对每个固定的 (y\in\mathcal{A})(f(x,y)) 关于 (x) 都是凸函数那么[ F(x)\sup_{y\in\mathcal{A}} f(x,y) ]关于 (x) 是凸的。这里最反直觉的地方在于(\mathcal{A}) 不需要是凸集。我们希望哪怕是从一堆毫无规律的函数里挑最大的那个凸性也不会被破坏。这个性质有一个非常重要的应用支撑函数。对任意集合 (C)[ \sigma_C(x)\sup_{y\in C} y^T x ]它是关于 (x) 的凸函数因为每个 (y^T x) 都是线性函数凸的。哪怕 (C) 本身是个离散点集甚至非凸集合支撑函数照样凸。另一个例子是[ |x|2\sup{|y|_2\le 1} y^T x ]这是从对偶范数的定义来的它说明欧几里得范数其实是一族线性函数的上确界。3.2 部分变量最小化压扁之后依然保持凸性如果说上确界是从多个函数里挑最大的那还有一个对偶方向的操作对一部分变量求最小值。设 (f(x,y)) 关于 ((x,y)) 联合凸(C) 是非空凸集那么[ g(x)\inf_{y\in C} f(x,y) ]关于 (x) 是凸的前提是 (\inf) 不是负无穷。这个命题的直觉是把一个凸曲面沿着 (y) 方向压扁到 (x) 轴上得到的截面函数仍然是凸的。想象一个碗沿某个方向压扁影子轮廓还是一个凹陷的碗形不会变成驼峰。这个性质的实际价值在于有时候问题里有些变量不是你想优化的你可以把它们最小化掉剩下的函数自动保持凸性。比如点到凸集的距离[ \text{dist}(x,C)\inf_{z\in C}|x-z|_2 ]因为 ((x,z)\mapsto |x-z|_2) 是联合凸的这是仿射复合 (|x-z|) 的性质对 (z\in C) 取下确界后距离函数关于 (x) 依然是凸的。3.3 透视运算处理比率结构的利器透视运算的定义是如果 (f) 是凸函数那么[ g(x,t)t f(x/t),\quad t0 ]关于 ((x,t)) 是凸的。这个运算在理论上很重要但实际建模中更容易遇到的是它的衍生形式。比如把透视运算和复合规则结合起来可以得到凸函数对某个正分母做除法的凸性结论。举一个常见例子(f(x)x^2)那么 (g(x,t)x^2/t)在 (t0) 时关于 ((x,t)) 是凸的。这个函数在通信系统的功率分配、几何规划等问题里经常出现是一个非常有用的凸化技巧。如果你手头有不规整的分式结构先想想能不能套透视运算往往比直接算二阶导快得多。4. 复合函数的凹凸性判定一张表解决八成问题4.1 标量复合规则现在进入本文的重头戏判断复合函数 (f(x)h(g(x))) 的凹凸性。其中 (h:\mathbb{R}\to\mathbb{R}) 是外层函数(g:\mathbb{R}^n\to\mathbb{R}) 是内层函数。下面的表是所有判断的基础外层 (h) 的凹凸性外层 (h) 的单调性内层 (g) 的条件复合 (h(g(x))) 的结论凸不减(g) 凸凸凸不增(g) 凹凸凹不减(g) 凹凹凹不增(g) 凸凹有一个特殊豁免条款如果内层 (g) 是仿射函数 (Axb)那么外层不需要满足任何单调性条件复合结果直接继承外层的凹凸性。这就是前面仿射复合那一节的内容它在复合表里是一个独立的特例。举个最典型的例子(f(x)-\log(x))。外层 (h(t)-\log(t)) 在 (t0) 上是凸函数并且单调不增导数 (-1/t0)。根据表格第二行只要内层 (g(x)) 是凹函数并且满足 (g(x)0)那么 (-\log(g(x))) 就是凸函数。这就是对数障碍函数 (-\log(b_i-a_i^T x)) 凸性的来源。再举个例子(f(x)\exp(x^2))。外层 (\exp(t)) 在 (\mathbb{R}) 上是凸函数且不减内层 (x^2) 是凸的根据表格第一行复合结果凸。如果你把这个函数画出来它确实是一个很陡的凸坑。4.2 为什么单调性是关键开关这张表不是死记硬背的它的内在逻辑可以用一元微积分看得清清楚楚。对 (f(x)h(g(x))) 求二阶导[ f(x)h(g(x))[g(x)]^2h(g(x))g(x) ]要让 (f(x)\ge 0)需要两个加项都不是负的。(h\ge 0) 对应外层 (h) 是凸函数。([g(x)]^2) 永远非负所以第一项的安全条件就是 (h\ge 0)。第二项要看符号配合如果外层 (h) 不减那么 (h\ge 0)此时要求 (g\ge 0)也就是内层 (g) 是凸函数。如果外层 (h) 不增那么 (h\le 0)此时需要 (g\le 0)也就是内层 (g) 是凹函数。你看表格四行的本质就是在安排 (h) 和 (g) 的符号相乘不会变负。凹函数的情况完全对称把整个不等式方向反过来即可。理解到这个层面即使碰到不熟悉的函数也能推出来而不是翻书。4.3 向量复合外层是多元函数怎么办上面讨论的是外层 (h) 只接受一个自变量。但现实中更常见的情况是外层有多个输入。比如 (\log\text{-sum-exp}) 函数[ h(u_1,\dots,u_k)\log\left(\sum_{i1}^k e^{u_i}\right) ]这个函数本身是 (\mathbb{R}^k\to\mathbb{R}) 的凸函数并且对每个自变量 (u_i) 都是单调不减的偏导数 (e^{u_i}/\sum_j e^{u_j}\in(0,1))恒为正。多元复合规则是这样的如果 (h) 是凸函数并且对每一个自变量都单调不减内层函数 (g_1,\dots,g_k) 全部是凸函数那么[ h(g_1(x),\dots,g_k(x)) ]是凸函数。同理如果 (h) 对每个自变量都单调不增则内层需要全是凹函数。凹函数的版本完全对偶。这个向量复合规则是很多人容易漏掉的一块拼图。有了它你才能理解为什么像[ \log\left(e^{x_1}e^{x_2}\dotse^{x_n}\right) ]这样的函数是凸的外层 (\log)-sum-exp 本身凸且逐坐标不减内层 (x_i) 是线性函数既凸也凹套上去结果必然凸。反过来如果内层是任意凸函数 (g_i(x))把每个 (g_i) 送进指数再取对数整体依然凸。这在构造代理损失函数、近似最大函数时非常有用。5. 常见复合函数家族实例指数、对数、幂函数、分式5.1 指数族复合外层 (\exp)(\exp(t)) 在整条实数轴上是凸函数且单调不减。因此根据复合表第一行任何凸函数 (g) 代入指数[ e^{g(x)} ]都是凸函数。这个结论很宽松不需要 (g) 有界或者非负。比如 (e^{x^2})、(e^{\max{x,0}})、(e^{|x|_1}) 全是凸的。相反如果你看到的是负指数 (e^{-g(x)})外层可以拆成 (h(t)e^{-t})它在 (\mathbb{R}) 上是凸函数但单调不增。于是需要内层 (g) 是凹函数复合结果才凸。这和第一行恰好形成镜像。5.2 对数族复合外层 (\log) 与 (-\log)对数函数在正数域是凹函数且单调不减。所以(\log(g(x)))内层 (g) 是凸函数且 (g(x)0) 时复合结果是凹函数。(-\log(g(x)))外层 (-\log) 是凸函数且单调不增内层 (g) 是凹函数且正值时复合结果是凸函数。这两个结论正好一凹一凸方向别搞混。很多做优化的人对 (-\log) 很熟悉因为它是内点法的核心组件。但对 (\log) 本身常见误区是觉得 (\log) 是凹的所以 (\log(\text{凸})) 应该是……这时候一定要查单调性(\log) 不减内层凸结论是凹不是凸。5.3 幂函数族一张小表搞定定义域限制在 (t0) 的幂函数 (t^p)其凹凸性和单调性可以归纳如下幂指数 (p)(t^p) 的凹凸性 ((t0))单调性与内层函数匹配的结论(p\ge 1)凸不减内层 (g) 凸 (\Rightarrow) (g^p) 凸(0\le p\le 1)凹不减内层 (g) 凹 (\Rightarrow) (g^p) 凹(p0)凸不增内层 (g) 凹 (\Rightarrow) (g^p) 凸特别地(p2) 是凸不减在正数域所以如果内层函数 (g(x)\ge 0) 且凸那么 (g(x)^2) 凸。(p1/2) 对应开根号是凹不减内层凹函数开根号依然凹。(p-1) 对应倒数 (1/t)凸且不增内层凹且正值取倒数之后变成凸。分式线性复合是倒数族最经典的应用。考虑[ f(x)\frac{1}{a^T xb} ]在定义域 ({x: a^T xb0}) 上外层 (1/t) 在正数域凸且不增内层 (a^T xb) 是仿射函数。根据仿射复合的特例规则内层不需要纠结凹凸性复合结果直接继承外层凸性。这类函数在分数规划、线性分式变换里频繁出现很多教材直接告诉你结论正分母的线性分式是凸的背后的来源就是复合规则。5.4 实战示例交叉熵损失也能拆机器学习里的逻辑回归损失通常是[ \ell(w)\log(1e^{-y w^T x}) ]这东西是不是凸的直接算 Hessian 可以但用复合规则更快。把它看成 (h(g(w)))内层 (g(w)-y w^T x) 是仿射函数外层[ h(t)\log(1e^t) ]这个函数俗称 softplus它是凸函数因为它的二阶导数 (e^t/(1e^t)^20)。仿射复合直接继承凸性所以整个损失函数是凸的。整个判断过程不超过十秒根本不需要展开二阶导矩阵。6. 判断流程、反例与踩坑记录6.1 一套可复用的五步判断流程看了这么多规则实际拿到一个函数时怎么操作我自己总结了一套固定流程每次按这个走基本不会乱把函数写成 (f(x)h(g(x))) 的形式确定最外层函数 (h) 是谁。如果嵌套多层先处理最外层逐层向内。判断外层 (h) 的凹凸性以及它在定义域内的单调性。注意不是在 (h) 的自然定义域上看而是在内层函数值域的范围内看。确定内层 (g) 的值域是否落在外层 (h) 的定义域内。这一步最容易出错后面会专门讲。判断内层 (g) 的凹凸性和单调性如果还要继续向里拆就把 (g) 当作下一轮的外层。查表匹配外层凹凸性、外层单调性和内层凹凸性三个条件。如果匹配成功结论直接到手如果匹配不上要么换一种拆法要么只能回到定义或者 Hessian。6.2 典型反例为什么外层凸加内层凸不一定凸很多人会形成一种错误直觉外层凸、内层凸复合就应该凸。举一个反例彻底打破这个幻觉[ h(t)t^2,\quad g(x)x^2-1,\quad f(x)h(g(x))(x^2-1)^2 ](h) 是凸函数(g) 也是凸函数二次函数开口向上但 (f(x)(x^2-1)^2) 在 ([-1,1]) 上是先下坡后上坡的W形不是凸函数。验证一下凸性定义取 (x-1,y1,\theta0.5)左边 (f(0)1)右边 (\theta f(-1)(1-\theta)f(1)0)不等式 (1\le 0) 显然不成立。问题出在哪外层 (t^2) 在整条实数轴上不是全局单调的在 (t\ge 0) 上单调不减在 (t\le 0) 上单调不增。内层 (g(x)x^2-1) 的值域包含了正负两段跨过了 (t0) 这个单调性切换点导致外层在不同区域用不同的单调方向凸性就保不住了。这个反例说明复合表中单调性条件不是可有可无的修饰而是保凸性的硬性门槛。6.3 定义域和值域三个隐蔽的坑第一个坑内层值域必须落在外层定义域里。这在初学阶段是定义域三个字但实际判断时经常被忽略。比如要判断 (-\log(g(x))) 的凸性前提是 (g(x)0) 对定义域内所有 (x) 成立。如果 (g(x)) 有可能取到非正值函数本身在那些点就没定义讨论凹凸性毫无意义。第二个坑外层函数必须在包含内层值域的区间上满足对应的单调性。还是拿 (t^2) 举例如果内层值域恰好是 ([0,\infty))那么 (t^2) 在值域区间上单调不减复合可以保凸。一个真实的例子是 (|Axb|_2^2)把它看成 (h(t)t^2) 和 (g(x)|Axb|_2)虽然 (t^2) 在整个实数轴上不单调但 (g) 的值域是 ([0,\infty))而 (t^2) 在非负区间单调不减所以 (( |Axb|_2)^2) 依然是凸的。这就是为什么很多教材会写凸函数的非负部分平方是凸的本质上只是在说值域限定了单调区间。第三个坑复合规则给出的是充分条件不是必要条件。规则不满足不代表函数一定不是凸的。我举一个真实的例子考虑 (-\log(x^2))定义域 (x\ne 0)。拆成外层 (h(t)-\log(t))内层 (g(x)x^2)。外层凸且不增内层是凸函数查表发现匹配不上第二行它要求内层凹。但 (-\log(x^2)-2\log|x|)它的二阶导数是 (2/x^20)实际上是凸函数。这个例子告诉你判断表只是安全通过的充分条件清单卡住的时候不要急着下结论说不是凸函数可以考虑换一种函数拆分方式或者直接回到定义验证。6.4 表达方式不唯一换一种拆分往往就通了遇到复合表匹配不上的情况先别放弃。同一个函数有多种拆分可能只是你选的拆分不好。比如[ f(x)\log(1e^{x^2}) ]如果拆成外层 (\log(t))凹、不减和内层 (1e^{x^2})凸、正值查表对应第三行凹不减 凹才出凹但内层是凸匹配不上。换一种拆法令 (g(x)x^2)外层 (h(t)\log(1e^t))此时外层是 softplus 函数凸、不减内层是凸函数匹配第一行结果是凸函数。同一个函数换一个角度看结论完全清晰了。所以实操时我建议多准备几种拆分方式把常数项并到外层还是内层、把平方放进外层还是内层、把某个复合函数看成一个整体还是拆成多层这些都会影响判断路线的长短。7. 我在实际建模中总结的几条判断经验最后分享几个这些年反复用到的土办法不算理论创新但确实帮我省了不少时间。第一遇到 (\max)、上确界、范数优先想逐点最大/上确界运算别想着求导。范数和分段线性函数基本上都是一族线性函数取上确界的结构这类函数凸性天然保证而且对不可导点完全无压力。第二遇到分母里有正函数优先想 (1/t) 复合或者透视运算。正分母的线性分式、正凹函数取倒数这是凸性判断的高频考点也是实际建模里分数规划问题的常用变形方向。第三遇到 (\log) 和 (\exp) 纠缠在一起优先想向量复合规则。(\log)-sum-exp、softmax、交叉熵这些结构靠标量复合表很难拆干净但放进外层凸且逐坐标不减的框架里一次就能看清。第四判断之前永远先确认定义域。很多看似复杂的函数卡住你的不是凹凸性而是定义域条件没满足。比如 (x\log x) 在 (x0) 上凸但定义域一旦扩展到 (x0)你需要单独处理边界。搞清楚定义域再谈单调性和凹凸性顺序不能乱。第五也是最重要的一条经验训练自己用结构而不是公式去看函数。看到一个表达式先不要急着展开而是问自己——它是由哪些已知凸/凹函数、通过哪些运算拼起来的这一步想清楚凹凸性判断就是套规则的事。如果拼不起来那才需要回到定义或 Hessian 做最后裁决。这套打法我用了很多年在机器学习、运筹学、信号处理的各种建模场景里几乎没有失效过。