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

上一节笔记：凸优化（1）——引入，优化实例分析，凸集举例与相关性质

——————————————————————————————————————————————————

大家好！

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

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

那么我们开始吧。

目录

• 凸函数的各类定义与举例
• 复合函数的凸性与应用
• 强凸与强光滑性

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的等价性。

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

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

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

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

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

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

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

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

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

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

复合函数的凸性与应用

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

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

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

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

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

强凸与强光滑性

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

我们先说强凸吧。

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

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

小结

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