我们主要考虑如下形式的无约束非光滑凸优化问题

$$\begin{equation}\label{minsumof2funs}\min_{x\in {\Bbb R}^n}F(x)=f(x)+h(Ax),\end{equation}$$

(1.1)

其中 $f: {\Bbb R}^n\rightarrow {\Bbb R}$ 是下半连续凸函数,$h: {\Bbb R}^m\rightarrow{\Bbb R}$ 是具有梯度 Lipschitz 连续的 $\mu$ -强凸函数,矩阵 $A \in {\Bbb R}^{m\times n}$.

许多现代统计和信号应用领域的问题 (如:信号噪声处理,压缩感知等) 都可以归结为具有问题 (1.1) 形式的非光滑凸优化问题. 众所周知,一个常用来估计稀疏变量 $x$ 的技术手段是LASSO^[16],利用它可以同时选择和估计变量. LASSO 可以被看作 $\ell_1$ -范数正则化问题,也就是问题 (1.1) 中的函数形式如

$$\begin{equation}\label{minspecialf1f2} f(x)=\lambda\|x\|_1 \mbox{和}h(\cdot)=\frac12\|\cdot-d\|^2,\end{equation}$$

(1.2)

其中最小化 $\|Ax-d\|^2$ 的作用是减少噪声,同时 $\ell_1$ -范数最小化可以使问题的解 $x$ 稀疏. 稀疏也意味着挑选出了变量 $x$ 的具有决定作用的分量.

Bakin^[1] 在 1999 年提出了适用于变量分块的 LASSO,同时也给出了问题的算法. 他当时提出的问题可以看成是问题 (1.1) 中函数形式为

$$\begin{equation}\label{newgrouplasso} f(x)=\sum_{J\in{\cal J}}w_J\|x_J\|_{K_J} \mbox{和}h(Ax)=\frac12\|Ax-d\|^2, \end{equation}$$

(1.3)

其中 ${\cal J}$ 是指标集 $\{1,\cdots ,n\}$ 的一个划分,$|J|$ 表示子集 $J\in {\cal J}$ 的基数(元素个数),$x_J\in {\Bbb R}^{|J|}$. $\{ w_J\}_{J\in{\cal J}}$ 是给定的非负常数集合,并且 $$\|x_J\|_{K_J}:=\sqrt{x^T_JK_Jx_J}=\|B_Jx_J\|,$$ 这里的 $B_J\in R^{|J|\times |J|}$ 是个非奇异矩阵,$K_J=B_J^TB_J\succ0$ 表示其是个对称正定矩阵.

这个形式的问题相当于用在变量为分块形式时的 LASSO. 更进一步, 当取 $K_J=I$,这个问题就是块 LASSO 手段^[19]. 大家可以参考文献 [2, 10]去了解块 LASSO 技术的应用, 也可以阅读文献[11] 去进一步了解在统计方面块 LASSO 的应用.

但是,由于块 LASSO 手段并不能使变量的分块稀疏, 文献 [7]中提出一个可以使变量分块稀疏的手段. 这个技术手段可以称为稀疏块 LASSO,同时也可以看成问题 (1.1) 中函数形式为

$$\begin{equation}\label{sparsegrouplasso} f(x)=\sum_{J\in{\cal J}}w_J\|x_J\|+\lambda\|x\|_1 \mbox{和}h(Ax)=\frac12\|Ax-d\|^2. \end{equation}$$

(1.4)

使用邻近梯度法 (PGM) 来求解问题 (1.1),取函数形式为 (1.3) 或者 (1.4)式. 线性收敛速率分别由文献[20]和[21] 证明.

本文主要结果如下.

在本文中,我们提出了一类修正的邻近梯度法来求解相同问题. 在保证算法是线性收敛的基础上, 与邻近梯度法相比,主要是以下方面做出了修正.

(1) 我们提出的修正邻近梯度法中的步长 $\alpha_k$ 是自适应的, 而邻近梯度法中的步长需要 3 次或更多次线搜索来得到. 从这个意义上来讲, 本文中的修正邻近梯度法的计算代价要小.

