专栏名称: 运筹OR帷幄

旨在为读者带来运筹学/优化理论最专业和前沿的资讯与报道，及其在供应链管理、人工智能等学科的交叉应用。专栏主编多为世界名校OR博士，50多位审稿人由全球高校教授、研究院科学家、企业CTO等组成。欢迎有稿费投稿，敬请加入全球最大华人运筹学社区。

凸优化（2）——凸函数，强凸函数及相关拓展

运筹OR帷幄 · 公众号 · · 2021-02-28 21:15

正文

↑↑↑↑↑点击上方蓝色字关注我们！

『运筹OR帷幄』转载

作者：学弱猹厦门大学信息与计算科学系本科生现快手广告算法工程师

编者按

从这一篇文章我们介绍凸函数的定义和基本性质，凸函数虽然定义简明扼要，但因为凸的性质在优化中实在是极为重要，所以我们有必要把它的一些延伸性质和一些常见的凸函数例子用单独的一节进行解释。

大家好！

在这一节，我们依然会介绍与凸相关的一些定义与性质，并且会介绍一些例子来说明如何证明和利用“凸”这个工具，包含凸与强凸的各种定义，性质和结论。

虽然这一节依然还不会进入到具体的算法，但我们还需要再强调的一点是：凸优化本身其实就有非常多的偏分析的内容。我们不会去涉及与算法毫无关联的部分，而更多的希望以算法为主轴来考虑不同的凸优化问题。虽然这不可避免的还是会涉及到一些很理论的内容，但这样至少每一个理论和思想可以对应的上实操的算法，相信对于学习和理解这些具体的思维会更有帮助，也不会出现“空谈理论”而丧失学习兴趣的情况。

那么我们开始吧。

Source

CMU 10-725, Convex Optimization
USTC, 最优化原理
Boyd, Vandenberghe, Convex Optimization
J.P. Hiriart-Urruty and C. Lemarechal (1993), Fundamentals of Convex Analysis
Amir Beck (2017), FIrst-order Methods in Optimization

凸函数的各类定义与举例

我们在上一节扯了一大堆皮，真正算介绍清楚的也只是凸集的一些概念。那么这一节我们希望介绍一些与凸函数（convex functions）有关的性质。作为凸优化的核心性质，我们多花一些篇幅来写它，也是理所应当。

首先我们给出最简单的凸函数的定义。

Definition 1: (Strictly) Convex Functions
若满足是凸集，且，那么称它是一个凸函数。如果等号处处不成立，则称它是一个严格凸函数。
Definition 2: (Strictly) Concave Functions
若是一个凸函数，那么定义是一个凹函数。如果等号处处不成立，则称它是一个严格凹函数。

这里要注意凸和凹并不是二元对立的关系。比方说对于线性函数，你会发现它既是凸函数，又是凹函数。

关于凹凸其实不同的人的看法会很不一样。这里我们要统一一下说法：所有的凸函数都是下面图中展示的那样，有的书上会翻译凸为下凸，翻译凹为上凸。这张图也很清楚的解释了凸函数的几何意义。可以看出，蓝点一定在绿点的上方（为了几何上的直观和容易理解，我们这里都是默认为二维平面上的函数。如果是高维上图肯定不一样，但是性质是相同的。之后的图也遵循这个原则）。

这里有一个容易被忽略的地方就是：无论是凸函数，还是凹函数，一定要求定义域为凸集。而且没有凹集的说法，比方说，这个函数就不是一个凸函数，但是如果只看左半边和右半边，它都是凸函数（感兴趣的可以自己画图看看）。这种奇怪的现象出现的原因就是它的定义域为，这个定义域并不是一个凸集。

当然了，凸函数不仅仅只有这一种定义，剩下的定义会用到它的一些一阶和二阶信息（也就是梯度和海塞矩阵的信息），所以会有不同的名字。

