PDF《VI - 1》

VI -

1 凸凸凸优 优 优化 化 化和 和 和单 单 单调 调 调变 变 变分 分 分不 不 不等 等 等式 式 式的 的 的收 收 收缩 缩 缩算 算 算法 法法第六讲: 线性约束凸优化扩展问题的 定制 PPA 和松弛 PPA 收缩算法 PPA-based contraction methods for general linearly constrained convex optimization 南京大学数学系 何炳生 hebma@nju.

edu.cn VI -

2 1 线线线性 性 性约 约 约束 束 束凸 凸 凸优 优 优化 化 化扩 扩 扩展 展 展问 问 问题 题题我们考虑如下的线性约束凸优化扩展问题: min{θ(x) | Ax ∈ B, x ∈ X} (1.1) 其中 θ(x) 是凸函数, A ∈ m*n , B ? m , X ? n 为闭凸集. 如果 B = {b}, 问题 (1.1) 就是前两讲讨论的问题. 推广前两讲的方法, 用来求解问题(1.1). 对任意给定的 r >

0 和a∈n,通篇我们假设 子子子问 问 问题 题题min {θ(x) + r

2 x ? a

2 | x ∈ X} 的的的求 求 求解 解 解是 是 是简 简 简单 单 单的 的的. 除此以外, 我们还假设 在在在闭 闭 闭凸 凸 凸集 集集B上上上的 的 的投 投 投影 影 影是 是 是容 容 容易 易 易实 实 实现 现 现的 的的. 显然, 分裂可行性问题 [8, 10], Find a point x ∈ X such that Ax ∈ B, 是(1.1) 中置 θ(x) ≡

0 的一种特殊形式. VI -

3 线线线性 性 性约 约 约束 束 束凸 凸 凸优 优 优化 化 化扩 扩 扩展 展 展问 问 问题 题 题等 等 等价 价 价的 的 的变 变 变分 分 分不 不 不等 等 等式 式式引进辅助变量 y. 问题 (1.1) 可以改写成 min{θ(x) | Ax ? y = 0, x ∈ X, y ∈ B}. (1.2) 对线性约束 Ax ? y =

0 引入 Lagrange 乘子 λ ∈ m , 问题 (1.2) 的Lagrange 函数是定义在 X * B * m 上的 L(x, y, λ) = θ(x) ? λT (Ax ? y). 求解问题 (1.1) 就相当于找一组 (x? , y? , λ? ), 使得 ? ? ? ? ? ? ? x? ∈ X, θ(x) ? θ(x? ) + (x ? x? )T (?AT λ? ) ≥ 0, ? x ∈ X, y? ∈ B, (y ? y? )T λ? ≥ 0, ? y ∈ B, λ? ∈ m , (λ ? λ? )T (Ax? ? y? ) ≥ 0, ? λ ∈ m . (1.3) VI -

4 通过定义 w = ? ? ? ? x y λ ? ? ? ? , F(w) = ? ? ? ? ?AT λ λ Ax ? y ? ? ? ? (1.4) 和W=X*B*m,变分不等式 (1.3) 能够写成 VI(W, F, θ) w? ∈ W, θ(x)?θ(x? )+(w?w? )T F(w? ) ≥ 0, ? w ∈ W. (1.5) 注意到仿射算子 F 是单调的. 由于 y 是辅助变量, 我们记 u = ? ? x λ ? ? 和?=X*m.设W? 是(1.5) 的解集, 并令 ?? = {(x? , λ? ) | (x? , y? , λ? ) ∈ W? }. VI -

5 我们分别给出为求解线性约束凸优化扩展问题 (1.1) 的PPA 收缩算法 和Relaxed PPA 收缩算法.

2 线线线性 性 性约 约 约束 束 束凸 凸 凸优 优 优化 化 化扩 扩 扩展 展 展问 问 问题 题 题的 的的PPA 算算算法 法法2.1 变变变分 分 分不 不 不等 等 等式 式 式框 框 框架 架 架下 下下Primal-Dual PPA 算算算法 法法对给定的 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.1) VI -

6 将任意的 w? = (x? , y? , λ? ) 代入上式中的 (x, y, λ) ∈ W, 并利用 F(w) 的表 达式 (1.4), 就有 ? ? ? xk ? x? ? λk ? λ? ? ? T ? ? ? ? ? r(xk ? ? xk ) A(xk ? ? xk ) ? ?+ ? ? AT (λk ? ? λk ) s(λk ? ? λk ) ? ? ? ? ? ≥ θ(? xk ) ? θ(x? ) + ( ? wk ? w? )T F( ? wk ). (2.2) 注意到 ( ? wk ? w? )T F( ? wk ) = ( ? wk ? w? )T F(w? ). 对?wk ∈ W, 有θ(? xk ) ? θ(x? ) + ( ? wk ? w? )T F(w? ) ≥ 0. 因此 (2.2) 的右端非负, 我们得到 (? uk ? u? )T G(uk ? ? uk ) ≥ 0, (2.3) VI -