X ( k 1) X X
(k )
X

p
,
当 p = 2 时，X
( k 1)
X 与 X

( k 1)
(k)
X

2
同阶无穷小
(k )
当 1, k 时， X
X (k ) X
X ( k 1) X
X
X
X
2
X ( k 2) X
则X ( k ) k X .
若 { X } 收敛于 X ，且满足 lim k
(k ) { X } 收敛于 X 的阶。 则 p 称为
X ( k 1) X X
(k )
X

p
,
当 p = 1 时，称为一阶收敛； 当 p = 2 时，称为二阶收敛；
1 T 结论：正定二次函数 f ( X ) X QX bT X c 有唯一 2 全局极小点：X Q 1b
无约束问题4-4
一.最速下降法
f (X ) ( NP) min X R
n

收敛性问题的基本概念 最速下降法的迭代原理 最速下降法的迭代步骤 最速下降法的举例 最速下降法的收敛结论
第四章 无约束最优化问题

4.1 非线性规划数学模型 4.2 凸函数和凸规划 4.3 一维搜索 4.4 无约束优化问题的解法
第四章 无约束最优化问题
第四节 无约束优化问题的解法

最速下降法 Newton法 拟Newton法 共轭梯度法
一.最速下降法
f (X ) ( NP) min X R
(k ) { X } 收敛于 X 的阶。 则p称为
X ( k 1) X X
(k )
X

p
,
( k 1) (k) X X 与 X X 当 p = 1 时， 同阶无穷小
( k 1) (k) X X X X 当 1, k性收敛；
无约束问题4-4
1.收敛性问题的基本概念 定义4-10
(k )
若 X ( k ) X k 0,
则X ( k ) k X .
若 { X } 收敛于 X ，且满足 lim k
(k ) { X } 收敛于 X 的阶。 则p称为
f ( X ( k ) )T p ( k ) f ( X ( k ) ) p ( k ) cos cos 1
n

收敛性问题的基本概念 最速下降法的迭代原理 最速下降法的迭代步骤 最速下降法的举例 最速下降法的收敛结论
无约束问题4-4
1.收敛性问题的基本概念 定义4-9
min f (X ) n
X R
(k ) 若序列 { X }，对于 0 ，存在正整数 N ( ),
(k ) (k ) X X X X k N 当 时，有 ，即 k 0,
最速下降法 Newton法
当 1 p 2 时，称为超线性收敛；拟Newton法
无约束问题4-4
1.收敛性问题的基本概念 定义4-12
若某算法对于任意正定二次目标函数,从任意初始点 出发,都能经过有限次迭代达到其极小点,则该算法称 为具有二次终止性的算法或二次收敛算法.
1 T f ( x1 , x2 ,, xn ) X QX bT X c 2 当 Q 为正定阵时，称 f (X) 为正定二次函数。
X (k ) X
X ( k 1) X
X ( k 2) X
X ( k 3) X
X ( k 4) X
0 .1
0.09
0.05
0.02
0.01
无约束问题4-4
1.收敛性问题的基本概念 定义4-10
(k )
若 X ( k ) X k 0,
(k ) { X } 收敛于 X ，记为X ( k ) X . 则称 k
X
0
X1
X
2
X3
X4
X
X k
X f ( X k ) X ( k ) k
无约束问题4-4
1.收敛性问题的基本概念 定义4-10
(k )
若 X ( k ) X k 0,
p( k )
X f ( x ( k ) h) f ( x ( k ) ) f ( x ( k ) )h (h) f ( X ( k ) p( k ) ) f ( X ( k ) ) f ( X ( k ) )T p( k ) ( ) f ( X ( k ) p( k ) ) f ( X ( k ) ) f ( X ( k ) )T p( k ) ( ) ( ) (k ) T (k ) ( f ( X ) p )0 充分小时 0 (k ) T (k ) 结论： 当 f ( X ) p 0 时，p(k)是 f (X)在X(k) 处的下降方向。
无约束问题4-4
2.迭代原理 梯度的性质： 函数f 证明：
(k ) ( k ) X ( k ) (X)在X 处的负梯度方向 f ( X ( k ) )
P
(k )
f ( X ( k ) )
P
是X(k)处函数值下降最快的方向。 (k )
P P
(k )
一元函数泰勒公式：
X p
(k )
(k )
(k )
则X ( k ) k X .
若 { X } 收敛于 X ，且满足 lim k
(k ) { X } 收敛于 X 的阶。 则p称为
X ( k 1) X X
(k )
X

p
,
当 p = 1 时，称为一阶收敛； 当 p = 2 时，称为二阶收敛；
X ( k 3) X
X ( k 4) X
0 .1
0.01
0.0001
108
1016
无约束问题4-4
1.收敛性问题的基本概念 定义4-10
(k )
若 X ( k ) X k 0,
则X ( k ) k X .
若 { X } 收敛于 X ，且满足 lim k