凸优化和非凸优化

机器学习（37） 

其中，是 凸集是指对集合中的任意两点，有，即任意两点的连线段都在集合内，直观上就是集合不会像下图那样有“凹下去”的部分。至于闭合的凸集，则涉及到闭集的定义，而闭集的定义又基于开集，比较抽象，不赘述，这里可以简单地认为闭合的凸集是指包含有所有边界点的凸集。

非凸优化问题如何转化为凸优化问题的方法：1）修改目标函数，使之转化为凸函数2）抛弃一些约束条件，使新的可行域为凸集并且包含原可行域

----------------------------------------------------------------------------------------------------------------------------------------------------------

关于凸优化的一些简单概念

机器学习（39） 

http://www.cnblogs.com/tornadomeet/p/3300132.html

没有系统学过数学优化，但是机器学习中又常用到这些工具和技巧，机器学习中最常见的优化当属凸优化了，这些可以参考Ng的教学资料：http://cs229.stanford.edu/section/cs229-cvxopt.pdf，从中我们可以大致了解到一些凸优化的概念，比如凸集，凸函数，凸优化问题，线性规划，二次规划，二次约束二次规划，半正定规划等，从而对凸优化问题有个初步的认识。以下是几个重要相关概念的笔记。

　　凸集的定义为：

　　其几何意义表示为：如果集合C中任意2个元素连线上的点也在集合C中，则C为凸集。其示意图如下所示：

　　常见的凸集有：

　　n维实数空间；一些范数约束形式的集合；仿射子空间；凸集的交集；n维半正定矩阵集；这些都可以通过凸集的定义去证明。

　　凸函数的定义为：

　　其几何意义表示为函数任意两点连线上的值大于对应自变量处的函数值，示意图如下：

　　凸函数的一阶充要条件为：

　　其中要求f一阶可微。

　　二阶充要条件为：

　　其中要求f二阶可微，表示二阶导数需大于0才是凸函数。

     按照上面的两个定义，如果f(x)=x^2肯定是凸函数，而g(x) = -x^2是非凸函数。也就是说开口向下的函数是非凸函数，但是对于这种情况可以通过添加负号变成凸函数，从而求解。

 　　常见的凸函数有：指数函数族；非负对数函数；仿射函数；二次函数；常见的范数函数；凸函数非负加权的和等。这些可以采用上面2个充要条件或者定义去证明。

　　凸优化问题（OPT）的定义为：

　　即要求目标函数是凸函数，变量所属集合是凸集合的优化问题。或者目标函数是凸函数，变量的约束函数是凸函数（不等式约束时），或者是仿射函数（等式约束时）。

　　对于凸优化问题来说，局部最优解就是全局最优解。

　　常见的凸优化问题包括：

　　线性规划（LP）：该问题是优化下面的式子：

　　其中那个不常见的奇怪符号表示按元素小于等于，后面出现类似符号可以类似理解。

　　二次规划（QP）：该问题是优化下面的式子：

　　二次约束的二次规划（QCQP）：该问题是优化下面的式子：

　　半正定规划（SDP）：该问题是优化下面的式子：

　　按照文章说SDP在机器学习领域应用很广，最近很流行，不过我好像没太接触到过。

　　参考资料：

     http://cs229.stanford.edu/section/cs229-cvxopt.pdf

为什么凸优化这么重要？

11 个回答

我就按着问题一个个的回答吧： 首先，在现实生活中，如果对实际问题进行建模，直接符合凸优化条件的问题很少很少，少的可怜，我们在机器学习中、深度学习中所谓的模型正好符合凸优化模型的情况是经过无数先辈几十年的沉淀转化而来的，现今的机器学习、深度学习，所谓的智能，其实也只是数据进行建模，kNN、贝叶斯、决策树、SVM做超平面分隔、k聚簇等等只是在使用统计学的方法来做决策，其实只是概率(对已发生事件的频率统计)选择来进行决策而已，而解决这些问题的过程当中，存在着无数约束条件:等式+不等式。求解ƒ(x),使得等式+不等式符合条件，经过先辈们的改善、切合，发现转化为凸优化可以解决这类问题。但是还有着大量的问题没法解决，例如NP问题，目前是无解的，因为它涉及的约束条件、可能性太多，计算过于复杂。我们没法直接将它转化为凸优化。 其次，凸优化的重要在于它是一个相对而言被嚼烂的数据模型，对凸优化的问题我们在基础数学上面已经有了很多解决方法，例如可以将凸优化问题Lagerange做对偶化，然后用Newton、梯度下降算法求解等等。

再次，现有的优化方法不是都解决了的，还是有很多问题是没有解决的，例如NP问题，如果转化为可解问题，如何对这些问题做近似优化处理，这就需要遇到具体问题的时候具体去分析，而且建立一个近似可解的优化模型需要我们对优化本身理解透彻。一个对水墨、颜料都不懂的画家如何能够创造出新颖的画风？

最后，回答末尾一个问题，凸优化的作用在于思维方式的转变，跟计算机思维方式一样，计算机从业人员在遇到问题的时候习惯了通过电脑去协助解决问题，而他们的价值不在于知道听得懂别人告诉他如何解决问题，而是遇到现实问题的时候都会将问题拆分成机器可以实现的方式去解决：例如遇到购物，阿里巴巴建立了网站、app、c/s系统、b/s系统，用互联网建立信息流，建立帝国。遇到查询问题，百度建立了搜索引擎。这种思维方式才是最重要的。。同样，凸优化的价值也在于思维转变，遇到现实生活问题的时候，我们必然要对问题进行建模，然后抽象问题，利用机器去帮助我们解决问题，那么，当问题的计算量接近无穷大的时候我们如何去解决？这就需要我们抽离问题抽象结构，想办法将转换成“凸优化问题”，因为凸优化已经被嚼烂，所以只要问题转化成凸优化，我们就可以分布迭代去运算，于是才有了机器学习、深度学习这一门门的交叉科学。凸优化是数学领域的重要分支，而计算机科学仅仅是数学这门基础科学的延伸而已，基础科学才是王道！！！ C#、java固然是被封装成了便于人类使用的高级语言，但是总有些功能是“已有实现”没有封装好的，这时就需要我们回归更加原始语言C、汇编去编程。。深究底层、精通基础科学才是从容面对所有问题的解决王道，学会别人解决过的问题只能让你解决相同的问题，现实是无限可能的，总有未解决过的问题等着你，凸优化，你值得拥有