f x1 , x2 c, c>0,
2
改写为：
x12 2c 1

2 x2

2c 2
2
1
二、最速下降法
x2
这是以
2c
1
和
2c
2
为半轴的椭圆
2c
2c
2
2
从下面的分析可见 两个特征值的相对
x1
大小决定最速下降法的收敛性。
（1）当 1 2 时，等值线变为圆
2 2
4 f x , 2
2 x1 2 x2 4 f ( x) , 2 x1 +4x2
4 d = f x , 2
0 0
=40 2 20 3 令 0= ' ( ) 80 20, 得 0 =1/4,
一
一维搜索
二 三 四
下 降 算 法
五
最速下降法 Newton法 共轭梯度法
多尺度法 （拟Newton法）
二、最速下降法 假设 f 连续可微，取 线搜索方向
k
d f ( x )
k
步长k 由精确一维搜索得到。 从而得到第 k+1次迭代点，即
f ( x k k d k ) min f ( x k d k )


(推论)在收敛定理的假设下，若f (x)为凸函数，则最速下降 法或在有限迭代步后达到最小点；或得到点列 x k ，它的任 何聚点都是 f (x)的全局最小点。
二、最速下降法

最速下降法特征：相邻两次迭代的方向互相垂直。
令
( ) f ( x d ), 利用精确一维搜索，可得
二、最速下降法 最速下降法收敛速度慢！ 在最速下降法中，利用精确一维 搜索求最佳步长，使得相邻两次迭代 的搜索方向总是垂直的， 使得逼近极小点过程是“之”字形，
x0
x2 d 2 d1 d 0 x1
这样从任何一个初始点开始，都可以很快到达极小点附 近，但是越靠近极小点步长越小，移动越慢，导致最速下降 法的收敛速度很慢。 实际运用中，在可行的计算时间内可能得不到需要的结果。
三、Newton法
2 例1：用Newton法求 f x1, x2 x12 25x2 的极小点。


解：取初始点 x 2, 2
0
T
则:
2 x1 4 2 2 0 0 f x |x0 , f x 100 0 50 50 x2
使得对于所有 1 i , j n 有：
Gij x Gij y x y , x, y R n
其中 Gij
x 是海赛阵
则当 x0 的 i, j 元素．
* x 充分靠近 时，对于一切 k , 牛顿迭代有意义， * x , 并且具有二阶收敛速度。 迭代序列 xk 收敛到
二、最速下降法

用于二次函数时的收敛速度分析
1 T 1 , 2分别 定理：二次函数 f ( x) x Ax, A为对称正定， 2
为其最小和最大特征值，从任意初点 x 出发，对二次函
数，用最速下降法产生的序列 {x
k 1
0
k
} ，对于 k 0 有
k
2 1 2 2 2 1 0 k k f (x ) ( ) f ( x ), x x 2 1 1 2 1 2 1 由于 1 x k 0. 2 1
10
d 0 / / d 2 / / d 4 / /... / / d 2 k
t , d 2 k t d 0
t与k有关
5
0
Ax tAx
2k
0
-5
-10
(d k f ( x k ) Ax k )
-15 -1.5 -1 -0.5 0 0.5 1 1.5
x tx .
2k 0
k
k 2
产生新
的搜索方向，然后继续使用最速下降方向。两种方向 交替使用，实践效果优于单纯使用最速下降方向。
可以利用最速下降法初期搜索效率高的特性，首先使 用最速下降法，然后使用其它局部收敛速度快的计算 方式。
三、Newton法 算法的基本思路 考虑从
xk
到
x
k 1
的迭代过程，在
x
k
点处对函数
此时
2 1 0 2 1
x0
x1
x1 0 因而由上述定理知：

0 || x1 || 0
即只需迭代一步就到了极小点。 （2）当 1 2 时, 等值线为椭圆。此时对于一 2 ， 等值线是很扁的椭圆
2 1 1，对于一般的初始点,收敛 此时 2 1
k
k

T
令
Q x f x k 2 f x k x x k 0 ，有
T 1 k 2 k k x x x x f x x x 2 k
三、Newton法
2 f x k x x k = f x k
若Hesse矩阵 f x 正定，则 f x
2 k
2
二次函数Q x 的极小点为 ：

k

存在，由此求出
k 1
x
以此
k 1
k +1
x f x
2

k

1
f x k
Newton法
* 极小点 的一个新的近似。此公式 x x 即为多元函数求极值的Newton迭代公式。 目标函数
采用非精确一维搜索求步长, 可使相邻两个迭代点处的
梯度不正交，从而改变收敛性。
二、最速下降法 采用加速梯度法 负梯度方向和 d
k
x x
k
k 2
结合。
由于最速下降法在极小点附近成“锯齿”状，因此下 降过程中的搜索方向可适时改变搜索方向的正交特性。
开始取负梯度方向，每两步用 d k
x x
二、最速下降法
第2次迭代：
1 1
1 4 2 f x1 1 , x =x +0 d = +1/4 = ， 2 1 2 1/2
1 0 0
2+ x + d = ， 1/2+2 ( )=f x1 + d 1 =f 2+ ,1/2+2
0
x k 1 x k +k d k x k k f ( x k )
单位向量
负梯度方向 d k f ( x k ) 是函数值减少最快的方向 。
f ( x)T d k f ( x ) d k cos(f ( x ), d k )
二、最速下降法 最速下降法的计算流程 (1) 选定某一初始点 x ，
作为
f x
Newton法的几何意义
二次函数 Q x 的等值线为 k 1 椭圆族。 x 为椭圆中心。 椭圆等值线逼近目标函数等值线！
等值线
三、Newton法 Newton法的计算步骤 已知目标函数 f x , 给定误差限 步骤1. 选定初始点 步骤2. 如果 f x k
得 1 =1/2,
继续迭代可得到函数的近似最优解……
二、最速下降法 最速下降法的收敛性分析 (收敛性定理)设目标函数 f (x)连续可微，且水平集
L x f ( x) f ( x 0 ) 有界，则最速下降法或者在有限迭代步
k x 后终止；或者得到点列 ，它的任何聚点都是f (x)的驻点。
2 k k k
f x d = -f x

线性方程组
三、Newton法 牛顿法收敛性 定理
f
设 f
*
* x x 二次连续可微， 是 f x 的局 部极小点，
x 0
假定 2 f x* 正定， 且海赛阵 满足Lipschitz条件，即存在
0,
0 T
解：函数的梯度为 第1次迭代：
0 0
0
1+4 0 0 x + d = ， ( )= f x + d =f 1+4 ,1 2 1 2
= 1+4 2 1 2 2 1+4 1 2 4 1+4
0
0 并令 k: 0
(2) 若 f ( x k ) (3)
, x* x k，否则转（3）；
d k f ( x k )
(4) 由精确一维搜索确定步长步长
k
k
，即由一个极小化
k
问题求得最佳步长
令 x k 1
min f ( x d )
xk k d k , k k 1, 转（2）。
f x
Tayloy展开：
f ( x ) f ( x ) f x
k
k

T
k x x
略去高阶项
T 1 k 2 k k k 2 x x f x x x o( x x ) 2
f ( x ) Q( x ) f ( x ) f x
x 0 , 计算 f 0 f x 0 , k : 0
，算法停止，x
k

.

*
xk
，否 步长确定
则转步骤3。
步骤3. 计算搜索方向 d f x
2


k
1
f x k
步骤4. 令
xk 1 xk d k , k k 1 ，转步骤2.