共轭梯度法原理共轭梯度法原理.pdf-资料库

§4 共轭梯度法共轭梯度法是利用目标函数的梯度逐步产生共轭方向并将其作为搜索方向的方法。本节先引进共轭方向的概念，讨论目标函数是二次函数时共轭方向的产生方法，由此得到无约束二次规划问题的共轭梯度法，然后将该算法推广到求解一般的无约束非线性规划问题。 4.1 共轭方向与共轭方向法定义 4.1 设 nnRH ×∈ 是对称正定阵。（1）若对非零向量 nR∈qp, ，有 p HT q =0 (4.1) 则称 p 和 q 是 H—共轭的，或称 p 与 q H—共轭。 d （2）若对非零向量组 1, d , m nR∈ ，对任意的 j i ≠ ， id 与 jd 是 H—共轭的，则称 1, d d 是 , m H—共轭方向组。当 H=I 时，(4.1)变为 qpT =0，即 p 与 q 互相正交，由此可见，“共轭”概念是“正交”概念的推广。下面的定理说明 H—共轭方向组与线性无关方向组的关系。定理 4.1 设 nnRH ×∈ d 是对称正定阵。若非零向量组 1, d 是 H—共轭方向组，则 1, d , m d 也 , m 是线性无关方向组。证明：设有实数 ,1 ，使 mαα , 1 d α 1 d α+ m + m =0 (4.2) 任取 i ∈ ,1{ m }, ，用 ( )i T Hd 左乘(4.2)，利用 id 与 jd 与 ( i∀ ≠ 的 H—共轭性得， ) j 由 i ≠d 0 和 H 是对称正定阵知 ( d ) i T iH ≠ d 0 ，于是据(4.3)有 iα =0。再由 i ∈ ,1{ m }, 的任意性得知 α d ( i )i T H d =0 (4.3) i α = 1 = mα = 0 d ，由此得 1, d 线性无关。证毕。 , m 将一组共轭方向作为搜索方向对无约束非线性规划问题(UNP)进行求解的方法称为共轭方向法。现在考虑无约束凸二次规划问题 x min ( ) x f = 1 2 T x H x b x (UQP) + T 其中矩阵 H R ×∈ 对称正定，向量 n n nR∈b x 。显然， ( ) ∇ f = H x b ， 2 ∇ + f =x ( ) H 为正定阵，因此 )(xf 是严格凸函数，并且 *x 是(UQP)的最优解的充要条件是 *xf∇ ( ) =0。易知，对于问题(UQP)，在迭代点 k nR∈x 处沿非零方向 ks 进行一维搜索时的最优步长 kλ = − k s ∇ f s x ( )k T s H kT k (4.4) 10

我们讨论用共轭方向法求解(UQP)时的有关结论。引理 4.1 设 H R ×∈ 是对称正定阵， 0, n n s s 是非零 H—共轭方向组， 0 nR∈x , k 。若对问题(UQP)，从 0x 出发，依次沿 0, s s 进行最优一维搜索： , k λ i = 最终得到 1k +x ，则 f arg min ( λ ≥ 0 +x i λ s ， 1i i + = x ) i x + s ， i iλ i ,0 = , k 证明：显然，对 i ,0 = , k ， 1 + x k ∇ x ( f k 1 + ) T s =0， i i ,0 = , k i 1 + = x k + ∑ i 1 = + j λ j s ，因此 j ∇ f ( x k 1 + ) = x H k 1 + + b = x H i 1 + + k ∑ j i 1 = + λ j j s H + = ∇ b f ( x i 1 + ) + k ∑ λ j i 1 = + j H s (4.5) j f arg min ( ≥ λ 0 +x i λ s 知 i ) ∇ x ( f i 1 + T ) s =0，于是据(4.5)并由 0, i s s 的 H—共轭性得 , k ∇ x ( f k 1 + ) T s = i ∇ f ( x i 1 + ) T i s k 1 − + ∑ i 1 = + j iT Hλ s s =0 j j 同时，由 λ i = 证毕。引理 4.1 说明，在 H-共轭条件下，得到以下定理。 ∇ x 与搜索方向 0, s 1 + ( ) f k s 均正交。同时，利用引理 4.1 马上 , k 定理 4.2 设 s H R ×∈ 是对称正定阵， 0 n n , s 是非零 G—共轭方向组， 0 nR∈x n− 1 , 。若对问题(UQP)，从 0x 出发，依次沿 0 s , s 进行最优一维搜索，最终得到 nx ，则 nx 是(UQP)的最优解。 n− 1 , s 证明：由定理 4.1 知 0 , s 线性无关，又根据定理 4.1， n− 1 , f∇ x ( )n T s =0， i i = ,0 , n − 1 (4.6) 由(4.6)知， ( f∇ x 与 n 个线性无关向量正交，于是 ( f∇ x =0，由此知 nx 是(UQP)的最优解。证毕。定理 4.2 告诉我们，若用一组共轭方向作为搜索方向求解(UQP)，那么最多迭代 n 次即可得到其最优 )n )n 解，因此共轭方向法具有二次终止性。对(UQP)，我们可以利用迭代点处的梯度产生共轭方向，这就是下面的共轭梯度法。 4.2 无约束凸二次规划问题的共轭梯度法共轭梯度法的思想是：首先以初始点 )0(x 处的负梯度作为初始搜索方向，即 0s = f−∇ x ，利用(4.4) 0( ) s ，然后依据 1x 处的负梯度和 0s 构造与 0s 是 H-共轭的方向 1s ，再利用(4.4) 0 s ，再依据 2x 处的负梯度和 0s 、 1s 构造与 0s 、 1s 均是 H-共轭的方向。以 1 0 x + = 0λ x 求得 0λ ，并得到 1 x 求得 1λ，并得到 2 此重复，直到求得 1nλ− 和 nx ，那么(UQP)的最优解 * 1λ = + x 1 根据共轭梯度法的思想，令 11 n=x x 。下面记 k g f= ∇ ( x 。 k )

= − = − 0 k g g 0 k s s ⎧ ⎪ ⎨ ⎪⎩ + β k 1 − s k 1 − + k 2 − ∑ i 0 = β ki i s , k = 1, , n − 1 (4.7) s 我们用归纳法来确定其中的参数，使 0 , s 为非零 H-共轭方向组。为此，设 0 s n− 1 , , s 是 H-共轭的， k − 1 , 我们确定参数 k = i ( ,0 ,1 − ββ ki f∇ ，设 ( ,0 = k , 首先对 i k − )2 s ，使 ks 与 0 , s 是 H-共轭的。 k − 1 , , ≠x )i 0(否则已得到(UQP)的最优解)，由(4.7)第二式并根据定理 4.2 知， ( g ) k T k s = − ∇ f k ( x ) 2 <0 0= ( s ) k T s H k 1 − = − ( g ) k T s H k 1 − + β k 1 − s k 1 − s H k 1 − 0= ( s ) k T i s H = − ( g ) k T i s H + β ki i s 即 ks 是 f 在 kx 处的下降方向，并且 i H i , s = 0, , k − 2 β k ( β = ki 1 − k ( = g s H )k T s s H k k 1 1 − − g s H )k T s s H i i , i (4.8) i = ,0 , k − 2 (4.9) 下面证明 kiβ =0( i = ,0 , k − 2 )。首先由(4.7)知， j g f= ∇ ( j x ( ) j ,0 = , k -1)是 0, s s 的线性组合，因此根据定理 4.2， , j 由于利用(4.10)知 ( g )k T j g =0， j ,0 = , k -1 (4.10) i s H = 1 ( λ i i 1 + g − g ， i ) i = ,0 , k − 2 (4.11) ( g ) k T i s H = 1 λ k ( g ) ( k T g i 1 + − g =0， i ) i = ,0 , k − 2 代入(4.9)得 kiβ =0。于是，(4.7)可简化为 0 k s s ⎧ ⎪ ⎨ ⎪⎩ = − = − 0 k g g + 其中 1−kβ 由(4.8)确定。下面推导 1−kβ 的几个等价式子。将(4.11)代入(4.8)，则 k 1 β − s 1 − k k = 1, , n − 1 (4.12) 对于(4.13)的分子，由(4.10)知， β k 1 − = g ( s ( k ) k T ) T 1 − 1 − k 1 − s H k s H = ( s g k 1 − ) ( k T ) ( T g g ( k g k 1 − − g k ( ) − k ) 1 − (4.13) ) 12

( g ) ( k T g k − g k 1 − ) = k g 2 对于(4.13)的分母，由(4.10)和(4.12)的第二式知， k 1 − ( s ) ( T g k − g k 1 − ) = − ( s k 1 − ) T g k 1 − = k ( g 1 kβ− − − 2 s k − 2 k 1 − ) T g = k 1 − g 2 因此，由(4.13)得到 1−kβ 的三个等价式子： β− k 1 = 2 k 21 − g g k (4.14) β− k 1 = − ( β k 1 − = ( g k T k s g ) 1 − g ) ( k T g k 2 k 1 − g (4.15) g k 1 − ) k − 21 − (4.16) 上述三个式子中均不出现 H ，它们分别称为 FR(Fletcher-Reeves) 公式、 Dixon 公式和 PRP(Polak-Ribiere-Polyak)公式。由此，利用(4.12)和(4.14)或(4.15)或(4.16)可得到求解无约束凸二次规划问题的共轭梯度法的具体迭代步骤。算法 4.1：求解凸二次规划的共轭梯度法 1．选定初始数据。给定初始点 0 2．最优性判别。若 ( f∇ x =0，停止，得 * )k 。令 k=0。 k=x nR∈x x ，否则转 3。 3．构造搜索方向。当 k=0 时令 0s = 或(4.16)确定。 f−∇ x ，当 k>0 时令 0( ) k s = − k g + s ，其中 1−kβ 由(4.14)或(4.15) k 1 kβ − 1 − 4．确定新的迭代点。令 kλ = − g ( ) k T s ) ( k T s k x s ， 1k + = kH k x + kλ s 。若 k+1=n，停止，得 * k =x x ，否则， 1k + k=k+1，转 2。注 4.1 为保证 H-共轭性，在 kx 处必须取 ks 为搜索方向，而不能取 ( s kα α> 0) 为搜索方向。利用定理 4.3，马上得到上述算法的有限终止性。定理 4.4 设 x ，则 Kx 是(UQP)的最优解，并且 nK ≤ 。 , H R ×∈ n n K 是对称正定阵。若用凸二次规划的共轭梯度法求解(UQP)时产生迭代点 x 1, 例 3.1 用共轭梯度法求解无约束非线性规划问题 min x f =x )( 2 x 1 + 2 x 2 2 给定初始点 )0(x = 1 ⎞ ⎟⎟ 1 ⎠ ⎛ ⎜⎜ ⎝ 。 13

首先， ∇ f x )( = 2 4 x 1 x 2 ⎛ ⎜⎜ ⎝ ⎞ ⎟⎟ ⎠ ，H= ∇ 2 xf )( = ⎛ ⎜⎜ ⎝ 02 40 ⎞ ⎟⎟ ⎠ ，以下利用(4.14)确定 kβ 。 k=0： ∇ )0(xf ( ) = ⎛ ⎜⎜ ⎝ 2 4 ⎞ =⎟⎟ ⎠ 1 2 ⎛ 2 ⎜⎜ ⎝ ⎞ ≠⎟⎟ ⎠ 0 ， (0) s = −∇ f ( x (0) ) 1 ⎛ ⎞ = − ⎜ ⎟ 2 ⎝ ⎠ 2 , 0λ = − (0) ∇ f s x ( T (0) s )T (0) s H (0) = (1) x = x (0) + 0λ s = (0) 1 ⎞ −⎟⎟ 1 ⎠ ⎛ ⎜⎜ ⎝ 5 18 × 1 2 ⎛ 2 ⎜⎜ ⎝ ⎞ =⎟⎟ ⎠ ⎛ ⎜⎜ ⎝ 9/4 9/1 − ⎞ ⎟⎟ ⎠ ， k=1： 54 × 2(4 + × )16 = 5 18 ， ∇ )1(xf ( ) = ⎛ ⎜⎜ ⎝ 9/8 9/4 − ⎞ =⎟⎟ ⎠ 4 9 ⎛ ⎜⎜ ⎝ 2 ⎞ ≠⎟⎟ 1 − ⎠ 0， =β 0 5 × 16 81 54 × = 4 81 ， (1) s = −∇ f ( x (1) ) + β 0 s = (0) 9/8 ⎛− ⎜⎜ 9/4 ⎝ ⎞ −⎟⎟ ⎠ 4 81 × 1 2 ⎛ 2 ⎜⎜ ⎝ ⎞ ⎟⎟ ⎠ = 20 81 4 × 9 × 2 20 ⎞ ×⎟ 81 ⎠ × 9 32( + )4 = 9 20 ， (2) x = (1) x + 1λ s = (1) 0 ⎛ ⎞ ⎜ ⎟ 0 ⎝ ⎠ 。 20 81 4 ⎛− ⎜⎜ 1 ⎝ ⎞ ⎟⎟ ⎠ , 1λ= − (1) ∇ f s x ( T (1) s )T (1) s H (1) = ⎛ ⎜ ⎝ * x = x )2( = ⎛ ⎜⎜ ⎝ 0 0 ⎞ ⎟⎟ ⎠ 。 4.3 一般无约束非线性规划问题的共轭梯度法现在考虑一般无约束非线性规划问题(UNP)，即 min x f x )( (UNP) 其中函数 )(xf 连续可微。由于这时(4.14)、(4.15)和(4.16)不一定等价，从而利用关于 kβ 的不同公式，将导出不同的共轭梯度法。 1． FR 共轭梯度法先给出基于(4.14)的求解(UNP)的共轭梯度法—FR 共轭梯度法的具体迭代步骤。算法 4.2 ：FR 共轭梯度法 1．初始步。给定初始点 nR∈)0(x ，精度参数ε>0。令 k=0。 2．终止判别。若 ∇ f x ( )(k ) ε≤ ，停止，得 ~ x = kx )( g ，否则令 ( k ) f= ∇ ( ) k x ，转 3。 ( ) )ks 3．构造搜索方向。当 k=0 或 n 的整数倍时，令 ( = ( )k−g ，否则令 ( s k ) = − g ( k ) + s ，其中 1−kβ k ( 1) kβ − 1 − 由 FR 公式(4.14)确定。 f min ( λ ≥ 4．进行一维搜索。求 0 ( k ) x + ) s 的最优步长或满足 Wolfe-powell 准则的可接受步长 kλ ，使 k ( λ ) D k = f ( x k ( ) ) − f ( x k ( ) + λ k s k ( ) ) ≥ ( δ k ( ) ( g k ( ) ) T s )2 2 k ( ) s (4.17) 14

( k 1) + | ( g ( k ) ) T s | ≤ − σ 3 ( g ( k ) ( k ) ) T s (4.18) 其中δ>0，0< 3σ <0.5。 x k 5．确定新的迭代点。令 ( 1) + = x k ( ) + kλ s ，k=k+1，转 2。 k ( ) 注 4.2 在 FR 共轭梯度法中，采用了 n 步重新开始的技巧，一是为了避免误差的积累，二是为了提高收敛速度。下面先讨论 FR 共轭梯度法的可行性。定理 4.5 设 Rf : n → 二次连续可微， R 1 2 xf∇ )( 有界， )(xf 有下界， nR∈)0(x 。则用 FR 共轭梯度法求解(UNP)时，存在满足条件(4.17)(4.18)的 kλ ，并且 ( g )k T ( ) s k ( ) + ( k ) g 2 ≤ u 2 g ， k ( ) ,1,0=k (4.19) 其中 =u σ 3 1 σ − 3 <1。证明：设 ∇ f x ( )(k ) ≠ 0。用归纳法证明结论。当 k=0 时， (0) s = − g ，(4.19)显然成立，并且 (0) f∇ ( x (0) (0) ) T s < 0 ，因此根据推论 2.1 知，满足条件 (4.17)的 0λ存在。显然，当 0λ为最优步长时，下的可接受步长时，(4.18)也成立。设 k=i 时(4.19)成立，则 f∇ ( x (1) ) T s (0) = 0 ，故(4.18)成立；当 0λ为 Wolfe-Powell 准则 i ( ) ( g (i) ) T s (1 ≤ + u ) i ( ) g 2 (4.20) 并且由 u<1 知 f∇ ( x i ( ) i ( ) T ) s < 0 ，因此满足条件(4.17)和(4.18)的 iλ确实存在。现在考虑 k=i+1 时。当 ( 1) + s i = − + g 时，(4.19)显然成立，当 i ( 1) s i ( 1) + = − g i ( 1) + + i ( 1) + 2 g g i ( ) s 时，利用条件(4.18)并由(4.20)， 2 i ( ) i ( 1) + ( g i ( 1) + ) T s + g i ( 1) + 2 = 2 i ( 1) + g g i ( 1) + ( g i ( ) ) T s 2 i ( ) ≤ σ 3 2 i ( 1) + g g i ( ) ( g i ( ) ) T s ≤ σ 3 (1 + u ) g i ( 1) + 2 i ( ) 2 = u +g i ( 1) 2 因此 k=i+1 时(4.20)也成立。并且由 u<1 知 ∇ f ( x i ( 1) + i ( 1) + ) T s < 0 ，因此满足条件(4.17)和(4.18)的 1iλ+ 确实存在。根据归纳法，得结论。证毕。下面先建立 FR 共轭梯度法的收敛性定理。 15

定理 4.6 设 Rf : n → 二阶连续可微， R 1 2 xf∇ )( 有界， )(xf 有下界， nR∈)0(x 。当用 FR 共轭梯度法求解(UNP)时，其中ε=0，（1）若产生有限序列 )1( x , , ) Kx ( ，则 f x∇ ( (K ) ) =0；（2）若产生无限序列 x )1( , x )2( , ，则 lim k inf ∞→ f x∇ ( )(k ) =0。证明：（1）根据算法的终止判别条件即得。（2）对 ,1,0=k ，根据算法的终止判别条件知， ∇ f x ( )(k ) ≠ 0。利用和(4.18)和(4.19)得到， ( k 1) + ( g k ( ) ) T s ≤ σ 3 k ( ) ( g k ( ) ) T s ≤ 3(1 σ + u ) k ( ) g 2 = u 2 g ， k ( ) ,1,0=k (4.21) 因此当 ( k ) s = − g ( k ) + 2 ( k ) 2 k 1) − g g ( ( k 1) − s 时，由(4.21)， 2 k ( ) s = ( k ) g 2 + 4 ( k ) 4 k 1) − g g ( ( k 1) − s 2 − 2 2 k ( ) 2 k 1) − g g ( k ( ) ( g ) T s ( k 1) − ≤ ( k ) g 2 + 4 k ( ) 4 k 1) − g g ( ( k 1) − s ≤ + u (1 2 ) ( k ) g 2 + ( k 1) − ( k 1) − s g + u 2 ( k ) g 2 4 k ( ) g (4.22) 2 2 4 s 当 ( k ) = − ) k g 时，(4.22)显然也成立。令 ( α = k ( k ) k ( ) s g α α− k 1 ≤ k 2 4 ，则由(4.22)， + + u (1 2 ) 2 ( k ) g (4.23) 由(4.17)知 f x ({ )(k )} 是下降序列，则由 )(xf 有下界得 f x ({ )(k )} 收敛。下面用反证法证明结论。假设 lim k inf ∞→ f x∇ ( )(k ) >0，则由 ∇ f x ( )(k ) ≠ 0 对一切 k 均成立知，存在γ>0，使 ( k ) g 2 = ∇ f ( x ( k ) ) 2 > γ 对一切 k 均成立。由(4.23)得 αα k ≤ k + u )21( + γ ，因此 1 − αα 0 ≤ k + ku 21 + γ ，由此得又利用(4.17)并由(4.19)， 1 ∞ ∑ kα k =0 发散 (4.24) >∞ )0( f ( x ) − k )( f ( x ) = lim k ∞→ ∞ ( ∑ k 1 = k )( f ( x ) − f ( x ( k )1 + )) 16 ∞ ≥ ∑ g ( δ k 0 = ( ( )k T ) s ( k ) )2 ( k ) s 2

≥ uδ − (1 ) 2 4 ( k ) ∞ ∑ g k 0 = 2 ( k ) s = 1( δ − u ) 2 ∞ ∑ k =0 1 α k 1 ∞ 因此 ∑ kα k =0 收敛，与(4.24)矛盾，由此得 lim k inf ∞→ f x∇ ( )(k ) =0。证毕。注 4.3 从定理的证明过程可以看出，若在 FR 共轭梯度法中没有采用 n 步重新开始的技巧，也能保证收敛性。注 4.4 利用定理 4.5 马上得到，若用 FR 共轭梯度法求解(UNP)，其中ε>0，那么算法一定有限步结束于(UNP)的近似平稳点 kx ，满足条件 ∇ f x ( )(k ) ε≤ 。 2．Dixon 共轭梯度法在 FR 共轭梯度法的第 3 步中，若用 Dixon 公式(4.15)代替 FR 公式(4.14)，这时的算法称为 Dixon 共轭梯度法。算法 4.3 ：Dixon 共轭梯度法 1．初始步。给定初始点 nR∈)0(x ，精度参数ε>0。令 k=0。 2．终止判别。若 ∇ f x ( )(k ) ε≤ ，停止，得 ~ x = kx )( g ，否则令 ( k ) f= ∇ ( ) k x ，转 3。 ( ) 3．构造搜索方向。当 k=0 或 n 的整数倍时令 ( )ks = ( )k−g ，否则令 ( ) k s = − g k ( ) + s ，其中 1−kβ 由 k ( 1) kβ − 1 − Dixon 公式(4.15)确定。 f min ( ≥ λ 4．进行一维搜索。求 0 ( k ) x + ) s 的最优步长或满足 Wolfe-powell 准则的可接受步长 kλ ，使(4.17) k ( λ ) 和 0 ( ≥ g ( k 1) + k ( ) T ) s ≥ σ 3 ( g k ( ) k ( ) T ) s (4.25) 成立，其中δ>0，0< 3σ <1。 x 5．确定新的迭代点。令 ( k 1) + = x ( k ) + kλ ) k s ，k=k+1，转 2。 ( 下面给出该算法的可行性和收敛性定理。定理 3.7 设 Rf : n → 二次连续可微， R 1 2 xf∇ )( 有界， )(xf 有下界， nR∈)0(x 。则用 Dixon 共轭梯度法求解(UNP)时，存在满足条件(4.17)和(4.25)的 kλ ，并且 k ( ) ( g k ( ) ) T s + k ( ) g 2 ≤ 0 ， ,1,0=k (4.26) 证明：设 ∇ f x ( )(k ) ≠ 0。用归纳法证明结论。 k=0 时， (0) s = − g ，(4.26)显然成立，并且 (0) f∇ ( x (0) (0) ) T s < 0 ，因此同定理 4.5 证明知，满足条件 (4.17)和(4.25)的 0λ存在。设 k=i 时(4.26)成立，则 17

资料库

共轭梯度法原理共轭梯度法原理.pdf

相关推荐

课程资源

热门标签

最新资料