大岩视点

首页-智闻
2020-07-15   作者:黄铂

岩论时光 | 大岩资本黄铂:最优化算法的前世今生(上篇)

近期,大岩资本成立七周年庆在深圳成功举办。周年庆上量化投资基金经理黄铂博士结合生活实践中的案例,深入浅出阐释了最优化算法的前世今生。


从实际生活中最基础的应用切入,黄铂博士将抽象的算法概念生动化,解释了什么叫最优化问题、凸优化及算法分类、机器学习与人工智能应用。


黄博士的分享内容较长,我们将分上、中、下三篇连载推出,本文为上篇。


最优化问题及基础应用


人生不如意之事十之八九,想达到我们想要达到的目标时,通常都有各种各样的限制。那么所谓最优化问题,就是指用最优的方式去平衡理想与现实之间的关系。以最简单的邮差送信问题为例,邮差从A出发,送信到BCD,最后回到A。邮差每天必须经过BCD,而且每个点每天只能经过一次,在这样的约束条件下,他的目标函数是尽可能以最短的时间完成送信。这个问题非常简单,只要把所有的路径枚举出来,然后取最短时间的方式即可。


幻灯片3.JPG


根据前面的例子,我们严格的将目标函数分为两大类。第一类是最大化,包括最大化盈利,最大化效率。另一类是最小化,包括最小化费用、时间和错误率。在金融行业,我们可以最大化预测股价的正确率,也可以最小化费用、最小化时间和错误率。当然,我们可以同时最大化盈利,最小化费用和时间。所以通常在很多的优化问题中,这两种任务可以组合起来出现在同一个问题框架下,这就是对于目标函数的定义。


最优化问题的两大类:连续优化与离散优化


关于约束条件,理想很美好,现实很骨感,在现实生活中,我们会遇到比如预算有限、时间有限、外部强制性条件等各种各样的问题,与目标函数一样,这些限制条件不是单一存在的,也可能同时存在同一个问题里,对于某一个优化问题来讲,限制条件越复杂,求解就越困难。基于此,我们简单根据它的约束条件以及目标函数变量类型将最优化问题分成两大类,连续优化和离散优化。


幻灯片7.JPG


连续优化正如图上所画,线中间没有断点,而离散优化的变量取值,是一个不连续的记录,就如同一开始讲的邮差送信问题。两类相较而言,离散优化会更难解决,因为离散优化多了一条限制条件——不连续的集合。很多时候,我们要求我们的变量是一个整数,或者来自一个给定的区间,所以说离散优化会比连续优化更难解,而两种算法也会有非常大的不一样。


从学术角度而言,连续优化与离散优化对应的是两个比较独立的学科,离散优化可能更多的应用于统计、大数据相关的场景,连续优化则会跟计算机密码学相关,更多的与我们现实生活中的运筹优化应用相关。


幻灯片8.JPG


从目标函数出发,它的最优值也分为两类,局部最优和全局最优。我们看图中黄色的点,在局部区域内是最低的,我们管这个值叫做局部最优值,但是当我们看整个图时,红色的点才是最低的,所以这个点我们叫全局最优值。通常来说,取局部最优值是相较容易的,因为基本上你只需要看它临近一小部分的信息就可以准确判断是否局部最优,而在现实应用中,其实仅仅知道局部最优值就足以解决很多问题。而更难的问题在于全局最优值,因为前提是你需要看到整个画面。


所以,对于这一类问题,我们目前没有一个特别好的解决方法。现实生活中,我们会有比较多的方法去求局部最优值,而往往我们找到的几乎跟实际上的全局最优值不一样。但有一个问题是例外,这类问题它具有比较好的性质,只要找到局部最优值,它就肯定是全局最优值,这类问题就叫凸优化。(未完待续)

版权声明:本文由大岩资本科学投资专家思考原创,如有转载或引用,请注明出处。