公司动态

数值优化｜笔记整理（1）——引入，线搜索：步长选取条件

大家好！

这是一个全新的系列，也是厦门大学数学科学学院第一年开设的课程。希望这一个全新的系列能够让大家（当然也包括我自己……）从一个系统的角度来看优化这一个主题。同样，这也是专栏内目前的第一个真正与我的主修专业——计算数学相关的系列笔记。

数值优化 (Numerical Optimization)在目前大数据时代的重要性不言而喻。无论是统计学，运筹学，应用数学等传统数学系的方向，还是机器学习，深度学习等人工智能的方向，你都可以看到数值优化的影子。比方说很多人都一定听说过梯度下降法，也叫最速下降法，我们知道它能够成为一个好的优化方法，是因为负梯度是函数等高线上最“陡”的方向。但是问题是，最速下降法真的最速吗？实现的时候要在这个方向走多少？要回答这个问题实际上并不是那么容易。同样的，优化的应用性很强，这一点所有人都没有异议。但是优化的理论性同样也很强，换句话说，会大量依赖传统数学系的数分高代，数值分析等课程的知识。因为没有理论，就像夜空中没有那最亮的星一样，无法指引你前行（我唱出来了2333）。

我之前在专栏和公众号里还有提到过凸优化 (Convex Optimization)的更新计划。凸优化是优化的一个真子集，因此它的重点自然会更关注一些“凸”的方法。我们先更新数值优化，其实也是因为这一门课更像是内功，有了内功，学习凸优化的工具，也会更加得心应手。因此虽然时间上凸优化不一定会在数值优化更新完才出现，但是在阅读顺序上，我们还是建议大家先阅读数值优化这一个系列。当然如果对于已经熟悉这些内容的同学来说，自然也就无所谓了。

这一门课我们主要参考的是教授的笔记，主要的参考书会在每一节的开头列出。这一个系列笔记也是教授个人研究成果的总结，因此需要事先提醒大家的是，本系列的课程内容禁止任何形式的盗用，具体是什么形式，法律条文里面都有哈。

对了，这里恰个饭：如果小伙伴有需要更系统、完善的入门学习课程，推荐深蓝学院XX的专门课程：

机器人中的数值优化 - 深蓝学院 - 专注人工智能与自动驾驶的学习平台

那么我们开始吧。

课堂笔记，教授主页：

math.fsu.edu/~whuang2/index.html

Nocedal, Wright, Numerical Optimization (Second Edition)

引入
向量求导举例
极值性质
收敛速度
线搜索方法引入

充分下降的步长选取条件

优化这个词对于很多人来说并不陌生。直观理解就是将一个事情不断做得更好，比方说在阿里，老板和你说“你被优化了”，意思就是你的离开对于公司来说更好（因为阿里可能需要更好的人），所以意思就是你被开除了。万事万物，如果我们把所有统计学家都干掉，不承认这个世界上存在随机性的话，都可以写成一个函数。那么优化的目标，就是要找到一个函数的极值，这个思维也会贯穿这个系列。当然，数学上来写，我们就是要考虑这么一个问题。

$\\min_{x \\in \\mathcal F}f(x)$

其中 $\\mathcal F$ 为可行域， $f$ 为一个 $\\mathcal F \ o \\mathbb R$ 的实值函数。当然你求最大值也是可以的，因为本质上就是在求 $-f(x)$ 在定义域上的最小值。同时，为了方便起见，我们之后不会刻意的说“求函数在定义域上的最小值”，而直接说求函数的最小值。

你理解了这个，你就理解了优化。但是 $f$ 和 $\\mathcal F$ 有多少种可能？这个是很难说的。问题规模大吗？问题可解吗？解决方案的效率如何？有没有隐患？任何一个问题都能衍生出无数子问题出来。我们之后的每一个系列，其实目的都是解决一个特定的问题。而不同问题之间的比较，相信也会让大家对不同的方法和优化的理论有更深的理解。

既然我们提到了最小值，那么自然我们要关注一些更细节的定义