Definition 3: First-order Characterization of Convex Functions
如果一阶可导，那么如果是凸的，并且，有，那么称它是一个凸函数。

相信你自己能明白凹函数的一阶信息的刻画定义是什么。

我们画一个图来解释一下一阶条件究竟在告诉我们什么。

可以看到一阶条件对应的直线肯定在凸函数的下方（绿点在蓝点的下方）。

一阶条件的一个最重要的推论就是，如果我们设，那么无论是什么，都会有。潜在的意思是说，对于凸函数做优化，驻点为0就说明找到了极小值，因此正如机器学习界经常说的一句话：当一个问题被证明是一个凸优化问题，那么基本上就可以算解决了。

一个自然的问题就是：为什么一阶条件是对的？这就是我们下面要说明的内容了。

Proposition 1:
证明Definition 1与Definition 3的等价性。

我们证明一下这个结论。首先假设Definition 1是正确的，也就是说我们有

那么注意到，，所以可以把这个式子化简一下，得到

设，会发现右边其实就是方向导数的定义，也就是说

取一个负号就好了。方向导数的求导内容可以参考《数值优化》的第一节，链接如下

数值优化（1）——引入，线搜索：步长选取条件

反过来，假如说Definition 3是正确的，那么我们考虑，取（这里要注意两个定义里面都要求了定义域是凸集）。就会有

第一个式子乘上，第二个式子乘上，加在一起即可。所以这就说明了结论。

关于凸函数，其实还有一个二阶信息的定义。

Definition 4: Second-order Characterization of Convex Functions
如果是二阶可微的，那么如果的定义域是凸集，并且，那么就是一个凸函数。

相信你自己能明白凹函数的二阶信息的刻画定义是什么。

我们依然通过图形来解释这个二阶条件的含义。

注意到二阶导数是对于一阶导数变化率的衡量。所以如果在某一个点，它的二阶导数为负，就意味着它之后的点的导数会减小，反过来就是增大。比方说蓝色的点（）那一处，可以看出切线的斜率为正，但跨过那个山峰之后，斜率就变成负的了。所以可以看出，海塞矩阵为正定的，在一维的情况下就是二阶导数为正，就会形成一个凸函数的形状。

事实上我们也可以来证明二阶信息刻画的定义与其它两个定义的等价性。

Proposition 2:
证明Definition 4与其它两个定义的等价性。

我们证明一下这个结论。还是考虑用一阶条件的不等式，我们有

但如果说，我们有，也就是说它存在一个下降的方向，也就是说。那我们设，可以得到

不难看出，不等式右边其实就是式子的Taylor展开到一阶的结果。换句话说如果我们希望利用到二阶信息，自然需要多做一些这样的工作。根据二阶Taylor展开，我们可以得到

所以对比一下一阶条件的不等式，无非就是需要说明一下并不是在所有情况下都成立。这个是显然的，因为我们有，所以只需要把取得特别小，这样的话根据二阶导的连续性，不难得到仍然是成立的，这就产生矛盾了。

关于二阶信息的这个定义也有个要注意的地方就是：如果一个函数是严格凸的函数，并不能够推出，一个反例就是，它肯定是严格凸的，但是在原点处，其二阶导数并不是一个正数。

关于凸函数的定义虽然多，但它们的适用范围还是有一些差别的。最要注意的就是它们对于函数可微性要求的不同。比方说如果函数没有办法在每一个定义域内的点都做到二阶可微，那么就不能够使用二阶信息对应的那个条件。

虽然我知道你可能开始感觉有些烦了，但是我们还是希望给出最后一个凸函数的性质，有的时候它会有一些计算上的方便。

Proposition 3:
给定点，如果是一个关于的凸函数，那么是凸函数。反之亦然。

我们就不证明这个了，因为走凸函数的原始定义即可。这个定义有的时候我们会称为叫一维刻画，因为它可以把一个任意维度的函数，通过一个给定的方向，来降维到一个一维函数，进而通过考虑的性质来解决问题。

