haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 初中数学初中数学

数学表

发布时间:2013-10-02 18:07:08  

第三章

使用导数的最优化方法

----研究无约束问题最优化方法

要用到目标函数的导数 ?解析法:在计算过程中 算法? 数值。 ?直接法:只用到目标函
精确一维搜索的一个重要性质:
设f ( x)具有连续的偏导数,且 ( k ?1)是从x ( k )出发沿方向 x 定理: d ( k )作一维搜索而得到的, 即 f ( x ( k ) ? ?k d ( k ) ) ? min f ( x ( k ) ? ?d ( k ) ), 则?f ( x ( k ?1) )T d ( k ) ? 0。

最速下降法
最速下降方向

min s.t.

f ( x) x ? En

f ( x)具有一阶连续偏导数。
取搜索方向:

d

(k )

? ??f ( x )
(k )

步骤:

1.给定初点 ? E , 允许误差 ? 0, 置k ? 1 x ? 。
(1) n

2.计算搜索方向 d
3.若 d
(k ) (k )

(k )

? ??f ( x ).
(k )
(k )

? ?,则停止计算;否则, x 出发, 从
(k )

沿d 进行一维搜索,求 k,使 ? f (x ? ?k d
(k )
(k )

) ? min f ( x
? ?0
(k )

(k )

? ?d

(k )

)。

4.令x

( k ?1)

?x

? ?k d ,置k :? k ? 1 ,返回2。

例: 求 min f ( x) ? ( x1 ?1)2 ? ( x2 ?1)2,取x(1) ? (0,0)T , ? ? 0.1. 解:

?f ( x) ? ?2( x1 ?1), 2( x2 ?1)?
d
(1)

T

第一次迭代

? ?(?2, ? 2) ? (2, 2) , d
T T

(1)

?2 2 ??

?从x 出发,沿方向 进行一维搜索,求步长1。 d ?
(1) (1)

min ? (? ) ? min f ( x ? ?d )
(1) (1)

? ?0

? ?0

? x ? ?d
(1)

(1)

? (2?, 2? ) ,?? (? ) ? (2? ?1) ? (2? ?1) .
T 2 2

1 令? ?(? ) ? 4(2? ? 1) ? 4(2? ? 1) ? 0,得 ?1 ? 2

令x( 2) ? x(1) ? ?1d (1) ? (1, 1)T .

第二次迭代

d ( 2) ? (0, 0)T ? d ( 2) ? 0 ? ? ,? (1, 1)T 为最优解。

2 求 min f ( x) ? x12 ? 25x2,取x(1) ? (2,2)T , ? ? 0.2. 例:

k

x(k )

d (k )

?k

d (k ) 100 3.84 3.5 0.134 ? ?

? 2? ? ? 1 ? 2? ? ? ? 1.92 ? 2 ? ? ? 0.003? ? ? ? 3 4 ? 0.07? ? ? 0.07? ? ? ? ? 0.067? ? ? 0 ? ? ? ?

?? 4 ? ? ? ? 100? 0.02 ? ? ? ? ? 3.84? ? ? 0.15 ? 0.482 ? ? ? ? ? 0.14? ? ? ? 3.50? 0.02 ? ? ? ? ? 0.134? ? ? 0 ? ? ? ?

最速下降法的收敛性
设 定理: f ( x)是连续可微实函数,解集合? ? {x | ?f ( x ) ? 0}, 最速下降算法产生的序列? x ( k ) ? 含于某个紧集,则序列
(k )

? ? x ?的每个聚点x ? ?。
证明: 最速下降算法A可表示为合成映射 其中D( x) ? ( x, ??f ( x))是E ? 2
n E n ?E n

A ? MD
n n En

的映射,算法M 是E ? E ? 2

的映射(即一维搜索)。 当d ? ??f ( x) ? 0时,由定理M 是闭映射。由于f ( x)是连续可微函数, 所以D连续, A在x(?f ( x) ? 0)处是闭的。 ? 其次,当x ? ?时,d ? ??f ( x) ? 0,因此对于y ? A( x),必有f ( y ) ? f ( x), 即f ( x)是关于?和A的下降函数

。 由假设,x ( k ) ? 含于紧集中,所以算法收敛。 ?

二次函数情形
1 T f ( x ) ? x Qx ? bT x 2

其中Qn?n是正定矩阵,其特征值为0 ? a ? ?1 ? ? ? ?n ? A

设f ( x )的唯一极小点为x*, 则Qx * ?b ? 0.定义函数 1 T E ( x ) ? ? x ? x *? Q ? x ? x *? , 2 1 T 则E ( x ) ? f ( x ) ? x * Qx *. 2 def

?f ( x ) ? ?E ( x ) ? Qx ? b ? g ( x )

最速下降法表示为

其中gk ? ?f ? x
(k )

x ( k ?1) ? x ( k ) ? ?k d ( k ) ? x ( k ) ? ?k g k
(k )

? ? Qx

(k )

? b.

T 1 (k ) ? f ? x ? ? g k ? ? ? x ? ? g k ? Q ? x ( k ) ? ? g k ? ? bT ? x ( k ) ? ? g k ? 2 gk T gk ? f ? x ( k ) ? ? g k ? 在?k ? T 处达到极小。 gk Qgk

x ( k ?1)

gk T gk ? x( k ) ? T gk gk Qgk

引理1 最速下降法满足
2 T ? ? gk gk ? ? ( k ?1) ? E ? x(k ) ?. E ?x ? ?1 ? ? ? g T Qg g T Q ?1g ? ? k k ?? k k? ? ?

Kantorovich不等式
设Qn?n是一个正定对称矩阵,则对任意的x, 有

? x x? 4aA ? ? x Qx ?? x Q x ? ? a ? A?
T 2 T T ?1

2

其中a和A分别是Q的最小和最大特征值.

定理(最速下降法—二次情形)

对任意x (0) ? E n,最速下降法产生的序列收 敛于f ( x )的唯一极小点x*, 而且,对任意的k , 有 E ?x
( k ?1)

? A?a ? ?? E ? x(k ) ? ? ? A? a ? ?
2

1 T 其中E ( x ) ? ? x ? x *? Q ? x ? x *? . 2

1 T 例:考虑二次函数f ( x ) ? x Qx ? bT x, 其中 2 ? 0.78 ? 0.02 ? 0.12 ? 0.14 ? ? ?0.02 0.86 ? 0.04 0.06 ? ? Q?? ? ?0.12 ? 0.04 0.72 ? 0.08 ? ? ? 0.06 ? 0.08 0.74 ? ? ?0.14 b ? ? 0.76,0.08,1.12,0.68?
2 T

其最小特征值a ? 0.52, 最大特征值A ? 0.94 ? A?a ? ? ? ? 0.081 ? A? a ? ? 每次迭代将使目标函数的误差减至十分之一以上. 等价于每次迭代将增加大约一位数字的精确度.

k 0 1 2 3 4 5 6

f ?x

(k )

?

0 ? 2.1563635 ? 2.1744062 ? 2.1746440 ? 2.1746585 ? 2.1746595 ? 2.1746595

非二次情形

设 定理: f ( x)存在连续二阶偏导数,x 是局部极小点, Hesse矩阵? 2 f ( x )的最小特征值a ? 0,最大特征值 为A,算法产生的序列? x ( k ) ? 收敛于点x,则目标函 数值的序列 f ? x

?

(k )

??以不大于
2

? A?a ? ? ? ? A? a ? 的收敛比线性的收敛于f ( x )。
A 令r = , 则 a 2 2 条件数 ? A ? a ? ? r ?1 ? ? ? ?? ? ? 1. ? A ? a ? ? r ?1 ?

结论:在相继两次迭代中,梯度方向互相正交.

证明:令

? (? ) ? f ( x ( k ) ? ?d ( k ) )
d ( k ) ? ??f ( x ( k ) ) 为求出从x 出发沿方向d 的极小点,令
(k ) (k )

? ?(?k ) ? ?f ( x ( k ) ? ?k d ( k ) )T d ( k ) ? 0
得 ? ?f ( x ( k ?1) )T ?f ( x ( k ) ) ? 0

即方向d ( k ?1) ? ??f ( x ( k ?1) )与d ( k ) ? ??f ( x ( k ) )正交。

牛顿法
? 基本思想:用一个二次函数去近似目标函数 f(x),然后精确地求出这个二次函数的极小点. ? ----一维搜索函数逼近法中的牛顿法的推广.

设x ( k )是f ( x )的极小点x *的第k次近似,将 f ( x )在x 点作二阶Taylor展开,得
(k )

f ( x ) ? ? ( x ) ? f ( x ( k ) ) ? ?f ( x ( k ) ) T ( x ? x ( k ) ) 1 (k ) T 2 (k ) (k ) ? ( x ? x ) ? f ( x )( x ? x ) 2 为求? ( x )的极小点,令 ?? ( x ) ? ?f ( x ) ? ? f ( x )( x ? x ) ? 0
(k ) 2 (k ) (k )

设? f ( x )可逆,则得
2 (k )

x

( k ?1)

?x

(k )

? ? f ( x ) ?f ( x )。
2 (k ) 2 ( k ) ?1 (k )

