PDF《VI - 1》

7 其中 G = ? ? rIn AT A sIm ? ? . 由于 rs >

AT A 时, 矩阵 G 是对称正定的. 根据 (2.3), 我们有 (uk ? u? )T G(uk ? ? uk ) ≥ uk ? ? uk

2 G, ? u? ∈ ?? . (2.4) 我们用 uk+1 = uk ? γ(uk ? ? uk ), γ ∈ (0, 2) (2.5) 生成新的迭代点 uk+1 , 一般取 γ ∈ [1.2, 1.9]. Theorem 2.1 The sequence {uk = (xk , λk )} generated by the proposed PPA method satis?es uk+1 ? u?

2 G ≤ uk ? u?

2 G ? γ(2 ? γ) uk ? ? uk

2 G. (2.6) ? B.S. He and X. M. Yuan, A contraction method with implementable proximal regularization for linearly constrained convex programming, Optimization Online, 2010. VI -

8 对对对给 给 给定 定 定的 的的(xk , λk ), 如如如何 何 何求 求 求得 得得(2.1) 的的的解 解解?wk = (? xk , ? yk , ? λk ) ∈ W 注意到 (2.1) 第一部分是求 ? xk ∈ X, 使得 θ(x) ? θ(? xk ) + (x ? ? xk )T {r(? xk ? xk ) ? AT λk } ≥ 0, ?x ∈ X. 因此, ? xk = Arg min θ(x) + r

2 x ? xk +

1 r AT λk

2 x ∈ X . 有了 ? xk , 注意到 (2.1) 的中间与第三部分在一起是 ? ? ? ? yk ∈ B, (y ? ? yk )T ? λk ≥ 0, ?y ∈ B A(2? xk ? xk ) ? ? yk + s(? λk ? λk ) = 0. (2.7) 对任意的 s >

0, 根据变分不等式与投影方程的关系, (2.7) 的第一部分有 ? yk = PB[? yk ? s? λk ]. (2.8) 而(2.7) 的下半部分可以改写成 ? yk = A(2? xk ? xk ) ? sλk + s? λk . (2.9) VI -

9 将(2.9) 代入 (2.8) 的右端, 就有 ? yk = PB[A(2? xk ? xk ) ? sλk ]. 以上式中的 ? yk 代入 (2.9), 就得到一个消去了 y 的?λk 的表达式. ? λk =

1 s PB[A(2? xk ? xk ) ? sλk ] ? [A(2? xk ? xk ) ? sλk ] . 用PPA 算法求解凸优化问题 (1.1), 总假设 r, s >

0 满足 rs >

AT A . Primal-Dual 生生生成 成成PPA 算算算法 法 法预 预 预测 测 测点 点点对给定的 (xk , λk ), 先用 min θ(x) + r

2 x ? xk +

1 r AT λk

2 x ∈ X . (2.10a) 求出预测点的 Primal 部分 ? xk . 然后令 ? λk =

1 s PB[A(2? xk ? xk ) ? sλk ] ? [A(2? xk ? xk ) ? sλk ] (2.10b) 得到预测点的 Dual 部分 ? λk . VI -

10 2.2 变变变分 分 分不 不 不等 等 等式 式 式框 框 框架 架 架下 下下Dual-Primal PPA 算算算法 法法与(2.1) 类似, 对给定的 uk = (xk , λk ), 也可考虑给出 ? wk = (? xk , ? yk , ? λk ), 使得 (? 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 ?A(? xk ? xk ) + s(? λk ? λk ) ? ? ? ? ? ? ? ? ≥ 0, ?(x, y, λ) ∈ W. (2.11) 同样的分析也会得到 (? uk ? u? )T G(uk ? ? uk ) ≥ 0. 所不同的是, 这里的 G = ? ? rIn ?AT ?A sIm ? ?. 这时要先解 (2.11) 中只含 ? yk , ? λk VI -

11 的部分, 采用求解 (2.7) 的方法求解如下的方程组. ? ? ? ? yk ∈ B, (y ? ? yk )T ? λk ≥ 0, ?y ∈ B Axk ? ? yk + s(? λk ? λk ) = 0. (2.12) Dual-Primal 生生生成 成成PPA 算算算法 法 法预 预 预测 测 测点 点点对给定的 uk = (xk , λk ), 先用 ? λk =

1 s PB[Axk ? sλk ] ? (Axk ? sλk ) (2.13a) 给出预测点的 Dual 部分 ? λk . 再通过求解 min θ(x) + r

2 x ? xk +

1 r AT (2? λk ? λk )

2 x ∈ X . (2.13b) 得到预测点的 Primal 部分 ? xk . 的确, 在

第一节的假设条件下, 用(2.10) 或者 (2.13) 求得 (? xk , ? λk ) 是容易实现 的. 若用 uk+1 = uk ? γ(uk ? ? uk ), γ ∈ (0, 2) 生成新的迭代点, 这些方法是第四讲 Customized PPA 方法的直接推广. VI -

12 3 基基基于 于于Primal-Dual 松松松弛 弛弛PPA 的的的收 收 收缩 缩 缩算 算 算法 法法我们考虑用 Relaxed PPA 求解扩展问题 (1.1) , 还是将 y 看作辅助变量. 求解 变分不等式 (1.3)-(1.4) 的经典的 PPA 算法是从 uk = (xk , λk ) 出发, 求?wk = (? xk , ? yk , ? λk ) ∈ W, 使得 θ(x)?θ(? xk ) + ? ? ? ? x ? ? xk y ? ? yk λ ? ? λk ? ? ? ? T ? ? ? ? ? ? ? ? ? ? ? ?AT ? λk ? λk A? xk ? ? yk ? ? ? ?+ ? ? ? ? r(? xk ? xk )