(2) 邻近梯度法的线性收敛性需要步长有一个理论上的下界 $\underline{\alpha}>0$ 和其他的前提条件,但是方法本身并不能保证步长不会太小. 而我们提出的修正邻近梯度法中的步长 $\alpha_k$ 有一个明确的下界. 这也解决了邻近梯度法的步长可能要很小的缺点.

本文内容安排如下.

修正邻近梯度法的算法框架是在第3节给出, 它的线性收敛性是在第4节给出. 第5节也是最后一节是我们的数值实验.

我们首先介绍几个基本的定义.

定义 2.1 设集合 $S\subset{\Bbb R}^n$,如果对任意的 $x_1,x_2 \in S$ 以及任意的 $\alpha\in [0, 1]$,有 $$\alpha x_1+(1-\alpha)x_2\in S,$$ 那么称 S 是凸集.

定义 2.2 设集合 $S\subset{\Bbb R}^n$ 为凸集,$\alpha\in[0, 1]$,$f$ 是定义在 S 上的函数. 如果对任意的 $x_1,x_2 \in S$,有 $$f(\alpha x_1+(1-\alpha)x_2)\leq\alpha f(x_1)+(1-\alpha)f(x_2),$$ 称 $f$ 为 S 上的凸函数.

函数 $f$ 在集合 S 上是$\mu$ -强凸函数当且仅当函数 $f-(1/2)\mu\|\cdot\|^2$ 在集合S上是凸函数.

定义 2.3 函数 $f$ 称为 coercive 的,如果 $$\lim_{\|x\|\rightarrow+\infty}f(x)=+\infty.$$

定义 2.4 函数$h$被称为 $L$ -Lipschitz 连续的,如果存在正数 L,使得对任意 $x,y$ 都有下式成立 $$\|h(x)-h(y)\|\leq L\|x-y\|.$$ 这里也称 $L$ 是函数 $h$ 的 Lipschitz 常数. 同理，如果称函数 $h$ 是梯度 $L$ -Lipschitz 连续的,就表示其梯度满足 $$\|\nabla h(x)-\nabla h(y)\|\leq L\|x-y\|.$$

接下来介绍一个求解非光滑凸优化问题 (1.1) 的常用方法: 邻近梯度法 (PGM)^{[3, 4]}.

先介绍邻近算子的定义. 对于凸函数 $\varphi(x)$ (可能非光滑),Moreu-Yoshida 邻近算子^[14] $\mbox{prox}_{\varphi}:{\Bbb R}^n\mapsto {\Bbb R}^n$ 定义如下

$$\begin{equation}\label{def-of-prox} \mbox{prox}_\varphi (x)=\mbox{arg}\min_{y\in {\Bbb R}^n}\varphi(y)+\frac12\|y-x\|^2. \end{equation}$$

(2.1)

因为 $\frac12\|\cdot-x\|^2$ 是强凸函数,$\varphi(\cdot)$ 是凸函数, 那么问题 (2.1) 的最小值存在且唯一,所以邻近算子 $\mbox{prox}_\varphi$ 在解决凸优化问题时有很好的适用性.

使用邻近算子,我们可以把问题问题 (1.1) 的最优性条件写成一个不动点方程

$$\begin{equation}\label{optimality} x=\mbox{prox}_{\alpha f}(x-\alpha A^T\nabla h(Ax)), \end{equation}$$

(2.2)

对于某些 $\alpha>0$. 邻近梯度法 (PGM) 可以通过如下迭代公式来解上面的不动点方程

$$\begin{equation}\label{form-of-it} x^{k+1}=\mbox{prox}_{\alpha_kf}(x^k-\alpha_kA^T\nabla h(Ax^k)),\quad k=0,1,2,\cdots, \end{equation}$$

(2.3)

其中 $\alpha_k>0$ 是步长.

即使被经常采用,邻近梯度法的收敛性分析还是非常少的. 例如,通过 文献[5,定理3.4],我们只知道如果步长 $\alpha_k$ 满足