( k ) ?1

牛顿 方向

令d

(k )

? ?? f ( x ) ?f ( x )

定理: f ( x )为二次可微函数,x ? E n,x 满足 设
?f ( x ) ? 0,且?2 f ( x ) ?1 存在。又设x (1)充分接近 x,使得存在k1 , k2 ? 0,满足k1k2 ? 1,且对每一个 x ? X ? x x ? x ? x (1) ? x ?2 f ( x ) ?1 ? k1和 x?x

?

?

?f ( x ) ? ?f ( x ) ? ? 2 f ( x )( x ? x )

? k2

成立,则牛顿法产生的序列收敛于x。

证明:牛顿算法映射定义为 A( x) ? x ? ? 2 f ( x) ?1 ?f ( x) 定义解集合? ? {x },令函数? ( x) ? x ? x 。 下证? ( x)是关于解集合?和算法A的下降函数。

令x ? X ,且x ? x,又令y ? A( x )。因为?f ( x ) ? 0 ? y ? x ? x ? ? 2 f ( x) ?1 ?f ( x) ? x ? ( x ? x ) ? ? 2 f ( x) ?1[?f ( x) ? ?f ( x )] ? ? 2 f ( x) ?1[?f ( x ) ? ?f ( x) ? ? 2 f ( x)( x ? x)] ? y ? x ? ? 2 f ( x ) ?1 ?f ( x ) ? ?f ( x ) ? ? 2 f ( x )( x ? x ) ? k1k2 x ? x ? x ? x 因此? ( x)为下降函数。 由定义y ? X , 故迭代产生的序列? x ( k ) ? ? X 。易知 X 为紧集,因此迭代产生的序列含于紧集中。 又算法A在紧集X 上是闭的, 所以迭代产生的序列? x
(k )

? 必收敛于x。

步骤:

1.给定初点x ? E , 允许误差? ? 0, 置k ? 0。
( 0) n

2.若 ?f ( x ) ? ?,则停止计算;否则, 转3。
(k )

3.计算 x
( k ?1)

?x

(k )

? ? f ( x ) ?f ( x ),
2 (k )

( k ) ?1

置k :? k ? 1,返回2。

例: 求 min f ( x) ? x ? 25x
2 1

2 2

解 : 取x ( 0 ) ? (2, 2)T , 则 ? 2 x1 ? ? 4 ? ?f ( x ) ? ? ? ? ? 50x ? x ( 0 ) ? ?100? ? ? ? 2? ?
(0)

x (1)

?1 ? 0? ? 2 0? ? 2 (0) ? ? ? 2 f ( x ( 0 ) ) ?1 ? ? 2 ? f (x ) ? ? ? 0 50? ? 1 ? ? ? ?0 ? 50 ? ? ? x ( 0 ) ? ? 2 f ( x ( 0 ) ) ?1 ?f ( x ( 0 ) ) ?1 ? 0? 2? ? 2 ? ? 4 ? ?0? ?? ? ? ??? ? 2? ? ?100? ? ? 0 ? ? ? ? 1 ?? ? ? 0 ? ? ? ? ? 50 ? ?

2 2 2 例:求 min f ( x ) ? 4 x1 ? x2 ? x1 x2


别取初始点为x A ? (1,1) , xB ? (3, 4) ,
T T

xC ? (2, 0)T , 精度要求? ? 10?3.
2 2 2 解: f ( x ) ? 4 x1 ? x2 ? x1 x2

?f ( x ) ? ? 8 x1 ? 2 x1 x2 , 2 x2 ? x ? 8 ? 2 x2 ? f ( x) ? ? ? ? 2 x1
2

2 1

?

T

? 2 x1 ? ?. 2 ?

1? 取x(1) ? xA ? (1,1)T , 则 ?
k 1 x(k ) 1.0000 1.0000 f ? x(k ) ? 4.000 4.5156 0.1273 0.0003 0.0000 ?f ? x ( k ) ? 6.0000 1.0000 ? 7.8750 ? 3.0625 ? 1.2911 ? 0.3540 ? 0.0459 ? 0.0223 ? 0.0001 ? 0.0000 ?f ? x ( k ) ? 6.0828 8.4495 1.3388 0.0511 0.0001 ?2 f ? x ( k ) ? 6.0000 ? 2.0000 ? 2.000 2.0000 10.500 1.5000 1.5000 2.0000 8.3300 0.3100 0.3100 2.0000 8.0222 0.0115 0.0115 2.0000 8.0000 0.0000 0.0000 2.0000

2 ? 0.7500 ? 1.2500 3 ? 0.1550 ? 0.1650 4 ? 0.0057 ? 0.0111 5 ? 0.0000 ? 0.0000

2? 取x(1) ? xB ? (3,4)T , 则 ?

k 1 2 3

x(k ) 3.0000 4.0000 2.8333 4.0000 2.8284 4.0000

f ? x(k ) ? 16.000 16.0000 16.0000

?f ? x ( k ) ? 0.0000 ? 1.0000 0.0000 ? 0.2078 0.0000 0.0000

?f ? x ( k ) ? 1.0000 0.0278 0.0000

?2 f ? x ( k ) ? 0.0000 ? 6.000 0.0000 ? 5.6667 0.0000 ? 5.6569 ? 6.0000 2.0000 ? 5.6667 2.0000 ? 5.6569 2.0000

? 3? 取x
2

(1)

? xC ? (2,0) , 得到
T (1)

? 8 ? 4? ? f ?x ?=? ? 2? ? ?4 由于Hesse矩阵不可逆,无法进行下一步。
用Newton法求解无约束问题会出现以下情形: (1)收敛到极小点。 (2)收敛到鞍点。 (3)Hesse矩阵不可逆,无法迭代下去。

优点:(1)Newton法产生的点列{x(k)}若收 敛,则收敛速度快---具有至少二阶收敛速率。 (2) Newton法具有二次终止性。 证明 : 设A为对称, 正定矩阵, 且 1 T f ( x) ? x Ax ? bT x ? c 2 ?1 令?f ( x) ? Ax ? b ? 0, 得x* ? ? A b.
若用Newton迭代公式, 从任一点x ( 0)出发, 得 x
(1)

?x

(0)

? ? f ( x ) ?f ( x )
2 (0)

( 0 ) ?1

? x ( 0) ? A?1 ( Ax( 0) ? b) ? ? A?1b ? x * .

缺点:
? (1)可能会出现在某步迭代时,目标函数 值上升. ? (2)当初始点远离极小点时,牛顿法产生 的点列可能不收敛,或者收敛到鞍点,或 者Hesse矩阵不可逆,无法计算. ? (3)需要计算Hesse矩阵的逆矩阵,计 算量大.

阻尼牛顿法

步骤: 1.给定初点 (1) ? E n , 允许误差 ? 0, 置k ? 1 x ? 。 (k ) 2 ( k ) ?1 2.计算?f ( x ),? f ( x ) 。
3.若 ?f ( x ) ? ? , 则停止迭代;否则,令
(k )

d ( k ) ? ??2 f ( x ( k ) ) ?1 ?f ( x ( k ) ). 4.从x ( k )出发,沿方向 ( k )作一维搜索: d

min f ( x ( k ) ? ?d ( k ) ) ? f ( x ( k ) ? ?k d ( k ) ),
?

令x

( k ?1)

?x

(k )

? ?k d

(k )

5.置k :? k ? 1,转2。

用阻尼牛顿法求解下列问题:

min f ( x) ? x14 ? x1x2 ? (1 ? x2 )2
解:取初始点x (1) ? (0, 0)T . ?0? ? 0 1? 2 (1) ?f ( x ) ? ? ? ? f ( x ) ?

? ? 2? ?1 2 ? ? ? ? ? ? 牛顿方向 d (1) ? ?? 2 f ( x (1) ) ?1 ?f ( x (1) )
(1)

? 0 1? ? 0 ? ? ? 2 ? ?? ?1 2 ? ? 2 ? ? ? 0 ? ? ? ? ? ? ? ? ? ? ? ? 从x (1)出发,沿d (1)作一维搜索,令

?1

? (? ) ? f ( x (1) ? ?d (1) ) ? 16?4 ? 1
令 则

? ?(? ) ? 64?3 ? 0 ?=0.

步骤: 1.给定初点 (1) ? E n , 允许误差 ? 0, 置k ? 1 x ? 。 2.计算?f ( x ( k ) ),Gk ? ? 2 f ( x ( k ) )。若 ?f ( x ( k ) ) ? ?,
则停止计算,得点x ;否则转3。 3.置Bk ? Gk ? ? k I , 其中? k 是一个非负数,选取? k,
(k )

修正牛顿法

使得Bk 是对称正定矩阵,计算修正牛顿方向 d ( k ) ? ? Bk ?1?f ( x ( k ) ). 4.从x ( k )出发,沿方向 ( k )作一维搜索: d
min f ( x ( k ) ? ?d ( k ) ) ? f ( x ( k ) ? ?k d ( k ) ),
?

令x ( k ?1) ? x ( k ) ? ?k d ( k )

5.置k :? k ? 1,转2。

