无约束非线性优化——最速下降法、牛顿法、共轭梯度法
无约束非线性优化——最速下降法、牛顿法、共轭梯度法
无约束非线性优化是优化理论中的一个重要分支，广泛应用于机器学习、深度学习等领域。本文将介绍三种基本的无约束优化方法：最速下降法、牛顿法和共轭梯度法。这些方法从不同的角度出发，通过迭代的方式寻找目标函数的极小值点。
本章对应的相关例题可见《无约束非线性优化算法例题-CSDN博客》
目录
1 非线性优化问题的相关概念
1.1 迭代格与要求
1.2 线性搜索
2 最速下降法
2.1最速下降法计算步骤
2.2 最速下降法的总体收敛性
3 牛顿法
3.1 牛顿法计算步骤
3.2 阻尼牛顿法计算步骤
4 共轭梯度法
4.1 轭梯度法求解线性方程
4.2 FR共轭梯度法计算步骤
1 非线性优化问题的相关概念
1.1 迭代问题的结构与格式要求
首先，介绍迭代问题的一般性结构。设非线性规划问题
其中
。
- 若
，即没有约束条件，在函数的整个定义域内寻找最优解，则问题为无约束优化问题； - 若
，即表示为约束条件为：
，的有约束优化问题。
设
为迭代算法的第k次迭代点，则第k+1次的迭代点表示为：
同时要求保证
且迭代点保持可行，这就是求解得非线性最优化问题的基本迭代格式和要求。
搜索方向
步长因子
1.2 线性搜索
选取步长因子α的问题称为线性搜索问题，它是一个一维搜索问题，其基本要求在于从
出发沿给定的搜索方向
确定
使得
对于这样的问题，有两种解决途径：
(1)精确线搜索。选取
使得
，
所得的
称为精确步长因子。一般可通过直接搜索或插值法来数值来求解，如0.618法、Fibonacci法、割线法、三点二次插值法等。但是这种 方法往往计算量很大，特别当迭代点远离最优解时，效率较低。
(2)不精确线搜索。
只要求选取
满足使得目标函数(1)每迭代一步都有充分下降即可，这样可以节省工作量。常用的方法有后退法、Armijo-Goldstein法及 Wolfe-Powell法。
定理1设
是下降方向，
是精确线搜索的步长因子。若存在常数
使得所有
有
，则
其中
为
与
之间的夹角。
不同的搜索方向将形成不同的最优化方法
2 最速下降法
最速下降法是无约束最优化最简单的方法，由法国科学家Cauchy于1847年提 出，继而由Curry等人进一步研究得到的方法。
设目标函数
在
附近连续可微，令
。将
在
处Taylor展 开
令
,有
若
，则
为下降方向。且由Cauchy-Schwartz不等式
有当且仅当
时，
最大。因而以为下 降方向的方法称为最速下降法。其迭代格式为
其中
由精确线搜索策略选取。
2.1最速下降法计算步骤
给定初点
,允许误差
，置k=1计算搜索方向
，如果
停止计算由精确线搜索计算步长
，使得令
，
，转步骤2
2.2 最速下降法的总体收敛性
定理2 设函数f(x)二次连续可微，且
，其中
为一常 数。则对任何给定的初始点
，由最速下降算法产生的序列
满足对某 个k有
，或
，或
。
最速下降法具有计算工作量小,存储量小等优点。但是,最速下降方向仅是函数 的局部性质,对整体求解过程而言,这个方法下降非常缓慢。其原因是精确线性搜索 使得
，即最速下降法中前后两次迭代的搜索方向是正交的。 所 以在靠近极小点附近时的路径呈现锯齿形，如下图下降十分缓慢。
定理3 设函数f(x)二次连续可微，由最速下降算法产生的序列
，收敛于最优 解
。如果存在m,M >0使得对任意属于
领域的x有
则有
线性收敛于
。
3 牛顿法
为加快收敛速度，我们考虑利用目标函数f(x)在迭代点
处的二阶Taylor展开 式作为逼近函数，并用这个二次函数的极小点序列去逼近目标函数的极小值点。这 就是牛顿法的基本思想。
设目标函数f(x)二次连续可微，将f(x)在当前迭代点
处作Taylor展开，并取二阶近似得
极小化上式右端有
若Hesse矩阵
正定，则得到右端二次函数的极小点，并以它作为无约 束问题最优值点的第k+1次近似，即
这就是牛顿法迭代公式，其中
3.1 牛顿法计算步骤
给定初点
,允许误差
，置k=1计算
，如果
，停止计算构造牛顿方向
，令
，
，转步骤2
定理4 设f(x)二阶连续可微，
为无约束问题的局部较小点，
正 定。如果Hesse矩阵
满足Lipschitz条件，即存在
使得
有
当初始点
充分靠近
，由牛顿法得到的
收敛到
，且具有二阶收敛速度。
3.2 阻尼牛顿法计算步骤
给定初点
,允许误差
，置k=1计算
，如果
停止计算构造牛顿方向
，由精确线搜索计算步长
使得令
，
，转步骤2
定理5 设f(x)二阶连续可微，对任意初始点
，存在常数m>0使得f(x)在水平集
上有
则在精确线搜索下，阻尼牛顿法产生的序列
满足：
当
为有限序列时，其最后一个点为唯一极小点当
为无限序列时，其收敛到唯一极小点
4 共轭梯度法
4.1 轭梯度法求解线性方程
给出共轭梯度法求解线性方程的步骤：
设
，A对称正定，求解：
给定初始近似向量
,取
对于
计算
计算过程中，若
，则
为方程
的解，停止计算。
4.2 FR共轭梯度法计算步骤
注意到二次函数的Hesse矩阵即为常数矩阵A，且Hesse矩阵A出现在计算
和
的公式中。而对一般非线性函数而言，每次迭代都需重新计算当前点的Hesse矩阵
计算量偏大。因此为方便将方法推广，我们需对
和
的计算做必要的修改。
对于非二次函数，精确步长因子无法获得显式公式表达，
将由精确线搜索过 程确定，即计算一维优化问题我们必须去除
公式中的Hesse矩阵的计算。
的计算可以只用目标函数值和梯度值完成公式修正，得到一般函数情形 下的Fletcher −Reeves公式：
FR共轭梯度法步骤
给定初点
,允许误差
，令
，置k=1如果
，停止计算由精确线搜索计算步长
，使得
，令
。
计算
，令k =k+1, 转步骤2.
由于共轭梯度法中含有最速下降法步骤，因此在较弱的条件下可以保证方法的总体收敛性。
定理6 设f(x)在有界水平集
上连续可微且下有界，则由共轭梯度算法产生的序列
至少有一个聚点是驻点，即
当
是有穷点列时，其最后一个点是f(x)的驻点当
是无穷点列时，其必有聚点且每个聚点都是f(x)的驻点
注：本篇内容均为对《高等工程数学》(朱元国 范金华 张军 编著，科学出版社)摘录与个人归纳总结，如需要更加详细了解，可阅读原书“第5章 最忧化方法”部分。