7.12最优化修正

BCD收敛性证明（续）

1 问题回顾

1.1 优化模型：

$$\begin{array}{r}\underset{x\in {\mathbb{R}}^n,y\in {\mathbb{R}}^m}{\min }\Psi (x,y)\stackrel{def}{=}f(x)+g(x)+H(x,y)\end{array}$$

1.2问题假设：

• $f:{\mathbb{R}}^n\to (-\infty ,+\infty ],g:{\mathbb{R}}^m\to (-\infty ,+\infty ]$ 为适当闭函数， $H:{\mathbb{R}}^n\times {\mathbb{R}}^m$ 为定义域上的连续可微函数.
• ${\inf }_{{\mathbb{R}}^n\times {\mathbb{R}}^m}\Psi >-\infty ,{\inf }_{{\mathbb{R}}^m}f>-\infty ,{\inf }_{{\mathbb{R}}^m}g>-\infty$
• $H$ 满足 $\nabla H$ 在有界集上是联合Lipschitz连续的，即对于任意的有界集 $B_1\times B_2\subset {\mathbb{R}}^n\times {\mathbb{R}}^m$ 存在 $L>0$ 使得对于任意的 $(x_i,y_i)\in B_1\times B_2,i=1,2$ 满足：$\begin{array}{r}\Vert ({\nabla }_{x}H(x_1,y_1)-{\nabla }_{x}H(x_2,y_2),{\nabla }_{y}H(x_1,y_1)-{\nabla }_{y}H(x_2,y_2)\Vert \le L\Vert (x_1-x_2,y_1-y_2)\Vert \end{array}$

1.3 迭代过程：

• $x_{k+1}\in \arg {\min }_x\left\{f(x)+H(x_k;y_k)+{\nabla }_{x}H(x_k;y_k{)}^T(x-x_k)+\frac{L_x}{2}\Vert x-x_k{\Vert }^2\right\}$
• $y_{k+1}\in \arg {\min }_y\left\{g(y)+H(x_{k+1};y_k)+{\nabla }_{y}H(x_{k+1};y_k{)}^T(y-y_k)+\frac{L_y}{2}\Vert y-y_k{\Vert }^2\right\}$
  （注：此处仅证明固定步长的收敛性）

2 已证明结论

2.1 充分下降：

$$\begin{array}{rl}& \exists {\rho }_1,{\rho }_1>0\\ & \\ s.t.{\rho }_1\Vert z^{k+1}& -z^k{\Vert }^2\le \Psi (z^k)-\Psi (z^{k+1})(1)\end{array}$$

2.2 次梯度上界：

假设算法产生的迭代序列$\{z^k\}$有界，找到另一个常数${\rho }_2$，使得次梯度有一个上界估计：

$$\begin{array}{r}\Vert w^{k+1}\Vert \le {\rho }_2\Vert z^{k+1}-z^k\Vert ,w^{k+1}\in \hat{\partial }\Psi (z^{k+1})(2)\end{array}$$

2.3 子序列收敛性：

定义 $\omega (z_0)$ 为近似点交替线性化方法从点 $z_0$ 出发产生迭代序列的所有极限点集，且 $\{z^k\}$ 是有界序列，则以下结论成立：

• 1. $\varnothing \ne \omega (z_0)\subset \mathrm{crit}\Psi =\{z:0\in \partial \Psi (z)\}$
• 2. $\omega (z_0)\text{ 是非空的连通紧集。}$
• 3. $\Psi$ 在 $\omega (z_0)$ 上是一个有限常数
• 4. $\{\Psi (z^k)\}$ 总是收敛的

3 全序列收敛证明

3.1 K-L性质：

3.1.1 定义：
定义函数族 ${\Phi }_{\eta }$ 是凹连续函数 $\phi :[0,\eta )\to {\mathbb{R}}^{+}$ 的集合，且满足如下条件：

• 1. $\phi (0)=0$
• 2. $\phi$ 在$(0,\eta )$ 内连续可微，在点 $0$ 处连续
• 3. $\forall s\in (0,\eta )$ 都有${\phi }^{\prime }(s)>0$
     设 $\sigma :{\mathbb{R}}^d\to (-\infty ,+\infty ]$ 是适当下班连续函数，则称 $\sigma$ 在点 $\bar{u}\in \mathrm{dom}\partial \sigma \stackrel{\text{def}}{=}\{u\mid \partial \sigma (u)\ne \varnothing \}$ 处具有KL性质，若存在 $\eta \in (0,+\infty ]$ 和 $\bar{u}$ 的一个邻域 $U$ 以及函数 $\phi \in {\Phi }_{\eta }$ ，使得 $\forall u\in U\cap \{\sigma (\bar{u})<\sigma <\sigma (\bar{u})+\eta \}$ 满足：

$${\phi }^{\prime }(\sigma (u)-\sigma (\bar{u}))\cdot \mathrm{dist}(0,\partial \sigma (u))\ge 1$$

若 $\sigma$ 在 $\mathrm{dom}\partial \sigma$ 上处处满足KL性质，则称 $\sigma$ 是一个KL函数.
3.1.2性质：

• 若 $\bar{u}\in \mathrm{dom}\sigma$ 不是适当闭函数$\sigma$ 的临界点，即 $0\notin \partial \sigma (\bar{u})$ ，则KL性质在 $\bar{u}$ 处自然成立.

---

Proof.
首先证明: $\exists c>0$ 使得如下推导式成立

$$\parallel u-\bar{u}{\parallel }_2+\parallel \sigma \left(u\right)-\sigma \left(\bar{u}\right){\parallel }_2<c\Rightarrow \mathrm{dist}\left(0,\partial \sigma \left(u\right)\right)\ge c.$$

反证法假设存在序列 $\left\{c_k\right\},c_k>0$ 且 $c_k\to 0$ ,存在点列 $\left\{u^k\right\}$ 使得 ${\Vert \begin{array}{c}{u}^k-\bar{u}\end{array}\Vert }_2+{\Vert \begin{array}{c}\sigma \left(u^k\right)-\sigma \left(\bar{u}\right)\end{array}\Vert }_2<c_k$ ,但是 $\mathrm{dist}\left(0,\partial \sigma \left(u^k\right)\right)<c_k$ , 也即 $\exists w^k\in \partial \sigma \left(u^k\right)$ 满足 ${\Vert \begin{array}{c}{w}^k\end{array}\Vert }_2<c_k$ . 由 $\partial \sigma$ 的闭性以及 $u^k\to \bar{u}$ , $w^k\to 0$ 可知, $0\in \partial \sigma \left(\bar{u}\right)$ . 矛盾.
然后: 取 $\phi \left(t\right)=c^{-1}t,u\in B\left(\bar{u},\frac{c}{2}\right)\cap \left[\sigma \left(\bar{u}\right)-\frac{c}{2}<\sigma \left(u\right)<\sigma \left(\bar{u}\right)+\frac{c}{2}\right]$ ,可得 $\mathrm{KL}$ 不等式在 $\bar{u}$ 处成立.

---

• 若 $0\in \partial \sigma \left(\bar{u}\right)$ ,此时 $\mathrm{KL}$ 性质保证了 “函数 $\sigma$ 可被锐化”. 令 $\tilde{\phi }\left(u\right)=\phi \left(\sigma \left(u\right)-\sigma \left(\bar{u}\right)\right)$ KL 性质在某种条件下可以改写成 $\mathrm{dist}\left(0,\partial \tilde{\phi }\left(u\right)\right)\ge 1$ 其中 $u$ 的取法需要保证 $\sigma \left(u\right)>\sigma \left(\bar{u}\right)$ . 3.1.3 特殊的KL函数-半代数函数 定义: 称 ${\mathbb{R}}^d$ 的子集 $S$ 是一个半代数集, 如果存在有限个实多项式函数 $g_{ij},h_{ij}:{\mathbb{R}}^d\to \mathbb{R}$ 使得$S={\cup }_{j=1}^p{\cap }_{i=1}^q\left\{u\in {\mathbb{R}}^d:g_{ij}\left(u\right)=0,h_{ij}\left(u\right)<0\right\}$ 称函数 $h:{\mathbb{R}}^d\to (-\infty ,+\infty ]$ 为半代数函数,若 $h$ 的函数图像 $\left\{\left(u,t\right)\in {\mathbb{R}}^{d+1}:h\left(u\right)=t\right\}$ 是 ${\mathbb{R}}^{d+1}$ 的半代数子集.
  设 $\sigma \left(u\right):{\mathbb{R}}^d\to \left(-\infty ,+\infty \right)$ 是下半连续适当函数,若 $\sigma$ 是半代数函数,则它在dom $\sigma$ 中任一点处满足KL性质. 常见的半代数函数:
• 多项式实值函数
• 半代数集的指示函数
• 半代数函数的复合
• $\cdots$
  3.1.4 一致KL性质 Lemma1: 设 $\Omega$ 是紧集, $\sigma :{\mathbb{R}}^d\to (-\infty ,+\infty ]$ 是适当下半连续函数, $\sigma$ 在 $\Omega$ 上为常数且在 $\Omega$ 的每个点处都满足KL性质,则存在 $\epsilon >0,\eta >0$ , $\phi \in {\Phi }_{\eta }$ ,使得对任意 $\bar{u}\in \Omega$ 和所有满足以下条件的 $u$ :$\left\{u\in {\mathbb{R}}^d:\mathrm{dist}\left(u,\Omega \right)<\epsilon \right\}\cap \left[\sigma \left(\bar{u}\right)<\sigma <\sigma \left(\bar{u}\right)+\eta \right]$ 有:

$${\phi }^{\prime }\left(\sigma \left(u\right)-\sigma \left(\bar{u}\right)\right)\mathrm{dist}\left(0,\partial \sigma \left(u\right)\right)\ge 1.$$

---

Proof.
由有限覆盖定理 ${\mathbb{R}}^d$ 上的紧集可以由有限多个开集覆盖. 设 $\mu$ 是 $\sigma$ 在 $\Omega$ 上的取值. 由于 $\Omega$ 是紧集,根据有限覆盖定理,存在有限多个开球 $B\left(u_i,{\epsilon }_i\right)$ (其中 $u_i\in \Omega ,i=1,2,\cdots ,p$ ) 使得 $\Omega \subset \bigcup _{i=1}^{p}B\left(u_i,{\epsilon }_i\right)$ .现在考虑这些点 $u_i$ . 在点 $u_i$ 上KL 性质成立,设 ${\phi }_i:\left[0,{\eta }_i\right)\to {\mathbb{R}}_{+}$是对应的重参数化子, 则对任意 $u\in B\left(u_i,{\epsilon }_i\right)\cap \left[\mu <\sigma <\mu +{\eta }_i\right]$ ,有逐点的 $\mathrm{KL}$ 性质:

$${\phi }_i^{\prime }\left(\sigma \left(u\right)-\mu \right)\mathrm{dist}\left(0,\partial \sigma \left(u\right)\right)\ge 1.$$

取充分小的 $\epsilon >0$ 使得

$$U_{\epsilon }\stackrel{\text{ def }}{=}\left\{u\in {\mathbb{R}}^d\mid \mathrm{dist}\left(u,\Omega \right)\le \epsilon \right\}\subset \bigcup _{i=1}^{p}B\left(u_i,{\epsilon }_i\right).$$

取 $\eta =\underset{i}{\min }{\eta }_i$ ,以及

$$\phi \left(s\right)=\sum _{i=1}^p{\phi }_i\left(s\right)$$

容易验证 $\phi \in {\Phi }_{\eta }$ . 对任意的 $u\in U_{\epsilon }\cap \left[\mu <\sigma <\mu +\eta \right]$ , $u$ 必定落在某个球 $B\left(u_{i_0},{\epsilon }_{i_0}\right)$ 中,我们有

$$\begin{array}{rl}{\phi }^{\prime }\left(\sigma \left(u\right)-\mu \right)\mathrm{dist}\left(0,\partial \sigma \left(u\right)\right)& =\sum _i^p{\phi }_i^{\prime }\left(\sigma \left(u\right)-\mu \right)\mathrm{dist}\left(0,\partial \sigma \left(u\right)\right)\\ & \ge {\phi }_{i_0}^{\prime }\left(\sigma \left(u\right)-\mu \right)\mathrm{dist}\left(0,\partial \sigma \left(u\right)\right)\\ & \ge 1.\end{array}$$

即一致KL 性质成立.

---

3.2 有限长度性质

设 $\Psi$ 是KL函数, $\{z^k\}$ 是BCD算法产生的点列且满足假设条件, 则一下结论成立:

$$\sum _{k=1}^{\infty }\Vert \begin{array}{c}{z}^{k+1}-z^k\end{array}\Vert <+\infty$$

---

Proof.

• 由于 $\{z^k\}$ 是有界序列, 由致密性定理,存在子列 $\left\{z^{k_q}\right\}\to \bar{z},q\to \infty$ . 且由子序列收敛结论3, 4知, 对应的函数值列有 $\underset{k\to \infty }{\lim }\Psi \left(z^k\right)=\Psi \left(\bar{z}\right)$ .
• 下证明只需证明 $\Psi \left(\bar{z}\right)<\Psi \left(z^k\right)$ 的情况 : 若不然, 由充分下降性不等式 $(1)$ 知, 如果存在 $\bar{k}$ 使得 $\Psi \left(z^{\bar{k}}\right)=\Psi \left(\bar{z}\right)$ , 于是有$z^{\bar{k}+1}=z^{\bar{k}}$ ,且 $z^k=z^{\bar{k}},\forall k>\bar{k}$ 于是全序列收敛自然成立.
• 由于$\underset{k\to \infty }{\lim }\mathrm{dist}\left(z^k,\omega \left(z^0\right)\right)=0$ , $\underset{k\to \infty }{\lim }\Psi \left(z^k\right)=\Psi \left(\bar{z}\right)$ , 于是可知, 对任意的 $\epsilon ,\eta >0$ ,存在充分大的正整数 $l$ ,使得对任意的 $k>l$ ,

$$\Psi \left(\bar{z}\right)<\Psi \left(z^k\right)<\Psi \left(\bar{z}\right)+\eta ,\mathrm{dist}\left(z^k,\omega \left(z^0\right)\right)<\epsilon .(3)$$

• 由子序列收敛性结论2, 3知, 极限点集 $\omega \left(z^0\right)$ 为紧集, $\Psi$ 为下半连续函数, 且满足KL性质, 且$\Psi$ 在 $\omega (z_0)$ 上是一个有限常数, 于是 $\Psi$ 在 $\omega (z_0)$ 上满足一致KL性质. 且由 $(3)$ 知, 对于上 $\epsilon ,\eta$ , 当 $k>l$ 时, $z^k$ 满足KL性质的前提条件, 即: $\left\{u\in {\mathbb{R}}^d:\mathrm{dist}\left(u,\omega (z_0)\right)<\epsilon \right\}\cap \left[\Psi \left(\bar{u}\right)<\Psi <\Psi \left(\bar{u}\right)+\eta \right]$ . 于是有 $\phi \in {\Phi }_{\eta }$ 满足

$${\phi }^{\prime }\left(\Psi \left(z^k\right)-\Psi \left(\bar{z}\right)\right)\mathrm{dist}\left(0,\partial \Psi \left(z^k\right)\right)\ge 1.\forall k>l$$

• 将次梯度上界 $(2)$ 中 $w^k$ 记作 $(A_x^k,A_y^k)$ , 于是有:

$$\mathrm{dist}\left(0,\partial \Psi \left(z^k\right)\right)\le \Vert \begin{array}{c}\left(A_x^k,A_y^k\right)\end{array}\Vert \le {\rho }_2\Vert \begin{array}{c}{z}^k-z^{k-1}\end{array}\Vert .$$

代入上式可得:

$${\phi }^{\prime }\left(\Psi \left(z^k\right)-\Psi \left(\bar{z}\right)\right)\ge \frac{1}{{\rho }_2}{\Vert \begin{array}{c}{z}^k-z^{k-1}\end{array}\Vert }^{-1}(4)$$

另外,由 $\phi$ 的凹性,有

$$\begin{array}{rl}& \phi \left(\Psi \left(z^k\right)-\Psi \left(\bar{z}\right)\right)-\phi \left(\Psi \left(z^{k+1}\right)-\Psi \left(\bar{z}\right)\right)\\ \ge & {\phi }^{\prime }\left(\Psi \left(z^k\right)-\Psi \left(\bar{z}\right)\right)\left(\Psi \left(z^k\right)-\Psi \left(z^{k+1}\right)\right)(5)\end{array}$$

• 定义常数 $C=\frac{2{\rho }_2}{{\rho }_1}>0$ ,定义${\Delta }_{p,q}=\phi \left(\Psi \left(z^p\right)-\Psi \left(\bar{z}\right)\right)-\phi \left(\Psi \left(z^q\right)-\Psi \left(\bar{z}\right)\right)$ , 其中$p,q$ 是正整数. 于是将 $(4)$ 代入 $(5)$ 后有:

$$\begin{array}{rl}{\Delta }_{k,k+1}& \ge {\phi }^{\prime }\left(\Psi \left(z^k\right)-\Psi \left(\bar{z}\right)\right)\left(\Psi \left(z^k\right)-\Psi \left(z^{k+1}\right)\right)\\ & \ge \frac{1}{{\rho }_2}\parallel z^k-z^{k-1}{\parallel }^{-1}\cdot \frac{{\rho }_1}{2}\parallel z^{k+1}-z^k{\parallel }^2\\ & =\frac{{\Vert \begin{array}{c}{z}^{k+1}-z^k\end{array}\Vert }^2}{C\Vert \begin{array}{c}{z}^k-z^{k-1}\end{array}\Vert }\end{array}$$

等价于:

$$\Vert \begin{array}{c}{z}^{k+1}-z^k\end{array}\Vert \le \sqrt{C{\Delta }_{k,k+1}\Vert \begin{array}{c}{z}^k-z^{k-1}\end{array}\Vert }.$$

根据基本不等式 $2\sqrt{ab}\le a+b,\forall a,b>0$ ,我们取 $a=\Vert \begin{array}{c}{z}^k-z^{k-1}\end{array}\Vert$ ,$b=C{\Delta }_{k,k+1}$ ,则 $2\Vert \begin{array}{c}{z}^{k+1}-z^k\end{array}\Vert \le \Vert \begin{array}{c}{z}^k-z^{k-1}\end{array}\Vert +C{\Delta }_{k,k+1}\forall k>l$

• 将上式进行累加可得:

$$\begin{array}{rl}2\sum _{i=l+1}^k\Vert \begin{array}{c}{z}^{i+1}-z^i\end{array}\Vert & \le \sum _{i=l+1}^k\Vert \begin{array}{c}{z}^i-z^{i-1}\end{array}\Vert +C\sum _{i=l+1}^k{\Delta }_{i,i+1}\\ & \le \sum _{i=l+1}^k\Vert \begin{array}{c}{z}^{i+1}-z^i\end{array}\Vert +\Vert \begin{array}{c}{z}^{l+1}-z^l\end{array}\Vert +C{\Delta }_{l+1,k+1}.\end{array}$$

最后一个不等式是因为 ${\Delta }_{p,q}+{\Delta }_{q,r}={\Delta }_{p,r}$ .

• 将上式化简可得:

$$\begin{array}{rl}& \sum _{i=l+1}^k\Vert \begin{array}{c}{z}^{i+1}-z^i\end{array}\Vert \\ & \le \Vert \begin{array}{c}{z}^{l+1}-z^l\end{array}\Vert +C\left(\phi \left(\Psi \left(z^{l+1}\right)-\Psi \left(\bar{z}\right)\right)-\phi \left(\Psi \left(z^{k+1}\right)-\Psi \left(\bar{z}\right)\right)\right)\\ & \le \Vert \begin{array}{c}{z}^{l+1}-z^l\end{array}\Vert +C\phi \left(\Psi \left(z^{l+1}\right)-\Psi \left(\bar{z}\right)\right).(6)\end{array}$$

等式右边是有界的数且与 $k$ 无关,由级数收敛的定义立即可得

$$\sum _{k=1}^{\infty }\Vert \begin{array}{c}{z}^{k+1}-z^k\end{array}\Vert <+\infty$$

---

3.3 全序列收敛

序列$\{zk\}$收敛到Ψ的一个临界点$z^{\ast }=(x^{\ast },y^{\ast })$．

---

Proof. 任取 $q>p>l$ 有:

$$\begin{array}{rl}{z}^q-z^p& =\sum _{k=p}^{q-1}\left(z^{k+1}-z^k\right)\end{array}$$

于是由三角不等式:

$$\Vert \begin{array}{c}{z}^q-z^p\end{array}\Vert =\Vert \begin{array}{c}\sum _{k=p}^{q-1}\left(z^{k+1}-z^k\right)\end{array}\Vert \le \sum _{k=p}^{q-1}\Vert \begin{array}{c}{z}^{k+1}-z^k\end{array}\Vert ,$$

而这说明 $\sum _{k=l+1}^{\infty }\Vert \begin{array}{c}{z}^{k+1}-z^k\end{array}\Vert$ 趋于 0 . 因此 $\left\{z^k\right\}$ 是一个柯西列,算法产生的迭代序列有全序列收敛性.

---

收敛速度证明

设 $\Psi$ 是 $KL$ 函数,其中重参数化子为 $\phi \left(t\right)=c\cdot t^{1-\theta }$ , $\theta \in [0,1)$ ,且满足假设条件,则算法产生的迭代点列 $\left\{z^k\right\}$ 收敛到临界点 $z^{\ast }$ 且满足如下性质: (1) 若 $\theta =0$ ,则 $\left\{z^k\right\}$ 有限步收敛到 $z^{\ast }$ ; (2) 若 $\theta \in \left(0,\frac{1}{2}\right]$ ,则 $\left\{\Phi \left(z^k\right)\right\}Q$ -线性收敛到 $\Phi \left(z^{\ast }\right)$ ,且 $\left\{z^k\right\}R$ -线性收敛 到 $z^{\ast }$ ; (3) 若 $\theta \in \left(\frac{1}{2},1\right)$ ,则存在 $\omega >0$ 使得 $\Vert \begin{array}{c}{z}^k-z^{\ast }\end{array}\Vert \le \omega k^{-\frac{1-\theta }{2\theta -1}}$ ,即 $\left\{z^k\right\}R$ -次线性收敛到 $z^{\ast }$

---

Proof.

• 对任意 $k\ge 0$ ,令 ${\Delta }_k=\sum _{p=k}^{\infty }\Vert \begin{array}{c}{z}^{p+1}-z^p\end{array}\Vert$ ,已证明它是有限数, 由三角不等式有 ${\Delta }_k\ge \Vert \begin{array}{c}{z}^k-z^{\ast }\end{array}\Vert$ ,因此要证明(2) 和(3) 只需证明 ${\Delta }_k$ 有对应的上界.
• 不失一般性,假设对任意 $k\ge 0$ 都有 ${\Delta }_k>0$ . 根据KL不等式和次梯度上界, 我们有

$${\phi }^{\prime }\left(\Psi \left(z^k\right)-\Psi \left(z^{\ast }\right)\right)\ge \frac{1}{\mathrm{dist}\left(0,\partial \Psi \left(z^k\right)\right)}\ge \frac{1}{{\rho }_2\Vert \begin{array}{c}{z}^k-z^{k-1}\end{array}\Vert }$$

将 $\phi \left(t\right)=c\cdot t^{1-\theta }$ 代入上式有

$$\frac{c\left(1-\theta \right)}{{\left(\Psi \left(z^k\right)-\Psi \left(z^{\ast }\right)\right)}^{\theta }}\ge \frac{1}{{\rho }_2\Vert \begin{array}{c}{z}^k-z^{k-1}\end{array}\Vert }(7)$$

整理可得

$$\Psi \left(z^k\right)-\Psi \left(z^{\ast }\right)\le {\left(c\left(1-\theta \right){\rho }_2\Vert \begin{array}{c}{z}^k-z^{k-1}\end{array}\Vert \right)}^{\frac{1}{\theta }}(8)$$

• 把式 $(8)$ 代入式 $(6)$ 中, 对于充分大的 $k$ 有:

$$\begin{array}{rl}{\Delta }_k& \le \Vert \begin{array}{c}{z}^k-z^{k-1}\end{array}\Vert +C\phi \left(\Psi \left(z^k\right)-\Psi \left(z^{\ast }\right)\right)\\ & ={\Delta }_{k-1}-{\Delta }_k+C\cdot c{\left(\Psi \left(z^k\right)-\Psi \left(z^{\ast }\right)\right)}^{1-\theta }\\ & \le {\Delta }_{k-1}-{\Delta }_k+Cc{\left(c\left(1-\theta \right){\rho }_2\parallel z^k-z^{k-1}\parallel \right)}^{\frac{1-\theta }{\theta }}\\ & ={\Delta }_{k-1}-{\Delta }_k+Cc{\left(c\left(1-\theta \right){\rho }_2\right)}^{\frac{1-\theta }{\theta }}{\left({\Delta }_{k-1}-{\Delta }_k\right)}^{\frac{1-\theta }{\theta }}.(9)\end{array}$$

• 考虑 $\theta \in \left(\frac{1}{2},1\right)$ ,则 $\frac{1-\theta }{\theta }<1$ ,又因为当 $k\to \infty$ 时 ${\Delta }_k\to 0$ , 于是可得: $({\Delta }_{k-1}-{\Delta }_k{)}^{\frac{1-\theta }{\theta }}\ge {\Delta }_{k-1}-{\Delta }_k$ ,由上述不等式我们可知存在正整数 $N_1$ 和正常数 $C_1$ 使得

$${\Delta }_k^{\frac{\theta }{1-\theta }}\le C_1\left({\Delta }_{k-1}-{\Delta }_k\right),\forall k\ge N_1.$$

定义 $h:\left(0,+\infty \right)\to \mathbb{R},h\left(t\right)=t^{-\frac{\theta }{1-\theta }}$ ,令 $R\in \left(1,+\infty \right)$ . 对 $k\ge N_1$ , 情形1:若 $h\left({\Delta }_k\right)\le Rh\left({\Delta }_{k-1}\right)$ . 上面的不等式可以写为

$$1\le \frac{C_1\left({\Delta }_{k-1}-{\Delta }_k\right)}{{\Delta }_k^{\frac{\theta }{1-\theta }}}$$

因此由 $h(t)$ 单调递减知:

$$\begin{array}{rl}1& \le C_1\left({\Delta }_{k-1}-{\Delta }_k\right)h\left({\Delta }_k\right)\\ & \le R{C}_1\left({\Delta }_{k-1}-{\Delta }_k\right)h\left({\Delta }_{k-1}\right)\\ & \le R{C}_1{\int }_{{\Delta }_k}^{{\Delta }_{k-1}}h\left(t\right)dt\\ & \le R{C}_1\frac{1-\theta }{1-2\theta }\left[{\Delta }_{k-1}^{\frac{1-2\theta }{1-\theta }}-{\Delta }_k^{\frac{1-2\theta }{1-\theta }}\right]\end{array}$$

因此如果令 $\mu =\frac{2\theta -1}{\left(1-\theta \right)R{C}_1}>0,\nu =\frac{1-2\theta }{1-\theta }<0$ 我们有 $0<\mu \le {\Delta }_k^{\nu }-{\Delta }_{k-1}^{\nu }$ .
情形二:若 $h\left({\Delta }_k\right)>Rh\left({\Delta }_{k-1}\right)$ . 令 $q={\left(\frac{1}{R}\right)}^{\frac{1-\theta }{\theta }}\in \left(0,1\right)$ ,则 ${\Delta }_k\le q{\Delta }_{k-1}$ ,再根据 $\nu <0$ 我们有:

$$\begin{array}{rl}{\Delta }_k^{\nu }& \ge q^{\nu }{\Delta }_{k-1}^{\nu }\\ & \\ {\Delta }_k^{\nu }-{\Delta }_{k-1}^{\nu }& \ge \left(q^{\nu }-1\right){\Delta }_{k-1}^{\nu }.\end{array}$$

由于 $q^{\nu }-1>0$ 且当 $p\to +\infty$ 时 ${\Delta }_p\to 0^{+}$ ,于是 $\left(q^{\nu }-1\right){\Delta }_{p-1}^{\nu }$ 单增, 所以存在 $\bar{\mu }>0$ 有 $\left(q^{\nu }-1\right){\Delta }_{p-1}^{\nu }>\bar{\mu },\forall p\ge N_1$ . 即我们有

$${\Delta }_k^{\nu }-{\Delta }_{k-1}^{\nu }\ge \bar{\mu }>0$$

综上所述,若令 $\hat{\mu }=\min \{\mu ,\bar{\mu }\}>0$ ,则 ${\Delta }_k^{\nu }-{\Delta }_{k-1}^{\nu }\ge \hat{\mu }>0,\forall k\ge N_1$ 通过将上述不等式从 $N_1$ 加到比 $N>N_1$ 我们可以得到 ${\Delta }_N^{\nu }-{\Delta }_{N_1}^{\nu }\ge \hat{\mu }\left(N-N_1\right)>0$ 因此,存在 $\omega >0$ 使得

$${\Delta }_N\le {\left[{\Delta }_{N_1}^{\nu }+\hat{\mu }\left(N-N_1\right)\right]}^{\frac{1}{\nu }}\le \omega N^{-\frac{1-\theta }{2\theta -1}}$$

即结论(3) 成立.

• 考虑 $\theta \in \left(0,\frac{1}{2}\right]$ ,此时 $\frac{1-\theta }{\theta }\ge 1$ , 又${\Delta }_k\to 0$ 于是可得, 对于充分大的 $k$ 有: $({\Delta }_{k-1}-{\Delta }_k{)}^{\frac{1-\theta }{\theta }}\le {\Delta }_{k-1}-{\Delta }_k$ ,由不等式 $(9)$ 知此时 ,存在正常数 $C_2>0$ 使得

$${\Delta }_k\le C_2\left({\Delta }_{k-1}-{\Delta }_k\right)$$

整理可得 ${\Delta }_k\le \frac{C_2}{1+C_2}{\Delta }_{k-1}$ ,再根据证明开始时我们得到的 ${\Delta }_k\ge \Vert \begin{array}{c}{z}^k-z^{\ast }\end{array}\Vert$ 有

$$\Vert \begin{array}{c}{z}^k-z^{\ast }\end{array}\Vert \le {\Delta }_k\le \frac{C_2}{1+C_2}{\Delta }_{k-1}\le \cdots \le {\left(\frac{C_2}{1+C_2}\right)}^k{\Delta }_0,$$

即 $\left\{z^k\right\}\mathrm{R}$ -线性收敛到 $z^{\ast }$ . 结合不等式 $(8)$ 整理可得:

$${\Vert \begin{array}{c}{z}^k-z^{k-1}\end{array}\Vert }^2\ge \frac{{\left(\Psi \left(z^k\right)-\Psi \left(z^{\ast }\right)\right)}^{2\theta }}{{\left(c\left(1-\theta \right){\rho }_2\right)}^2}.$$

再根据充分下降性 $(2)$ 知存在 $C_3>0$ 使得对充分大的 $k$ 有

$$\begin{array}{rl}\Psi \left(z^{k+1}\right)-\Psi \left(z^k\right)& \le -\frac{{\rho }_1}{2}{\Vert \begin{array}{c}{z}^{k+1}-z^k\end{array}\Vert }^2\\ & \le -\frac{{\rho }_1}{2}\frac{{\left(\Psi \left(z^{k+1}\right)-\Psi \left(z^{\ast }\right)\right)}^{2\theta }}{{\left(c\left(1-\theta \right){\rho }_2\right)}^2}\\ & \le -\frac{{\rho }_1}{2}\frac{\left(\Psi \left(z^{k+1}\right)-\Psi \left(z^{\ast }\right)\right)}{{\left(c\left(1-\theta \right){\rho }_2\right)}^2}\left(\theta \in (0,1/2]\right)\\ & =-C_3\left(\Psi \left(z^{k+1}\right)-\Psi \left(z^{\ast }\right)\right).\end{array}$$

整理可得:

$$\Psi \left(z^{k+1}\right)-\Psi \left(z^{\ast }\right)\le \frac{1}{1+C_3}\left(\Psi \left(z^k\right)-\Psi \left(z^{\ast }\right)\right)$$

即 $\left\{\Phi \left(z^k\right)\right\}$ Q-线性收敛到 $\Phi \left(z^{\ast }\right)$ . 综上可知结论(2)成立.

• 考虑 $\theta =0$ ,令 $I\text{:=}\left\{k\in \mathbb{N}:z^{k+1}\ne z^k\right\}$ ,取 $k$ 充分大,在$(7)$代$\lambda \theta =0$ 得

$$\Vert \begin{array}{c}{z}^k-z^{k-1}\end{array}\Vert \ge \frac{1}{c{\rho }_2}>0$$

再由充分下降性得:

$$\Psi \left(z^{k+1}\right)\le \Psi \left(z^k\right)-\frac{{\rho }_1}{2}{\Vert \begin{array}{c}{z}^{k+1}-z^k\end{array}\Vert }^2\le \Psi \left(z^k\right)-\frac{{\rho }_1}{2c^2{\rho }_2^2}.$$

若 $I$ 是无限集,则上式两端令 $k\to \infty$ 得 $0<-\frac{{\rho }_1}{2c^2{\rho }_2^2}$ ,矛盾. 故 $I$ 为有限集, 因此结论(1)成立.