共轭方向法
共轭方向
设A是n ? n对称正定矩阵,若 n中的两个方 E 定义: 向d (1)和d ( 2 )满足 (d (1) )T Ad ( 2 ) ? 0 则称这两个方向关于 共轭,或称它们关于 正交。 A A 若d (1) , d ( 2 ) , ? , d ( k )是E n中k个方向,它们俩俩 关于A共轭,即满足 (d ( i ) )T Ad ( j ) ? 0, i ? j , i, j ? 1, ? , k

则称这组方向是 共轭的,或称它们为 的k个共轭方向。 A A

例:

? 1? ?? 3? ?1 ? ?1 ? ? 0? (1) (1) (2) (2) x ?? ? y ?? ? x ?? ? y ?? ? ? 0? ? 0? ?1 ? ? 2? ? ? ? 3? ? 1? ? 1? ? 2 1? (3) (3) x ?? ? y ?? ? A?? 1? ?1? 1 2? ? ? ? ? ? 1? ?? 3? ? 2 1? (1) T (1) 则x Ay ? ?1 0 ? ? ?? 2 ? ? 0 ?1 2 ? ? ? ? ? ? 3?

定理1 设A是n阶对称正定矩阵, (1) , d ( 2) ,?, d ( k ) d

是k个A共轭的非零向量,则这 个向量线性无关。 k
证明: 设存在数?1 , ? 2 , ? ,? k ,使得

?1d (1) ? ? 2 d ( 2) ? ? ? ? k d ( k ) ? 0
左乘d
( i )T

A,
( i )T

因为d (1) , d ( 2 ) , ? , d ( k )是k个A共轭的非零向量, 所以有? i d Ad ( i ) ? 0,
( i )T

又因为A正定,所以d ??i ? 0

Ad

(i )

?0

? d (1) , d ( 2) , ? , d ( k )线性无关。

定理2:设有二次函数

1 T T f ( x) ? x Ax ? b x ? c, 2 (0) (1) ( n ?1) 其中An?n是对称正定矩阵, , d , ?, d d 是A共轭的非零向量,从任 意一点x min f ( x
? ?0
(k ) (0)

?E 出
n

发,依次沿这组向量进 行一维搜索, ? ?d
(k )

) ? f (x

(k )

? ?k d

(k )

)

x ( k ?1) ? x ( k ) ? ?k d ( k ) 则?f ( x
( k ?1) T

k ? 0,1, ?, n ? 1

) d

( j)

? 0, j ? 0,1,?, k。

证明:? ?f ( x) ? Ax ? b
? ?f ( x ( k ?1) ) ? Ax( k ?1) ? b ? A( x ( k ) ? ?k d ( k ) ) ? b ? Ax( k ) ? ?k Ad ( k )

? b ? A( x ( k ?1) ? ?k ?1d ( k ?1) ) ? ?k Ad ( k ) ? b ? Ax( k ?1) ? ?k ?1 Ad ( k ?1) ? ?k Ad ( k ) ? b ? ? ? Ax
( j ?1)

?

i ? j ?1

? ?i Ad ? b ? ?f ( x
(i ) ( j ?1) T

k

( j ?1)

)?

i ? j ?1 ( i )T

?i Ad (i ) ?

k

? ?f ( x 右乘d

( k ?1) T

) ? ?f ( x

) ?

i ? j ?1 ( j)

? ?i d

k

AT
( j)

: ?f ( x

( k ?1) T

) d

( j)

? ?f ( x

( j ?1) T

) d

?

i ? j ?1

? ?i d

k

( i )T

AT d ( j )

? ?f ( x ( j ?1) )T d ( j ) ? 0, d ( 0 ) , d (1) , ? , d ( n ?1)是A共轭的 ? ?f ( x ( k ?1) )T d ( j ) ? 0, j ? 0,1, ? , k .

定理3: 设有二次函数

1 T T f ( x) ? x Ax ? b x ? c, 2 (0) (1) ( n ?1) 其中An?n是对称正定矩阵, , d , ?, d d 是A共轭的非零向量,从任 意一点x ( 0 ) ? E n出 发,依次沿这组向量进 行一维搜索, min f ( x ( k ) ? ?d ( k ) ) ? f ( x ( k ) ? ?k d ( k ) )
? ?0

x ( k ?1) ? x ( k ) ? ?k d ( k )
(n)

k ? 0,1, ?, n ? 1
n

则至多经过n步收敛,即x 是f ( x)在E 上的 极小点.

证明:设x* ? E n是f ( x )在E n上的极小点, 则?f ( x*) ? Ax * ?b ? 0 ? d (0) , d (1) ,? , d ( n ?1)为一组A共轭的非零向量, ? 线性无关,即构成E n的一组基 ? x * ? x (0)可由这组向量线性表出,令 x * ? x (0) ? a0d (0) ? a1d (1) ? ? ? an ?1d ( n ?1) 两边左乘d d
( j )T ( j )T

A:
( j )T

A( x * ? x ) ? a0d
(0)

Ad ? d

(0)

? ? ? an ?1d d
( j )T

( j )T

Ad ( n ?1)

? aj ?

d

( j )T

A( x * ? x )
(0) ( j )T ( j )T

( j )T

( Ax * ? Ax (0) ) Ad ( j )

d ? d

Ad
( j )T

( j)

( ?b ? Ax (0) ) Ad
( j)

d

(1)

另一方面,由x ( k ?1) ? x ( k ) ? ?k d ( k ) , 依次递推得 x
(n)

?x

(0)

? ?0 d
( j )T

(0)

? ?1d
(0)

(1)

? ? ? ?n ?1d d
( j )T

( n ?1)

两边左乘d

A: ?x )
( j)

?j ?
? d

d

( j )T

A( x
( j )T

(n)

?

( Ax ( n ) ? Ax (0) ) d
( j )T

d

Ad
(n)

Ad d

( j) (0)

( j )T

(?f ( x ) ? b ? Ax )
(0) ( j )T ( j)

?

d

( j )T

(? Ax
( j )T

? b)

d Ad 与( )比较,得: 1 a j ? ? j , j ? 0,1,? , n ? 1.

Ad

( j)

? x * ? x (0) ? x ( n ) ? x (0) ? x* ? x ( n ) .

定理(扩张子空间定理,expanding subspace theorem)
1 T 设有函数 f ( x) ? x Ax ? bT x ? c 2 其中A为n阶对称正定矩阵,d (1) , d (2) ,? , d ( k )是A共轭的非零 向量。以任意的x (1) ? E n为初始点,依次沿d (1) , d (2) ,? , d ( k ) 进行一维搜索,得到点x (2) , x (3) ,? , x ( k ?1),则x ( k ?1)是f ( x)在 线性流形 M k x (1) ; ?d (1) , d (2) ,? , d ( k ) ? ? x (1) ? Bk 上的唯一极小点。特别的,当k ? n时,x ( n ?1)是f ( x)在E n 上的唯一极小点。

?

?

k ? ? (1) (i ) ? ? x x ? x ? ? ?i d , ?i ? R ? i ?1 ? ?

证明

:由于f ( x )是严格凸函数,所以对?y ? M k , 有 f ( y ) ? f ( x ( k ?1) ) ? ?f ( x ( k ?1) )T ( y ? x ( k ?1) ).
( k ?1)

? y, x

? M k ,? 可设y ? x

(1)

? ? ?i d , x
(i ) i ?1

k

( k ?1)

?x

(1)

? ? ?i d ( i )
i ?1

k

f ( y ) ? f ( x ( k ?1) ) ? ?f ( x ( k ?1) )T ( x (1) ? x ( k ?1) ) ? ? ?i ??f ( x ( k ?1) )T d ( i ) ? ? ?
i ?1

k

? f (x

( k ?1)

) ? ? ?i ??f ( x ?
i ?1

k

( k ?1) T

) d ? ? ? ?i ??f ( x ( k ?1) )T d ( i ) ? ? ? ?
(i ) i ?1

k

若能证明?f ( x ( k ?1) )T d ( i ) ? 0,则x ( k ?1)是M k的极小点。

要证明x( k ?1)是f ( x)在x (1) ? Bk 上的唯一极小点,只 需证明在x( k ?1)处,?f ( x( k ?1) )与子空间Bk 正交。

k ? 1时,由一维搜索定义知?f ( x (2) ) ? B1. 假设k ? m ? n时,?f ( x ( m ?1) ) ? Bm , 下证?f ( x ( m ? 2) ) ? Bm ?1。 注意?f ( x ( m ? 2) ) ? Ax ( m ? 2) ? b, x ( m ? 2) ? x ( m ?1) ? ?m ?1d ( m ?1) ??f ( x ( m ? 2) ) ? Ax ( m ? 2) ? b ? A( x ( m ?1) ? ?m ?1d ( m ?1) ) ? b ? ?f ( x ( m ?1) ) ? ?m ?1 Ad ( m ?1) ? d (i )T ?f ( x ( m ? 2) ) ? d (i )T ?f ( x ( m ?1) ) ? ?m ?1d (i )T Ad ( m ?1) 当i ? m ? 1,由一维搜索定义有d (i )T ?f ( x ( m ? 2) ) ? 0, 当1 ? i ? m,由归纳假设,有d (i )T ?f ( x ( m ?1) ) ? 0。 由于d (1) , ,d ( m ?1)关于A共轭,因此有 ? d (i )T Ad ( m ?1) ? 0 ? d (i )T ?f ( x ( m ? 2) ) ? 0 ? ?f ( x ( m ? 2) ) ? Bm ?1.

当k ? n时,d (1) , d (2) ,? , d ( n )是E n的一组基, 若?f ( x ( n ?1) ) ? 0,令 ?f ( x ( n ?1) ) ? ?1d (1) ? ? 2 d (2) ? ? ? ? n d ( n ) 两边左乘?f ( x ( n ?1) )T , 得 ?f ( x ( n ?1) )T ?f ( x ( n ?1) ) ? ?1?f ( x ( n ?1) )T d (1) ? ? ? ? n?f ( x ( n ?1) )T d ( n ) ? ?f ( x ( n ?1) )T ?f ( x ( n ?1) ) ? 0,矛盾, 所以,?f ( x ( n ?1) ) ? 0, 即x ( n ?1)是函数f ( x)在E n上的唯一极小点。

从任意点出发,依次 共轭方向法 沿某组共轭方向进行 一维搜索求解非线性 步骤(适用于正定二次函数) 规划问题的方法。

1.给定初始点 (0) ? E n,选定下降方向 (0),令k ? 0。 x d

2.从x ( k )出发,沿d ( k )方向进行一维搜索,求 k: ? min f ( x ( k ) ? ?d ( k ) ) ? x ( k ) ? ?k d ( k ) 令x ( k ?1) ? x ( k ) ? ?k d ( k ),计算?f ( x ( k ?1) ).

3.若 ?f ( x

( k ?1)

) ? 0,则停止迭代,否则转 4。
( k ?1)

4.选定共轭方向d d
( j )T

,使满足

Ad ( k ?1) ? 0, j ? 0,1, ? , k .

令k ? k ? 1,返回2。

d ( k )T ( Ax (0) ? b) ?f ( x ( k ) )T d ( k ) ? ? ( k )T ( k ) . 结论:?k ? ? ( k )T (k ) d Ad d Ad
证明: x ( k ?1) ? x ( k ) ? ?k d ( k

),则有 设
0 ? ?f ( x
T

( k ?1) T

) d

(k )

?d

( k )T

?f ( x

( k ?1)

)?d

( k )T

( Ax( k ?1) ? b) Ad ( k )

? d ( k ) ( Ax( k ) ? ?k Ad ( k ) ? b) ? ?k ? ? 又由0 ? d ?d
( k )T ( k )T

?f ( x ( k ) )T d ( k ) d
( k )T

( Ax( k ) ? ?k Ad ( k ) ? b) ? b) ? ??k d
k ?1 i ?0 ( k )T