Definition 1: Global Minimizer
如果对任意的 $x \\in \\mathcal F$ ，都有 $f(x^*) \\le f(x), x^* \\in \\mathcal F$ 成立，那么 $x^*$ 就是函数的全局最小值。

非常直观明了。同时，为了方便起见，我们说函数“取到最小值”，就是指函数取到全局最小值。

Definition 2: (Strict) Local Minimizer
如果对任意的 $x \\in \\mathcal F$ ，都有 $f(x^*) \\le f(x), x^* \\in \\mathcal N_{x ^ *}\\subset \\mathcal F$ 成立，那么 $x^*$ 就是函数的局部最小值。如果严格不取等，那么就称它为严格局部最小值。这里 $\\mathcal N_{x ^*}$ 称为 $x^*$ 的邻域。

在数分一中我们学过，邻域就是包含它的一个无穷小量的球，也就是 $B(x^*, \\epsilon)$ 。换句话说，空间中任何一个与 $x^*$ 距离小于 $\\epsilon$ （小于等于也是可以的，这个细节不重要）的点，都在它的邻域，这里的 $\\epsilon$ 充分小（我喜欢将充分小理解为，令 $\\epsilon \ o 0$ ，对于我的理论不会有破坏）。

还有一个概念可能比较陌生。我们也写在这里

Definition 3: Isolated Local Minimizer
如果 $x^*$ 是 $f(x)$ 的唯一局部最小值，则称它是孤立局部最小值。

一个很好的区分这两个概念的例子是这么一个函数

$f(x)=\\begin{cases}-x & x \\le 0 \\\\ 1 & x \\ge 1^- / x \ e \\frac1k \\\\ x & others\\end{cases}$

这里的 $1^-$ 是指它的左极限。这个函数不难看出，在 $x=0$ 的时候取到最小值，它也是局部最小值，也是严格局部最小值。但是它并不是孤立局部最小值，因为 $f(\\frac1k)=\\frac1k, \\forall k \\in N^+$ ，这就相当于说，无论我这个邻域球取得多小，都会涵盖住 $\\frac 1k$ 这个点（有理数的稠密性），而 $\\frac 1k$ 也是局部最小值（这里有一个容易混的地方。根据定义，它是相对于 $B(\\frac1k, \\epsilon)$ 的局部最小值，但是如果相对 $B(0, \\epsilon)$ ，它并不是最小值），这就说明了我们的结论。当然，这个例子也说明了，得到局部最小值和得到全局最小值是两码事。

接下来，我们给出一些与凸有关的定义。当然有的书上把它写成了下凸。

Definition 4: Convex Set
对于集合 $\\mathcal S$ 以及集合内的任意两点 $x, y$ ，如果对任意的 $\\alpha \\in[0,1]$ ，都有 $ax + (1-a)y \\in \\mathcal{S}$ ，那就称集合是一个凸集。

下面这张图就很好的解释了凸的含义。右边的这个集合就不是凸集，因为它“凹”下去了，所以线段中间的部分就不属于那个集合了。

Definition 5: Convex Function
如果函数 $f: \\mathbb{R}^n \ o \\mathbb R$ 的定义域是一个凸集并且满足对任意 $\\alpha \\in[0, 1]$ ，有 $f(\\alpha x + (1-\\alpha )y) \\le \\alpha f(x) + (1-\\alpha)f(y)$ ，则称它是一个凸函数。

通过这个定义不难验证，对应的 $-f(x)$ 就是一个凹函数 (concave function)，也就是很多书上写的上凸函数。

相信你在引入中已经可以看出来，我们所关注的优化问题已经不再是一元微积分里关注的内容。而更多的关注多元实值函数。这样的话，我们对应的函数求导，求积分等等，都会变成向量求导和向量积分。也就是变成了求梯度和求海塞矩阵。也正是如此，我们需要重新回头来看我们学过的求导运算。这一部分的内容极端重要，在人工智能领域也有很多应用。

在此之前，我们自然需要一些梯度和海塞矩阵的定义。

