数值优化（1）——引入，线搜索：步长选取条件
大家好！
这是一个全新的系列，也是厦门大学数学科学学院第一年开设的课程。希望这一个全新的系列能够让大家（当然也包括我自己……）从一个系统的角度来看优化这一个主题。同样，这也是专栏内目前的第一个真正与我的主修专业——计算数学相关的系列笔记。
数值优化 (Numerical Optimization)在目前大数据时代的重要性不言而喻。无论是统计学，运筹学，应用数学等传统数学系的方向，还是机器学习，深度学习等人工智能的方向，你都可以看到数值优化的影子。比方说很多人都一定听说过梯度下降法，也叫最速下降法，我们知道它能够成为一个好的优化方法，是因为负梯度是函数等高线上最“陡”的方向。但是问题是，最速下降法真的最速吗？实现的时候要在这个方向走多少？要回答这个问题实际上并不是那么容易。同样的，优化的应用性很强，这一点所有人都没有异议。但是优化的理论性同样也很强，换句话说，会大量依赖传统数学系的数分高代，数值分析等课程的知识。因为没有理论，就像夜空中没有那最亮的星一样，无法指引你前行（我唱出来了2333）。
我之前在专栏和公众号里还有提到过凸优化 (Convex Optimization)的更新计划。凸优化是优化的一个真子集，因此它的重点自然会更关注一些“凸”的方法。我们先更新数值优化，其实也是因为这一门课更像是内功，有了内功，学习凸优化的工具，也会更加得心应手。因此虽然时间上凸优化不一定会在数值优化更新完才出现，但是在阅读顺序上，我们还是建议大家先阅读数值优化这一个系列。当然如果对于已经熟悉这些内容的同学来说，自然也就无所谓了。
这一门课我们主要参考的是教授的笔记，主要的参考书会在每一节的开头列出。这一个系列笔记也是教授个人研究成果的总结，因此需要事先提醒大家的是，本系列的课程内容***禁止任何形式的盗用***，具体是什么形式，法律条文里面都有哈。
那么我们开始吧。
Reference
- 课堂笔记，教授主页：https://math.fsu.edu/~whuang2/index.html
- Nocedal, Wright, Numerical Optimization (Second Edition)
目录
- 引入
- 向量求导举例
- 极值性质
- 收敛速度
- 线搜索方法引入
- 充分下降的步长选取条件
引入
优化这个词对于很多人来说并不陌生。直观理解就是将一个事情不断做得更好，比方说在阿里，老板和你说“你被优化了”，意思就是你的离开对于公司来说更好（因为阿里可能需要更好的人），所以意思就是你被开除了。万事万物，如果我们把所有统计学家都干掉，不承认这个世界上存在随机性的话，都可以写成一个函数。那么优化的目标，就是要找到一个函数的极值，这个思维也会贯穿这个系列。当然，数学上来写，我们就是要考虑这么一个问题。
接下来，我们给出一些与凸有关的定义。当然有的书上把它写成了下凸。
向量求导举例
相信你在引入中已经可以看出来，我们所关注的优化问题已经不再是一元微积分里关注的内容。而更多的关注多元实值函数。这样的话，我们对应的函数求导，求积分等等，都会变成向量求导和向量积分。也就是变成了求梯度和求海塞矩阵。也正是如此，我们需要重新回头来看我们学过的求导运算。这一部分的内容极端重要，在人工智能领域也有很多应用。
在此之前，我们自然需要一些梯度和海塞矩阵的定义。
我们给出一个实际的例子
我们相信各位同学还会对矩阵求导很感兴趣，但是我们这里不再关注那么多，绝大部分的优化问题通过向量求导的工具就已经足够解决。当然我们如果在具体的例子中需要依赖矩阵求导的工具，我们会再回头来介绍它。
极值性质
说到这里，我们需要提一句的是，除非函数是凸函数，否则任何一个优化方法都只能够求解局部最小值。也正是因为如此，求解全局最小值是一个异常困难的问题，也正是因为如此，优化方法才会如此火爆。
收敛速度
我们在之前介绍了很多性质，有的人可能会疑惑，既然我们有了这些定理，为什么我们还需要依赖优化的工具来求解函数极值呢？这是因为虽然我们可以说明
是一个函数极值的必要条件，但是，真正的函数的
这个方程好解吗？答案是否定的，甚至于说可不可解都不知道（也就是说没有解析解）。因此我们往往需要在数值意义上，通过迭代的方法得到我们的驻点 (stationary point)，也就是梯度为0的点。
顾名思义，收敛速度就是在考察一个优化方法的效率高低。我们要注意的是，每一个优化的方法，也就是用来求函数极值的方法，都有各自的优劣。其中一个因素就是速度，收敛的速度快或慢，自然会影响一个问题求解的效率高低。
实际问题中我们怎么考察收敛速度呢？一般会依赖如下定义。
这个定义考察的则是函数差值的根号，因此我们称它为根号收敛速度。
到此，我们铺垫好了优化的所有的基础理论，接下来我们就可以根据这些工具，来介绍不同的优化方法了。
线搜索方法引入
我们在https://zhuanlan.zhihu.com/p/60473090中简单介绍过线搜索方法，它既可以认为是一个单独的方法，也可以认为是一类方法。说它是一个优化方法，是因为它本身通过一些条件的检查，本身就是一个完整的成体系的迭代方法。说它是一类方法，是因为很多其它的方法需要以线搜索作为先行，通过其它的修改使得优化方法的性质发生改变。
这样说其实还是挺抽象的，我们思考一个更本质的问题：如何用迭代方法做优化？本质上，既然是迭代方法，那么自然是一步一步来的。我刚开始在一个初始点，然后我通过迭代，每一步都比上一步的函数值减小一些，直到函数值不能够再更小了，是不是就可以得到一个局部最小值点了？
充分下降的步长选取条件
在这一部分我们主要关注的是迭代方法的步长选取问题。换句话说，如何选取步长，才能使得迭代能够收敛到驻点？过大过小肯定都不行吧？要解决这个问题，事实上也需要很多铺垫，我们慢慢来看。
有了Proposition 8，我们就可以找下降方向了。这样就够了吗？好像依然是不行的。下面我们举一个例子来说明反例。
下面我们来图解一下这个条件。
那么有没有其它的条件呢？答案当然是肯定的。我们这里再给出两个常用的步长选取条件
还是一样，画几张图就都明白了。
下一张图对应的是弱Wolfe条件。
可以看出它还要求在每一步所选取的截取函数
的斜率不断的增大（想想为什么）。注意到我们刚开始要选取一个下降方向，也就是说我们的截取函数的斜率都一定是负的。那么添加这个条件，就是要求斜率不要震荡。
为什么不允许震荡呢？看一下下面这张图。
（这张图中黑线是f(x)，不是h(α)）。可以看出，它的斜率在正负之间不断的切换，这样就会导致迭代点不断的左右横跳（Example 3），这个时候每一次都会使得函数值下降，但是并无法收敛到驻点。
那么强Wolfe条件说明了什么呢？还是看一下下面这张图
可以看出，除了要求每一次斜率必须增大以外，我还不允许斜率增加的特别大（因为这样有可能会使得下降不够充分）。因此实际上就比弱Wolfe条件要“更强了”。
再多嘴一句，因为出现了很多图，所以一定要区分黑线究竟是h(α)还是f(x)。
好的，我们这一节先说到这里。
小结
本节我们主要介绍了优化的基本理论和工具，包括极值的性质和一些求微分的工具。有了这些工具之后我们就开始探讨优化中，有关步长的优化方法的条件。在下一节我们会看到，不同的步长选取方法之间各有千秋，但它们都可以导致全局收敛性，具体的证明并不容易，我们下一节再说。