机器学习之最优化

这篇关于最优化的文章是最近学习的一个总结，放在简书上，方便以后查阅，如果帮助了其他读者，也算一件好事。

一、前言

现实生活中，当我们面临抉择（有几个备选方案可选），我们总是会希望可以做出最优选择，所以可以对所面临的问题进行建模，也就是根据需要考虑的因素，得到一个代价函数（损失函数）或者收益函数，然后求解该优化问题，寻找函数的最值点，得到最优选择。

例如种地问题，问：种x亩的玉米和y亩的小麦可以获得最大收益，x和y均未知，且满足一定约束条件，调整x和y，使得目标函数达到最大，也就得到了最优选择。

大部分的机器学习算法都可以归结为最优化问题，例如logistic回归和神经网络，都是调整模型参数，使得损失函数最小，得到参数的最优值；SVM中，调整模型参数，使得划分超平面距离两个类边缘的间隔最大，即得到模型的最优解。

二、从最优化到凸优化

一般情况下求解一个函数的最值并不容易，因为容易陷入局部极值，所以一般的最优化问题直接穷举遍历（解空间比较小）或者使用启发式搜索（解空间很大，NP问题）。而凸优化问题（convex optimization）则可以高效地求解最值，基于目标函数的“凸”性，它的局部最优解即为全局最优解。

一旦一个问题转化为凸优化问题，那么这个问题就得到了解决，因为凸优化已经被研究透了。

三、凸优化的定义：

（1）凸集（convex sets）：集合中任意两点的连线都在这个集合中。

（2）凸函数（convex functions）：函数曲线任意两点的连线都在函数上方。

（3）凸优化：调整优化变量使得目标函数（是一个凸函数）最小，优化变量属于凸集，或者说优化变量需要满足一定的不等式约束和等式约束。

四、凸优化问题分类：

（1）线性规划（LP, linear programming）：目标函数和不等式约束都是线性函数。

（2）二次规划（QP, quadratic programming）：目标函数是凸二次函数，不等式约束是线性函数。

（3）二次约束二次规划（QCQP, quadratically constrained quadratic programming）：目标函数和不等式约束都是凸二次函数。

五、凸优化问题求解的一般方法：

根据凸函数的性质，只要一直沿着可以使目标函数变小的方向搜索，就可以找到最小值，所以可以使用梯度下降的方法。

要更新某一个优化变量，只需对这个优化变量求偏导，然后计算它处于当前值的导数，即梯度，也就是目标函数在此处的变化率，然后乘上步长，即得到修正量，然后根据负梯度方向更新这个优化变量即可。

六、求解线性规划：

先画出可行域，然后将顶点代入目标函数，求得最大值或最小值即可。

这是因为，目标函数是线性函数，所以只要x或y增大，目标函数都会增大，所以可能的最优解一定在可行域的边界上。沿着边界，x或y会增大，直到遇到拐点（也就是可行域的顶点），遇到拐点之后，x或y可能会减小，所以最优解只可能是几个交点之一。

转载请注明如下内容：

文章来自简书，作者：就是杨宗

原文链接：http://www.jianshu.com/p/b47daa391e2d