|
|
作为半个搞优化的人，一直没有系统的整理优化算法方面的知识，知道昨天受师兄炜哥的熏陶，想想学了这么多年，也是时候该整理一下了。最优化算法的发展史要追溯到17世纪法国的一位业务数学家费马，之所以称他是业余数学家是因为这家伙是个律师。西方数学界无数杰出的数学家可能在他那个时代都没有可以与之匹敌的成就。在律师界他是玩数学玩的最溜的，在数学界他又是搞律师搞得最好的。你说气人不气人！！！
最著名的应该是费马大定理（当整数 n>2时，关于x,y,z的方程x^2+y^2=z^2没有正整数解）。我就不说这个定理在数学界有多牛了，反正就是人家凭借这个收到了10万马克的奖励。 那么他对于优化的贡献是提出了梯度下降论——最速下降法，这应该是优化思想的最早期阶段了。
什么意思呢？简单点说吧，拿线性方程举例：就是在线性有边界的方程上，你随便取一个自变量范围内的数，沿着斜率方向（梯度方向），以一定的步长d进行迭代更新，达到最值的速度是最快的。当然你也可以不按照斜率方向去找最值（结果是你找不到！！！原谅我就是这么皮）有人说这个玩意还需要证明吗？我在想说这话的人肯定是脑子不好使。让你知道1+1=2简单，让你证明1+1=2估计你这辈子也难了。这个理论提出的是目标函数对自变量X的一阶导数为梯度下降方向
到了1687年牛顿也就是我们牛大爷出来了，他提出了牛顿法，什么意思呢？是在费马的基础上提出了梯度下降方向，此时的步长就是个问题，前面讲到以一定的步长来进行迭代更新，那么什么是一定的步长呢？牛大爷就是干的解决这个活的。他提出的二阶导数，从某种程度上来将就是将hessian矩阵的逆矩阵的负来作为步长来整理。
此时的迭代变成了Xn=Xn-1-d,d=-G^-1*g, 此时的G就是hessian矩阵，g是一阶导数。对X不停的迭代直至收敛，可以用来求解部分非线性问题了。从工科的角度来看，在求解的过程中知道g怎么来的，G怎么来的就可以了。应用时可以直接利用软件实现。论证过程见这个梯度下降法与牛顿法的解释与对比 - happy_lion - 博客园。
那么是不是这样就完整了呢？我们找到了梯度方向，找到了步长计算方法，在求解最值过程中，理论上达到了一个完整的平衡了。但是这里面也有一个问题，首先每次计算步长的时候都需要求解hessian矩阵，同时有些目标函数在求解hessian矩阵的过程非常复杂。这给实际应用造成了很多的麻烦。于是又出现了一种算法，拟牛顿算法他在解决hessian矩阵求解方面利用目标函数和一阶段导数的信息来构建hessian近似阵，其中包括DFP、BFGS、L-BFGS几种新的计算方法，这样在计算机求解过程中，节约了大量的时间。
先讲DFP方法，假设有个复杂的目标函数f(x,y),初值我们自己随便给一个x0,y0，没关系，这样我们先求解目标函数的一阶段导数（也就是梯度），同时求解该目标函数的二阶导数hessian阵H0(必须是正定矩阵，所以可以选择单位正定阵来作为初始矩阵来进行更新)，新的迭代值x1,y1就出来了。
新的（x1,y1）可以得到新的g1 , s0=(x1,y1)-(x0,y0), k0=g1-g0此时下一步的H1就不需要再进行hessian近似阵的求解了。而是：
,这样来说下一次的g1和下一次的H1都有了，就又可以求解写一个(x2,y2)。不知道这样说的明不明白。那么什么时候迭代结束呢？这个时候我们要设定一个阀值，就是两个最近的自变量之间的二范数的值小于这个阀值，阀值设定一般都设定的非常小。
为了不把整个过程说的过于复杂我全文只说它的演变过程。DFP方法进化而来的是BFGS方法，它与DFP方法的不同是在于hessian矩阵的近似相上加入了一个修正项。详细参考 这个用Newton法、DFP法和BFGS法求函数极值_百度文库。在收敛速度上面牛顿法是最快的，但是计算代价是最大的，比较DFP方法和BFGS方法上，它们俩的差距在于初值的选取上，当初值的选取距离真实值比较远时，此时选择BFGS方法，更有优势。
再进行发展的时候，出现了另一种新的方法共轭梯度法（CG算法），在解决大型的线性方程组求解的过程中，对于Hessian的求解麻烦，步长寻找困难，这部分共轭梯度法刚好解决了这部分的麻烦。同时也解决了最速下降法的锯齿性现象。在收敛的角度来看，它具有超线性瘦脸的优势。它的求解过程只需要一阶导数的相关信息。
红色共轭梯度法，绿色牛顿法
先求取目标函数的一阶导数梯度方向g0，然后再根据共轭梯度原则求解新的梯度方向P0，在选择P0的时候我们要考虑当前梯度方想是否与所求解的值的范围的截面垂直。这里面有个重要的常数正定矩阵G，对于所有的线性非线性的函数都可以在进行一阶导数后得到的自变量常数系数正定阵G。假定：
从最开始X0开始，此时的d0为目标函数F（x）对于x0这个地方的一阶导数的值的反方向（也就是-g0）。这其实就是梯度方向了。接下来就是步长值αk，第一个是α0，这种精确计算步长值的方法其实在解决实际应用过程中不太实用。
这样下一个X1就得到了，接下来就不能再用之前的梯度了，这个β0有很多的算法。此时的梯度方向应该换个思维来进行求解新的梯度下降方向d1：
步长α1与α0的计算方式是一样的，这样不停的进行下一个Xk+1的计算。当前后两个自变量的差值的二范数小于某个阀值的时候，循环结束。
在优化理论上都喜欢拿爬山理论来解释这个玩意，不管是什么优化算法，都是可以用一阶线性方程和二阶牛顿方程来解释的。这是最容易让人理解优化的方式。共轭梯度方法最重要的就是共轭方向的理解：
S1与S2的方向就是共轭方向，S1代表则第一次你搜索的梯度方向，S2就是纠正后的共轭方向。相当于什么呢？你爬山的时候可以直接爬上去，但是你不能保证你每次爬的方向都是直接上山的方向，虽然你知道大方向上你是在往上爬，但是路线可能不是最好的路线，而共轭梯度法就解决你向上爬的时候的方向问题，它利用就相当于前几次你都爬的方向不太对，在有限次数就可以找对最正确的攀爬方向。（共轭梯度法我的理解就这个情况，可能我也没讲的很清楚，希望有更厉害的能用更简洁朴素，甚至诙谐幽默的语言来解释这个问题）
好了这些问题解决了，但是在求解方程最值的问题上，我们还需要考虑另一个问题，就是约束问题，等式约束问题和不等式约束问题。这里扩散引申一下，我们真是遇到的很多问题，并不是一个凸函数或者一个凹函数，它可能是很多个凹凸组成的曲线，甚至它有可能在维度上不是我们理解的简单的二维平面问题，三维的，四维的，甚至是更高维度的，而我们只能用归纳方法去进行推测，利用一维、二维、三维的最优化理论图像去进行更高维度的变换。当然我们如果了解傅里叶变换，这些都不是什么问题，在遇到很多凹凸组成的曲线上例如：
这样的简单的二维平面上的自变量取值范围一定的求解极值问题，欧洲大神给你解决，这里面涉及到的人物比较多，最后只是用了拉格朗日的名字来命名这个方法。它的主导思想是将一个约束类问题转化为无约束问题求解。也就是这么说吧，如果有等式约束或者不等式约束，给它们都加上一个未知乘子λ构建一个函数，然后让原函数加上这个构建的函数来组成一个新的目标函数。这样还是利用之前的方法来求解。整个过程拉格朗日乘子法_百度文库
讲到这里基本上常规的传统优化方法已经差不多将完了，总结来看，我们能够了解在寻优过程中最重要的是两个点，一个是梯度下降方向，另一个是步长值。人类的智慧在于发现问题以后，会不停的解决问题。接下来就讲一下关于启发式算法。启发式算法真正的体现了劳动人民的智慧。 |
本帖子中包含更多资源
您需要 登录 才可以下载或查看，没有账号？立即注册
×
|
窥视卡
雷达卡
发表于 2023-2-11 12:59
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