PDF《VI - 1》

18 The Primary Contraction Methods 对给定的 uk 和由 (3.15) 生成的 ? uk , 用uk+1 = uk ? M(uk ? ? uk ) (3.16) 生成新的迭代点. 在由 (3.15) 生成的 ? uk 的过程中, 采用 Armijo 法则, 要求做到 对对对给 给 给定 定 定的 的的r>

0和和和ν∈(0, 1), 选选选取 取取s使使使得 得得1rAT (λk ? ? λk )

2 ≤ ν r xk ? ? xk

2 + s λk ? ? λk

2 . (3.17) 特别当 s 取得使 srν ≥ AT A 时, 条件 (3.17) 自然成立. 根据迭代公式 (3.16) 有uk ? u?

2 H ? uk+1 ? u?

2 H = uk ? u?

2 H ? (uk ? u? ) ? M(uk ? ? uk )

2 H = 2(uk ? u? )T HM(uk ? ? uk ) ? M(uk ? ? uk )

2 H . VI -

19 对上式右端的 (uk ? u? )T HM(uk ? ? uk ) 使用 (3.10), 我们有 uk ? u?

2 H ? uk+1 ? u?

2 H ≥ 2(uk ? ? uk )T HM(uk ? ? uk )? M(uk ? ? uk )

2 H . (3.18) 对(3.18) 的右端进一步处理得 2(uk ? ? uk )T HM(uk ? ? uk ) ? M(uk ? ? uk )

2 H = (uk ? ? uk )T (HM + MT H ? MT HM)(uk ? ? uk ). 利用矩阵恒等式 MT H + HM ? MT HM = H ? (MT ? I)H(M ? I) 和H与M的定义 (见(3.7) 和(3.9)), 经过简单计算就有 VI -

20 MT H + HM ? MT HM = ? ? rIn

0 0 sIm ? ? ? ? ?

0 0

1 r A

0 ? ? ? ? rIn

0 0 sIm ? ? ? ?

0 1 r AT

0 0 ? ? = ? ? rIn

0 0 sIm ?

1 r AAT ? ? . 因此得到 2(uk ? ? uk )T HM(uk ? ? uk ) ? M(uk ? ? uk )

2 H = uk ? ? uk

2 H ?

1 r AT (λk ? ? λk )

2 . (3.19) 在条件 (3.17) 满足的情况下, 从(3.19) 式得到 2(uk ? ? uk )T HM(uk ? ? uk ) ? M(uk ? ? uk )

2 H ≥ (1 ? ν) r xk ? ? xk

2 + s λk ? ? λk

2 . (3.20) 以(3.20) 代入 (3.18), 就有下面的定理: VI -

21 Theorem 3.1 在基于 Primal-Dual 松弛 PPA 的收缩算法中, 如果产生预测点时 条件 (3.17) 成立, 则由初等收缩算法 (3.16) 生成的序列 {uk = (xk , λk )} 满足 uk+1 ? u?

2 H ≤ uk ? u?

2 H ? (1 ? ν) uk ? ? uk

2 H . (3.21) 定理 3.1 是保证初等收缩算法收敛的关键不等式. 3.3 一一一般 般 般的 的 的收 收 收缩 缩 缩算 算 算法 法法一般收缩算法用同样的给定方向 d(uk , ? uk ), 通过计算步长确定下一个迭代点. 在H-模的意义下, 使新的迭代点靠解集尽可能近一些. 一一一般 般 般的 的 的收 收 收缩 缩 缩算 算 算法 法法I对给定的 uk 和由 (3.15) 生成的 ? uk , 用我们用 u(α) = uk ? αM(uk ? ? uk ) (3.22) 产生依赖于步长 α 的迭代点. 对由 (3.15) 生成的 ? uk , 要求做到 VI -

22 对对对给 给 给定 定 定的 的的r>

0, 选选选取 取取s使使使得 得得1sA(xk ? ? xk )

2 +

1 r AT (λk ? ? λk )

2 ≤

2 r xk ? ? x........