$$\begin{equation}\label{def-of-alpha} 0 < {\rm{ }}\underline{\alpha}\le \alpha_k\le \bar{\alpha} < {\frac{2}{L\|A\|^2}},\quad k=0,1,2,\cdots, \end{equation}$$

(2.4)

其中 $L$ 是函数 $h$ 的梯度 $\nabla h$ 的 Lipschitz 常数.

那么由邻近梯度法 (2.3) 得到的迭代序列 $\{x^k\}_{k\geq0}$ 收敛到问题 (1.1) 的一个解. 收敛速率是次线性 $O(1/k)$ (参见文献[12]). 除了一些特殊情况外, 它的线性收敛速率还是没有得到证明. Luo^[9],Tseng^[13], Luo^[20] 和 Zhang^[21] 已经证明了邻近梯度法 (PGM) 在 $f(x)$ 满足某些条件时的线性收敛速率,并且这不需要 $h(Ax)$ 是强凸函数的前提. 特别地，在一些应用中，不论是 LASSO,块 LASSO,或者稀疏块 LASSO, 测量值的个数一般是远小于未知量的个数,也就是说 $m\ll n$,所以矩阵 $A$ 不可能列满秩,这意味着 $h(Ax)$ 不可能是强凸函数.

考虑求解问题 (1.1),取函数形式为 (1.3) 或者 (1.4)式. 在这一节,我们将给出解此问题的修正邻近梯度法 (MPGM) 的框架以及分析.

对问题(1.1)的MPGM算法

步 1 任意初始点 $x^0$ 和一个比较小的正数 $\varepsilon$,取 $k=0$.

步 2 计算 $y^k=\mbox{prox}_{f}(x^k-A^T\nabla h(Ax^k))$, 如果 $\|x^k-y^k\|\leq \varepsilon$,停止;

其它,计算 $z^k=x^k-y^k+A^T(\nabla h(Ax^k)-\nabla h(Ay^k)$).

取$\alpha_k=\|x^k-y^k\|^2/\|z^k\|^2$,计算 $x^{k+1}=x^k-\alpha_kz^k$.

步 3 如果 $\|x^{k+1}-x^k\|\leq \varepsilon$,停止; 否则, 取 $k=k+1$,转步 2.

引理 3.1 考虑问题 (1.1),$\bar{X}$ 表示该问题的最优解集合. 假设 $\bar{X}\neq\emptyset$,那么

(1) $\bar{X}$ 是一个闭凸集.

(2) $x\rightarrow Ax$ 在集合$\bar{X}$内是个常值函数,即存在 $\bar{s} \in \mbox{dom}(h)$ 使得对任意 $x\in \bar{X}$,有

$$\begin{equation}\label{ax=ybar} Ax=\bar{s}. \end{equation}$$

(3.1)

证 (1) 因为问题 (1.1) 的目标函数 $F(x)$ 是个下半连续凸函数,根据文献 [8,性质1.1.6 和 性质 1.2.2],水平集 $\{x|F(x)\leq \min F\}$ 是个闭凸集.

(2) 相同的证明大家可以参考文献 [21,引理 2] 或者文献 [20,性质 2],这里我们就不再赘述.

引理 3.2 假设问题 (1.1) 的最优解集合 $\bar{X}$ 非空. 对任意 $x\in \mbox{dom}(f+h\circ A)$, 令 $$y(x)=\mbox{prox}_{f}(x-A^T\nabla h(Ax)), ~~\bar{X}_1=\{x|x=y(x)\}$$ 和 $$\bar{X}_2=\{x|x=y(x)-A^T(\nabla h(Ax)-\nabla h(Ay(x)))\}.$$ 那么 $\bar{X}$ 是一个闭凸集,并且 $$\bar{X}_1=\bar{X}_2=\bar{X}.$$

