为什么 Non-Convex Optimization (非凸优化)受到了越来越大的关注?

2018/12/04 15:11
阅读数 6.5W

前言:运筹学在国内,远没有统计和人工智能来的普及。相信很多人不知道,运筹学正是研究优化理论的学科,而人工智能最后几乎都能化简成求解一个能量/损失函数的优化问题。因此,我把它称为人工智能、大数据的“引擎”。

本文的详细版本已发表在我的专栏:

离散/整数/组合/非凸优化概述及其在AI的应用 - 知乎专栏

言归正传,为什么非凸优化受到越来越多的关注?

1,首先大家需要知道Convex VS Non-Convex的概念吧?

数学定义就不写了,介绍个直观判断一个集合是否为Convex的方法,如下图:

简单的测试一个集合是不是凸的,只要任意取集合中的俩个点并连线,如果说连线段完全被包含在此集合中,那么这个集合就是凸集,例如左图所示。

 

2,凸优化-相对简单

凸优化有个非常重要的定理,即任何局部最优解即为全局最优解。由于这个性质,只要设计一个较为简单的局部算法,例如贪婪算法(Greedy Algorithm)或梯度下降法(Gradient Decent),收敛求得的局部最优解即为全局最优。因此求解凸优化问题相对来说是比较高效的。这也是为什么机器学习中凸优化的模型非常多,毕竟机器学习处理大数据,需要高效的算法。

 

3,非凸优化-非常困难

而非凸优化问题被认为是非常难求解的,因为可行域集合可能存在无数个局部最优点,通常求解全局最优的算法复杂度是指数级的(NP难)。如下图:

最经典的算法要算蒙特卡罗投点法了,大概思想便是随便投个点,然后在附近区域(可以假设convex)用2中方法的进行搜索,得到局部最优值。然后随机再投个点,再找到局部最优点。如此反复,直到满足终止条件。

假设有1w个局部最优点,你至少要投点1w次吧?并且你还要假设每次投点都投到了不同的区域,不然你只会搜索到以前搜索过的局部最优点。

 

4,非凸优化为何重要,开始受到重视?

因为现实生活中,几乎所有问题的本质是非凸的。把3中的图看作山川盆地,你在现实中有见过左图这么“光滑”的地形么?右图才是Reality!

 

5,为何要学凸优化呢?

科学的本质便是由简到难,先把简单问题研究透彻,然后把复杂问题简化为求解一个个d俄简单问题。例如3中经典的投点法,就是在求解一个个的凸优化问题。假设需要求解1w个凸优化问题可以找到非凸优化的全局最优点,那么凸优化被研究透彻了,会加速凸优化问题的求解时间,例如0.001秒。这样求解非凸优化问题=求解1w个凸优化问题=10秒,还是可以接受的嘛!

机器学习中的优化理论,需要学习哪些资料才能看懂? - 知乎

6,运筹学中线性规划与凸优化的关系

线性规划是运筹学最基础的课程,其可行域(可行解的集合)是多面体(polyhedron),具有着比普通的凸集更好的性质。因此是比较容易求解的(多项式时间可解)。

听我唠叨下知乎第一场有关运筹学的Live:

大数据人工智能时代的运筹学 -- Robin Shen 2017.06.11的知乎Live

7,运筹学中(混合)整数规划与非凸优化的关系

大家或许不知道,(混合)整数规划被称为极度非凸问题(highly nonconvex problem),如下图:

实心黑点组成的集合,是一个离散集,按照1中判断一个集合是否为凸集的技巧,我们很容易验证这个离散集是非凸的。因此整数规划问题也是一个非凸优化问题,并且它也是NP难的。

那么整数规划的求解思路呢,也遵循了科学研究的本质,即被分解为求解一个个的线性规划问题。感兴趣的朋友可以搜索分支定界法。

 

8,(混合)整数规划为何重要?

虽然时间是连续的,但是社会时间却是离散的。例如时刻表,通常都是几时几分,即使精确到几秒,它还是离散的(整数)。没见过小数计数的时刻表吧?

同样,对现实社会各行各业问题数学建模的时候,整数变量有时是不可避免的。例如:x辆车,y个人。x,y这里便是整数变量,小数是没有意义的。

 

9,深度学习为何非凸?

深度学习里的损失函数,是一个高度复合的函数。什么叫复合函数?好吧,例如h(x)=f(g(x))就是一个f和g复合函数。

当f,g都是线性的时候,h是线性的。但在深度学习里用到的函数,Logistic, ReLU等等,都是非线性 ,并且非常多。把他们复合起来形成的函数h,便是非凸的。

求解这个非凸函数的最优解,类似于求凸优化中某点的gradient,然后按照梯度最陡的方向搜索。不同的是,复合函数无法求gradient,于是这里使用Back Propagation求解一个类似梯度的东西,反馈能量,然后更新。

 

10,深度学习的优化问题在运筹学看来是“小儿科”

这句话可能会打脸大部分观众。

深度学习中的优化问题,虽然目标函数非常复杂,但是它没有约束阿!大家如果学过运筹学,就知道它由目标函数和约束条件组成,而约束条件,是使得运筹学的优化问题难以求解的重要因素。

点到为止。欲知详情,请戳:

[运筹帷幄]大数据和人工智能时代下的运筹学 - 知乎专栏

但是没办法,机器学习、深度学习还是这么火,所以,顺应时代潮流,写了这个:

想学数据分析(人工智能)需要学哪些课程? - 知乎

总结:

机器学习、数据科学因为处理数据量庞大,因此研究问题主要的方法还是凸优化模型,原因正是求解高效,问题可以scale。虽然目前还很小众,但是随着计算机硬件能力的提高,以及GPU并行计算的流行,以及非凸优化算法、模型的进化,想必非凸优化,甚至(混合)整数规划会是未来的研究热点。

展开阅读全文
加载中

作者的其它热门文章

0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部