On Convergence Rate of Three-block APGM

为了后续讨论的方便和简洁, 在这一部分做一些符号说明和假设.

记Ω=X₁×X₂×X₃×$\mathbb{R} $^p, 且记最优解为Ω^*.令ω=(x₁, x₂, x₃, λ)^T, ω^*=(x₁^*, x₂^*, x₃^*, λ^*)^T, 根据(3)式的一阶最优性条件, 解(3)式等同于找到ω^*∈Ω^*使得

其中ξ_i(x_i^*)∈∂f_i(x_i^*), i=1, 2, 3.

进一步地, 下面这些假设将应用于本文后续分析.

假设1  函数f_i(i=2, 3)分别是以η_i>0(i=2, 3)为参数的强凸函数, 即以下不等式成立:

或等价地

其中:ξ_i(x_i)∈∂f_i(x_i), ξ_i(y_i)∈∂f_i(y_i)(i=2, 3).

为了分析方便, 将会频繁地用到如下不等式和等式:

其中(10), (11)式中G∈$\mathbb{R} $^n×n为半正定矩阵.

为了书写简洁, 我们进一步定义

记问题(3)的目标函数为f(u)=∑_i=1³f_i(x_i); 记λ_max(B)为实对称矩阵B的最大特征值; 记‖x‖为x的欧氏范数.

接下来, 我们注意到, F是一个具有反对称矩阵的仿射性质算子, 即具有以下性质:

引理1  假设$ \frac{1}{\mu } \le \min \left\{ {\frac{{{\eta _2}}}{{2{\lambda _{\max }}(\mathit{\boldsymbol{A}}_2^{\rm{T}}{\mathit{\boldsymbol{A}}_2})}}, \frac{{{\eta _3}}}{{2{\lambda _{\max }}(\mathit{\boldsymbol{A}}_3^{\rm{T}}{\mathit{\boldsymbol{A}}_3})}}} \right\}$, 其中η₂和η₃的定义见假设1, 序列{ω^k:=(x₁^k, x₂^k, x₃^k, λ)}由(6)式生成.则对∀ω^*∈Ω^*, 下面不等式成立

其中: ${\mathit{\boldsymbol{G}}_i} = \frac{{{\mathit{\boldsymbol{I}}_{{n_i}}}}}{{\mu {\tau _i}}} - \frac{{\mathit{\boldsymbol{A}}_i^{\rm{T}}{\mathit{\boldsymbol{A}}_i}}}{\mu } > \mathit{\boldsymbol{0}}, {\tau _i}{\lambda _{\max }}(\mathit{\boldsymbol{A}}_i^{\rm{T}}{\mathit{\boldsymbol{A}}_i}) < 1, \;i = 1, 2, 3 $.

证  由(6)式的一阶最优性条件, 对∀ x_i^k+1∈X_i, ξ_i(x_i^k+1)∈∂f_i(x_i^k+1), i=1, 2, 3有

再由(6)式的最后一步, (14)式可以被重新表示为

联立(15)式的i=1, 2, 3的情形便可得到以下不等式

现在关键的一步是要证得(16)式前两项有界, 应用(10), (11)式, 我们可以得到

联合(17)以及(6)式的最后一步可得, 对∀x_i^k+1∈X_i, ξ_i(x_i^k+1)∈∂f_i(x_i^k+1), i=1, 2, 3和∀λ∈$\mathbb{R} $^l有

应用(10)式得到下面等式

应用(8)式得到对i=2, 3有

令(18)式u=u^*

综合(18)-(21)式得

将(22)式结合$\frac{1}{\mu }{\lambda _{\max }}(\mathit{\boldsymbol{A}}_i^{\rm{T}}{\mathit{\boldsymbol{A}}_i}) - \frac{{{\eta _i}}}{2} \le 0\left( {i = 2, 3} \right) $, 得到(13)式成立.

接下来将要证明遍历情况下(6)式的收敛率$ O\left( {\frac{1}{t}} \right)$.

定理1  假设$ \frac{1}{\mu } \le \min \left\{ {\frac{{{\eta _2}}}{{2{\lambda _{\max }}(\mathit{\boldsymbol{A}}_2^{\rm{T}}{\mathit{\boldsymbol{A}}_2})}}, \frac{{{\eta _3}}}{{2{\lambda _{\max }}(\mathit{\boldsymbol{A}}_3^{\rm{T}}{\mathit{\boldsymbol{A}}_3})}}} \right\} $, 序列{ω^k:=(x₁^k, x₂^k, x₃^k, λ)}由(6)式生成.对任意的整数t>0, 令

则对任意的ω^*∈Ω, 通过定义ρ:=max{d‖λ^*‖+1, ‖λ^*‖+1}, 得到

即在遍历情况下, 目标函数和等式约束的残差都以$O\left( {\frac{1}{t}} \right) $的速率收敛到0,

证  因为ω^k∈Ω, 所以对任意的整数t>0有ω^t=(u^t, λ^t)∈Ω.由引理1和∑_i=1³A_ix_i^*=b并结合(12)式和f(·)的凸性, 得到

不等式(24)对所有的λ∈$\mathbb{R} $^l都成立.由(3)式的鞍点定理得到

又记A:=(A₁, A₂, A₂), A∈$\mathbb{R} ^{l \times \sum {_{i = 1}^3} {n_i}}$; b:=λ_max(A), 由不等式(25)与ρ=max{d‖λ^*‖+1, ‖λ^*‖+1}得到不等式

在(24)式中, 令$ \mathit{\boldsymbol{\lambda }}: = - \frac{{\rho (\sum {_{i = 1}^3} {\mathit{\boldsymbol{A}}_i}\bar x_i^t - b)}}{{\left\| {\sum {_{i = 1}^3} {\mathit{\boldsymbol{A}}_i}\bar x_i^t - b} \right\|}}$, 并且利用∑_i=1³A_ix_i^*=b即能得到

我们定义函数υ(δ)=min{f(u)|$\sum {_{i = 1}^3} $A_ix_i-b=δ, x_i∈X_i}, 易证υ是凸的且B^Tλ^*∈∂υ(0), 这表明

令δ^t=∑_i=1³A_ix_i^t-b, 定义$K: = \frac{1}{{2\mu }} $∑_i=1²‖∑_j=i+1³A_j(x_i^*-x_i⁰)‖²+μ‖λ⁰‖², 则

将ρ=max{d‖λ^*‖+1, ‖λ^*‖+1}带入(29)式

联立(26), (27)和(30)式, 可以得到

所以, 由(30)和(31)式立刻就能得到(23)式.

至此, 在遍历情况下建立了3块(6)式的$ O\left( {\frac{1}{t}} \right)$收敛率.

本文在遍历情况下分析了交替邻近梯度法(APGM)的次线性收敛率.这是第一个对多块APGM进行次线性收敛率的分析.