证 对任意 $x\in\bar{X}_1$,$y(x)=x$,$\nabla h(Ax)=\nabla h(Ay(x))$,我们有 $x\in\bar{X}_2$. 因此,$\bar{X}_1\subseteq\bar{X}_2.$ 假设存在 $x\in\bar{X}_2$ 但是 $x$ 不属于 $\bar{X}_1$,即$\|x-y(x)\|\neq0$. 那么 $$\begin{eqnarray*} % \nonumber to remove numbering (before each equation) && \|x-y(x)+A^T(\nabla h(Ax)-\nabla h(Ay(x)))\|^2\\ &=&\|x-y(x)\|^2+2\langle x-y(x),A^T(\nabla h(Ax)-\nabla h(Ay(x)))\rangle\\ &&+\|A^T(\nabla h(Ax)-\nabla h(Ay(x)))\|^2 \\ &\geq&\|x-y(x)\|^2+2\langle Ax-Ay(x),\nabla h(Ax)-\nabla h(Ay(x))\rangle\\ &\geq&\|x-y(x)\|^2+2\mu\|Ax-Ay(x)\|^2>0. \end{eqnarray*}$$ 这与 $x\in\bar{X}_2$ 矛盾. 也就是说,$\bar{X}_2\subseteq\bar{X}_1.$ 从而, $\bar{X}_1=\bar{X}_2.$

对任意 $x\in\bar{X}$,由问题 (1.1) 的最优性条件和性质, 当且仅当 $$\begin{eqnarray*} 0&\in& \partial f(x)+A^T\nabla h(Ax) \Leftrightarrow x-A^T\nabla h(Ax)\in x+\partial f(x) \\ &\Leftrightarrow& x =\mbox{prox}_{f}(x-A^T\nabla h(Ax)) \Leftrightarrow x\in\bar{X}_1. \end{eqnarray*}$$ 因此,$\bar{X}_1=\bar{X}_2=\bar{X}.$

注 3.1 引理 3.2 说明如果 MPGM 算法产生的序列收敛,那么它肯定收敛于问题 (1.1) 的某个最优点,这与邻近梯度法的结果一致.

引理 3.3 MPGM 算法中的步长 $\alpha_k$ 满足

$$\begin{equation}\label{stepsize} \alpha_k\geq\frac1{(1+L\|A\|^2)^2},~~k=1,2,\cdots, \end{equation}$$

(3.2)

其中 $L$ 是梯度 $\nabla h(x)$ 的 Lipschitz 常数.

证 $$\begin{eqnarray*} \frac1{\alpha_k}&=&\frac{\|x^k-y^k+A^T(\nabla h(Ax^k)-\nabla h(Ay^k))\|^2} {\|x^k-y^k\|^2} \\ &\leq& 1+\frac{2\langle x^k-y^k,A^T(\nabla h(Ax^k)-\nabla h(Ay^k))\rangle}{\|x^k-y^k\|^2} +\frac{\|A^T(\nabla h(Ax^k)-\nabla h(Ay^k))\|^2}{\|x^k-y^k\|^2}\\ &\leq& 1+2L\|A\|^2+(L\|A\|^2)^2=(1+L\|A\|^2)^2. \end{eqnarray*}$$ 证毕.

注 3.2 引理 3.3 说明 MPGM 算法的步长有一个明确的正数下界, 因此不可能无限地小. 而邻近梯度法并不能满足这一点.

另外,在每次迭代中,MPGM 算法需要另外计算一次函数梯度, 但是邻近梯度法需要3次或更多次线搜索. 所以 PGM 算法的计算代价要高于 MPGM 算法.

在这一节,我们将证明在上一节提出的修正邻近梯度法 (MPGM) 的线性收敛性. 在此之前,我们回顾并写出我们解决问题的前提条件.

前提条件

(A1) $f,h$ 是下半连续凸函数; $f+h\circ A$ 是 coercive 的;

(A2) $h$ 是 $\mu$ -强凸函数并且是梯度 $L$ -Lipschitz 连续的,其中 $\mu,L>0$;

(A3) $H(s):=\nabla^2h(s)$ 是 $L'$-Lipschitz 连续函数,$L'>0$.

