PDF《VI - 1》

0 s(? λk ? λk ) ? ? ? ? ? ? ? ? ? ? ? ≥ 0, ?w ∈ W. (3.1) 直接求解 (3.1) 显然是有困难的. Relaxed PPA 考虑将第一部分中的 ? λk 松弛成 λk , 或者将第三部分中的 ? xk 松 弛成 xk , 求解松弛后的问题, 生成预测点, 构造收缩算法. 3.1 Primal-Dual 生生生成 成 成预 预 预测 测 测点 点点VI -

13 如果我们将 (3.1) 第一部分中的 ? λk 换 (松弛) 成λk , 就得到一个 Relaxed PPA 子问题: 求?wk = (? xk , ? yk , ? λk ) ∈ W, 使得 θ(x)?θ(? xk ) + ? ? ? ? x ? ? xk y ? ? yk λ ? ? λk ? ? ? ? T ? ? ? ? ? ? ? ? ? ? ? ?AT λk ? λk A? xk ? ? yk ? ? ? ?+ ? ? ? ? r(? xk ? xk )

0 s(? λk ? λk ) ? ? ? ? ? ? ? ? ? ? ? ≥ 0, ?w ∈ W. (3.2) 注意到 (3.2) 可以写成 (? xk , ? yk , ? λk ) ∈ W, θ(x) ? θ(? xk ) + ? ? ? ? x ? ? xk y ? ? yk λ ? ? λk ? ? ? ? T ? ? ? ? ? ? ? ? ? ? ? ?AT ? λk ? λk A? xk ? ? yk ? ? ? ? + ? ? ? ? r(? xk ? xk ) ? AT (? λk ? λk )

0 s(? λk ? λk ) ? ? ? ? ? ? ? ? ? ? ? ≥ 0, ?(x, y, λ) ∈ W. VI -

14 将上式的 (x, y, λ) ∈ W 用任意的 w? = (x? , y? , λ? ) 代替, 并利用 F(w) 的表 达式 (1.4), 就有 ? ? ? xk ? x? ? λk ? λ? ? ? T ? ? ? ? ? r(xk ? ? xk )

0 ? ?+ ? ? AT (λk ? ? λk ) s(λk ? ? λk ) ? ? ? ? ? ≥ θ(? xk ) ? θ(x? ) + ( ? wk ? w? )T F( ? wk ). (3.3) 注意到 (3.3) 的右端非负. 因此有 (? uk ? u? )T Q(uk ? ? uk ) ≥ 0, ? u? ∈ ?? , (3.4) 其中 Q = ? ? rIn AT

0 sIm ? ? (3.5) 是非对称的. 根据 (3.4), 我们有 (uk ? u? )T Q(uk ? ? uk ) ≥ (uk ? ? uk )T Q(uk ? ? uk ), ? u? ∈ ?? . (3.6) VI -

15 基于 Relaxed PPA 的收缩算法, 我们都考虑 H-模下的收缩, 其中 H = ? ? rIn

0 0 sIm ? ? , (3.7) 是正定的分块数量矩阵. 我们都采用 d(uk , ? uk ) = M(uk ? ? uk ) (3.8) 作为寻查方向, 其中 M = H?1 Q, M = ? ? In

1 r AT

0 Im ? ? (3.9) 是分块上三角矩阵, 其对角部分是单位矩阵. 注意到关系式 (3.6) 则为 (uk ? u? )T HM(uk ? ? uk ) ≥ (uk ? ? uk )T HM(uk ? ? uk ), ? u? ∈ ?? , (3.10) 对对对给 给 给定 定 定的 的的(xk , λk ), 如如如何 何 何求 求 求得 得得(3.2) 的的的解 解解?wk = (? xk , ? yk , ? λk ) ∈ W VI -

16 注意到 (3.2) 最上面的部分是 ? xk ∈ X, θ(x )?θ(? xk ) + (x ? ? xk )T {?AT λk + r(? xk ? xk )} ≥ 0, ?x ∈ X. 未知的只有 ? xk , 它可以通过求解子问题 min θ(x) + r

2 x ? xk +

1 r AT λk

2 x ∈ X (3.11) 得到. 由W=X*B*m,根据变分不等式和投影方程之间的关系, (3.2) 的 中间部分可以写成 ? yk = PB[? yk ? s? λk ], (3.12) 其中 s 为任意大于零的常数. 根据 (3.2) 的第三部分, 有?yk = A? xk + s(? λk ? λk ). (3.13) 以(3.13) 中的 ? yk 代入(3.12), 就得到由 ? xk 和λk 给出的 ? λk 的表达式 ? λk =

1 s PB[A? xk ? sλk ] ? [A? xk ? sλk ] . (3.14) 根据上面的分析, 我们得到了生成预测点 ? uk = (? xk , ? λk ) 的方法. VI -

17 PrimalCDual Method 生生生成 成 成预 预 预测 测 测点 点点对给定的 (xk , λk ) 和r>

0, 通过求解 min θ(x) + r

2 x ? xk +

1 r AT λk

2 x ∈ X (3.15a) 得到 Primal 预测点 ? xk . 再选取适当的 s >

0 并用 ? λk =

1 s PB[A? xk ? sλk ] ? [A? xk ? sλk ] (3.15b) 生成 Dual 预测点 ? λk (如何选取 s >

0 放在后面讨论). 把用松弛 PPA 按先 ? xk (primal) 后?λk (dual) 的顺序生成预测点 ? uk = (? xk , ? λk ), 然后构造的收缩算法称为基于Primal-Dual 松弛 PPA 的收缩算法 (Primal-dual relaxed PPA based contraction method). 3.2 初初初等 等 等的 的 的收 收 收缩 缩 缩算 算 算法 法法The Primary Contraction Methods (初等的收缩算法) 是指对确定的方向取单位 步长的收缩算法. VI -