Definition 6: Gradient
$f \\in C^1$ , 定义 $f(x)$ 的梯度为一个 $n$ 维向量，且对应的第 $i$ 个分量为 $\\frac{\\partial f}{\\partial \\xi_i}(x)$
Definition 7: Hessian
$f \\in C^2$ , 定义 $f(x)$ 的海塞矩阵为一个 $n \ imes n$ 维的矩阵，且对应的第 $(i, j)$ 个分量为 $\\frac{\\partial ^2 f}{\\partial \\xi_i \\partial \\xi_j}(x)$

根据这个定义，我们自然想到，如果我能够根据每一个分量求导，就能够求出梯度和海塞矩阵。这里我们给一个简单的例子。

Example 1
考虑 $f(x)=x^Tx$ ， $x \\in \\mathbb R^n$ ，求 $\ abla f(x)$

采用土的方法，将它的表达式拆出来，然后分量求导即可。注意到 $x^T x=\\sum_{i=1}^n x_i^2$ ，所以可以得到 $\\frac{\\partial f}{\\partial x_i}=2x_i$ ，因此拼在一起，就可以得到 $\ abla f(x)=2x$ 。

但是这样做，实际上是很低效的，我们解一些简单的算例自然没有问题，但是实际问题上，我们这样做很多时候会破坏多元函数的一个整体性。因此我们通过介绍一些简单的性质来简化我们的运算。

Proposition 1:
设 $f: \\mathbb R^n \ o \\mathbb R$ ，且 $f \\in C^1$ ，那么 $D f(x)[v]=v^T \ abla f(x)$ ，这里左边指的是方向导数 $\\frac{\\partial f}{\\partial v}$ 。

数分三中介绍过这个式子，其实就是方向导数的公式。

Proposition 2:
设 $f: \\mathbb R^n \ o \\mathbb R$ ，且 $f \\in C^2$ ，那么 $D (\ abla f(x))[v]=\ abla^2 f(x) \\cdot v$ ，这里左边指的是方向导数 $\\frac{\\partial \ abla f}{\\partial v}$ 。

这里的话只需要注意，每一个梯度的分量也都是一个多元函数即可。

有了这两个式子，结合一下方向导数最本质的极限定义 $\\frac{\\partial f(x)}{\\partial v}=\\lim _{t \ o 0}\\frac{f(x + tv) - f(x)}{t}$ ，我们就不难得到我们的结论。

我们给出一个实际的例子

Example 2: Ridge Regression
考虑 $f(\\beta)=(Y - X \\beta)^T(Y - X\\beta) + \\lambda \\beta^T \\beta$ ， $X \\in \\mathbb R^{n \ imes p}$ ， $Y, \\beta \\in \\mathbb R^n$ ，求梯度与海塞矩阵。

熟悉的人会知道，这个就是岭回归的目标函数的一种形式。

有一部分 $\\lambda \\beta^T \\beta$ 我们已经求过梯度了，为 $2\\lambda \\beta$ （注意 $\\lambda \\in \\mathbb R$ 为常数），那么剩下的部分我们设为 $g(\\beta)$ ，先根据Proposition 1，我们有

$D g(\\beta)[v]=v^T \ abla g(\\beta)=\\lim_{t \ o 0}\\frac{g(\\beta + tv) -g(\\beta)}{t}$

事实上，设 $Z=Y - X \\beta$ ，不难求得分子为

$\\begin{aligned}g(\\beta + tv) -g(\\beta) &=(Z - t X v)^T (Z - t Xv) - Z ^T Z \\\\ &=-t Z ^ TXv - tv^T X^T Z + t^2 (Xv)^T Xv \\end{aligned}\\\\$

这一系列式子中我们可以忽略最后一项（因为 $t \ o 0$ 的时候，最后一项为一个小量）。所以可以得到

$v^T \ abla g(\\beta)=-Z^T X v - v^T X^T Z=-2v^TX^TZ$

这是因为 $Z^TXv$ 根据题目条件，容易发现是一个数，因此求转置不会改变值。

