数学知识

凸优化（Convex Optimization）

凸集（Convex Set）

凸集是一系列点的集合，凸集中任意两点之间所连线段一定落在集合内部，如下图所示。

站在集合内部看向集合边界时，集合的边界都是向外凸出的，就是凸集；如果是向内凹陷的，就不是凸集。

凸集的定义

空间，对于某个子集，从中挑选任意两个元素，对于，如果满足：

那么集合S是一个凸集，否则为非凸集。该判断标注和凸集的定义是定价的，本质是看元素之间所连线段是否落在集合内部，如下图所示：

凸函数

基于凸集的概念可以定义凸函数。凸函数一类具有特殊性质的函数统称，如果函数的定义域为凸集，且对于定义域内任意两个元素，对任意满足：

即函数上任意两点所连线段落于函数曲线上方或恰好在曲线上，称为凸函数，否则为非凸函数。下图展示时的情况：

如果是凸函数，则称为凹函数（Concave Function）。凸函数或凹函数并不是两者必取其一，如果的函数形状存在起伏或没有规律，既不是凸函数也不是凹函数。

函数最小值

对任意一个函数，可能存在多个局部极小点，但全局最小点只有一个。但如果是凸函数，那么只存在一个局部极小点，该点也就是非全局最小点。

求解函数最小值的常用方法就是梯度下降法。深度学习中的损失函数通常是非凸函数，只能得到局部极小点。非凸问题的传统做法：

• 块坐标下降法：每次迭代的过程中，只针对一个变量进行优化求解，其余变量保持不变，然后交替求解。
• 逐次凸逼近法：将目标函数在定点进行一阶泰勒展开，然后构建近似函数，近似函数代替原目标函数进行求解。
• 松弛变量引入法：引入松弛变量，将原目标函数中难以解决的公式部分用松弛变量代替，使目标函数变为凸函数。