1 d = f x , 2
1
2+ x + d = ， 1/2+2
1 1
2
( )=f x1 + d 1 =f 2+ ,1/2+2
= 2+ 2 1/2+2 2 2+ 1/2+2 4 2+ ,
k
k
x k +1.
(4) 检查得到的新点 x k +1是否为极小点或近似极小点。 若是，则停止迭代。 否则，令 k : k 1，转(2)继续进行迭代。 在以上步骤中，选取步长可选用精确一维搜索或者非精确一 维搜索， 下降方向的选取正是下面我们要介绍的，下降方向选取的不 同，得到不同的算法。
最速下降法
( )=f x 2 + d 2 =f 5/2+2 ,3/2
= 5/2+2 2 3/2 2 5/2+2 3/2 4 5/2+2
2 2
=10 2 5 27/4 令 0= ' ( ) 20 5,
3 2 2
5/2 2 3 f x3 1/2 , x =x +2 d = +1/4 = ， 1 3/2 1 5/4
继续迭代可得到函数的近似最优解。
得 2 =1/4,
最速下降法的收敛性分析
无约束优化的最优性条件----一阶必要条件
定理(一阶必要条件) 设 f : R n R ，若 x 为 f ( x ) 的局部极小点，且在 N ( x*)
内连续可微，则
f ( x* ) 0.
无约束优化的最优性条件----二阶必要条件
定理（二阶必要条件） 若 x * 为 f x 的局部极小点，且在 N x * 内 f x 二次连续 可微，则 f ( x* ) 0, 2 f ( x* ) 半正定。
假设 f 连续可微，
负梯度方向
这是函数值减少 最快的方向
d f ( x ) f ( x k k d k ) min f ( x k d k )
k k
0
步长 k 由精确一维搜索得到。 从而得到第 k+1次迭代点，即
x k 1 x k +k d k x k , x4 不是极小点；
2 0 f x2 是正定矩阵； 0 2
2
x2 是极小点；
2 0 f x3 是负定矩阵； 0 2
2
x3 是极大点。
• 对某些较简单的函数，这样做有时是可行的； • 但对一般n元函数 f(x) 来说，由条件 f ( x) 0 得到的是一个 非线性方程组，解它相当困难。 • 为此，常直接使用迭代法。
k
的任何聚点都是 f (x)的全局最小点。
最速下降法的两个特征
1. 相邻两次迭代的方向互相垂直
令
( ) f ( xk d k ),
最速下降法
负梯度方向 d k f ( x k )是函数值减少最快的方向 ？ 令 p 是单位长度的向量， p 1, 0,
f ( x p) f ( x)+f ( x)T p o( )
P是什么方向时，函数值 f ( x p) 下降最快？也就是
f ( x)T p 取得最小值？ p是什么方向时，
函数 f x 的Hesse阵：
2
0 2 x1 f x 0 2 x2 2 在点 x1 , x2 , x3 , x4 处的Hesse阵依次为：
利用二阶条件 判断驻点是否 是极小点
2 f x2 0 2 0 2 2 2 f x3 , f x4 0 2 0
令 f x 0, 即：
x12 1 0 2 x2 2 x2 0
得到驻点：
1 1 1 1 x1 , x2 , x3 , x4 . 0 2 0 2
无约束优化的最优性条件
线搜索方法：迭代点沿某方向产生 根据迭代点是否 沿某个方向产生 信赖域方法： 迭代点在某区域内搜索产生
线搜索迭代法的步骤
(1) 选定某一初始点 x 0 ，并令 k: 0. (2) 确定搜索方向 d k .
k ，以产生下一个迭代点 (3) 从 x 出发，沿方向 d 求步长
*
求解 (1)的计算方法称为无约束最优化方法。
最优化方法中的基本方法---无约束优化方法
无约束最优化方法应用广泛，理论也比较成熟；
可将约束优化问题转化为无约束优化问题来处理；
f ( x), x D min f ( x) min F ( x), 其中F ( x) xD xR n , others.
2
=5 2 5 11/2 令 0= ' ( ) 10 5,
2 1 1
2 1 5/2 f x 2 2 , x =x +1d = +1/2 = ， 1 1/2 2 3/2
解析法要用到目标函数的梯度或者Hesse矩阵，容易想到 利用一阶必要条件将无约束优化问题转化成一个梯度为0确定 的方程组。 这里用到的一阶必要条件就是最优性条件。 所谓最优性条件，是指最优化问题的最优解所要满足的 必要条件或充分条件。 这些条件对于最优化算法的建立和最优化理论的推导都是 至关重要的。
0 0
=40 2 20 3 令 0= ' ( ) 80 20, 得 0 =1/4,
第2次迭代：
1
0 =1/4, d 0 = 4 , 2 x1 2 x2 4 f ( x ) , 2 2 x1 +4x2 4 2 f x1 1 , 1 0 0 1 x =x +0 d = +1/4 = ， 2 1 2 1/2
f ( x)T p f ( x) p cos(f ( x), p)
f ( x) f ( x) ，此时由f ( x) p f ( x) 可得 p f ( x)
T
当 cos(f ( x), p) 1 时，f ( x)T p 最小，最小值为
T
最速下降法
最速下降法是求多元函数极值的最古老的数值算 法，早在1847年法国数学家Cauchy提出该算法，后来 Curry作了进一步的研究。 该方法直观，简单，计算方便，而且后来的一些新的 有效的方法大多数是对它的改进，或受它的启发而得到 的。
解析法：利用函数的一阶或二阶导数的方法 收敛速度快，需要计算梯度或者Hesse矩阵 无约束优化方法 可求得目标函数的梯度时使用解析法 本章介绍解析法 直接法：仅利用函数值的信息，寻找最优解
不涉及导数，适用性强，但收敛速度慢 在不可能求得目标函数的梯度或偏导数时使用直接法
最优性条件(Optimality Conditions)
2 2
2 0 f x1 , 0 2
0 , 2 0 . 2
1 1 1 1 x1 , x2 , x3 , x4 . 0 2 0 2
无约束优化的最优性条件
2 0 2 2 0 f x1 , f x4 是不定矩阵； 0 2 0 2

