2 T 2
S8: 按( 11) 式计算比值 D k; x k+ 1 = x k + dk xk if D k > 0 其它 ;
k+ 1 = K k + $ k , 其中 $ k 按( 10) 式计算: K K K k, A 2 + d k +2 ] max [ $ k > G 2 D k < G 2 G1 < D k < G 1 D
T
由 ( 2) 式得: B k d k + ck A A k d k + ¨x l ( x k , K k ) + ck A K g k = 0 即有 :
T B k d k + ck A T k A kd k = - ¨ xl( xk, K k ) - ck A K g k
( 3)
1 T -1 假定 B k 是可逆的, ( 3) 式两端分别左乘 k A k B k , 得 c 1 T - 1 T 1 T -1 T - 1 ( + Ak B k A k) Ak d k = A k Bk ¨ xl (xk, K k ) - A k B k A k gk ck ck gk -1 1 + AT -1 k Bk ¨ xl( xk, K k) - ( k B k A k ) gk + = - 1AT ck ck ck = 即有 : 令 则有 :
$ k+ 1 =
k $ k, A 1 + d k +2 ] min[ $
S9: 计算 B k+ 1 , C k+ 1 : = C k , 转 S2.
3
算法的收敛性分析
我们在以下的分析中 , 假设如下的条件成立: 假设 ( 1) { x k } 是一有界序列; ( 2) P x I X = { x g ( x ) = 0 } 有 A ( x ) 列满秩 ; ( 3) Pk, B k 正定且一致有界. 引理 1 = LC , 则一定存在 设 D 是一正定矩阵, L是大于 0 的常数 , 如果( L I + D) C 0 < Q< 1, 使得 + C+2 [ Q+ C +2. 证 因 LX 0, 故有( L I+ D )C = L (I+ D )C = LC L ( 12)
k = ( C k C ck
1 T -1 -1 T -1 xl( xk, K k) + A k B k A k) (g k - Ak B k ¨ ck
( 4)
A k d k = - gk +
信赖域法求解子问题 :
T 1 d T B kd m in ¨ xL (xk, K k , ck ) d + n 2 dI R C k s. t . AT k d + gk = ck +d +2 [ $ k
T m
¨ xl( x, K ) = ¨ f ( x ) + KA ( x )
T
¨ xL (x, K , c) = ¨ xl( x, K ) + cA T ( x ) g( x )
2 2 ¨ x L (x, K , c) = ¨2 xl( x , K ) + c E gi ( x ) ¨ g i ( x ) + cA T ( x ) A ( x ) i= 1
k: = C k + 1 , 转 S4. C
S6: 如果 +g k + 2 + + ¨f k - A T kK k +2 [ E , 则停止计算 ; 否则, 解 ( 5) 、 ( 6) 、 ( 7) 得 d k . 1 2 T 2 S7: 由( 10) 式计算 D k ; 如果 D k \ C k [ + g k +2 - + g k + A k d k +2 ] , 则转 S8; 2 否则 , 令 C k : = 2 Ck , D k : = D k + C k [ +g k +2 - +g k + A k d k +2 ] .
ck 2 [ +g( x k ) +2 2 - +g( x k + d k ) +2 ] ( 9) 2
令
ck T 1 dT T T 2 Dk = - ¨ x l k dk k B k d k - $K k gk + A k dk + [ +g( x k ) +2 2 - +g(x k + d k ) +2 ] ( 10) 2 2 我们把 D k 作为价值函数的预估下降量.
( 8)
我们把 5 k ( x ) 作为价值函数, 故有: 5k ( x k ) - 5k ( x k + dk ) = L( x k , K k , ck ) - L ( x k + d k , K k+ $ K k , ck )
T = l( x k , Kk ) + l( x k + dk , K k) - $ K k g( x k + dk ) +
T - 1 - 1 T - 1 1 k k k k k k x k k k k+ 1 = ( C ck + A B A ) ( g - A B ¨ l ( x , K + C) 故有 : -1 T -1 ( 1 + AT k Bk A k) C k+ 1 = g k - A k B k ¨ xl( xk, K k+ C k) ck -1 T -1 = g k - AT k B k ¨ xl ( x k , K k ) - A k B k A kC k 1 T -1 -1 T -1 C k = ( + A k B k A k ) ( g k - A k B k ¨x l ( x k , K k ) 故有: ck 1 T - 1 T - 1 ( + A kBk A k) C k = gk - A k B k ¨x l ( x k , K k) 即 : ck C k -1 T -1 = gk - A T k Bk ¨ xl( xk, K k) - A kBk A kC k化的信赖域法
531
k 为 5 k ( x ) 的实际下降量与预估下降量的比值, 即 : 令D
5k ( x k ) - 5k ( x k + dk ) D k = Dk
( 11)
2
算法
信赖域算法如下 :
n S1: 给出 x 1 I R n , $ 1 > 0, K 1 I R , c1 > 0, 0< A < 1 , 0< A 1 < 1< A 2 , 0< G 1< G 2 < 1,
令
1 Q = +I + D + 2 , 则 0< Q < 1 L 所以 + C+ 2 [ Q+ C+2 .
引理 2
若 A k 满秩 , B K 正定 , 则 A T k B k A k 正定.
T
证 对 P x X 0, 因 B K 正定 , 则 x B k x > 0 T T T T T 又因 A k 满秩 , 即有 A T k x X 0, 从而( A k x ) B k ( A k x ) > 0, 即 x ( A k B k A k ) x > 0 故 xT ( AT k B kA k ) x > 0 P x X 0 所以 A T k B k A k 正定 . 定理 1 在算法中 , 内循环 S 4 ) ) ) S 5 是有限的 . 证 因
k: = 1, E\0, 计算 B 1 . S2: 如果 g k = 0, 转 S6. S3: 计算 Ck . S4: 如果 A +g k + \
k + +C , 转 S6. ck
1 T - 1 - 1 T - 1 k+ 1 = ( k k k k k k x k k k S5: 计算 C ck + A B A ) ( g - A B ¨ l ( x , K+ C ) 令
( 5) ( 6) ( 7)
其中 , 称 C k 为广义 L agr ange 乘子 为使搜索方向 d k 趋向可行域 , 一方面可使罚因子 c k y ] ; 但另一方面, 如果 C k U 0, 则点 x k + d k 是非常接近可行的 , 而不必罚因子 ck y ] , 故需要选择 ck , 使得 g k A T k d [ 0, 即- g T k g k+ gT kC k +C k + +gk + [ 0 或 +g k + 2 \ , 并且我们进一步把条件加强为: ck ck A+g k + \ +C k + ck 其中 0 < A< 1
T
1 k T -1 1 T - 1 k) ) - ( ( g - A k B k ¨x l ( x k , K + A kBk A k)g k ck ck
1( 1+ AT - 1 - 1 - 1 AT kd k= kBk A k) ( gk - A T k Bk ¨x l ( x k , K k ) ) - gk ck ck
令
B( x , K , c) = ¨ x l( x , K ) + c E gi ( x ) ¨ gi ( x )
2 2 i= 1
m
*
收稿日期 : 2006 - 05 - 09 接收日期 : 2007 - 01 - 25 基金项目 : 国家自然科学基金资助项 目( 70771078, 70471034, A 0324666) 作者简介 : 王芳华 ( 1969 - ) , 男 , 湖南湘潭 , 讲师 , 硕士生 , 研究方向 : 最优化理论与算法 .