(A4) {误差界条件:} 令 $\bar{X}$ 表示问题 (1.1) 的最优解集, $\mbox{dist}_{\bar{X}}(x) := \min\limits_{x^*\in \bar{X}}\|x -x^*\|$.

那么对任意的 $\xi\ge \min F(x)$,存在 $\kappa,\; \varepsilon > 0$ 使得

$$\begin{equation}\label{error-bd-cond} \mbox{dist}_{\bar{X}}(x)\le \kappa\|\mbox{prox}_{f}(x-A^{T}\nabla h(Ax))-x\|, \end{equation}$$

(4.1)

对任意满足 $\|\mbox{prox}_{f}\left(x-A^T\nabla h(Ax)\right)-x\| \le \varepsilon$ 和 $F(x)\leq\xi$ 的 $x$ 成立.

误差界条件 (A4) 对于 MPGM 算法的线性收敛性证明是非常重要的.

我们给出下面的引理来推导出 MPGM 算法的线性收敛性证明.

引理 4.1 对任意 $x^*\in\bar{X}$,由引理 3.1,$\bar{s}=Ax^*$, 存在邻域 $B(\bar{s},\delta)$,使得当 $Ax\in B(\bar{s},\delta)$, $y=\mbox{prox}_{f}(x-A^T\nabla h(Ax))$,$\eta\in[Ax,\bar{s}],\xi\in[Ax,Ay]$,有下式成立 $$\langle A(x-y),(H(\eta)-H(\xi))A(x-x^*)\rangle-\mu\|A(x-x^*)\|^2\leq0.$$

