优化理论复习——（三）

本篇介绍无约束优化的问题，通过四种算法来进行求解的过程和思路，也是最优化方法中的最重要的一类问题。
无约束优化问题主要是通过迭代搜索算法来切结，比线性规划的计算量都小一点。

无约束优化问题

最优性条件

首先是无约束优化问题的最优性条件，是必要条件，得是局部极小才有梯度=0和hesse阵半正定。

其次是充分条件：

无约束凸规划则可以直接有以下充要条件：

之前的学习中我们知道了线搜索迭代算法，这里把它用来计算最优值，一般思路如下：


接下来我们学习四种迭代算法的基本思路和性质：

最速下降法

最速下降法，这是因为负梯度方向是下降的最快的，顾名。

最速下降法具有全局收敛性。然后用精确一维线搜索时的步长为：

这里要求了二次正定函数。步长信息就是已知的。

牛顿法

然后是牛顿法，经典牛顿法步长为1：

注意，经典牛顿法不一定是下降方向，
所以计算hesse阵很重要。

经典牛顿法一般都不会让你一直求，这里注意一下，这里需要注意什么是二次终止性：

收敛上看，它是局部二阶收敛的：

由于经典牛顿法比较特殊，所以还是需要引入带线搜索的牛顿法，其中用精确一维线搜索时是阻尼牛顿法：

带线搜索的牛顿法具有全局收敛性和局部二阶收敛速度。

共轭梯度法

共轭有以下特征：


以下关于极小值的两个定理：


对于标准的二次函数使用共轭方向法就为：

这里面方向和步长就不一样了，方向是共轭方向，步长还是精确一维线搜索得到的步长。

拟牛顿法

拟牛顿法和牛顿法比较类似，不同的是用的是hesse阵是用H函数估计出来的：

也就是说他的迭代方向H（k）不再是hesse的逆矩阵，而是-H(K)g_k。

所以算法稍微复杂一点：

加入了一步计算H的，其余的相差不大。
理论性质方面，DFP算法的性质有：
首先是满足拟牛顿方程（H_k+1的表达式），同时产生的搜索方向是共轭方向。
然后也有二次终止性：

到此为止就介绍完了所有的无约束优化问题的内容。