对凸优化（Convex Optimization）的一些浅显理解

©作者 |  李航前

单位 |  EPFL

研究方向 |  计算机图形学与三维视觉

最近学习了一些凸优化课程，整理笔记的同时写下一些自己的理解，向着头秃的道路上越走越远。

凸优化是应用数学的一个基本分支，几乎在工程、基础科学和经济学的所有领域都有应用。例如，如果不理解凸优化的对偶理论，就不可能完全理解统计学习中的支持向量机（SVM）、电力市场中的节点定价、经济学中的基本福利定理或两人零和博弈中的纳什均衡。在计算机 AI 算法学习中，凸优化也是必要的一环。

先来做一些铺垫，引用自 EPFL 的凸优化课程，首先来看一个数学优化问题，如下图，该问题是为了寻找目标函数的最小值，其中涉及了目标函数，决策变量，可行域等概念。

▲ from MGT-418 Convex Optimization 

下面在说下确界的问题，下确界一定有（可以是负无穷）但是最小值不一定有。

▲ from MGT-418 Convex Optimization

▲ from MGT-418 Convex Optimization

以上说了全局最小值，但是一些情况下没有办法获得全局最小值，所以就要去计算局部最小值。它叫 优化问题。

▲ from MGT-418 Convex Optimization

下图可视化展示了全局最小值和局部最小值的区别。

有了一些直观的认识和浅显的理解，下面我们来具体聊凸函数的概念及判定方法、凸集、常见目标函数。

凸集和凸函数

从函数的凹凸性而言，我们通常把函数分为凸函数和非凸函数。凸函数是有且只有全局最优解的，而非凸函数可能有多个局部最优解，这些特性我会在下文中进行详细解释。在前言中，我提到过优化问题是机器学习模型中的核心部分，而针对不同模型，有不同的方法论对其目标函数进行优化。例如针对逻辑回归、线性回归这样的凸函数，使用梯度下降或者牛顿法可以求出参数的全局最优解，针对神经网络这样的非凸函数，我们可能会找到许多局部最优解。

不难看出，我们希望在实际解决问题过程中，都希望我们建立的目标函数是凸函数，这样我们不必担心局部最优解问题，但实际上，我们遇到的问题大多数情况下建立的目标函数都是非凸函数，因此我们需要根据场景选择不同的优化方法。

凸优化定义

就定义而言，凸优化是：在最小化（最大化）的优化要求下，目标函数是凸函数且约束条件所形成的可行域集合是一个凸集的优化方法，因此凸优化的判定条件有两个，1.函数定义域是凸集 2.目标函数是凸函数。

凸集的定义：假设对于任意 x, y ∈ C and 任意参数 α ∈ [0, 1], 我们有 αx + (1 − α)y ∈ C，集合 C 为凸集。

凸集的理解：对凸集的理解，我们可以分别从理论定义的角度和函数图像的角度两方面理解。从定义上讲，对于集合 C 中的任意两个元素 x 和 y，需要满足 αx + (1−α)y 的值也需要在集合 C 中；从函数图像角度讲，这个定义中的式子含义是，x、y 两点连线上的任意一个点都需要属于集合 C，如下图所示，任何证明集合是凸集的方法都可以通过定义和函数图像两方面进行。

凸集的性质： 两个凸集的交集也是凸集。（注意，两个凸集的并集就不一定还是凸集了）

常见凸集与证明方法：

凸函数定义： 函数 f 的定义域为凸集，对于定义域里的任意 x, y，函数满足：

凸函数与凹函数之间的关系：如果 f(x) 是凸函数，则 -f(x) 是凹函数

凸函数的证明方法 （函数定义域为凸集的前提下）：

常见凸函数及证明

常见目标函数

针对一个 AI 问题，我们都可以将 AI 问题拆解为建立模型+优化模型这两块内容的，对于任何一个 AI 问题，其目标函数都可以用以下形式表示：

我将解决业务问题中的常用套路称为算法思维，并总结了以下 4 个重要步骤：

1. 将业务场景中需要解决的问题转化为数学问题，并写出严格的数学模型（目标函数）
2. 针对写出的数学模型判断凹凸性
3. 根据目标的函数的凹凸性判断问题类型（如果目标函数是凸函数，我们需要判断该函数所属问题类型，常见的问题类型有 Linear Programming、Quadratic Programming 等；如果目标函数是非凸函数，也需要判断其所属问题类型，常见有 Setcover Problem，Max flow Problem 等）

4. 根据不同的问题类型使用不同的优化方法论解决问题。

其实在实际解决问题的过程中，其实大家都不太会在意第 1,2 个步骤点，可能都会直接通过经验去查找相应的工具解决问题，但是这样的解决思路是不太好的，因为在这个过程中，我们可能不知道需要解决的问题和我们选择的工具是否匹配，如果结果不太理想，我们可能也不知道其中的原因。但是如果我们在解决问题前，定义了严格的目标函数，我们不仅可以针对该目标函数选择相应的优化方法，也可以根据业务场景，对目标函数进行相应调整，增加项目的成功率。

而实际工作中常见的目标函数大概有以下：

参考文献

[1] EE-556：https://moodle.epfl.ch/course/view.php?id=14220

[2] MGT-418：https://moodle.epfl.ch/course/view.php?id=15778

[3] AI工程师必备技能-凸优化介绍：https://www.jiqizhixin.com/articles/2019-01-23-15

特别鸣谢

感谢 TCCI 天桥脑科学研究院对于 PaperWeekly 的支持。TCCI 关注大脑探知、大脑功能和大脑健康。

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：hr@paperweekly.site 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·