不動點迭代(Fixed-point iteration)

(不動點)
$x$為單值算子$\mathbb{T}$的不動點，如果$$\mathbb{T} x =x$$
記$\text{Fix} \mathbb{T}=\{x|x=\mathbb{T}x\}=(\mathbb{I}-\mathbb{T})^{-1}(0)$為單值算子$\mathbb{T}$的不動點集合。

如果單值算子$\mathbb{T}$是非擴張的且$\text{dom} {\mathbb{T}}=\mathbb{R}^n$，則$\text{Fix} \mathbb{T}$是閉凸集。

不動點迭代(FPI)的格式為：$$x^{k+1}=\mathbb{T}x^k(k=0,1,2,\dots)$$
如果$\mathbb{T}$是一個收縮算子，則可以利用$Banach$不動點定理得到收斂性，且收斂到不動點。但是對于優化問題，收縮的條件不易滿足，下面我們來考慮對平均算子使用不動點迭代。

注意到，對于任意的非擴張算子$\mathbb{T}$，則有平均算子$(1-\theta)\mathbb{I}+\theta\mathbb{T}$的不動點集合與$\mathbb{T}$是相同的，于是只要對平均算子$(1-\theta)\mathbb{I}+\theta\mathbb{T}$運用不動點迭代就可以得到非擴張算子$\mathbb{T}$的不動點。

假設$\{V^k\},\{S^k\}$是非負數列，且$V^{K+1}\leq V^k-S^k(k=0,1,2,\dots)$，則$\{V^k\}$單調遞減，且$S^K\rightarrow 0$\\
又若$\{S^k\}$單調遞減，則$S^K\leq \frac{V^0}{N+1}$

(平均算子不動點迭代的收斂性)
有平均算子$\mathbb{I}=(1-\theta)\mathbb{I}+\theta\mathbb{S}$，其中$\mathbb{S}$為非擴張算子，且$\text{Fix}\mathbb{T}$，令：$$x^{k+1}=\mathbb{T}x^k(k=0,1,2,\dots)$$
則$\{x^k\}$收斂于$\text{Fix}\mathbb{T}$中的一點，且$\{\Vert x^{k+1}-x^k \Vert\}$單調遞減且滿足
$$\Vert x^{k+1}-x^k \Vert^2\leq\frac{\theta}{(k+1)(1-\theta)}dist^2(x^0,\text{Fix}\mathbb{T})$$

\begin{proof}
\begin{align*}
\Vert x^{k+1}-x^* \Vert^2&=\Vert (1-\theta)x^k+\theta\mathbb{S}x^k-x^* \Vert^2\\
&=\Vert (1-\theta)x^k+\theta\mathbb{S}x^k-(1-\theta)x^*+\theta\mathbb{S}x^* \Vert^2\\
&=\Vert (1-\theta)(x^k-x^*)+\theta(\mathbb{S}x^k-\mathbb{S}x^*)\Vert^2\\
&=(1-\theta)\Vert x^k-x^*\Vert ^2 +\theta\Vert\mathbb{S}x^k-\mathbb{S}x^*\Vert^2-\theta(1-\theta)\Vert\mathbb{S}x^k-x^k\Vert^2\\
&\leq (1-\theta)\Vert x^k-x^*\Vert ^2 +\theta\Vert x^k-x^*\Vert^2-\theta(1-\theta)\Vert\mathbb{S}x^k-x^k\Vert^2\\
&=\Vert x^k-x^*\Vert^2-\theta(1-\theta)\Vert\mathbb{S}x^k-x^k\Vert^2\\
&=\Vert x^k-x^*\Vert^2-\frac{(1-\theta)}{\theta}\Vert x^{k+1}-x^k\Vert^2\\
\end{align*}
則根據引理4.1得到$\{\Vert x^k-x^*\Vert \}$單調遞減，到$\{\Vert x^{k+1}-x^k\Vert \}$收斂于0。\\
又因為$\mathbb{T}$是非擴張算子，則有$\{\Vert x^{k+1}-x^k\Vert \}$單調遞減。于是根據引理4.1，得到：
$$\Vert x^{k+1}-x^k\Vert^2\leq\frac{\theta}{(k+1)(1-\theta)}\Vert x^0-x^*\Vert^2$$
則：
$$\Vert x^{k+1}-x^k\Vert^2\leq\frac{\theta}{(k+1)(1-\theta)}\text{dist}^2(x^0,\text{Fix}\mathbb{T})$$

