凸优化初步了解
凸优化是个大话题，常见却又从未系统去理解，这里做一些初步了解。
优化（optimization）
机器学习的大部分事情，就是把任务建模成一个优化问题：
\[ \min_{x\in D} f(x) \]
用高中数学的用词来讲，就是让 \(x\) 在定义域 \(D\) 上找到特定位置，使 \(f(x)\) 达到最小值。
机器学习中，我们通常用梯度下降、牛顿迭代等方法来找最优解，也就是利用函数的导数，或数据的梯度，来迭代地找到达到最优解的优化变量的位置。
我们曾经学函数的时候直到，可以利用“导数=0”来求最大或最小值，也知道对于一些函数，这个方法是不适用的，比如三次函数，拐点梯度为0但并不是最大或最小值。显然，二次函数的形状是“凸的”，三次函数则不是。
如果机器学习中的问题能够适用“梯度为0则为最优解”，或问题可以转换成适用的问题，那么优化问题就会变简单。那么我们可以对问题做限定：
- 函数是凸函数
- 优化变量的可行域是凸集
凸集
通过二次函数与三次函数，凸函数还算容易理解。那么凸集是什么呢？
对于n维空间集合D中任意两点 \(p_{1}\) 与 \(p_{2}\) ， 对 \(\theta \in [0, 1]\) 都有
\[ \theta p_{1} + (1-\theta)p_{2} \in D \]
则该集合D是凸集。
也比较显而易见，用二维空间理解的话，就是没有洞也没有凹槽。
显然在不加约束的情况下，任意维度空间都满足上面公式，即都是凸集。
那么如果作为一个课程，就可以出不少有意思的考试题了：给不同类型的约束，证明约束下的可行域是否是凸集。
比如线性规划：如果每条直线都取一侧作为可行域，一系列直线的交集肯定是个凸集。
- 多个凸集的交集也是凸集
- 线性等式约束可行域是凸集
凸函数
在定义域内，任意两点 \(p_{1}\) 与 \(p_{2}\) ，都满足
\[ f(\theta p_{1} + (1 - \theta)p_{2}) \leq \theta f(p_{1}) + (1 - \theta)f(p_{2}) \]
则 f 是凸函数。
当然，实际问题中往往不那么直观，就会有更多数学工具与方法来证明函数凸性，比如海瑟矩阵是否正定等等，读研时候学过，早忘一干二净了。。。
凸优化
如果一个最优化问题的可行域是凸集，并且目标函数是凸函数，则该问题为凸优化问题。
证明一个优化问题是凸优化，就从以上内容着手，证明凸函数一般就证明海瑟矩阵半正定，证明可行域是凸集就可以利用许多已有的结论。凸优化的通用写法是
\[ \min f(x) \\ g_{i} (x) \leq 0, i = 1, ..., m \\ h_{i} (x) = 0, i = 1, ..., p \]
很多地方见到这么写，就是不解释 g、h 是什么，急死个人，对小白很不友好。
这里 \(g_{i}(x)\) 是不等式约束函数，为凸函数。
\(h_{i} (x)\) 是等式约束函数，为仿射函数，仿射函数即相对于线性函数而言， Ax+b 是线性函数，Ax即仿射函数，可以理解为“穿过原点”。
这是用了前面说的凸集中被证明的结论：凸集的交集是凸集，线性等式约束的可行域是凸集，那么就可以用这两点来描述一个更具体的凸优化，分别对应 \(g\) 函数集合与 \(h\) 函数集合。
局部最优与全局最优
目标函数是凸函数、优化变量的可行域是凸集，这两个条件缺其中任何一个都不能保证局部最优解是全局最优解。
也即两者都满足才是凸优化问题，而凸优化问题可以放心地找局部最优，同时也就找到了全局最优。
证明过程也不十分复杂，这里就不照搬资料了。
求解
梯度下降、牛顿法、拟牛顿法这些研究生课也学过，现在竟不记得那门课叫什么名字，只记得是数学院的老师讲的，十分受用。
难者不会，会者不难。非本篇文章重点，这里掠过。
各种各样的机器学习方法，大都也是在梯度下降的思想上设计的。支持向量机、逻辑回归等等等等。就想起当时老师说：
模拟退火、遗传算法这些随机算法都发不了什么好期刊了，因为它们不“数学”，收敛靠概率，不能数学地证明收敛时间。而梯度下降、拟牛顿法等等是基于数据梯度方向的，可以严谨地证明收敛性和收敛时间。
小结
不求甚解地了解了一下凸优化，背后的数学优美而复杂，而浅尝辄止地理解一下概念未尝不可。