无约束优化的最优性条件----二阶充分条件
定理(二阶充分条件)
f ( x* ) 0, 2 f x 正定，则 x 为 f ( x) 的严格局部极小
点。
设 f : R n R ，若在 N ( x*) 内 f ( x ) 二次连续可微，且
如果 2 f x 负定，则 x 为 f ( x ) 的严格局部极大点。
最速下降法的迭代格式
x 0 ， 0 并令 k: 0 (1) 选定某一初始点
(2) 若 f (3)
k
( x k ) , x* x k，否则转（3）；
k
d f ( x )
(4) 由精确一维搜索确定步长步长 问题求得最佳步长 令 xk 1 xk
k
，即由一个极小化
例 利用最速下降法求解 min f ( x ) x1 2 x2 2 x1 x2 4 x1 ,
2 2
2 x1 2 x2 4 解：函数的梯度为 f ( x) , 2 x1 +4x2
第1次迭代：
4 4 0 0 f x , d = f x , 2 2
f ( x* ) 0, 则 x 为 f ( x) 的唯一全局极小点。
无约束优化的最优性条件
例： 利用最优性条件求解下列问题： 利用一阶条件 求驻点 利用二阶条件 判断驻点是否 是极小点
解：
1 3 1 3 2 min f x x1 x2 x2 x1 3 3 f f 2 x1 1, x22 2 x2 , x1 x2
0
取 x 0 1,1 .
T
( )=f x 0 + d 0 =f 1+4 ,1 2
= 1+4 2 1 2 2 1+4 1 2 4 1+4
2 2
1+4 x + d = ， 1 2
收敛性定理： 设目标函数 f (x)连续可微，且水平集 L x f ( x) f ( x 0 ) 有界，则最速下降法或者在有限迭代步后终止；或者得 到点列 推论： 在收敛定理的假设下，若f (x)为凸函数，则最速下降法 或在有限迭代步后达到最小点；或得到点列 x ，它