因为我们的方向 $v$ 是任意取的，所以根据左右的对应，就可以得到我们的结论 $\ abla g(\\beta)=-2X^TZ=-2X^T(Y-X\\beta)$ ，所以综合在一起，我们就可以得到

$\ abla f(\\beta)=-2X^T (Y -X\\beta)+2\\lambda \\beta$

接下来，我们来计算海塞矩阵。也很容易，根据Proposition 2即可得到

$D (\ abla f(\\beta))[v]=\\lim_{t \ o 0}\\frac{\ abla f(\\beta + tv) - \ abla f(\\beta)}{t}=(2X^T X + 2\\lambda I) \\cdot v$

（不要忘记写上单位阵），同样的根据 $v$ 的任意性，就可以得到

$\ abla ^2 f(x)=2(X^T X + \\lambda I)$

因此我们就证明完了结论。

学过岭回归的同学就知道，这里如果我们要求函数的最小值，那么令 $\ abla f(\\beta)=0$ ，可以得到 $\\hat \\beta=(X^T X + \\lambda I)^{-1}X^T Y$ ，而岭回归的情况下， $X^TX + \\lambda I$ 是正定的，因此运算合法，并且 $\ abla^2f(x)$ 处处正定，也就得到了函数的凸性和 $f(\\hat \\beta)$ 确实是全局最小值的结论。

我们相信各位同学还会对矩阵求导很感兴趣，但是我们这里不再关注那么多，绝大部分的优化问题通过向量求导的工具就已经足够解决。当然我们如果在具体的例子中需要依赖矩阵求导的工具，我们会再回头来介绍它。

显然，如果要求极值，如果我们没有好的工具，也无从下手。事实上我们在上一部分的Example 2已经使用过，也就是说我们通过 $\ abla f(x)=0$ 来找函数的极小值。但是这为什么是对的呢？多元函数的情况和一元函数类似吗？这就是我们要关心的部分。

在介绍相关性质之前我们还是先需要一些其它的结论。

Proposition 3: Taylor Expansion
设 $f: \\mathbb R^n \ o \\mathbb R$ ， $f \\in C^2$ ，那么存在 $\ au_1, \ au_2, \ au_3 \\in (0, 1)$ ，使得
(1) $f(x + p)=f(x) + \ abla f(x+\ au_1 p)^T p$
(2) $f(x+p)=f(x) + \ abla f(x)^T p + \\frac 12 p^T \ abla ^2 f(x + \ au_2 p) p$
(3) $\ abla f(x+p)=\ abla f(x) + \\int_0 ^1 \ abla ^2 f(x + \ au_3 p)p d\ au_3$

这事实上也就是多元泰勒展开的定义。刚开始可能大家不太熟悉，但是我们会反复用到它们，所以也不用担心。

同样，为了方便起见，我们不再说明 $f : \\mathbb R^n \ o \\mathbb R$ 这个事实。

好的，接下来我们会介绍一系列极值性质。

Proposition 4: First Order Necessary Condition
设 $f \\in C^1$ ，若 $x^*$ 是一个局部最小值，那么 $\ abla f(x^*)=0$

我们证明一下这个结论，联系一下一元微积分里面的结论，事实上导函数的直观意义就是斜率。对于一个最小值点，它的导函数为0也是直观上显然的。那么在梯度的意义下，如果我们要证明这个结论，只需要说明，若 $\ abla f(x^*) \ e 0$ ，这个点就不是极小值点就好，也就是说我们要说明还会存在更小的。而考察更小的可能，最稳妥的自然是负梯度方向，这也就是我们证明的思路。

如果说 $\ abla f(x^*) \ e 0$ ，那么考察一下负梯度方向 $p=- \ abla f(x^*)$ ，就可以得到 $p^T \ abla f(x^*) < 0$ （想想为什么），根据我们导函数的连续性可以推出梯度的连续性，也就是说存在一个较小的 $T$ ，使得

$p^T \ abla f(x^* + \ au p) < 0, \\forall \ au \\in (0 , T)$