写了这么多凸函数的定义和性质，我们来给一些具体的例子吧。

Example 1: (Source: USTC)
证明是一个凹函数。

这里的就是对称正定阵的意思，给这个限制是为了让行列式都为正数。

对于这个题，最直接的方法就是走原始的定义，但不好做。最硬核的方法就是直接矩阵求导得到

根据它的负定性得到结论。矩阵求导的方法可以看我录制的视频

https://www.bilibili.com/video/BV1ZK4y1b7Xt/

的对应内容。但这一题我们这两个方法都不使用，我们考虑使用Proposition 3的这个性质来求解。

设，那么只要说明是一个凹函数即可。那么这个时候，注意到

其中代表它的平方根阵。如果说为它的特征值分解，那么，其中就是一个对角矩阵，元素为特征值的根号。多说一句，如果矩阵不正定，平方根阵不一定存在。

因为我们需要说明这个函数关于是凹的，所以这一部分可以不管。那么关键就落在了中，注意到这个矩阵一定是正定阵（想想为什么？），所以可以设为特征值分解，就可以得到

所以换句话说，对于这个矩阵，它的特征值就是，所以根据行列式与特征值的关系，我们会有

为了方便后续的说明，这里补充一个凸函数的性质。

Lemma 1:
若函数都是凸的，那么它们的非负凸组合得到的函数也是凸的。对于凹函数也有类似的结论。

这个性质的证明很简单，我们略过它。这里的非负凸组合和第一节的凸锥组合的概念非常类似。

有了这个性质，其实只需要说明对于一个通用的函数关于是凹函数即可。这个就很简单了，因为，所以就很容易得到结论了。

我们这里单独列出Lemma 1，是因为它是凸函数的一个非常常用的小结论。我们后面的一些例子中还会努力去抽象出这样的一些小结论，这样的话对于很多有趣的问题，就不难通过这些结论来看到更本质的东西。

Example 2: (Source: USTC)
运筹学中经常会出现的极小极大问题，本质上是一个凸优化问题。

这句话乍一眼看有点不可思议，但是拆解来看并不困难。首先引入一个凸函数的小结论。

Lemma 2:
设是一个凸函数，那么函数是一个凸函数。

还是一样我们略去证明。这里取成的原因是上界不一定可以取得到。当然了通过这个性质就会发现，极小极大问题本质上就是最小化一个凸函数，所以它是一个凸优化问题。换句话说它是一个好解决的问题。所以很多人会说，一个问题流行，并不一定是因为它有用，而是因为它好做。

好的，简单的问题我们就写到这里，接下来我们来看一些更复杂的情况。

复合函数的凸性与应用

凸函数的一个更加重要的利器就是函数的复合。如果可以很好地利用上它，对于一些问题的研究就会省去不少的功夫。

所谓的复合函数，其实就是考虑形式

我们假如说它们的性质足够的好，具有二阶可导的性质。那么可以得到

所以我们可以看出这么一个有意思的结论。

Theorem 1: Rules for Composite Convex Functions
设二阶可导，且，那么
如果为凸函数，并且不降，为凸函数，那么为凸函数。
如果为凸函数，不增，为凹函数，那么为凸函数。
如果为凹函数，不降，为凹函数，那么为凹函数。
如果为凹函数，不增，为凸函数，那么为凹函数。

也就是说这个定理提供了四条判断复合函数凸性的准则，验证它们只需要代入上面的观察它是否为非负数就可以了。也就是说只要函数的性质足够的好，分析复合函数的凸性并不是一件困难的事情。

有的人可能会质疑说：你这只是一维的情况啊。不过比较幸运的是，把它推广到一般的情况，也是成立的。这里就不细说证明了，感兴趣的同学们可以查查相关资料。

好的，我们来举一个例子看看。