证 注意到 $\bar{X}$ 是闭凸集. 如果 $A(x-x^*)=0$,那么 $x\in\bar{X}$, 并且由引理 3.2,$y\in\bar{X}$. 假设 $A(x-x^*)\neq0$. 当 $x$ 充分靠近 $x^*$ 且 $Ax\neq Ax^*$ 时, 由于临近算子是非扩张的,再由文献 [20,引理 2]有 $\|x-\bar{x}\|\leq \kappa'\|Ax-\bar{s}\|$, 这里 $$\bar{x}:=\mbox{arg}\min\limits_{w\in\bar{X}}\{\|x-w\|\},$$ 我们有 $$\begin{eqnarray*} \|Ay-Ax^*\|&=&\|Ay-A\bar{x}\|\leq\|A\|\|y-\bar{x}\|\\ &\leq&\|A\|\,\|x-A^T\nabla h(Ax)-\bar{x}+A^T\nabla h(A\bar{x})\|\\ &\leq&\|A\|(\|x-\bar{x}\|+\|A^T(\nabla h(Ax)-\nabla h(A\bar{x}))\|)\\ &\leq&\|A\|(\kappa'\|Ax-\bar{s}\|+\|A^T(\nabla h(Ax)-\nabla h(\bar{s}))\|)\\ &\leq&(\kappa'\|A\|+L\|A\|^2)\|Ax-\bar{s}\|\\ &=&M\|Ax-\bar{s}\| =M\|A(x-x^*)\|, \end{eqnarray*}$$ 其中 $M:=\kappa'\|A\|+L\|A\|^2$,再由条件 (A3) 和 $\eta\in[Ax,\bar{s}],\xi\in[Ax,Ay]$, $$\begin{eqnarray*} &&\langle A(x-y),(H(\eta)-H(\xi))A(x-x^*)\rangle\\ &\leq& \|A(x-y)\|L'\|\eta-\xi\|\|A(x-x^*)\|\\ &\leq&\|A(x-y)\|L'\{\|A(x-x^*)\|+\|A(x-y)\|\}\|A(x-x^*)\|\\ &=&L'\|A(x-y)\|^2\|A(x-x^*)\|+L'\|A(x-y)\|\|A(x-x^*)\|^2\\ &=&L'\|A(x-y)\|\{\|A(x-y)\|\|A(x-x^*)\|+\|A(x-x^*)\|^2\}\\ &\leq&L'\|A(x-y)\|\{(\|A(x-x^*)\|+\|A(x^*-y)\|)\|A(x-x^*)\|+\|A(x-x^*)\|^2\}\\ &\leq&L'\|A(x-y)\|\{\|A(x^*-y)\|\|A(x-x^*)\|+2\|A(x-x^*)\|^2\}\\ &\leq&L'\|A(x-y)\|\{M\|A(x-x^*)\|^2+2\|A(x-x^*)\|^2\}\\ &\leq&L'(M+2)\|A(x-y)\|\|A(x-x^*)\|^2. \end{eqnarray*}$$ 当 $x$ 充分靠近 $x^*$ 时,$\|A(x-y)\|$ 无限接近 $0$, 所以我们有 $$L'(M+2)\|A(x-y)\|\leq\mu.$$ 结论得以证明.

定理 4.1 考虑求解问题 (1.1),取函数形式为 (1.3) 或者 (1.4). 如果 $\bar{X}\neq\emptyset$,那么

对任意 $\zeta \in {\Bbb R}$,$\{x|F(x)\leq\zeta\}$ 是有界的. 并且误差界条件 (4.1) 成立.

证 证明见文献 [21,定理 2] 和文献 [20,定理1].

现在,我们可以证明我们提出的修正邻近梯度法的线性收敛性了.

定理 4.2 假设函数 $f$ 和 $h$ 满足条件 (A1)--(A4),并且问题 (1.1) 的最优解集 $\bar{X}$ 非空. 那么由上面的 MPGM 算法得到的迭代序列是收敛的,并且当初始点 $x^0$ 离最优解集 $\bar{X}$ 充分近时,该迭代序列以线性的速率收敛到最优解集 $\bar{X}$ 中的一个点.

证 在 MPGM 算法中, $$y^{k}=\arg\min_{x}\left\{f(x)+\frac{1}{2}\|x-x^{k}+A^{T}\nabla h(Ax^{k})\|^2\right\},~k=0,1,2,\cdots.$$ 所以, $$x^k-y^k-A^T\nabla h(Ax^k)\in \partial f(y^k).$$ 因此对任意的 $x^*\in\bar{X}$,由问题 (1.1) 的最优性条件, $-A^T\nabla h(Ax^*)\in\partial f(x^*)$. 由 $\partial f$ 的单调性^[15],我们有

$$\begin{equation}\label{monotone} \langle x^k-y^k-A^T(\nabla h(Ax^k)+A^T\nabla h(Ax^*)),~~y^k-x^*\rangle\geq0, \end{equation}$$

(4.2)

即 $$\langle x^k-y^k-A^T\nabla h(Ax^k)+A^T\nabla h(Ax^*),~~x^k-x^*-(x^k-y^k)\rangle\geq0.$$ 所以我们可以推得 $$\begin{eqnarray*} &&\langle x^k-x^*,x^k-y^k\rangle+\langle x^k-y^k,A^T(\nabla h(Ax^k)-\nabla h(Ax^*)) \rangle\\ &\geq& \langle x^k-x^*,A^T(\nabla h(Ax^k)-\nabla h(Ax^*))\rangle + \|x^k-y^k\|^2. \end{eqnarray*}$$ 根据函数 $h$ 的强凸性,我们进一步有

$$\begin{eqnarray} &&\langle x^k-x^*,x^k-y^k\rangle+\langle x^k-y^k,A^T(\nabla h(Ax^k)-\nabla h(Ax^*))\rangle\nonumber\\ &=&\langle x^k-x^*,x^k-y^k\rangle+\langle A(x^k-y^k),\nabla h(Ax^k)-\nabla h(Ax^*)\rangle\nonumber\\ &\geq&\langle A(x^k-x^*),\nabla h(Ax^k)-\nabla h(Ax^*)\rangle + \|x^k-y^k\|^2\nonumber\\ &\geq&\mu\|A(x^k-x^*)\|^2 + \|x^k-y^k\|^2\label{mpgm1}. \end{eqnarray}$$

(4.3)

从而,我们有

$$\begin{eqnarray} &&\|x^{k+1}-x^*\|^2=\|x^k-x^*-\alpha_kz^k\|^2\nonumber\\ &=&\|x^k-x^*-\alpha_k(x^k-y^k+A^T(\nabla h(Ax^k)-\nabla h(Ay^k)))\|^2\nonumber\\ &=& \|x^k-x^*\|^2-2\alpha_k\langle x^k-x^*,x^k-y^k+A^T(\nabla h(Ax^k)-\nabla h(Ay^k))\rangle+\alpha_k^2\|z^k\|^2\nonumber\\ &=& \|x^k-x^*\|^2-2\alpha_k\{\langle x^k-x^*,x^k-y^k\rangle+\langle x^k-y^k,A^T(\nabla h(Ax^k)-\nabla h(Ax^*))\rangle\nonumber\\ &&+\langle x^k-x^*,A^T(\nabla h(Ax^k)-\nabla h(Ay^k))\rangle -\langle x^k-y^k,A^T(\nabla h(Ax^k)-\nabla h(Ax^*))\rangle\} \nonumber\\ &&+\alpha_k\|x^k-y^k\|^2\nonumber\\ & \le & \|x^k-x^*\|^2-2\alpha_k(\mu\|A(x^k-x^*)\|^2 + \|x^k-y^k\|^2) +\alpha_k\|x^k-y^k\|^2\nonumber\\ && -2\alpha_k\{\langle A(x^k-x^*),\nabla h(Ax^k)-\nabla h(Ay^k)\rangle-\langle A(x^k-y^k),\nabla h(Ax^k)-\nabla h(Ax^*)\rangle\}\nonumber\\ &= &\|x^k-x^*\|^2-2\alpha_k\mu\|A(x^k-x^*)\|^2 -\alpha_k\|x^k-y^k\|^2\nonumber\\ && -2\alpha_k\{\langle A(x^k-x^*),H(\xi)A(x^k-y^k)\rangle-\langle A(x^k-y^k),H(\eta)A(x^k-x^*)\rangle\}\nonumber\\ &= &\|x^k-x^*\|^2-2\alpha_k\mu\|A(x^k-x^*)\|^2 -\alpha_k\|x^k-y^k\|^2\nonumber\\ && +2\alpha_k\langle A(x^k-y^k),(H(\eta)-H(\xi))A(x^k-x^*)\rangle\nonumber\\ &=&\|x^k-x^*\|^2-\alpha_k\|x^k-y^k\|^2 +2\alpha_k\{\langle A(x^k-y^k),(H(\eta)-H(\xi))A(x^k-x^*)\rangle\nonumber\\ &&- \mu\|A(x^k-x^*)\|^2\}\nonumber\\ &\leq &\|x^k-x^*\|^2-\alpha_k\|x^k-y^k\|^2\label{locallity}\\ &\leq& \|x^k-x^*\|^2-\frac1{(1+L\|A\|^2)^2}\|x^k-y^k\|^2=\|x^k-x^*\|^2-\rho\|x^k-y^k\|^2, \label{finalbig} \end{eqnarray}$$

(4.4)

这里 $\rho:=\frac1{(1+L\|A\|^2)^2}.$ 第一个不等式由 (4.3) 式得到, 第二个不等式来源于引理 4.1,由引理 3.3 可以推出第三个不等式.

综上,我们得到序列 $\{x^k\}$ 是有界的并且随着 $k \rightarrow +\infty$, $x^k-y^k \rightarrow 0$. 因此,它存在收敛的子序列 $\{x^{k(j)}\}$,并且它的极限点 $x^{\infty}$ 是同时满足 $\{x^{k(j)}\}\rightarrow x^{\infty}$ 和 $y^{k(j)} \rightarrow x^{\infty}$ 的. 取任意 $x\in R^n$ 和 $w\in \partial f(x)$. 由 (4.2) 式和 $\partial f$ 的单调性 $$\langle x^k-y^k-A^T(\nabla h(Ax^k))-w,~~y^k-x\rangle\geq0.$$ 那么沿 $k(j)$ 取极限得到 $$\langle -A^T(\nabla h(Ax^{\infty}))-w,~~x^{\infty}-x\rangle\geq0.$$ 因为 $\partial f$ 是极大单调算子^[6],我们可以得到 $$-A^T(\nabla h(Ax^{\infty}))\in \partial f(x^{\infty}).$$ 因此,$x^{\infty}\in\bar{X}$. 由 (4.5) 式知 $$\|x^{k+1}-x^{\infty}\|^2\leq \|x^k-x^{\infty}\|^2-\rho\|x^k-y^k\|^2,$$ 那么,序列 $\{\|x^k-x^{\infty}\|\}$ 收敛. 又由于它的子序列 $\{\|x^{k(j)}-x^{\infty}\|\}$ 收敛到 $0$,所以 $\{\|x^k-x^{\infty}\|\}$ 收敛到 $0$. 从而有,$x^k\rightarrow x^{\infty}$. 记 $$\bar{x}^k:=\mbox{arg}\min\limits_{x\in\bar{X}}\|x-x^k\|,~k=1,2,\cdots,$$ 由于 $\bar{X}$ 是闭集,从而 $\bar{x}^k\in\bar{X}$. 由 (4.5) 式和定理 4.1推得 $$\|x^{k+1}-\bar{x}^{k+1}\|^2\leq\|x^{k+1}-\bar{x}^k\|^2\leq\|x^k-\bar{x}^k\|^2-\rho\|x^k-y^k\|^2\leq(1-\frac{\rho}{\kappa^2})\|x^k-\bar{x}^k\|^2,$$ 这意味着 $\{x^k\}$ 以线性速率收敛到最优解集 $\bar {X}$ 中的一点.

在本节中,我们同时用我们提出的修正邻近梯度法 (MPGM) 和原始的邻近梯度法 (PGM) 来求解取函数形式为 (1.4)式的问题(1.1). 我们选取了几类不同的数据来测试两个算法的效果,并把它们做了比较与分析. 数值实验是在一台具有 Intel Core CPU $2.20$ GHz 和$2$ GB RAM的电脑上进行的. 软件平台是 MATLAB $8.0.0$ (R2012b). 终止误差精度 ($\varepsilon$) 取 $10^{-6}$.

在两个算法中,矩阵 $A$,向量$d$ 和 初始向量 $x^{0}$ 是随机选取的. 至于函数 (1.4) 中的参数与分块,我们选取 $\lambda =w_{J}=1$,并把集合$\{1,2,\cdots,n \}$ 分为 $10$ 块. 不失一般性,对称正定矩阵 $K_{J}$ 我们设为单位矩阵. 这是由于对称正定矩阵与单位矩阵合同,选取单位矩阵与其情况等价.

我们测试了两个算法的计算时间和最优目标函数值来显示它们在计算效果方面的差异,数值实验结果见表 1.

在表 1 中,第一列中是矩阵 $A$ 的维数. 邻近梯度法 (PGM) 的测试结果 (计算时间和最优函数值) 分别放在第二和第三列. 对应的,修正邻近梯度法 (MPGM)的结果放在第四和第五列. 表中的数据显示两个算法的最优值是几乎相同的,但是 MPGM 算法是在较少的计算时间内完成的. 这很好地对应了我们在引言的最后部分所 说明的我们所提出的修正邻近梯度法 (MPGM) 相对于邻近梯度法 (PGM) 的改进. 主要原因是我们提出的修正邻近梯度法中的步长 $\alpha_k$ 是自适应的,而邻近梯度法中的步长需要3次或更多次线搜索来得到. 同时还有步长 $\alpha_k$ 在我们提出的 MPGM 算法中有个明确的正数下界,从而每一步迭代都有明确的行进. 而 PGM 算法可能会出现步长很小的情况,这样可能会导致迭代的效果相对改变不明显.