接下来我们考虑在什么式子上我们会用到这个结论？事实上就是我们Proposition 3的第一个式子。注意到对于任意的 $\\mu \\in[0, T]$ ，我们有

$f(x^* + \\mu p)=f(x^*) + \ abla f(x^* + \ au p)^T \\cdot \\mu p=f(x^*) + \\mu p^T \ abla f(x^* + \ au p) < f(x^*) \\\\$

这里要注意我们的性质中， $\ au$ 是任意的。因此我们就证明了结论。

仅仅这一个性质来说明极小值还不够，就像我们在Example 2中用了海塞矩阵一样，我们在这里也要考虑海塞矩阵带给我们的信息。

Proposition 5: Second Order Necessary Condition
设 $f \\in C^2$ ，若 $x^*$ 是一个局部最小值，那么 $\ abla^2f(x^*) \\ge 0$

这里要注意，如果说矩阵 $\\ge 0$ ，就代表半正定。

完全相同的思路，如果说海塞矩阵在 $x^*$ 处非半正定，那就说明存在一个方向 $p \\in \\mathbb R^n$ ，使得 $p^T \ abla^2 f(x^*) p < 0$ ，考虑一下Proposition 3的第二个式子并结合 $\ abla f(x^*)=0$ 即可，这里我们略去证明。

接下来我们加入函数的凸性，再介绍两个极值性质。

Proposition 6:
若 $f$ 是凸函数，那么局部最小值即为全局最小值。

还是依然考虑使用反证法，也就是说如果设 $x^*$ 为局部最小值， $y^*$ 为全局最小值，并且 $f(y^*)=f(x^*)$ ，那么根据凸函数的性质，对于任意的 $\\lambda \\in[0,1]$ ，有

$f(\\lambda y^* + (1-\\lambda)x^*) \\le \\lambda f(y^*) + (1-\\lambda) f(x^*) < f(x^*)$

我们稍作修改，可以得到 $f(\\lambda(y^*-x^*) + x^*) < f(x^*)$ ，这说明什么？说明 $y^* - x^*$ 是一个下降方向。为什么这样就不行了呢？这是因为，局部最小值是不允许出现下降方向的，否则会违背定义。因此结论成立。

Proposition 7:
若 $f$ 是凸函数， $f \\in C^1$ ，那么任何一个驻点都是全局最小值点。

这个直观上也很显然，也就是说，如果一个点不是全局最小值，那么我们只要证明它不是驻点即可（相当于使用了逆否条件）。

假如说点 $x^*$ 不是全局最小值点， $y^*$ 是全局最小值点，那么就有 $f(y^*) < f(x^*)$ 。使用和Proposition 6同样的方法，不难得到结论 $f(\\lambda(y^*-x^*) + x^*) < f(x^*)$ ，也就是说 $y^* - x^*$ 是 $x^*$ 上的一个下降方向，也就是说这个点不是一个局部最小值点，那么自然不可能是驻点，这就得到结论了。

这里要补充说明一点的是，这个性质的证明还可以考虑使用Proposition 1，得到

$\\lim_{\\lambda \ o 0}\\frac{f(x^* + \\lambda (y^* - x ^*)) - f(x^*)}{\\lambda}=(y^* - x^*)^T \ abla f(x^*) < 0$

所以可以得到 $\ abla f(x^*) \ e 0$ 。但是我们没有在Proposition 6中使用，这是因为我们没有 $f \\in C^1$ 的条件，因此梯度不一定存在。

我们在证明中使用了一个概念叫下降方向，虽然直观上非常清晰，但我们还是需要给一下它的严格定义。

Definition 8: Descent Direction
设 $f \\in C^1$ ， $p \\in \\mathbb R^n$ ，如果对于充分小的 $\\alpha$ ，有 $f(x+\\alpha p) < f(x)$ ，则称 $p$ 是一个下降方向。

说到这里，我们需要提一句的是，除非函数是凸函数，否则任何一个优化方法都只能够求解局部最小值。也正是因为如此，求解全局最小值是一个异常困难的问题，也正是因为如此，优化方法才会如此火爆。