( Ax

(k )

Ad ( k )

将x ( k ) ? x ( 0) ? ? ?i d (i ) 代入上式,且 (i )共轭,得 d d ( k ) ( Ax( 0) ? b) ? ??k d ( k ) Ad ( k ) ? ?k ? ?
T T

d

( k )T

( Ax( 0) ? b) Ad ( k )

d

( k )T

共轭方向法
步骤(适用于正定二次函数)

1.给定初始点 (0) ? E n,选定下降方向 (0),令k ? 0。 x d

2.计算?k ? ? 令x
( k ?1)

d

( k )T

( Ax

(0)

? b)

Ad ( k ) (k ) (k ) ( k ?1) ? x ? ?k d ,计算?f ( x ). d
( k ?1)

( k )T

,

3.若 ?f ( x

) ? 0,则停止迭代,否则转 4。
( k ?1)

4.选定共轭方向d d
( j )T

,使满足

Ad ( k ?1) ? 0, j ? 0,1, ? , k .

令k ? k ? 1,返回2。

共轭方向法
步骤(适用于正定二次函数)

1.给定初始点 (0) ? E n,选定下降方向 (0),令k ? 0。 x d

2.计算?k ? ? 令x ( k ?1)

?f ( x ( k ) )T d ( k )
( k )T (k )

,

d Ad ? x ( k ) ? ?k d ( k ),计算?f ( x ( k ?1) ).
( k ?1)

3.若 ?f ( x

) ? 0,则停止迭代,否则转 4。
( k ?1)

4.选定共轭方向d d
( j )T

,使满足

Ad ( k ?1) ? 0, j ? 0,1, ? , k .

令k ? k ? 1,返回2。

1 2 1 2 例: min x ? x2 ? x3 2 2
2 1

A ? diag(2, 1, 1), x ( 0) ? (1, 1, 1)T , d ( 0) ? (?1, ? 2, 0)T , ?f ? (2 x1 , x2 , x3 )T
k 0 1 2 3 x(k ) (1, 1, 1)
T

d (k ) (?1, ?2, 0)
T T

?f ( x ( k ) ) (2, 1, 1)
T

?k
2 3
T

?1 1 ? ? , ? , 1? ?3 3 ?

(1, ?1, 0) (0, 0, 1)

T

?2 1 ? ? , ? , 1? ?3 3 ?
T

1 ? 3 ?1

? 0, 0, 1? T ? 0, 0, 0 ?
T

T

? 0, 0, 1? T ? 0, 0, 0 ?

共轭梯度法(Conjugate Gradient Method)(FR法)
记号: ?f ( x
(k )

) ? gk

在共轭梯度法中,初始点处的搜索方向取 为该点的负梯度方向,即取

d (1) ? ??f ( x(1) ) ? ? g1
而以下各共轭方向d(k)由第k次迭代点x(k)处的负梯 度-gk与已经得到的共轭向量d(k-1)的线性组合来确定。

选取初始点x (1),取d (1) ? ? g1 , 从x (1)出发,沿d (1)做一维搜索,

1 T T min f ( x) ? x Ax ? b x ? c 2
?1 ? ?
?f ( x (1) )T d (1)
(1)T (1)

?

g1 g1
(1)T

T

当x (1)

d Ad d Ad ? x *时, g1 ? 0 ? ?1 ? 0。

, x ( 2 ) ? x (1) ? ?1d (1) (1)

若x ( 2 ) ? x * (否则迭代终止),则 2 d (1) ? 0 ? g 2与d (1)线性无关。 g
T

令d ( 2 ) ? ? g 2 ? ?1d (1) 用d
(1)T

A左乘上式,并令 d
(1)T

(1)T

Ad ( 2 ) ? 0,得 d
(1)T

d Ad d Ad (1) 从x ( 2)出发,沿d ( 2 )做一维搜索,得

?1 ?

d

Ag2
(1)

(1)T

?d

( 2)

? ?g2 ?

Ag2

(1)T

d (1)

?2 ? ?

?f (

x ) d
( 2) T

( 2)

d

( 2 )T

Ad

( 2)

?

g 2 g 2 ? ?1?f ( x ) d
T ( 2) T

(1)

d

( 2 )T

Ad

( 2)

? d

g2 g2
( 2 )T

T

Ad ( 2 )

以此类推,得

d

(k )

? ? g k ? ? k ?1d d
( k ?1)T

( k ?1)

? k ?1 ?
x
( k ?1)

Agk
( k ?1)

d Ad (k ) (k ) ? x ? ?k d gk gk
T ( k )T

( k ?1)T

?k ?

d

Ad

(k )

定理:对正定二次函数,FR法在m ? n次一维搜索后终止, 且对?i (1 ? i ? m), 下列关系式成立: (1) d
( i )T

Ad
(i )

( j)

? 0, j ? 1, 2,? , i ? 1;
T (i )

d ( k ) ? ? g k ? ? k ?1d ( k ?1)

(2) giT g j ? 0, j ? 1, 2,? , i ? 1; (3) gi d
T

? ? g i g i .(蕴含d

? 0)

? k ?1 ?

d d

( k ?1)T

Ag k

( k ?1)T

Ad ( k ?1)

证明:(用归纳法) i ? 1时,g1 ? ?f ( x (1) ), d (1) ? ? g1 ,? (3)成立。 i ? 2时,由构造法,d
(2)T (1)

Ad

? 0,即(1)成立。

由一维搜索性质,?f ( x (2) )T d (1) ? 0,而 d (1) ? ? g1 ? g 2T g1 ? 0 ? (2)成立。 ? d (2) ? ? g 2 ? ?1d (1) ? g 2T d (2) ? g 2T (? g 2 ? ?1d (1) ) ? ? g 2T g 2 ? (3)成立。

假设对某个3 ? i ? m, (1), (2), (3)均成立,下证对 ? 1也成立。 i 先证(2) (2) x (i ?1) ? x (i ) ? ?i d (i )

?f ( x (i ?1) ) ? Ax (i ?1) ? b ? Ax (i ) ? ?i Ad (i ) ? b ? ?f ( x (i ) ) ? ?i Ad (i ) 即gi ?1 ? gi ? ?i Ad
(i )

giT gi 归纳假设 ? giT d (i ) 其中?i ? (i )T (i ) ? ?0 ( i )T (i ) d Ad d Ad ? gi ?1T g j ? ? giT ? ?i d (i )T AT ? g j ? gi g j ? ?i d
T T ( i )T ( i )T

(1) d

( i )T

Ad ( j ) ? 0

(2) gi T g j ? 0 (3) gi T d ( i ) ? ? gi T gi .
d ( k ) ? ? g k ? ? k ?1d ( k ?1)

A ? ?d Ad
( j)

( j)

? ? j ?1d

( j ?1)

?
( j ?1)

? gi g j ? ?i d

? ?i ? j ?1d

( i )T

Ad

? k ?1 ?

d d

( k ?1)T

Ag k

( k ?1)T

i? j ?0 ? ?? T gi g j ? giT g j ? ?i ? j ?1d (i )T Ad ( j ?1) ? 0 i ? j ? ?

Ad ( k ?1)

(1) d ( i ?1) ? ? gi ?1 ? ?i d ( i ) d
( i ?1)T

Ad

( j)

? ? ? gi ?1 ? ?i d

(i ) T

?

Ad ( j ) ? ? g i ?1T Ad ( j ) ? ?i d ( i )T Ad ( j )

d (i )T Agi ?1 若i ? j ,由?i ? ( i )T ( i ) ? d ( i ?1)T Ad ( i ) ? 0,以下假设i ? j。 d Ad ? gi ?1 ? gi ? ( Ax ( i ?1) ? b ? ( Ax ( i ) ? b)) ? A( x ( i ?1) ? x ( i ) ) ? A( x ( i ) ? ?i d ( i ) ? x ( i ) ) ? ?i Ad (i ) ( i )T (1) d Ad ( j ) ? 0 gi ?1 ? gi (i ) ? Ad ? (2) g T g ? 0

?i

i

j

?d ??

( i ?1)T

Ad
T i ?1

( j)

? ?g

T i ?1

g j ?1 ? g j

?j

? ? i d (i )T Ad ( j )

(3) gi T d ( i ) ? ? gi T gi .

1

?j

g

g j ?1 ?

1

?j

gi ?1T g j ? ?i d (i )T Ad ( j ) ? 0

(3) g ? ?g ?g

T i ?1 T i ?1

d

( i ?1)

?g
T i ?1

T i ?1

?? g
d
i (i )

i ?1

? ?i d

(i )

?
(1)

g i ?1 ? ? i g

(i )

T i ?1

d

?g d

?? g

T i ?1

? ? i ?1d

( i ?1)

?
d

? ? i ?1 g ?g
T i ?1

T i ?1

( i ?1) T i ?1

? ? ? ? i ?1 ? ?1 g (? g1 ) ? 0
T i ?1

T i ?1

? ? i ?1 ? ?1 g d
( i ?1)

? ?g
( k ?1)T

g i ?1.

(1) d

( i )T

Ad ( j ) ? 0

d

(k )

? ? g k ? ? k ?1d d d Ag k
( k ?1)T

( k ?1)

(2) gi T g j ? 0 (3) gi T d ( i ) ? ? gi T gi .

? k ?1 ?

Ad ( k ?1)

gi ?1 d Agi ?1 (i ? 1, gi ? 0). 定理: ?i ? (i )T (i ) ? 2 d Ad gi

( i )T

2

证明:由Ad 1

( j)

?

1

?j
T

?g

j ?1

? g j ?得 g i ?1 ? g i g i ?1
T

?i ?

?i
d

?g i ?1 ? g i ?
1

g i ?1 ?

g d

(i )T

?i

?g i ?1 ? g i ?
2

T i ?1 (i )T

g i ?1 ? d

(i )T

gi
Ad ( j ) ? 0

g i ?1 g i ?1 ? ? 2 g gi gi g

T i ?1 T i

(1) d

( i )T

(2) gi T g j ? 0 (3) gi T d ( i ) ? ? gi T gi .

步骤(FR共轭梯度法)

1.给定初始点x ,置k ? 1 。
(1)

2.计算g k ? ?f ( x ( k ) ),若 g k ? 0,则停止计算,得点 x ? x ;否则进行下一步。
(k )

3.令d

(k )

? ? g k ? ? k ?1d

( k ?1)

,其中,当k ? 1时, gk g k ?1
2 2

? k ?1 ? 0,当k ? 1时,? k ?1 ?
4.令x
( k ?1)


gk d
T (k ) ( k )T

?x

(k )

? ?k d ,其中?k ? ?
(k )

d

Ad ( k )



5.若k ? n,则停止计算,得点 ? x x k ? k ? 1,返回2。

( k ?1)

;否则,置

例:

1 2 1 2 min x ? x2 ? x3 2 2
2 1
T (1) T

解:?f ( x) ? (2x1, x2 , x3 ) , 取x ? (1,1,1) .
k 1 2 3 x(k ) gk
T

? k ?1
T

d (k ) ? (2, 1, 1)
T

?k
3 5 5 6

?1, 1, 1?

(2, 1, 1)
T

0
T

? 1 2 2? ?? , , ? ? 5 5 5? (0, 0, 0)T

? 2 2 2? ?? , , ? ? 5 5 5?

2 25

6 (1, ? 2, ? 2)T 25

例:

1 2 1 2 min x ? x2 ? x3 2 2
2 1
(1)

A ? diag (2, 1, 1), x (1) ? (1, 1, 1)T , d ? (?1, ? 2, 0) , ?f ? (2 x1 , x2 , x3 )
T
(1)

T

2 从x 出发,沿方向d 做一维搜索,得?1 ? , 3
(1)

?1 1 ? ?2 1 ? ? x ? x ? ?1d ? ? , ? ,1? , g 2 ? ? , ? ,1? . ?3 3 ? ?3 3 ? d (1)T Ag 2 1 (2) (1) 令d ? ? g 2 ? ?1d ,其中?1 ? (1)T (1) ? ? d Ad 9
(2) (1) (1)

T

T

? d

(2)

? 5 5 ? ? ? ? , , ?1 ? ? 9 9 ?

T

21 从x 出发,沿方向d 做一维搜索,得?2 ? , 26
(2) (2)

? x

(3)

?x

(2)

? ?2 d

(2)

? 9 9 5 ? ? ?? , , ? , ? 78 78 26 ?
T

T

? 18 9 5 ? g3 ? ? ? , , ? . ? 78 78 26 ? d (2)T Ag3 45 (3) (2) 令d ? ? g3 ? ? 2 d ,其中? 2 ? (2)T (2) ? d Ad 676 1 T (3) ? d ? ?131, ?53, ?175? 676

结论:d 与d 关于A共轭,d 与d 关于A共轭,
(1) (2) (2) (3)

但d 与d 关于A不共轭。
(1) (3)

用于一般函数的共轭梯度法
与原方法的主要区别:
d Ad 必须用其他一维搜索方 法来确定。
矩阵? 2 f ( x ( k ) )代替。

(1) 步长

?k 不能再用公式 k ? ? ?

gk d
( k )T

T

(k ) (k )

计算,

(2) 凡用到矩阵A之处,需用现行点处的 Hession

(3) 有限步迭代达不到极小 点。

迭代的延续方法:

(1) 直接延续:即总用公式 d 构造搜索方向。

( k ?1)

? ? g k ?1 ? ? k d

(k )

(2) 重新开始,把 步作为一轮,每搜索一 n 轮之后, 取一次最速下降方向, 开始下一轮。

计算参数? k的常用公式: ?f ( x ( k ?1) )T ?f ( x ( k ?1) ) ?k ? ? f ( x ( k ) )T ? f ( x ( k ) ) Fletcher ? Re eves ( FR ) Polak ? Ribiere ? Polyak ( PRP ) Crowder ? Wolfe Daniel Dixon Dai ? Yuan

?k ? ?k ?

?f ( x ( k ?1) )T ? ?f ( x ( k ?1) ) ? ?f ( x ( k ) ) ? ?f ( x ) ?f ( x )
(k ) T (k )

?f ( x ( k ?1) )T ? ?f ( x ( k ?1) ) ? ?f ( x ( k ) ) ? d
( k )T

? ?f ( x

( k ?1)

) ? ?f ( x ) ?
(k )

?f ( x ( k ?1) )T ? 2 f ( x ( k ?1) )d ( k ) ?k ? d ( k )T ? 2 f ( x ( k ?1) )d ( k ) ?f ( x ( k ?1) )T ?f ( x ( k ?1) ) ?k ? d ( k ) T ?f ( x ( k ) ) ?f ( x ( k ?1) )T ?f ( x ( k ?1) ) ? k ? ( k )T d ? ?f ( x(k ?1) ) ? ?f ( x(k ) ) ?

步骤(FR共轭梯度法)

1.给定初始点x ,允许误差? ? 0,置y
(1)

(1)

?x ,
(1)

d (1) ? ??f ( y (1) ), k ? j ? 0。 2.若 ?f ( y ( j ) ) ? ? , 则停止计算;否则作一 维搜索,求? j
满足f ( y ( j ) ? ? j d ( j ) ) ? min f ( y ( j ) ? ?d ( j ) ), 令y ( j ?1) ? y ( j ) ? ? j d ( j )。 3.若j ? n,则转4,否则转 。 5 ( j ?1) 2 ?f ( y ) ( j ?1) ( j ?1) ( j) 4.令d ? ??f ( y ) ? ? jd , ? j ? , 2 ?f ( y ( j ) )
置j ? j ? 1,转2。 5.令x ( k ?1) ? y ( n?1) , y (1) ? x ( k ?1) , d (1) ? ??f ( y (1) ), j ? 1

k ? k ? 1,返回2。

变尺度法(Variable Metric Method) 拟牛顿法(Quasi-Newton Method)
这是一种求解无约束极值问题的有效算法, 由于它既避免了计算二阶导数、矩阵及其求逆 过程,又比最速下降法的收敛速度快,特别是 对高维问题具有显著的优越性,所以,它被 公认为求解无约束极值问题最有效的算法之一。

牛顿法的缺点:
? (1)可能会出现在某步迭代时,目标函数 值上升. ? (2)当初始点远离极小点时,牛顿法产生 的点列可能不收敛,或者收敛到鞍点,或 者Hesse矩阵不可逆,无法计算. ? (3)需要计算Hesse矩阵,计算量大.

基本原理:
x ( k ?1) ? x ( k ) ? ?k d ( k )
阻尼牛顿法:

d ( k ) ? ?? 2 f ( x ( k ) ) ?1 ?f ( x ( k ) )

?k ? ? ? ?最佳步长。
为了避免计算 2 f ( x ( k ) ) ?1,设法构造另一个矩阵 k,用 ? H 它直接逼近? f ( x ) 。 要求:
2 ( k ) ?1

(1)每一步都能以现有的信 息来确定下一个搜索方 向。 (2)每一次迭代,目标函数 值均有所下降。

(3) H k ? ? 2 f ( x ( k ) ) ?1.

设在第k次迭代后,得到点x ( k ?1) . f ( x) ? f ( x
( k ?1)

) ? ?f ( x

( k ?1) T

) (x ? x

( k ?1)

1 ) ? ( x ? x ( k ?1) )T ?2 f ( x ( k ?1) )( x ? x ( k ?1) ) 2

? 在x ( k ?1)附近有 ?f ( x ) ? ?f ( x ( k ?1) ) ? ?2 f ( x ( k ?1) )( x ? x ( k ?1) ) 令x ? x ( k ),则有 ?f ( x ( k ) ) ? ?f ( x ( k ?1) ) ? ?2 f ( x ( k ?1) )( x ( k ) ? x ( k ?1) ) 记p ( k ) ? x ( k ?1) ? x ( k ) , q( k ) ? ?f ( x ( k ?1) ) ? ?f ( x ( k ) ) ? q ( k ) ? ?2 f ( x ( k ?1) ) p ( k ) 设?2 f ( x ( k ?1) )可逆,则 p ( k ) ? ?2 f ( x ( k ?1) ) ?1 q( k ) 处的Hesse矩阵的逆矩阵。 令p ( k ) ? H k ?1q ( k ) (*) ? 计算出p ( k )和q( k )后,可以根据(*)估计在x ( k ?1)

拟牛顿 条件

拟牛顿法步骤

1.给定初始点x(0),正定矩阵H 0,允许误差? ? 0; 计算g0 ? ?f ( x(0) ), 置k ? 0。
2.若 g k ? ? , 则停止计算;否则,计算搜索方向 d ? ? H k gk。
k

3.作一维搜索,求?k , 满足 f ( x ( k ) ? ?k d ( k ) ) ? min f ( x ( k ) ? ? d ( k ) ), 令x ( k ?1) ? x ( k ) ? ?k d ( k )。

4.计算g k ?1 ? ?f ( x

( k ?1)

),并且对矩阵H k 进行校正,

得到H k ?1,使之满足拟牛顿条件;令k ? k ? 1,返回2。

秩1校正
一般策略: H1取为任一个n阶对称正定矩阵,

通过修正H k 给出H k ?1。

令 H k ?1 ? H k ? ?H k
确定?H k的方法之一:令 ?H k ? ? k Z Z
(k ) ( k )T

校正 矩阵

其中? k 为常数,Z ( k )为n维列向量, ? ?H k 是秩为 的对称矩阵,Z ( k )的选取应使 1 拟牛顿条件成立,即 ( k ) ? H k ?1q ( k ) . p

? p ( k ) ? H k q ( k ) ? ? k Z ( k ) Z ( k )T q ( k ) ? Z (k ) p(k ) ? H k q(k ) ? ? k Z ( k )T q ( k )

(1)

另一方面, 式两端左乘q ( k )T (1) q ( k )T ? p ( k ) ? H k q ( k ) ? ? ? k ( Z ( k )T q ( k ) ) 2 ??H k ? ? k Z Z
(k ) ( k )T

p
? Hkq
(k )

(k )

? Hk ?1q
(k ) T

(k )

? ?k

?p

(k )

??p

(k )

? Hkq
(k )

?

? k Z ( k )T q ( k )
(k ) T

? k Z ( k )T q ( k )
(k )

?p ?

(k )

? Hkq

(k )

?? p
( k )T (k )

(k )

? Hkq

?

? k (Z

q )

(k ) 2

?p ?

? Hkq q
( k )T (k ) T

p(k ) ? H k q(k ) ? ?

?? p

(k )

? Hkq

(k ) T

?

? H k ?1 ? H k

?p ?

? Hkq q
( k )T

(k )

?p

?? p

(k )

(k )

? H k q(k ) ?

? Hkq

?

1.给定初始点x(0),正定矩阵H 0,允许误差? ? 0; 计算g0 ? ?f ( x ), 置k ? 0。 2.若 g k ? ? , 则停止计算;否则,计算搜索方向
(0)

拟牛顿法步骤

d k ? ? H k gk。 3.作一维搜索,求?k , 满足

f ( x ( k ) ? ?k d ( k ) ) ? min f ( x ( k ) ? ? d ( k ) ), 令x ? x ? ?k d 。 4.计算g k ?1 ? ?f ( x ( k ?1) ), p ( k ) ? x ( k ?1) ? x ( k ) , q (

k ) ? g k ?1 ? g k ,
( k ?1) (k ) (k )

H k ?1 ? H k

?p ?

(k )

? Hk q

(k )

q ( k )T ? p ( k ) ? H k q ( k ) ?

?? p

(k )

? Hkq

(k ) T

?

令k ? k ? 1,返回2。

DFP算法(变尺度法) 定义:

?H k ?

p p

(k )

p

( k )T (k ) (k )

( k )T

? p

Hkq q q
( k )T (k ) ( k )T

(k )

( k )T

Hk
( k )T

q

H k q(k )
(k )

H k ?1 ? H k ?
DFP公式

p

p

( k )T

?

Hkq q q
( k )T

Hk

q

Hkq

(k )

DFP法计算步骤:

1.给定初始点 (1),计算误差 ? 0。 x ? 2.置H1 ? I,计算g1 ? ?f ( x(1) ),置k ? 1 。
3.令d (k ) ? ?Hk gk .
4.从x ( k )出发,沿d ( k )做一维搜索: ( x ( k ) ? ?k d ( k ) ) ? min f ( x ( k ) ? ?d ( k ) ) f 令x ( k ?1) ? x ( k ) ? ?k d ( k )。

5.若 ?f ( x ( k ?1) ) ? ?,则停止迭代,得点 x ? x ( k ?1);否则转 6。

6.若k ? n,则令x(1) ? x( k ?1),返回2;否则,进行 。 7
7.令g k ?1 ? ?f ( x ( k ?1) ), p k ? x ( k ?1) ? x ( k ) , q k ? ?f ( x ( k ?1) ) ? ?f ( x ( k ) ), H k ?1 ? H k ? 置k ? k ? 1,返回3。 p
(k ) ( k )T (k ) ( k )T

p

p

( k )T

?

Hkq q q
( k )T

(k )

Hk

q

Hkq

(k )

,

例: 用DFP方法求解下列问题:

min 2x ? x ? 4x1 ? 2 T 解:?f ( x) ? ? 4 x1 ? 4, 2 x2 ?
2 1 2 2

初始点和初始矩阵分别取为: x
(1)

? (2, 1) , H1 ? I
T

第 一 次 迭 代

在点x 处的梯度为g1 ? ? 4, 2 ? ,
(1) T

令搜索方向 d
(1)

(1)

? ? H1 g1 ? ? ?4, ?2 ?
(1)

T

5 从x 出发,沿方向d 做一维搜索,得?1 ? , 18 ? x
(2)

? x ? ?1d
(1)

(1)

?8 4? ? 4 8? ? ? , ? , g2 ? ? ? , ? . ?9 9? ? 9 9?

T

T

第二次迭代

? 10 5 ? ? 40 40 ? (1) p ? ?1d ? ? ? , ? ? , q ? g 2 ? g1 ? ? ? , ? ? 9? 9 ? ? 9 ? 9 1 ? 86 ? 38 ? H2 ? p k ? x ( k ?1) ? x ( k ) , ? ? 360 ? ?38 305 ? q k ? ?f ( x ( k ?1) ) ? ?f ( x ( k ) ), 12 ? 1 ? (2) 令 d ? ? H 2 g2 ? ? ? 51 ? ?4 ? 17 (2) (2) 从x 出发,沿方向d 进行一维搜索,得?2 ? , 36 ? x (3) ? x (2) ? ?2 d (2) ? (1, 0)T
(1) (1)

T

T

此时,g3 ? (0, 0) ,? x
T

(3)

? (1, 0) 为最优解。
T

例: 用共轭梯度法求解下列问题:

min 2x ? x ? 4x1 ? 2
2 1 2 2

? 4 0? 解:?f ( x) ? ? 4 x1 ? 4, 2 x2 ? A?? ? ?0 2? 初始点和初始矩阵分别取为:x (1) ? (2, 1)T
T

第 一 次 迭 代

在点x 处的梯度为g1 ? ? 4, 2 ? ,
(1) T

令搜索方向 d
(1)

(1)

? ? g1 ? ? ?4, ?2 ?
(1)

T

5 从x 出发,沿方向d 做一维搜索,得?1 ? , 18 ? x
(2)

? x ? ?1d
(1)

(1)

?8 4? ? 4 8? ? ? , ? , g2 ? ? ? , ? . ?9 9? ? 9 9?

T

T

第二次迭代

g2 ? 4 8? g 2 ? ? ? , ? , ?1 ? ? 9 9? g1 令 d
(2) (2)

T

2 2

4 ? 81

? ? g 2 ? ?

1d

(1)

20 ? 1 ? ? ? ? 81 ? ?4 ?

9 从x 出发,沿方向d 进行一维搜索,得?2 ? , 20 (3) (2) (2) T ? x ? x ? ?2 d ? (1, 0)
(2)

此时,g3 ? (0, 0)T ,? x (3) ? (1, 0)T 为最优解。

DFP算法(变尺度法)

?H k ?

p p

(k )

p

( k )T (k ) (k )

( k )T

? p

Hkq q q
( k )T (k ) ( k )T

(k )

( k )T

Hk
( k )T

q

Hkq q

(k )

H k ?1 ? H k ?

p

p

( k )T

?

Hkq q
( k )T

(k )

Hk

q

H k q(k )

定理:设矩阵H k 是正定对称矩阵,且p

( k )T

q( k ) ? 0,

则由DFP公式构造的H k +1是正定对称的。

证明:由于p q
( k )T

( k )T

q ( k ) ? 0,所以q ( k ) ? 0,由H k的正定性,得到
T (k ) 2

H k q ( k ) ? 0, 所以DFP公式有意义。对?x ? 0, 考察
T

x H k ?1 x ? x
T

?x H x?
k

p

p

( k )T

q

(k )

? ? ?x
q
T k

T

Hkq

(k ) 2

?

( k )T

?

?x

T

Hk x? q

?

( k )T

Hkq
( k )T

(k )

q
T

Hkq

? ? ?x H q ? ? ?x
(k ) 2 (k )

H k q( k )

T

p

(k ) 2

?

p

( k )T

q( k )

由Cuachy ? schwarz不等式,知

?x

Hk x? q

?

( k )T

Hkq

(k )

? ? ?x H q ?
T k

(k ) 2

且等式成立当且仅当存在? ? 0,使得x ? ? q ( k ) ? x T H k ?1 x ? 0 ? H k ?1正定。

推论:若d ( k )是下降方向,且一维搜索是精确的, 并设H k 是正定对称矩阵,则H k ?1也是正定对称阵. 证明:因为一维搜索是精确的,所以有
?f ? x
( k ?1) T

?

d

(k )

?0

而且步长?k ? 0. 由于 p ( k ) ? x ( k ?1) ? x ( k ) ? x ( k ) ? ?k d ( k ) ? x ( k ) ? ?k d ( k ) ? ?f ? x ?p
( k )T ( k ?1) T

?

p(k ) ? 0

q

(k )

?p

( k )T

?

?f ? x ( k ?1) ? ? ?f ? x ( k ) ?
( k )T

?

? ?p

( k )T

?f ? x

(k )

? ? ??k d

?f ? x ( k ) ? ? 0,

由定理知,H k +1是正定的。

定理:设初始矩阵H1是正定对称矩阵,且一维搜索 是精确的,若gk ? ?f ? x ( k ) ? ? 0,则产生的搜索方 向d ( k )是下降方向. 证明:用归纳法证明g k T d ( k ) ? 0.
当k ? 1时,H1正定,因此 g d
T 1 (1)

? ? g H1 g1 ? 0.
T 1

d

(k )

? ? H k gk .

假设当k ? m时,命题为真, 即g mT d ( m ) ? 0, 由推论,H m ?1正定,因此有 g m ?1T d ( m ?1) ? ? g m ?1T H m ?1 g m ?1 ? 0, 即当k ? m+1时,命题为真.

定理:用DFP算法求解正定二次函数 1 T T f ( x ) ? x Ax ? b x ? c, 2 若一维搜索是精确的,假设已进行了m 次迭代,则 (1)搜索方向d (1) ,? , d ( m )是m个非零的关于A 共轭的方向; (2)对于j ? 1, 2,?, m, 有 H m ?1q 其中p
(i ) ( j)

?p

( j)

且当m ? n时,有 ?x
( i ?1)

H m ?1 ? A?1.
(i )

?x

? ?i d .
(i)

证明:由算法知,d (1) ,? , d ( m )是非零的。 用数学归纳法证明 ? p Ap ? 0, 1 ? j ? i ? m ? ? ( j) ( j) 1 ? j ? m. ? H m ?1 Ap ? p

? 当m ? 1时,有
( i )T ( j) (1) (1)T (1) (1)T (1)

d ( k ) ? ?Hk gk

() p(i ) ? ?i d i

? p p H1q q H1 ? (1) H 2 Ap = ? H1 ? (1)T (1) ? (1)T Ap (1) ? ? ? p q q H1q ? ? 由于 Ap ( i ) ? A ? x ( i ?1) ? x ( i ) ? ? gi ?1 ? gi ? q ( i ) 所以 H 2 Ap (1) =p (1) . 当m ? 2时,有 p
(2)T

Ap

(1)

? ?2d

(2)T

Ap

(1)

? ??2 ? H 2 g 2 ? Ap (1)
T

? ??2 g 2T H 2 Ap (1) ? ??2 g 2T p (1) ? ??1?2 g 2T d (1) ? 0

由拟牛顿条件,得 而

H 3q(2) ? p (2) ,
(2) (2)T (2) (2)T

Ap (2) ? q(2) , 所以, H 3 Ap (2) =p (2) .
(1)

? p p H1q q H 2 ? (1) 又H 3 Ap = ? H 2 ? (2)T (2) ? (2)T Ap (2) ? ? ? p q q H 2q ? ? ? H 2 Ap ?
(1)

p p p
(2) (2)T

(2)

(2)T
T

Ap
(2)

(1)

(2)

q

?

H1q q q
(1)

(2) (2)T (2)T

H 2 Ap

(1)

H 2 q(2)

?p ?
(1)

H1q

? Ap ?
H 2q

(2) T (2)

p

(1)

q

?p .

? p Ap ( j ) ? 0, ? ? ( j) ( j) ? H m?1 Ap ? p . ? (i ) (i ) Ap ? q
( i )T

? p Ap ( j ) ? 0, 1 ? j ? i ? k ? 1 ? 假设m ? k ? 1时,有 ? ( j) ( j) 1 ? j ? k ? 1. ? H k Ap ? p ? 当m ? k时,对1 ? j ? k ? 1
( i )T

p

( k )T

Ap

( j)

? ?k d

( k )T

Ap

( j)

? ??k ? H k g k ? Ap
T

( j)

T T T ? ??k g k H k Ap ( j ) ? ??k g k p ( j ) ? ??k ? j g k d ( j ) ? 0.

对1 ? j ? k , ? p p Hk q q Hk ? ( j) H k ?1 Ap ? ? H k ? ( k )T ( k ) ? ( k )T Ap (k ) ? ? ? p q q Hkq ? ? 若j ? k , 将Ap ( k ) ? q ( k )代入得H k ?1 Ap ( k ) ? p ( k ) .
(k ) ( k )T ( k ) ( k )T ( j)

? p p Hkq q Hk H k ?1 Ap ? ? H k ? ( k )T ( k ) ? ( k )T (k ) ? p q q Hkq ? 若j ? k , 则
(k ) ( k )T ( k ) ( k )T ( j)

? ( j) ? Ap ? ? H k Ap
( j)

H k ?1 Ap
( j)

( j)

? H k Ap
(k )

( j)

?

p p p p( j)

(k )

( k )T

Ap
(k )

( j)

( k )T

q

?

Hkq q q

( k ) ( k )T ( k )T

H k q( k )

=p

?

Hkq

? Ap

(k ) T (k )

?

q

( k )T

Hkq

? p( j )

? 命题成立

? p Ap ( j ) ? 0, ? ? ( j) ( j) ? H m?1 Ap ? p . ? (i ) (i ) Ap ? q
( i )T

令 D ? ? p (1) , p (2) ,? , p ( n ) ?
(1) (2) (n)

由于p , p ,? , p 是一组关于A共轭的非零向量, 因此它们线性无关,故,D是可逆矩阵, 由于 H n ?1 AD ? D 所以 H n ?1 ? A?1.

定理:若gi ? 0,i ? 1, 2,?, n,则DFP方法构造的
矩阵H i (i ? 1, 2,?, n)为对称正定矩阵。

推论:若目标函数是正定二次函数,则DFP方法经

有限步迭代必达极小点。
定理:如果f ( x)是E n上的二次连续可微实函数,对
? 任意的x ? E n,存在常数m ? 0,使得当 ? ? x ? C ( x) ? {x | f ( x) ? f ( x)} y ? E 时,有m y ? yT ? 2 f ( x) y,则DFP方法产生的
n 2

序列? x ( k ) ? 或终止于或收敛于f 在E n上的唯一极小点。

信赖域方法
基本思想:在当前迭代点的某个邻域内(通称取

为以当前迭代点为中心的球域,称为信赖域), 根据已知的有关优化问题的信息,确定一个模型 函数来近似原来的目标函数;然后,在该领域内 极小化模型函数确定可能的改进点;最后,根据 一定标准决定是否接受这个可能的改进点。

基本原理 min
f ( x) ? f ? x

f ( x), x ? R
(k )

n

将f ( x)在给定点x 展开

? ? ?f ? x ? ? x ? x ? 1 ? ? x ? x ? ? f ? x ?? x ? x ? 2
(k ) (k ) T (k ) (k ) T 2 (k ) (k ) (k )

记d ? x ? x ( k ),得到模型函数

?k (d ) ? f ? x

? ? ?f ? x ?

(k ) T

1 T 2 d ? d ? f ? x(k ) ? d . 2

子问题 1 T (k ) (k ) T min ?k (d ) ? f ? x ? ? ?f ? x ? d ? d Bk d .
2 s.t. d
2

? rk

其中Bk 是f ( x)的Hesse矩阵或者它的某个近似矩阵。

若Bk =0,则子问题的最优解为 d
(k )

?f ( x ) ? ?rk , (k ) ?f ( x )
(k ) 2
(k )

此时为最速下降法。
若Bk =? f ( x ),则子问题对应Newton方法.
2

信赖域半径的确定
通过比较迭代过程中模型函数和目标函数的下 降量,确定下一个迭代过程的信赖域半径.

f (x ) ? f (x ? d ) f (x ) ? f (x ? d ) ?k ? ? (k ) ?k (0) ? ?k (d ) f ( x ( k ) ) ? ?k ( d ( k ) )
(k ) (k ) (k ) (k ) (k ) (k )

若? k ? 0,则f ( x ( k ) ) ? f ( x ( k ) ? d ( k ) ),这说明可以拒绝 当前的改进量d ,并且需要减小信赖域半径;若? k 接近
(k )

于1,则当前的信赖域内,模型函数较好地近似了目标函 数,在下次迭代过程中可以适当地增加信赖域半径。

1. 给定可行点 (1),信赖域半径1,参数0 ? ? ? ? ? 1 x r 及精度要求 ,置k :? 1 ? 。 (k ) (k ) (k ) 2. 计算f ( x ),?f ( x )。若 ?f ( x ) ? ?,则停止
计算,得解x ( k );否则,计算 2 f ( x ( k ) )。 ? 3. 求解子问题

步骤:

1 T 2 min ?k (d ) ? f ( x ) ? ?f ( x ) d ? d ? f ( x ( k ) )d 2 s.t. d 2 ? rk,
(k ) (k ) T

得到子问题的最优解d ( k ),令 f ( x(k ) ) ? f ( x(k ) ? d (k ) ) ?k ? 。 (k ) (k ) f ( x ) ? ?k (d )

4. 如果?k ? ?,令x ( k ?1) ? x ( k );如果?k ? ?,令 x ( k ?1) ? x ( k ) ? d ( k )。
1 5. 修改rk。如果? k ? ?,令rk ?1 ? rk;如果 2 ? ? ? k ? ?,令rk ?1 ? rk;如果? k ? ?,令rk ?1 ? 2rk。

6. 置k :? k ? 1 ,转步骤2。

子问题的精确求解法

定理:向量d * 是信赖域子问题 1 T min ? ( d ) ? f ( x ) ? ?f ( x ) d ? d Bd 2 s.t. d 2 ? r
T

的全局最优解,当且仅当存在实数? ? 0,使得下面 条件都成立。 ( B ? ? I )d * ? ??f ( x ) (1) (2) (3)

? ?r ? d * 2 ? ? 0
( B ? ? I )是半正定矩阵。

( B ? ? I )d * ? ??f ( x )

必要性证明

? ?r ? d * 2 ? ? 0
( B ? ? I )是半正定矩阵。

假设d * 是子问题的

全局最优解 ,则下面 两种情形之一会出现: (1) 当 d * 2 ? r时,d * 实际上是函数 (d )的一 ? 个无约束局部极小点, 所以有 ?? (d *) ? Bd * ??f ( x) ? 0, ? ? (d *) ? B是半正定矩阵
2

容易看出,? ? 0满足条件(1), (2), (3)。

(2) d * 2 ? r, 则子问题的约束在d * 点是积极的。 子问题的Lagrange函数可以表示为 ? r2 d T d ? L( d , ? ) ? ? ( d ) ? ? ? ? 2 2 ? ? ? ? ?? ? 0, 满足?d L( d *, ? ) ? ?f ( x ) ? ( B ? ? I )d * ? 0,

? r ? d*2 ?0
2 2

?

?

即条件(1),(2)成立.对满足 d

2

? r的任意向量d , 有 ( d *T d * ?d T d )

? (d ) ? ? (d *) ? ? (d *) ?
T

?
2

1 T 1 T T ? ?f d ? d ( B ? ? I )d ? ?f d * ? d * ( B ? ? I )d * 2 2 ? ?f ? ?( B ? ? I )d *,? 上式等价于 1 (d ? d *)T ( B ? ? I )( d ? d *) ? 0. ? (3)成立。 2

充分性证明

假设条件(1), (2), (3)成立,则d * 是二次函数 ? T 1 T T L ( d ) ? ? ( d ) ? d d ? f ( x ) ? ?f ( x ) d ? d ( B ? ? I ) d 2 2 的全局最优解,所以 (d ) ? L(d *),即 L 2 2 T 由于条件(2)等价于? (r ? d * d *) ? 0, 所以有 2 ? ? ? 0, ? 对所有满足 d

? (d ) ? ? (d *) ?

?

(d *T d * ? d T d )

? (d ) ? ? (d *) ?

?

(r 2 ? d T d ).
2

? r的向量d,

? (d ) ? ? (d *)成立,
? d * 是子问题的全局最优解 。

2 例: f ( x) ? x14 ? x12 ? x2 ? 4 x2 ? 5 min

取初始点x

(1)

?0? 1 3 ? ? ?, r1 ? 1, ? ? ,? ? . ?0? 4 4 ? ?
(1)

第一次迭代:

? 0? ? 2 0? 2 (1) f ( x ) ? 5 ?f ( x ) ? ? ? ? f ( x ) ? ? ? ? 4? 0 2? ? ? ? ? 解子问题:
(1)

1 T 2 (1) min ?1 (d ) ? f ( x ) ? ?f ( x ) d ? d ? f ( x )d 2 s.t. d 2 ? 1
(1) (1) T

即求解
2 min ?1 (d ) ? 5 ? 4d 2 ? d12 ? d 2 2 s.t. d12 ? d 2 ? 1

? 0? ? ?, 且f ( x (1) ? d (1) ) ? 2, ?1 (d (1) ) ? 2, 得最优解d ? ? ? ?1 ? 实际下降量与预测下降 量之比为:
(1)

f (x ) ? f (x ? d ) ?1 ? ?1 ?? (1) (1) f ( x ) ? ?1 (d )
(1) (1) (1)

逼近成功, 令x

( 2)

? x ?d
(1)

(1)

? 0? ? ? ?, r2 ? 2r1 ? 2. ?1 ? ? ?

? 0? ? 2 0? 2 (2) f ( x ) ? 2 ?f ( x ) ? ? ? ? f ( x ) ? ? ? ?2 ? 0 2? ? ? 解子问题:
(2) (2) 2 min ? 2 ( d ) ? 2 ? 2d 2 ? d12 ? d 2

第二次迭代:

s.t. d ? d ? 4 ? 0? ( 2) 得最优解d ? ? ?, 且f ( x ( 2) ? d ( 2) ) ? 0, ? 2 (d ( 2) ) ? 1, ?1 ? ? ?
2 1 2 2

f (x ) ? f (x ? d ) ?2 ? ? 2 ?? ( 2) ( 2) f ( x ) ? ? 2 (d )
( 2) ( 2) ( 2)

逼近成功, 令x

( 3)

?x

( 2)

?d

( 2)

?0? ? ? ?, r3 ? 2r2 ? 4. ? ?

第三次迭代:

经计算 ? 0? f ( x ) ? 1 ?f ( x ) ? ? ?, ? 0? ? ? ?0 ? ( 3)

? x ? ? ?是最优解。 ? 2?
( 3) ( 3)


网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com