Example 3: log-sum-exp function (Source: CMU, USTC)
证明是一个凸函数。

这个函数还是比较有名的，因为它是的一个好的近似，所以有的时候会把它叫做soft-max。神经网络里面的softmax层其实就从这儿来。

可以看出这个函数是一个复杂的复合。但也有比较好拆分出来的一些复合结构。比方说指数上的就可以拉出来作为一个新的函数。所以实际上我们的内层函数是一个仿射函数，当然是一个凸函数，外层函数就是

（这里的就是的各个分量）这个函数当然是一个不降的函数。所以根据上面提供的几条准则，就可以知道，我们通过这个，就可以看出的凸性。

对它求海塞矩阵，其实就直接按照正常的求偏导的思路就好。也就是说

然后就可以把它写成一个更加紧凑的形式

其中。

如果要说明它是一个凸函数，那么如何说明它是一个正定矩阵呢？如果通过fancy的方法解决不了，那不如考虑考虑走定义。也就是考虑计算。

注意到

看似没什么规律，但是用上条件，根据柯西不等式就可以得到正定矩阵的结论，这里留给读者思考。

这个性质看似好，但也有很多局限性。假如说这几个函数的定义域不是全空间怎么办？假如说它们二阶可微的这个条件不满足怎么办？因此我们需要对它做一些修正，这就是下面的这个修改版的复合函数凸性的性质。

Theorem 2: Modified Rules for Composite Convex Functions
设，那么
如果为凸函数，并且不降，为凸函数，那么为凸函数。
如果为凸函数，不增，为凹函数，那么为凸函数。
如果为凹函数，不降，为凹函数，那么为凹函数。
如果为凹函数，不增，为凸函数，那么为凹函数。

哎，为什么凭空多出来一个？这个东西可以理解为是的一个拓展。换句话说就是在其它没有定义的地方人为规定它们都是正无穷或者负无穷。比方说对于，这个就是一个定义域不在全空间的函数。但是我们可以通过延拓，也就是额外设。这是因为当（也就是说从右边开始逼近）的时候，可以得到。这样的话就可以得到一个凸的，又具有单调性的函数。如果可以构造出一个这样的全空间的函数，又不影响原始定义域的值，那就算是一个合理的拓展。

事实上我们是可以利用theorem 1和基本的凸的定义来推出theorem 2的，不过碍于篇幅我们略去这一部分内容。似乎这一节略去的内容有点多，但是我想如果只是一路看下来，即使有醍醐灌顶之感，也多是错觉。挖一些坑让读者自己去思考，有的时候会有意想不到的效果hhh。

有的人可能会问为什么一定要对做一个拓展。这里有一个不错的反例：考察，，那么这个时候，我们可以得到

很明显这个函数并不是一个凸函数，因为它的定义域都不是一个凸集。但是如果我们只是使用的单调性，会发现既是凸函数又是凹函数，这很明显是说不通的。错误的原因就在于，如果我们考虑的拓展，会发现无论我们要求它的函数是凸还是凹，都做不到让是单调的。所以即使是一个单调函数，也不能够推出的凸性，也就说明了存在的必要性。下面这张图就描述了这个窘境。

也就是说，无论是选择凸的（绿色线部分，表示），还是凹的（红色线部分，表示），都做不到单调。

好的，关于凸的内容，我们就说这么多。

强凸与强光滑性

还有一些篇幅，我们对凸做一些更细节的刻画，也就是下面要说的强凸和强连续性。我们说它是“更细节”的，是因为有专门的刻画这种性质的量度。而在很多实际的问题中，如果能够施加对这种强凸和强连续性的要求，会对很多算法的性质有很大的改进。

我们先说强凸吧。

Definition 5: Strong Convexity
若函数是一个凸函数，那么就是一个凸性量度为的强凸函数。

这里提醒大家一下，没有额外加标识的范数都是2-范数。