我们在之前介绍了很多性质，有的人可能会疑惑，既然我们有了这些定理，为什么我们还需要依赖优化的工具来求解函数极值呢？这是因为虽然我们可以说明 $\ abla f(x^*)=0$ 是一个函数极值的必要条件，但是，真正的函数的 $\ abla f(x^*)=0$ 这个方程好解吗？答案是否定的，甚至于说可不可解都不知道（也就是说没有解析解）。因此我们往往需要在数值意义上，通过迭代的方法得到我们的驻点 (stationary point)，也就是梯度为0的点。

顾名思义，收敛速度就是在考察一个优化方法的效率高低。我们要注意的是，每一个优化的方法，也就是用来求函数极值的方法，都有各自的优劣。其中一个因素就是速度，收敛的速度快或慢，自然会影响一个问题求解的效率高低。

实际问题中我们怎么考察收敛速度呢？一般会依赖如下定义。

Definition 9: Q-rate of convergence
设自变量第 $k$ 步的迭代点为 $x_k$ ，且 $x_k \ o x^*$ ，那么如果
(1) $\\frac{\\|x_{k+1}- x^*\\|}{\\|x_k - x^*\\|}\ o 1$ ，则称为次线性收敛速度。
(2) $\\frac{\\|x_{k+1}- x^*\\|}{\\|x_k - x^*\\|}< \\delta < 1$ ，则称为线性收敛速度。
(3) $\\frac{\\|x_{k+1}- x^*\\|}{\\|x_k - x^*\\|^p}< C$ , $p > 1$ ，则称为超线性收敛速度。
(4) $\\frac{\\|x_{k+1}- x^*\\|}{\\|x_k - x^*\\|^p}< C$ , $p=2$ ，则称为二次收敛速度。

可以看出，这个定义本质上是考察相邻两点的差值的商，因此我们称它为商收敛速度。

Definition 10: R-rate of convergence
设 $f(x_k) \ o f(x^*), k \ o \\infty$ ，且 $f(x_k)-f(x^*) \\le \\epsilon_k$ ，那么如果
(1) $\\sqrt[k]{\\epsilon_k}\ o 1$ ，则称为次线性收敛速度。
(2) $\\epsilon_k=O(\\frac 1k)$ ，则称为 $O(\\frac1k)$ 收敛速度。
(3) $\\sqrt[k]{\\epsilon_k}< \\delta < 1$ ，则称为线性收敛速度。
(4) $\\sqrt[k]{\\epsilon_k}=0$ ，则称为超线性收敛速度。

这个定义考察的则是函数差值的根号，因此我们称它为根号收敛速度。

到此，我们铺垫好了优化的所有的基础理论，接下来我们就可以根据这些工具，来介绍不同的优化方法了。

我们在

学弱猹：矩阵流形优化|笔记整理（4）——拉回，优化计算实例，指数映射

中简单介绍过线搜索方法，它既可以认为是一个单独的方法，也可以认为是一类方法。说它是一个优化方法，是因为它本身通过一些条件的检查，本身就是一个完整的成体系的迭代方法。说它是一类方法，是因为很多其它的方法需要以线搜索作为先行，通过其它的修改使得优化方法的性质发生改变。

这样说其实还是挺抽象的，我们思考一个更本质的问题：如何用迭代方法做优化？本质上，既然是迭代方法，那么自然是一步一步来的。我刚开始在一个初始点，然后我通过迭代，每一步都比上一步的函数值减小一些，直到函数值不能够再更小了，是不是就可以得到一个局部最小值点了？

假如说我们现在在一个点 $x$ 上，接下来我们考察点 $x+\\alpha p$ ，我们的目标自然是希望

$f(x + \\alpha p) < f(x)$

也就是要寻找下降方向。这里 $\\alpha$ 为步长，而 $p$ 为搜索方向。你可以看出，任何一个依赖线搜索的方法，本质上都是关心这两个元素。要不就是希望找到一个合适的步长，要不就是希望找到一个合适的方向。比方说如果我们选取好搜索方向 $p=-\ abla f(x)$ ，那么只要考虑步长的限制条件就好，这样得到的方法就是我们已经很熟悉的最速下降法。

