《用Python学习数值分析-- 最优化》

2017-09-13

  最优化对应的术语是”optimization“。是工科的基础课程。数值分析与最优化是高度相关的,都大概在四年级或者研一时教授。最优化课程更加基础一些,覆盖了理论基础,想要把课程里的算法实现出来,需要深入的线性代数、矩阵计算、数值计算的知识。最优化就是机器学习的核心,在图形学方向也是基础的课程。这也是我这两三年来用固定的业余时间来补充数学课程的原因。NA 和 Optimization本就是一体的,相当于实践与理论的关系,有一本教材甚至就叫Numercial Optimization[1],太厚。在这里稍微提一下optimization,就相当于提纲挈领的做一下总结吧。 
  optimization指寻找现实世界实值函数(objective function f (x))的最大值或者最小值。把函数翻转,最大值就变成了最小值,所以,只有一个问题。优化问题一般分为“无约束”与“约束”两类。与直觉相反,有约束条件的问题,反而更难以求解一些。所以,我们可以把注意力集中在无约束优化上,这是基础。Timothy的书中也只提到了这一部分。无约束优化也分为两种:是否依赖于f的导数。我们应该尽量的使用导数,NA问题中都是如此。人脑对一个函数降维较为容易,第三四代编程语言写的程序对函数降维可没那么简单,对于高维复杂函数,我们人脑也无能为力。维度,是困难的始祖,是深渊。即使高维中的线性规划问题,都需要海量的计算。单纯形法复杂度为O( 2n )。高维非线性问题,更是困难。
  optimization问题比解方程困难。解方程组,我们只是求解一个一个或者几个确定解。而求解optimization问题,我们求解的结果是一个集合。用数值计算的方法解optimization问题,一般按照是否有导数来分为两类。 
  一,没有导数

  1. 黄金分割搜索
  2. Successive parabolic interpolation(SPI) 
  3. Nelder-Mead search

  我们很少见到这类方法,是因为我们很少用。这里只需要简单了解一下即可。解方程的方法中也有不依赖于的导数的方法:割线法、Brent's Method。
  黄金分割搜索类似于解方程用的“包围法”,如熟知的解单变量方程的二分法。前者寻找函数曲线的最低点,后者寻找曲线与y轴的交点,为什么分割比例不一样呢?因为二分法在最糟糕的情况下表现的比其他比例要好。
  Nelder-Mead 方法是更常用的方法,1965年提出。这个方法使用了单纯形的概念,是n维空间n+1个顶点的多边形。导数是带有解析信息的,不用导数必然会有代价。这里的代价就是这个方法可能收敛到一个非驻点(非驻点对于我们来说是没有意义的),除非求解的问题满足很强烈的要求。常见的改良算法是再利用梯度下降的信息。这种改良依然会遇到其他问题。
  二,有导数

  1. Newton's Method
  2. Steepest Method
  3. Conjugate Gradient Search(CG)

  这三个方法就更常见了,在解方程(组)中就开始使用。Newton–Raphson Method,需要我们提供求解的区间。类似于解方程时需要提供距离根足够近的初始点,这里提供的求解区间也需要足够的小。
  最速下降法,并不是指从山峰下降到谷底的速度最快,而是指每一步迈出,都是朝着坡度最大的方向下去,但是,没有长远的目光。牛顿法,每迈一部前,向后多看几步。所以,目光长远的,反而能以最短的路径下到谷底。wiki的图很形象。
  共轭梯度法通常和前面的梯度下降法比较,两个算法都针对对称正定矩阵。本方法一般用来解决无约束凸二次规划问题。这个问题稍微复杂一些。以后单独总结一下吧。
  scipy提供的算法以Nelder-Mead,Newton, CG,Trust Region方法为主。衍生方法可能是结合了其他的方法。单变量函数使用minimize_scalar(),多变量使用minimize()。使用方式参看链接[4],基本上就能够明白如何使用了。在这里,我觉得,如果不做算法研究,前期只需要了解这些数学概念的基础,在了解一下lib的使用方法与限制。等用到工作中后,如果发现有问题,再来深入。

 

  1. Numercial Optimization, 2nd Edition,Jorge Nocedal
  2. Numerical Analysis,  Timothy Sauer
  3. https://docs.scipy.org/doc/scipy/reference/optimize.html
  4. https://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html

2017-09-13  后记
  这段时间,把我学习数值分析时做的杂乱的笔记、练习整理了一下,贴了出来,再不整理就怕丢了。算是一个阶段性的总结了。完成了一个里程碑,还有下一个。我在大学期间没有好好学习这些东西,需要花费时间补回来--实在令人悲伤。转眼已毕业四年,我也能对自己问心无愧的说,这时间,没有白过。在未来还有很多困难,慢慢解决吧。

如果有任何意见,欢迎留言讨论。


[ 主页 ]
COMMENTS
POST A COMMENT

(optional)



(optional)