下面證明點列$\{x^k\}$收斂于$\text{Fix}\mathbb{T}$中一點：\\
由上述證明可知，點列$\{x^k\}$有界，取其中一個聚點$y^*$，則有$\{x^{k_i}\}$使得$x^{k_i}\rightarrow y^*(i\rightarrow+\infty)$\\
由于$\Vert x^{k+1}-x^k\Vert\rightarrow 0$，則$(\mathbb{T}-\mathbb{I})(x^k)\rightarrow 0$，則$(\mathbb{T}-\mathbb{I})(x^{k_i})\rightarrow 0$，則由海涅定理得到$$(\mathbb{T}-\mathbb{I})(y^*)=0$$,則$y^*\in\text{Fix}\mathbb{T} $\\
將前半部分的$x^*$替換成$y^*$，則有$\{\Vert x^k-y^*\Vert \}$單調遞減有下界，則存在極限，又因為子列$\{\Vert x^{k_i}-y^*\Vert \}$有極限$0$，則$\{\Vert x^k-y^*\Vert \}$有極限$0$，于是$$x^k\rightarrow y^*$$，即點列$\{x^k\}$收斂于$\text{Fix}\mathbb{T}$中一點。
\end{proof}

(Forward Step method)

問題:找到$x\in \mathbb{R}^n$使得$0 = \mathbb{F}(x)$等價于求解$ \text{Fix}(\mathbb{I}-\alpha\mathbb{F})$
則FPI為$$x^{k+1}=x^k-\alpha\mathbb{F}x^k:=\mathbb{T}(x^k)$$

如果$\mathbb{F}$是$\beta-$余強制的，即$\left\langle \mathbb{F}x-\mathbb{F}y,x-y \right\rangle\geq \beta \Vert \mathbb{F}x-\mathbb{F}y \Vert^2 ,\forall x,y\in dom{F}$\\
則
\begin{align*}
\Vert \mathbb{T}x-\mathbb{T}y \Vert^2 &=\Vert (\mathbb{I}-\alpha\mathbb{F})x-(\mathbb{I}-\alpha\mathbb{F})y \Vert^2\\
&=\Vert x-y-\alpha(\mathbb{F}x-\mathbb{F}y) \Vert^2\\
&=\Vert x-y\Vert^2-2\alpha\left\langle \mathbb{F}x-\mathbb{F}y,x-y \right\rangle+\alpha^2\Vert \mathbb{F}x-\mathbb{F}y \Vert^2\\
&\leq\Vert x-y\Vert^2-2\alpha\beta\Vert \mathbb{F}x-\mathbb{F}y \Vert^2+\alpha^2\Vert \mathbb{F}x-\mathbb{F}y \Vert^2
\end{align*}
由此可以得到，當$\alpha^2-2\alpha\beta \leq 0(\text{即}0<\alpha \leq 2\beta)$時，$\mathbb{T}$為非擴張算子，則$\mathbb{T}_0=\mathbb{I}-2\beta\mathbb{F}$是非擴張算子。\\
而$\mathbb{T}=\mathbb{I}-2\alpha\mathbb{F}=(1-\theta)\mathbb{I}+\theta(\mathbb{I}-2\beta\mathbb{F})=\mathbb{I}-2\theta\alpha\mathbb{F}$，其中$\theta=\frac{\alpha}{2\beta}$，則$\mathbb{T}$是$\frac{\alpha}{2\beta}-$平均算子，所以FPI收斂(當$0<\alpha < 2\beta$)。\\

又若$\mathbb{F}$是$\mu-$強單調的，即$\left\langle \mathbb{F}x-\mathbb{F}y,x-y \right\rangle\geq \mu \Vert x-y \Vert^2 ,\forall x,y\in dom{F}$\\
則
\begin{align*}
\Vert \mathbb{T}x-\mathbb{T}y \Vert^2 &=\Vert (\mathbb{I}-\alpha\mathbb{F})x-(\mathbb{I}-\alpha\mathbb{F})y \Vert^2\\
&=\Vert x-y-\alpha(\mathbb{F}x-\mathbb{F}y) \Vert^2\\
&=\Vert x-y\Vert^2-2\alpha\left\langle \mathbb{F}x-\mathbb{F}y,x-y \right\rangle+\alpha^2\Vert \mathbb{F}x-\mathbb{F}y \Vert^2\\
&\leq\Vert x-y\Vert^2-2\alpha\mu\Vert x-y \Vert^2+\frac{\alpha^2}{\beta^2}\Vert x-y \Vert^2(\beta-\text{余強制}\Rightarrow \frac{1}{\beta}-\text{Lipschitz})\\
&=(1-2\alpha\mu +\frac{\alpha^2}{\beta^2})\Vert x-y \Vert^2
\end{align*}
則當$0<\alpha<2\mu\beta^2$時，$\mathbb{T}$是收縮算子，所以收斂。


根據上述分析，當$\mathbb{F}=\nabla f$時，可以推出梯度下降法的收斂性。