很显然，要寻找下降方向，光一个式子是不够的，你没有任何其它分析的工具自然不行，因此我们还需要补一个结论。

Proposition 8:
设 $f \\in C^1$ , $p \\in \\mathbb R^n$ ，如果
$-p^T \ abla f(x_k)=\\|p \\|_2 \\|\ abla f(x_k)\\|_2 \\cos \ heta_k > 0$ 则 $p$ 是一个在 $x$ 点处的下降方向。

这个性质的证明和之前证明 $\ abla f(x)=0$ 的方法一模一样，我们不再给出证明的细节。但是通过这个，其实你可以看出来，并不是一定要 $p=-\ abla f(x)$ 才是下降方向，只需要搜索方向 $p$ 与负梯度 $-\ abla f(x)$ 成一个锐角即可。

在这一部分我们主要关注的是迭代方法的步长选取问题。换句话说，如何选取步长，才能使得迭代能够收敛到驻点？过大过小肯定都不行吧？要解决这个问题，事实上也需要很多铺垫，我们慢慢来看。

有了Proposition 8，我们就可以找下降方向了。这样就够了吗？好像依然是不行的。下面我们举一个例子来说明反例。

Example 3:
考虑函数 $f(x)=\\frac12 x^2$ ，并设迭代初值 $x_0=1$ ，使用最速下降法并设置步长为 $\\alpha_k=2 - \\frac 1{|x_k| \ imes 2^{k+2}}$ ，问迭代是否下降？迭代是否收敛至驻点？

这里要注意的是，使用最速下降法就是给定了每一步的方向为当前点的负梯度。那么这种情况下，相当于自变量迭代的公式为

$x_{k+1}=x_k - \\alpha_k \ abla f(x_k)=-x_k(1 - \\frac 1{|x_k| \ imes 2^{k+2}})$

这样的话，容易写出这个数列的通项公式为

$x_{2k}=\\frac12 + \\frac1{2^{2k + 1}}, x_{2k+ 1}=-\\frac 12 - \\frac 1{2^{2k + 2}}$

代入计算函数值会发现每一步确实满足函数值在不断下降，但是数列的极限均为 $\\frac 12$ ，换句话说就是迭代并没有收敛到驻点。

也许有些人会发现这个序列的问题所在了。正如级数求和有收敛和发散一说，函数不断的下降并不能导致下降的量的和足够的大。也就是说，我们需要一些条件，来保证我们的函数值真的能够充分下降。

首先我们介绍一下Armijo条件。

Definition 11: Armijo Condition
设 $h(\\alpha)=f(x + \\alpha p)$ ，且设 $l(\\alpha)=h(0) + c_1 \\alpha h'(0)$ ，其中 $c_1 \\in (0, 1)$ 。如果 $h(\\alpha) \\le l(\\alpha)$ ，则 $\\alpha$ 满足Armijo条件。

下面我们来图解一下这个条件。

（注意黑线是 $h(\\alpha)$ ，不是 $f(x)$ ，也就是说如果 $h(\\alpha)$ 一般是一个先减再增的函数，不然就不是下降方向了）。可以看出，蓝线就是在 $h(0)$ 处画的切线，而红线就是我们的 $l(\\alpha)$ ，那么根据Armijo条件，在红线下方的黑线那一部分就是满足条件的 $\\alpha$ 。从直观上来看，因为它们在一条直线的下方，所以下降的程度比线性函数要快，因此可以认为是充分下降。

但是很遗憾，这个条件依然不足够用来作为满足全局收敛性（就是迭代收敛到全局最小值）的保证。我们同样给一个反例。

Example 4:
考虑与Example 3相同的函数和初始点，并考虑最速下降法。设步长 $\\alpha_k=\\frac1{x_k 2 ^{k+2}}$ ，判断迭代是否满足Armijo条件，并判断迭代是否收敛至驻点？

