【最优化(三)】无约束可微优化问题一阶算法建立
前面第一节笔记中已经简单的介绍了，最优化问题的定义，最优化问题的分类，以及全局最优，局部最优等基本的概念。然后在第二节笔记中我们又展示了零阶优化算法求解高维优化问题的缺点，接下来本次笔记就从简单的无约束可微优化问题开始，并且采用一阶优化算法来求解无约束可微优化问题。1 从几何角度构建连续优化问题算法架构
我们寻找最优解的过程类似于一个从起始点开始走到最优点的过程，如下图所示：
如果我们把这个走到的过程类比为你从一个地方走到另外一个地方的过程的话，这里边存在三个至关重要的因素能保证你走到最终的目的地：
[*]每一步走的方向（搜索方向）
[*]第二个是每一步走多远（搜索步长）
[*]第三个是何时停下来（最优性条件）
我们把这三个关键部分构成一个迭代算法的基本框架如下所示：
Step 1: 给定一个初始点 x_0 \in R^n, k:=0
Step 2: 若在当前的点 x_k 满足终止条件，则停止算法搜索并输出最优解，否则进入下一步
Step 3：确定 f(x) 在点 x_k 处的搜索方向 d_k
Step 4: 确定步长 \alpha_k，使 f(x_k + \alpha_k d_k) 比 f(x_k) 更好
Step 5: x_{k+1}:=x_k+\alpha _kd_k，k:=k+1，跳转到 Step 2
在上述算法框架中 Step 2 对应终止条件，Step 3 对应搜索方向，Step 4 对应搜索步长。 接下来我们第三章就介绍搜索方向如何获得，第四章就介绍搜索步长如何获得，第五章就介绍终止条件，在第六章就是把前面几部分内容融合在一起构成一个整体的算法，就是最速下降法。
2 搜索方向
因为我们的原始问题是求解函数 f(x) 的极小值，自然而然我们会想到，每次在迭代的时候如果能保证让迭代之后的 f(x) 朝着下降的方向前进的话，那么我们就会越来越接近极小值点。接下来我们就借助微积分的知识来定义出下降方向。
2.1 下降方向的定义
对于可微函数 f，在某一点 x_k\in R^n处，如果存在存在向量满足：
\nabla f\left( x_k \right) ^Td_k<0 \quad (3.1) \\
那么称 d_k 为函数 f 在点 x_k 处的一个下降方向。
从上述下降方向的定义，容易验证：如果函数 f 在点 x_k 处存在一个下降方向 d，那么对于任意的 T>0，存在 t\in (0,T]，使得
f(x_k+td_k) <f(x_k) \quad (3.2) \\
证明上述命题其实就是一阶泰勒展开：
f\left( x_k+td_k \right) - f\left( x_k \right)= t\nabla f\left( x_k \right) ^Td_k+o\left( \lVert td_k \rVert \right)\quad (3.3) \\
从上述式子可知：由于 \nabla f\left( x_k \right) ^Td_k<0，所以当 t\rightarrow 0 时有
f\left( x_k+td_k \right) -f\left( x_k \right) <0 \quad (3.4) \\
至此(3.2)的命题得到证明。
从式(3.4)可以看出沿着下降方向进行搜索确实是可以让目标函数逐渐发生改进。从几何的观点出发内积小于0表示的含义就是两个向量直接的夹角是一个钝角，那么进一步等价表示为 d_k 和 -\nabla f\left( x_k \right) 之间的夹角是一个锐角。也就是说只要和负梯度方向呈夹角是一个锐角的那么均为下降方向。这就是式(3.4)背后的几何含义。
2.2 负梯度方向是一个下降方向？
那么具体怎么才能得到下降方向呢？我们不妨令
d_k=-\nabla f\left( x_k \right)\\
带入到(3.1)式可得：
-\nabla f\left( x_k \right) ^Td_k=-\nabla f\left( x_k \right) ^T\nabla f\left( x_k \right) =-\lVert \nabla f\left( x_k \right) \rVert _{2}^{2} \quad (3.5) \\
从上式中我们不难发现 若 \nabla f\left( x_k \right) \ne 0，则上式必然满足-\nabla f\left( x_k \right) ^Td_k=-\nabla f\left( x_k \right) ^T\nabla f\left( x_k \right) <0也就是说当 \nabla f\left( x_k \right) \ne 0，总是可以保证 -\nabla f\left( x_k \right)是一个下降方向。
3 搜索步长
在确定了搜索方向之后，我们接下来需要确定的就是搜索步长，那么搜索步长也是要保证按照这个步长去走的话依然保证目标函数是下降的即可，把上面的表述转化为数学表达式为：
f\left( x_k+t_kd_k \right) <f\left( x_k \right) \quad (4.1)
在上式中要注意的是此时搜索方向 d 已经是确定的，而我们需要找到一个 t_k 满足式(4.1) 的条件。
确定步长方法1：精确线搜索法
其中一种方法就是采用精确线搜索法，通过求解如下优化问题来得到步长 t_k
\underset{t_k\ge 0}{\min}f\left( x_k+t_kd_k \right) \quad (4.2) \\
显然满足式(4.2)的解必然满足式(4.1)。
精确线搜索的所构成的优化问题是一维优化问题，在上一节笔记中我们曾介绍过用均匀网格法来求解一维优化问题是可行的。所以求解(4.2)的时候我们可以直接采用均匀网格法来做，设 t_k\in \left[ 0,U \right]，然后从中均匀选取 M 个点选出最小的即可，具体过程可以参考上一节笔记中的均匀网格法。
确定步长方法2：Armijo准则
另外一种方法就是采用非精确线搜索法，其中 Armijo 准则就是一种确定步长 t_k的方式，如下所示：
f\left( x_k+t_kd_k \right) \le f\left( x_k \right) +\rho t_k\nabla f\left( x_k \right) ^Td_k,\ \ \rho \in \left( 0,1 \right) \quad (4.3) \\
在式(4.3)中 \rho是一个参数。不等式的右侧是一个关于步长t_k的线性函数。由于d是一个下降方向，所以\nabla f\left( x_k \right) ^Td<0, 只要保证 \alpha 取得不是很小，那么总是可以保证新的函数点 f\left( x_k+t_kd_k \right) 对比之前的函数点 f(x_k)不仅仅是下降，而且是有一定幅度的下降，这个幅度就是 式(4.3) 右端的第二项 \rho t_k\nabla f\left( x_k \right) ^Td_k
这里我们会产生一个问题就是 满足式(4.3)条件的步长 t_k 是否总是存在？
还是采用泰勒展开来证明上述命题：
f\left( x_k+t_kd_k \right)= f\left( x_k \right) +t_k\nabla f\left( x_k \right) ^Td_k+o\left( \lVert t_kd_k \rVert \right)\quad (4.4) \\
由于 \nabla f\left( x_k \right) ^Td_k<0 并且 \rho \in \left( 0,1 \right), 所以当 t_k\rightarrow 0 时有
f\left( x_k+t_kd_k \right) \le f\left( x_k \right) +\rho t_k\nabla f\left( x_k \right) ^Td_k\quad (4.5) \\
只要 t_k 充分接近0，则总可以找到让式(4.3)成立的 t_k>0
4 终止准则
如前所述我们已经可以得到搜索方向（往哪里走）和搜索步长（走多少）两个最重要的组成部分。接下来很重要的一个问题就是什么时候停下来。显然停下来的地方是全局最优或者局部最优那就是我们所希望的。基于此我们给出优化问题(1.1)的局部最优解的充分和必要条件，以便于我们设计出合适的终止准则。
4.1 一阶必要条件
设目标函数 f(x) 可微并且其导函数连续，x^* 为 f(x) 的一个局部极小点，则必有
\nabla f\left( x^* \right) =0 \quad (5.1) \\
证明：
假定 \nabla f\left( x^* \right) \ne 0，则存在 d \in R^n，使得 d^T\nabla f\left( x^* \right) <0,，比如总可以取 d=-\nabla f\left( x^* \right) 让上式成立。 同时由于 \nabla f\left( x \right) 是一个连续函数，存在 \delta >0，使得如下表达式成立：
d^T\nabla f\left( x^*+\alpha d \right) <0,\ \alpha \in \left( 0,\delta \right]\\
由微分中值定理可知，对任意的 \alpha _1\in \left( 0,\delta \right]，存在 \alpha \in \left( 0,\alpha _1 \right)，使得
f\left( x^*+\alpha _1d \right) =f\left( x^* \right) +\alpha _1d^T\nabla f\left( x^*+\alpha d \right)\\
上式中等号右端第二项是小于0的，所以有 f\left( x^*+\alpha _1d \right) < f\left( x^* \right)，由此可知 x^* 不是 f(x) 的局部极小点。与假设矛盾，故命题得证。
证毕
4.2 二阶必要条件
设 f(x) 二阶可导，并且其二阶导函数是连续的，x^* 是 f(x)的一个局部极小点，则 \nabla ^2f\left( x^* \right) 半正定。
证明：
采用反证法，假定在 x^* 处，存在 d\in R^n，使得 d^T\nabla ^2f\left( x^* \right) d<0，由 \nabla ^2f\left( x \right) 的连续性可知，存在 \delta >0，使得如下表达式成立：
d^TH\left( x^*+\alpha d \right) d<0,\ \alpha \in \left( 0,\delta \right]\\
由 f(x) 在 x^* 处的泰勒展开及一阶必要性条件可知，对任意的 \alpha _1\in \left( 0,\delta \right]，存在 \alpha \in \left( 0,\alpha _1 \right)，使得如下表达式成立：
f\left( x^*+\alpha _1d \right) =f\left( x^* \right) +\frac{1}{2}\alpha _{1}^{2}d^TH\left( x^*+\alpha d \right) d \\
由于上式中等式右端第二项小于0，所以有 f\left(x^*+\alpha_1d\right)<f\left(x^*\right) 这与 x^* 是局部极小点矛盾，因此命题得到证明。
证毕
4.3 二阶充分条件
设 f(x) 二阶可导，并且其二阶导函数是连续的，\nabla f\left( x^* \right) =0 并且 \nabla ^2f\left( x^* \right) 正定， 则 x^* 是 f(x)的一个严格局部极小点。
证明：对任意的单位向量 d\in R^n, f(x) 在 x^*的泰勒展开为
f\left( x^*+\alpha d \right) =f\left( x^* \right) +\frac{1}{2}\alpha _{}^{2}d^TH\left( x^* \right) d+o\left( \alpha ^2 \right)\\
由 H\left( x^* \right) 的正定性可知，正定二次函数 d^TH\left( x^* \right) d 在有界闭集上 \left\{ d|\lVert d \rVert =1 \right\}上有正的最小值，我们设这个最小值为 \gamma >0，由此进一步可得：
f\left( x^*+\alpha d \right) \ge f\left( x^* \right) +\frac{1}{2}\alpha _{}^{2}\gamma ^2+o\left( \alpha ^2 \right)\\
由此可知，存在 \varepsilon >0，当 \alpha \in \left( 0,\varepsilon \right) 时，有
f\left( x^*+\alpha d \right) >f\left( x^* \right)\\
表明 x^* 是 f(x) 的严格局部极小点。
5 最速下降法
前面我们已经得到了搜索方向，搜索步长和终止准则三大要素，基于这三大要素我们给出最速下降法的算法流程：
Step 1: 任意给出 x_0 \in R^n, \epsilon>0, k:=0
Step 2: 若满足终止条件 \lVert \nabla f\left( x_k \right) \rVert ^2<\epsilon，则停止迭代 输出x_k为最优解；若不满足终止条件则继续
Step 3: 令搜索方向 d_k=-\nabla f\left( x_k \right)
Step 4: 由线搜索方法确定出步长 \alpha_k
Step 5: x_{k+1}:=x_k+\alpha _kd_k，k:=k+1，跳转到 Step 2
观察上述算法 Step 2 中我们采用了4.1中的一阶必要条件来作为终止条件；Step 3 中我们采用负梯度作为搜索方向，确实我们也在2.2节中验证了负梯度是一个下降方向；Step 4 中我们采用线搜索方法。在前面我们已经把每一个模块都解释清楚了，这里给出最速下降法的算法流程就非常非常自然。
把上述最速下降法的搜索过程用动图表示出来，如下所示：（这也是我们文章一开始的图）
当然需要注意的是在 Step 2 中我们选择的是负梯度作为搜索方向，所以该算法就叫做最速下降法，因为负梯度是在局部最快的下降方向。显然在很多情况下，函数的下降方向并不是唯一的，如果选择了不同的下降方向则构成不同的算法，这些算法将会在我们后边的章节中展开讲解。
6 最速下降法收敛性的证明
最速下降法的收敛性证明需要以下三个假设条件：
[*]目标函数的 Hessian 矩阵满足： \nabla ^2f\left( x \right) \le LI ，其中L为常数，I为单位矩阵。
[*]目标函数存在下界 f(x) \ge f^*
[*]搜索步长选择为 \alpha _k=\frac{1}{L}
对 f(x_{k+1}) 做二阶泰勒可得式(7.1)
f\left( x_{k+1} \right) =f\left( x_k \right) +\nabla ^Tf\left( x_k \right) \left( x_{k+1}-x_k \right) +\frac{1}{2}\left( x_{k+1}-x_k \right) ^T\nabla ^2f\left( w \right) \left( x_{k+1}-x_k \right) \quad \left( 7.1 \right)\\\le f\left( x_k \right) +\nabla ^Tf\left( x_k \right) \left( x_{k+1}-x_k \right) +\frac{L}{2}\lVert x_{k+1}-x_k \rVert ^2\quad \left(7.2 \right)\\=f\left( x_k \right) -\alpha _k\lVert \nabla f\left( x_k \right) \rVert ^2+\frac{L\alpha _{k}^{2}}{2}\lVert \nabla f\left( x_k \right) \rVert ^2\quad \left( 7.3 \right)\\=f\left( x_k \right) +\left( \frac{L\alpha _{k}^{2}}{2}-\alpha _k \right) \lVert \nabla f\left( x_k \right) \rVert ^2\quad \left( 7.4 \right)\\
从式(7.1)到(7.2)是因为假设条件1成立。
从(7.2)到(7.3)是因为最速下降法的迭代公式 x_{k+1}:=x_k+\alpha _kd_k
从式(7.3)到(7.4)就是简单的同类项合并。
观察式(7.4)不难发现若 \left( \frac{L\alpha _{k}^{2}}{2}-\alpha _k \right)< 0，则可以保证目标函数的下降性：$ f\left( x_{k+1} \right)
我们把假设条件3代入到式(7.4)可得
\frac{1}{2L}\lVert \nabla f\left( x_k \right) \rVert ^2\le f\left( x_{k+1} \right) -f\left( x_k \right)\\
上式是一个递推表达式，我们对前K项可得：
\sum_{k=1}^{K-1}{\lVert \nabla f\left( x_k \right) \rVert ^2}\le 2L\sum_{k=1}^{K-1}{\left( f\left( x_{k} \right) -f\left( x_{k+1} \right) \right)}=2L\left( f\left( x_1 \right) -f\left( x_{K+1} \right) \right) \quad (7.5) \\
我们设从第1步到第K步过程中最小的 \lVert \nabla f\left( x_k \right) \rVert ^2为\underset{k\in \left\{ 1,2,...K \right\}}{\min}\lVert \nabla f\left( x_k \right) \rVert ^2
由此可得：
K\underset{k\in \left\{ 1,2,...K \right\}}{\min}\lVert \nabla f\left( x_k \right) \rVert ^2\le \sum_{k=1}^K{\lVert \nabla f\left( x_k \right) \rVert ^2}\quad (7.6) \\
结合式(7.5)和(7.6)可得：
K\underset{k\in \left\{ 1,2,...K \right\}}{\min}\lVert \nabla f\left( x_k \right) \rVert ^2\le \sum_{k=1}^K{\lVert \nabla f\left( x_k \right) \rVert ^2}\le 2L\left( f\left( x_1 \right) -f\left( x_{K+1} \right) \right)\\
进一步整理上式可得：
\underset{k\in \left\{ 1,2,...K \right\}}{\min}\lVert \nabla f\left( x_k \right) \rVert ^2\le \frac{2L\left( f\left( x_1 \right) -f\left( x_{K+1} \right) \right)}{K} \\
由于等式右端项2L\left( f\left( x_1 \right) -f\left( x_{K+1} \right) \right) 都是有界的常数值（根据假设2可得），进一步可得：
\underset{k\in \left\{ 1,2,...K \right\}}{\min}\lVert \nabla f\left( x_k \right) \rVert ^2\le \frac{2L\left( f\left( x_1 \right) -f\left( x_{K+1} \right) \right)}{K}=O\left( \frac{1}{K} \right)\\
\underset{k\in \left\{ 1,2,...K \right\}}{\min}\lVert \nabla f\left( x_k \right) \rVert ^2\le \frac{2L\left( f\left( x_1 \right) -f\left( x_{K+1} \right) \right)}{K}=O\left( \frac{1}{K} \right)\\ 小白表示看不懂
页:
[1]