文档介绍：: .
沖理^
数学与计算科学学院
实验报告
实验项目名称使用非精确线搜索 Armjo算法确定步长
的最速下降法
所属课程名称最优化方法
实验类型算法编程
实验日期
班级
学号
姓名
成绩
」、实验概述：
【实验目的】
1. 通过实验掌握最速下降法的 Matlab算法的基本步骤;
2. 通过实验掌握Armijo算法确定步长；
3. 掌握最速下降法的思想及迭代步骤。
【实验原理】
：
最古老的优化方法，十九世纪中叶由 Cauchy提出思想：每次沿负梯度方向进行搜索
等值线（面）
负梯度方向也称为最速下降方向: 举例：
事实上，对任意p Rn且||p||j, 由Cauchy - Schwarz不等式得
"(Xk)TP--|Pf(Xk)|| ||P|F-||'f(Xk)||
当取p = Nf(Xk)时等号成立，即p= MX)是下列问题
|^f(Xk)|| 匹 f(Xk)||
的解
mam
算法步骤:
步1给定初始点X。 Rn,精度；.0•令k=0;
步2若||'f(xk)肚，则得解xk,算法终止否则
计算d^A f (Xk),然后转步3；
步3由线性搜索计算步长:-k;
步4 令Xk 1 二x「: kdk,kuk 1,转步 2.
优点：
对于简单的二元二次函数极小化问题，最速下降法在有限次迭代并没有求出其精确最优解,但能以较慢的速度无限接近最优解.
最速下降法的收敛性：全局收敛性：
由于最速下降法的搜索方向与负梯度方向一致，即二k =0,且
||W(Xk)"||dk||
所以，我们很容易得到最速下降算法的全局收敛性.
的迭
采用精确搜索，或Armijo搜索或Wolfe - Powell搜索的最速下降法产生代序列3讣满足
lim ||^f (xj ||=0
k_.
由例子看到，最速下降法的收敛速度至多是线性的，
收敛速度估计：设矩阵Q对称正定,q Rn .记■ max和饰分别是Q 的最大和最小特征值，瓷= 化
min 问题：
1 t T
min f (x)二 x Qx q x
2
则由采用精确搜索的最速下降法产生的点列｛ Xk｝满足
||Xk + -x* IQ 兰|||Xk-x*||Q ()
1
* „ -I- ■"
其中x是问题的惟一解，|| x ||Q二x Qx 2
#
#
对于二次函数，由于I f （x） = Qx q且在x处
'、f （x ） = Qx q = 0
1 * t * 1 *2
则 f (x)- f (x ) (x-x ) Q(x-x ) || x-x ||q
2 2
所以()可以改写成
f (Xk 1)- f (x ) <
[f(Xk)-f(x*)]
#
由收敛速度估计式（）看到,最速下降的收敛速度与矩阵 Q的条件数有关,当接近于1,最速下降收敛很快，特别，当.=1即Q的所有特征值相等时，算法只需一次迭代即可