所以说强凸是比严格凸要更强的一个概念。而这个定义也说明了，确确实实是有一个拉凸的效果的。这个思想我们在《数值优化》中的第6节，介绍拟牛顿方法的时候用上过，感兴趣的可以参考

数值优化（6）——拟牛顿法：BFGS，DFP，DM条件

其实在有的书上还有其它强凸的定义，但是这个定义是最自然的，所以我也就懒得把其它定义放上来了。

接下来说说强光滑性。

Definition 6: Smoothness
如果满足，，那么称它具有的光滑性量度。

这里要注意，一是我没有在英文原版中加上strongly这个词，是因为原版就没有这个词，所以为了尊重我还是写成了smoothness。二是这个性质其实就是Lipschitz连续的意思，《数值优化》中也多次有提到。无非只是在不同的环境中，换了不同的叫法而已。

关于凸性和光滑性，最重要的性质就是下面的这两个。

Theorem 3:
以下性质等价
强凸，且凸性量度为

这是一系列关于强凸性的结论，而且是多个结论的相互等价性。比较常见的做法就是证明出一条逻辑链，只要这个逻辑链能够构成一条环，且囊括这里面所有的结论就可以了。

我们先证明。假如说强凸，那么有是一个凸函数，那么注意到对于凸函数，我们有

这个性质可以参考《数值优化》的第C节

数值优化（C）——二次规划（下）：内点法；现代优化：罚项法，ALM，ADMM；习题课

的习题课部分。那么我们又可以发现，所以代入就可以了。

然后我们证明。注意到如果设，那么会有

两边除以，并且令，根据方向导数的公式（但这次用的是计算海塞矩阵的公式，《数值优化》第1节），可以得到

这个就是的意思，因为是任意的。

接下来证明，这个没什么好说的，二阶Taylor展开就可以了，和上面证明凸函数的二阶信息等价性是类似的思路。然后就是，这个也是一样，只需要证明是一个凸函数。而注意到第四个式子想说明的内容是

而这个就是凸函数的一阶信息刻画，所以自然也就得到了结论。至此我们已经得到了一条完整的闭环，所以这个等价性就算证明完毕了。

强凸性有这样的刻画，强光滑性自然也有，我们来看一下有什么不同呢？

Theorem 4:
以下性质等价
是Lipschitz连续的，且常数为。

这个证明的逻辑链稍微有些不同。首先是，这个可以根据Cauchy不等式来得到，也就是

再证明，方法和上面完全一样，这里我们也略过。下面是，二阶Taylor展开就可以了，然后是，这个可以把交换一下顺序，然后两个不等式加在一起得到结论。最后就是，这个可以考虑对梯度再做一次Taylor展开，也就是说

然后注意到是恒成立的，移项就可以得到结论了。到此为止逻辑闭环已经得到，所以结论也就证明完毕了。

强凸和强光滑性是非常好的函数性质，而且就这两个大定理就可以看出，它们利用了二阶信息，对函数分别提供了一个上界和一个下界（对应Theorem 3和4的最后一个不等式）。当然关于它们的性质远不止这些，这只是最有代表性的一个。其它的性质可以参考Source中的Amir Beck(2017)，这本书用了整整一章来说明这些。

好的，关于凸函数的各种性质，我们就说这么多，下一节我们会换换口味，介绍一些算法，并观察凸性对算法造成的影响。

小结

本节主要关注的是函数的凸性，如何判断函数的凸性是这一节主要解决的问题。可以看出凸是非常重要的一个主题，函数有不同的性质，就会有不同的凸函数刻画。而且其实很多时候，判断函数的凸性不一定是一个很容易的问题，而通过观察函数的凸性，有的时候还能发现一些意想不到的问题的本性，我们这一节通过几个小例子（但也只是几个小例子）说明了这一点。另外，还介绍了强凸和强光滑性。它们是凸性的延伸，我们之后会看到它们的作用。

火柴OR青年