在这里，我们同样的步骤可以得到数列迭代的通项公式为 $x_{k+1}=\\frac 12 + \\frac 1{2^{k+2}}$ ，可以看出，这个时候，取 $c_1=0.5$ ，就能够得到

$h(\\frac 1{x_k2^{k+2}})=f(x_k - \\frac 1{2^{k+2}})$ , $l(\\frac 1{x_k 2^{k+2}})=f(x_k) -\\frac{x_k}{2^{k+3}}$

（注意到 $h'(0)=p^T \ abla f(x)$ ，其中 $x$ 是当前的迭代点）。细节上不难验证满足充分下降的条件，但是你观察一下通项公式就知道数列的极限依然是 $\\frac 12$ ，所以依然不会收敛到驻点。

你可以看出来这个反例的产生源自于我们的步长选取过于保守。也就是说，我们的步长选取应该要大胆一些。这个思路就引导我们去考虑如下的Armijo-Goldstein条件。

Definition 12: Armijo Goldstein Condition
若步长 $\\alpha$ 满足 $h(\\alpha) \\le l(\\alpha)=l(\\alpha)=h(0) + c_1 \\alpha h'(0)$ ，并且 $\\alpha$ 是集合 $\\{t^{(i)}: t^{(i)}\\in[\ au_1 t^{(i-1)}, \ au_2 t^{(i-1)}], t^{(0)}=1\\}$ 中最大的那个， $c_1 \\in (0, 1)$ 任意给定，且 $0 < \ au_1 \\le \ au_2< 1$ ，则称步长满足A-G条件。

在解释这个条件之前要多提一句这里“任意给定”的意思。这里的意思是我们的 $c_1$ 可以随便取，只要给定这个 $c_1$ 之后，条件满足就可以。换句话说，假如说 $c_1=0.5$ ，你选取了一个步长满足这个条件，那就够了。

下面我们解释一下这个条件。也就是说，我们的步长刚开始会设置为 $t_0=1$ ，然后我们第二步的选取，就在 $[\ au_1, \ au_2]$ 中随便取一个，设为 $t_1$ ，然后第三步就在 $[\ au_1t_1, \ au_2 t_1]$ 中随便取一个，设为 $t_2$ ，以此类推就可以得到这样的序列。因为我们要的是集合中最大的那一个，所以我们事实上就是不断的尝试，从刚开始的步长开始，每一次都不断的缩小步长，直到步长满足A-G条件，我们就选取这个步长作为 $\\alpha$ 并开始迭代。

有一种简易的方案，就是设 $\ au_1=\ au_2$ ，这个时候相当于给定了一个系数 $\\rho < 1$ ，假如说我们的步长 $\\alpha$ 太大了，导致无法满足A-G条件中的不等式，那么直接考虑 $\\alpha^*=\\rho \\alpha$ 即可。这样的话，一方面，我们一开始的探索就会很大胆，另一方面我们也不会过于保守，因为只要我们达到条件，就会采用这个步长。具体的算法过程如下图

那么有没有其它的条件呢？答案当然是肯定的。我们这里再给出两个常用的步长选取条件

Definition 13: Weak Wolfe Conditions
如果步长 $\\alpha$ 满足
$\\begin{aligned}& h(\\alpha) \\le l(\\alpha)=h(0) + c_1 \\alpha h'(0)\\\\ & h'(\\alpha) \\ge c_2 h'(0) \\end{aligned}\\\\$ 且 $0 < c_1 < c_2 < 1$ 任意给定。则称它满足弱Wolfe条件。

还有一个条件与之对应

Definition 14: Strong Wolfe Conditions
如果步长 $\\alpha$ 满足
$\\begin{aligned}& h(\\alpha) \\le l(\\alpha)=h(0) + c_1 \\alpha h'(0)\\\\& |h'(\\alpha)| \\le c_2| h'(0)|\\end{aligned}\\\\$ 且 $0 < c_1 < c_2 < 1$ 任意给定。则称它满足强Wolfe条件。