这回的问题是
$$\begin{array}{lll}\text{ (P) }& \min & f(\mathbf{x})\\ & \text{ s.t. }& x\in C\end{array}$$
其中$f$是一个定义在闭凸集$C$上的连续可微函数。

稳定

稳定点定义

设$f$是一个定义在闭凸集$C$上的连续可微函数
设${\mathbf{x}}^{\ast }\in C$,如果$\forall \mathbf{x}\in C,\nabla f({\mathbf{x}}^{\ast }{)}^T(\mathbf{x}-{\mathbf{x}}^{\ast })\ge 0$
则称${\mathbf{x}}^{\ast }\in C$是一个稳定点(stationary point)

定理1

设$f$是一个定义在闭凸集$C$上的连续可微函数
设${\mathbf{x}}^{\ast }$是（P）一个局部最小值，则${\mathbf{x}}^{\ast }$是（P）的一个稳定点

证明：
假设${\mathbf{x}}^{\ast }$不是一个稳定点，则
$\exists x\in C,\nabla f({\mathbf{x}}^{\ast }{)}^T(\mathbf{x}-{\mathbf{x}}^{\ast })<0$
令$\mathbf{d}=\mathbf{x}-{\mathbf{x}}^{\ast }$,
则$f^{\prime }({\mathbf{x}}^{\ast },\mathbf{d})<0$
所以$\exists ϵ>0,\forall t\in (0,ϵ),f({\mathbf{x}}^{\ast }+t\mathbf{d})<f({\mathbf{x}}^{\ast })$
因为$C$是一个凸集，
所以${\mathbf{x}}^{\ast }+t\mathbf{d}=(1-t){\mathbf{x}}^{\ast }+t\mathbf{x}\in C$
所以${\mathbf{x}}^{\ast }$不是局部最小点，矛盾

定理2

设$f$是一个定义在闭凸集$C$上的连续可微凸函数
则${\mathbf{x}}^{\ast }$是一个稳定点当且仅当${\mathbf{x}}^{\ast }$是（P）的最优解

证明：
必要性和定理1一样
充分性：设${\mathbf{x}}^{\ast }$是（P）的一个稳定点，设$\mathbf{x}\in C$,则
$$f(\mathbf{x})\ge f({\mathbf{x}}^{\ast })+\nabla f({\mathbf{x}}^{\ast }{)}^T(\mathbf{x}-{\mathbf{x}}^{\ast })\ge f({\mathbf{x}}^{\ast })$$
所以${\mathbf{x}}^{\ast }$是最优解

正交投影算子

投影第二定理

设$C$是一个闭凸集，$\mathbf{x}\in {\mathbb{R}}^n$,
则$\mathbf{z}=P_C(\mathbf{x})$当且仅当
$$(\mathbf{x}-\mathbf{z}{)}^T(\mathbf{y}-\mathbf{z})\le 0,\forall \mathbf{y}\in C$$

证明：
$\mathbf{z}=P_C(\mathbf{x})$当且仅当他是
$$\begin{array}{ll}\min & g(y)\equiv \Vert y-x{\Vert }^2\\ \text{ s.t. }& y\in C.\end{array}$$
的最优解
根据定理2，他是一个稳定点
所以
$$\nabla g(\mathbf{z}{)}^T(\mathbf{y}-\mathbf{z})\ge 0,\forall \mathbf{y}\in C$$
于是
$$(\mathbf{x}-\mathbf{z}{)}^T(\mathbf{y}-\mathbf{z})\le 0,\forall \mathbf{y}\in C$$

定理3

设$C$是一个闭凸集，则
1.$\forall \mathbf{v},\mathbf{w}\in {\mathbb{R}}^n$
$${\left(P_C(\mathbf{v})-P_C(\mathbf{w})\right)}^T(\mathbf{v}-\mathbf{w})\ge {\Vert P_C(\mathbf{v})-P_C(\mathbf{w})\Vert }^2$$
2.$\forall \mathbf{v},\mathbf{w}\in {\mathbb{R}}^n$
$$\Vert P_C(\mathbf{v})-P_C(\mathbf{w})\Vert \le \Vert \mathbf{v}-\mathbf{w}\Vert$$
证明：
1.
根据投影第二定理
$$\begin{gathered} {\left(\mathbf{v}-P_C(\mathbf{v})\right)}^T\left(P_C(\mathbf{w})-P_C(\mathbf{v})\right)\le 0 \\ {\left(\mathbf{w}-P_C(\mathbf{w})\right)}^T\left(P_C(\mathbf{v})-P_C(\mathbf{w})\right)\le 0 \end{gathered}$$
加起来得
$${\left(P_C(\mathbf{w})-P_C(\mathbf{v})\right)}^T\left(\mathbf{v}-\mathbf{w}+P_C(\mathbf{w})-P_C(\mathbf{v})\right)\le 0$$
进而
$${\left(P_C(\mathbf{v})-P_C(\mathbf{w})\right)}^T(\mathbf{v}-\mathbf{w})\ge {\Vert P_C(\mathbf{v})-P_C(\mathbf{w})\Vert }^2$$
2.
如果$P_C(\mathbf{v})=P_C(\mathbf{w})$，显然成立，
如果$P_C(\mathbf{v})\ne P_C(\mathbf{w})$
根据柯西不等式
$${\left(P_C(\mathbf{v})-P_C(\mathbf{w})\right)}^T(\mathbf{v}-\mathbf{w})\le \Vert P_C(\mathbf{v})-P_C(\mathbf{w})\Vert \cdot \Vert \mathbf{v}-\mathbf{w}\Vert ,$$
于是
$$\begin{gathered} {\Vert P_C(\mathbf{v})-P_C(\mathbf{w})\Vert }^2\le \Vert P_C(\mathbf{v})-P_C(\mathbf{w})\Vert \cdot \Vert \mathbf{v}-\mathbf{w}\Vert \\ \Vert P_C(\mathbf{v})-P_C(\mathbf{w})\Vert \le \Vert \mathbf{v}-\mathbf{w}\Vert \end{gathered}$$

定理4

设$f$是一个定义在闭凸集$C$的连续可微的函数
设$s>0$，则${\mathbf{x}}^{\ast }$是问题（P）的稳定点，
当且仅当
$${\mathbf{x}}^{\ast }=P_C\left({\mathbf{x}}^{\ast }-s\nabla f\left({\mathbf{x}}^{\ast }\right)\right)$$
证明：
根据投影第二定理${\mathbf{x}}^{\ast }=P_C\left({\mathbf{x}}^{\ast }-s\nabla f\left({\mathbf{x}}^{\ast }\right)\right)$
当且仅当
$${\left({\mathbf{x}}^{\ast }-s\nabla f\left({\mathbf{x}}^{\ast }\right)-{\mathbf{x}}^{\ast }\right)}^T\left(\mathbf{x}-{\mathbf{x}}^{\ast }\right)\le 0\forall \mathbf{x}\in C$$
进而
$$\nabla f{\left({\mathbf{x}}^{\ast }\right)}^T\left(\mathbf{x}-{\mathbf{x}}^{\ast }\right)\ge 0,\forall \mathbf{x}\in C$$
所以是一个稳定点

梯度投影法

随机选一个初始点${\mathbf{x}}_0\in C$
a)用线搜索选择一个步长$t_k$
b) ${\mathbf{x}}_{k+1}=P_C\left({\mathbf{x}}_k-t_k\nabla f\left({\mathbf{x}}_k\right)\right)$
c)如果$\Vert {\mathbf{x}}_k-{\mathbf{x}}_{k+1}\Vert \le ϵ$，则输出${\mathbf{x}}_{k+1}$

其实这和我们的梯度方法差不都，只不过普通的梯度方法可能会超出这个$C$，所以梯度投影法把他再投影回来

约束问题的充分下降引理

设$f\in C_L^{1,1}(C)$
其中$C$是一个闭凸集
$\forall \mathbf{x}\in C,t\in (0,\frac{2}{L})$,
$$f(\mathbf{x})-f\left(P_C(\mathbf{x}-t\nabla f(\mathbf{x}))\right)\ge t\left(1-\frac{Lt}{2}\right){\Vert \frac{1}{t}\left(\mathbf{x}-P_C(\mathbf{x}-t\nabla f(\mathbf{x}))\right)\Vert }^2$$
证明：
令${\mathbf{x}}^{+}=P_C(\mathbf{x}-t\nabla f(\mathbf{x}))$
根据下降引理
$$f\left({\mathbf{x}}^{+}\right)\le f(\mathbf{x})+⟨\nabla f(\mathbf{x}),{\mathbf{x}}^{+}-\mathbf{x}⟩+\frac{L}{2}{\Vert \mathbf{x}-{\mathbf{x}}^{+}\Vert }^2$$
根据投影第二定理
$$\begin{array}{rl}⟨\mathbf{x}-t\nabla f(\mathbf{x})-{\mathbf{x}}^{+},\mathbf{x}-{\mathbf{x}}^{+}⟩& \le 0\\ ⟨\nabla f(\mathbf{x}),{\mathbf{x}}^{+}-\mathbf{x}⟩& \le -\frac{1}{t}{\Vert {\mathbf{x}}^{+}-\mathbf{x}\Vert }^2\end{array}$$
结合一下
$$f(\mathbf{x})-f\left(P_C(\mathbf{x}-t\nabla f(\mathbf{x}))\right)\ge t\left(1-\frac{Lt}{2}\right){\Vert \frac{1}{t}\left(\mathbf{x}-P_C(\mathbf{x}-t\nabla f(\mathbf{x}))\right)\Vert }^2$$

梯度映射定义

$$G_M(\mathbf{x})=M\left[\mathbf{x}-P_C\left(\mathbf{x}-\frac{1}{M}\nabla f(\mathbf{x})\right)\right]$$
其中$M>0$

所以下降引理也可以写成
$$f(\mathbf{x})-f\left(P_C(\mathbf{x}-t\nabla f(\mathbf{x}))\right)\ge t\left(1-\frac{Lt}{2}\right){\Vert G_{\frac{1}{t}}(\mathbf{x})\Vert }^2$$

定理6

设$f$是定义在闭凸集$C$上的连续可微函数
设$L_1\ge L_2$,则$\forall \mathbf{x}\in {\mathbb{R}}^n$
$$\Vert G_{L_1}(\mathbf{x})\Vert \ge \Vert G_{L_2}(\mathbf{x})\Vert$$
或者
$$\frac{\Vert G_{L_1}(\mathbf{x})\Vert }{L_1}\le \frac{\Vert G_{L_2}(\mathbf{x})\Vert }{L_2}$$

证明：利用投影第二定理
$\forall \mathbf{v}\in {\mathbb{R}}^n,\mathbf{w}\in C$
$$⟨\mathbf{v}-P_C(\mathbf{v}),P_C(\mathbf{v})-\mathbf{w}⟩\ge 0$$
令$\mathbf{v}=\mathbf{x}-\frac{1}{L_1}\nabla f(\mathbf{x}),\mathbf{w}=P_C\left(\mathbf{x}-\frac{1}{L_2}\nabla f(\mathbf{x})\right)$
于是
$$⟨\mathrm{x}-\frac{1}{L_1}\nabla f(\mathrm{x})-P_C\left(\mathrm{x}-\frac{1}{L_1}\nabla f(\mathrm{x})\right),P_C\left(\mathrm{x}-\frac{1}{L_1}\nabla f(\mathrm{x})\right)-P_C\left(\mathrm{x}-\frac{1}{L_2}\nabla f(\mathrm{x})\right)⟩\ge 0$$
或者
$$⟨\frac{1}{L_1}{G}_{L_1}(\mathbf{x})-\frac{1}{L_1}\nabla f(\mathbf{x}),\frac{1}{L_2}{G}_{L_2}(\mathbf{x})-\frac{1}{L_1}{G}_{L_1}(\mathbf{x})⟩\ge 0$$
轮换一下$L_1,L_2$
$$⟨\frac{1}{L_2}{G}_{L_2}(\mathbf{x})-\frac{1}{L_2}\nabla f(\mathbf{x}),\frac{1}{L_1}{G}_{L_1}(\mathbf{x})-\frac{1}{L_2}{G}_{L_2}(\mathbf{x})⟩\ge 0$$
$(1)\ast L_1+(2)\ast L_2$得
$$⟨G_{L_1}(\mathbf{x})-G_{L_2}(\mathbf{x}),\frac{1}{L_2}{G}_{L_2}(\mathbf{x})-\frac{1}{L_1}{G}_{L_1}(\mathbf{x})⟩\ge 0,$$
整理得
$$\frac{1}{L_1}{\Vert G_{L_1}(\mathbf{x})\Vert }^2+\frac{1}{L_2}{\Vert G_{L_2}(\mathbf{x})\Vert }^2\le \left(\frac{1}{L_1}+\frac{1}{L_2}\right)G_{L_1}(\mathbf{x}{)}^T{G}_{L_2}(\mathbf{x})$$
利用柯西不等式
$$\frac{1}{L_1}{\Vert G_{L_1}(\mathbf{x})\Vert }^2+\frac{1}{L_2}{\Vert G_{L_2}(\mathbf{x})\Vert }^2\le \left(\frac{1}{L_1}+\frac{1}{L_2}\right)\Vert G_{L_1}(\mathbf{x})\Vert \cdot \Vert G_{L_2}(\mathbf{x})\Vert$$
如果$G_{L_2}(\mathbf{x})=0$,则结论成立
如果$G_{L_2}(\mathbf{x})\ne 0$
令$t=\frac{\Vert G_{L_1}(\mathrm{x})\Vert }{\Vert G_{L_2}(\mathrm{x})\Vert }$
则
$$\begin{array}{rl}\frac{1}{L_1}{t}^2-(\frac{1}{L_1}+\frac{1}{L_2})t+\frac{1}{L_2}& \le 0\\ (t-1)(\frac{1}{L_1}t-\frac{1}{L_2})& \le 0\\ 1\le t\le \frac{L_1}{L_2}& \end{array}$$
于是
$$\Vert G_{L_2}(\mathbf{x})\Vert \le \Vert G_{L_1}(\mathbf{x})\Vert \le \frac{L_1}{L_2}\Vert G_{L_2}(\mathbf{x})\Vert .$$

回溯法

设参数$(s,\alpha ,\beta )$，其中$s>0,\alpha \in (0,1),\beta \in (0,1)$
一开始$t_k=s$
当
$$f\left({\mathbf{x}}_k\right)-f\left(P_C\left({\mathbf{x}}_k-t_k\nabla f\left({\mathbf{x}}_k\right)\right)\right)<\alpha t_k{\Vert G_{\frac{1}{t}}\left({\mathbf{x}}_k\right)\Vert }^2$$
时，
令$t_k=\beta t_k$
也就是说$t_k=s{\beta }^{i_k}$,其中$i_k$是满足
$$f\left({\mathbf{x}}_k\right)-f\left(P_C\left({\mathbf{x}}_k-s{\beta }^{i_k}\nabla f\left({\mathbf{x}}_k\right)\right)\right)\ge \alpha s{\beta }^{i_k}{\Vert G_{\frac{1}{s{\beta }^{i}k}}\left({\mathbf{x}}_k\right)\Vert }^2$$
的最小非负整数

如果$t_k=s$满足条件
显然$t_k\ge s$
如果不满足，则$t_k=s{\beta }^{i_k}$时才满足条件
也就是说$\frac{t_k}{\beta }$是不满足条件的
即
$$f\left({\mathbf{x}}_k\right)-f\left(P_C\left({\mathbf{x}}_k-\frac{t_k}{\beta }\nabla f\left({\mathbf{x}}_k\right)\right)\right)<\alpha t_k{\Vert G_{\frac{\beta }{t_k}}\left({\mathbf{x}}_k\right)\Vert }^2$$

$x=x_k,t=\frac{t_k}{\beta }$代入充分下降引理得
$$f\left({\mathbf{x}}_k\right)-f(P_C\left({\mathbf{x}}_k-\frac{t_k}{\beta }\nabla f\left({\mathbf{x}}_k\right)\right)\ge \frac{t_k}{\beta }\left(1-\frac{L{t}_k}{2\beta }\right){\Vert G_{\frac{\beta }{t_k}}\left({\mathbf{x}}_k\right)\Vert }^2$$
取这两个式子的右边，得
$$\frac{t_k}{\beta }\left(1-\frac{L{t}_k}{2\beta }\right){\Vert G_{\frac{\beta }{t_k}}\left({\mathbf{x}}_k\right)\Vert }^2<\alpha t_k{\Vert G_{\frac{\beta }{t_k}}\left({\mathbf{x}}_k\right)\Vert }^2\Rightarrow t_k\ge \frac{2(1-\alpha )\beta }{L}$$
综上所述
$$t_k\ge \min \left\{s,\frac{2(1-\alpha )\beta }{L}\right\}$$

引理1

考虑问题（P）
设$C$是一个闭凸集
$f\in C_L^{1,1}(C)$有下界
设 { x k } k ≥ 0 \{\mathbf{x}_k\}_{k\ge 0} {xk​}k≥0​是利用梯度投影法产生的序列，
其中步长用的要么是固定步长$t_k=\bar{t}\in (0,\frac{2}{L})$，要么是回溯法（其中参数$(s,\alpha ,\beta )$满足$s>0,\alpha \in (0,1),\beta \in (0,1)$）
那么$\forall k\ge 0$
$$f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_{k+1}\right)\ge M{\Vert G_d\left({\mathbf{x}}_k\right)\Vert }^2$$
其中
$$M=\{\begin{array}{ll}\bar{t}\left(1-\frac{\bar{t}L}{2}\right)& \text{ 固定步长 }\\ \alpha \min \left\{s,\frac{2(1-\alpha )\beta }{L}\right\}& \text{ 回溯法 }\end{array}$$
且
$$d=\{\begin{array}{ll}1/\bar{t}& \text{ 固定步长 }\\ 1/s& \text{ 回溯法 }\end{array}$$

证明：
固定步长：直接代入，成立

回溯法：
因为回溯法，$t_k$其实是越来越小的，所以，$t_k\le s$
根据定理6
$$\Vert G_{1/t_k}\left({\mathbf{x}}_k\right)\Vert \ge \Vert G_{1/s}\left({\mathbf{x}}_k\right)\Vert$$
所以
$$f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_{k+1}\right)\ge \alpha t_k{\Vert G_{\frac{1}{t_k}}\left({\mathbf{x}}_k\right)\Vert }^2\ge \alpha \min \left\{s,\frac{2(1-\alpha )\beta }{L}\right\}{\Vert G_{1/s}\left({\mathbf{x}}_k\right)\Vert }^2$$
成立

收敛性

考虑问题（P）
设$C$是一个闭凸集
$f\in C_L^{1,1}(C)$有下界
设 { x k } k ≥ 0 \{\mathbf{x}_k\}_{k\ge 0} {xk​}k≥0​是利用梯度投影法产生的序列，
其中步长用的要么是固定步长$t_k=\bar{t}\in (0,\frac{2}{L})$，要么是回溯法（其中参数$(s,\alpha ,\beta )$满足$s>0,\alpha \in (0,1),\beta \in (0,1)$），那么
(a)序列 { f ( x k ) } \{f(\mathbf{x}_k)\} {f(xk​)}单调不增，并且$f({\mathbf{x}}_{k+1})<f({\mathbf{x}}_k)$,除非${\mathbf{x}}_k$是一个稳定点
(b)当$k\to \infty$时，$G_d({\mathbf{x}}_k)\to 0$
其中$$d=\{\begin{array}{ll}1/\bar{t}& \text{ 固定步长 }\\ 1/s& \text{ 回溯法 }\end{array}$$

证明：
(a)
由引理
$$f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_{k+1}\right)\ge M{\Vert G_d\left({\mathbf{x}}_k\right)\Vert }^2\ge 0$$
所以单调不增
当且仅当$G_d\left({\mathbf{x}}_k\right)=0$时取等
也就是说${\mathbf{x}}_k$是一个稳定点

(b)
因为 { f ( x k ) } \{f(\mathbf{x}_k)\} {f(xk​)}单调递减有下界，收敛
所以$k\to \infty ,f({\mathbf{x}}_k)-f({\mathbf{x}}_{k+1})\to 0$
于是当$k\to \infty$时，$G_d({\mathbf{x}}_k)\to 0$

收敛速率

在上面的条件下
设$f^{\ast }$是序列 { f ( x k ) } \{f(\mathbf{x}_k)\} {f(xk​)}的极限，那么$\forall n=0,1,2,\cdots$
$$\underset{k=0,1,\dots ,n}{\min }\Vert G_d\left({\mathbf{x}}_k\right)\Vert \le \sqrt{\frac{f\left({\mathbf{x}}_0\right)-f^{\ast }}{M(n+1)}}$$
其中
$$M=\{\begin{array}{ll}\bar{t}\left(1-\frac{\bar{t}L}{2}\right)& \text{ 固定步长 }\\ \alpha \min \left\{s,\frac{2(1-\alpha )\beta }{L}\right\}& \text{ 回溯法 }\end{array}$$
且
$$d=\{\begin{array}{ll}1/\bar{t}& \text{ 固定步长 }\\ 1/s& \text{ 回溯法 }\end{array}$$

证明：
$$\begin{array}{rl}\sum _{k=0}^n\left(f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_{k+1}\right)\right)& \ge \sum _{k=0}^{n}M{\Vert G_d\left({\mathbf{x}}_k\right)\Vert }^2\\ f\left({\mathbf{x}}_0\right)-f\left({\mathbf{x}}_{n+1}\right)& \ge M\sum _{k=0}^n{\Vert G_d\left({\mathbf{x}}_k\right)\Vert }^2\end{array}$$
又因为$f({\mathbf{x}}_{n+1})\ge f^{\ast }$
所以
$$f\left({\mathbf{x}}_0\right)-f^{\ast }\ge f\left({\mathbf{x}}_0\right)-f\left({\mathbf{x}}_{n+1}\right)\ge M\sum _{k=0}^n{\Vert G_d\left({\mathbf{x}}_k\right)\Vert }^2$$
又因为
$$\sum _{k=0}^n{\Vert G_d\left({\mathbf{x}}_k\right)\Vert }^2\ge (n+1)\underset{k=0,1,\dots ,n}{\min }{\Vert G_d\left({\mathbf{x}}_k\right)\Vert }^2$$
所以
$$f\left({\mathbf{x}}_0\right)-f^{\ast }\ge M(n+1)\underset{k=0,1,\dots ,n}{\min }{\Vert G_d\left({\mathbf{x}}_k\right)\Vert }^2$$
进而
$$\underset{k=0,1,\dots ,n}{\min }\Vert G_d\left({\mathbf{x}}_k\right)\Vert \le \sqrt{\frac{f\left({\mathbf{x}}_0\right)-f^{\ast }}{M(n+1)}}$$

凸函数

$$\begin{array}{lll}\text{ (P) }& \min & f(\mathbf{x})\\ & \text{ s.t. }& x\in C\end{array}$$
其中$f$是一个定义在闭凸集$C$上的连续可微函数。
设 { x k } k ≥ 0 \{\mathbf{x}_k\}_{k\ge 0} {xk​}k≥0​是梯度投影法用固定步长$\bar{t}\in (0,\frac{1}{L}]$产生的序列。
假设$X^{\ast }$是最优解集，并且非空，$f^{\ast }$是最优解，则
(a)$\forall k\ge 0,{\mathbf{x}}^{\ast }\in X^{\ast }$
$$2\bar{t}\left(f\left({\mathbf{x}}_{k+1}\right)-f\left({\mathbf{x}}^{\ast }\right)\right)\le {\Vert {\mathbf{x}}_k-{\mathbf{x}}^{\ast }\Vert }^2-{\Vert {\mathbf{x}}_{k+1}-{\mathbf{x}}^{\ast }\Vert }^2$$
(b)$\forall n\ge 0$
$$f\left({\mathbf{x}}_n\right)-f^{\ast }\le \frac{{\Vert {\mathbf{x}}_0-{\mathbf{x}}^{\ast }\Vert }^2}{2\bar{t}n}$$

证明：
(a)
由下降引理
$$f\left({\mathbf{x}}_{k+1}\right)\le f\left({\mathbf{x}}_k\right)+⟨\nabla f\left({\mathbf{x}}_k\right),{\mathbf{x}}_{k+1}-{\mathbf{x}}_k⟩+\frac{L}{2}{\Vert {\mathbf{x}}_k-{\mathbf{x}}_{k+1}\Vert }^2$$
根据凸函数的一节条件
$f({\mathbf{x}}_k)\le f({\mathbf{x}}^{\ast })+⟨\nabla f({\mathbf{x}}^{\ast }),{\mathbf{x}}_k-{\mathbf{x}}^{\ast }⟩$
有
$$f\left({\mathbf{x}}_{k+1}\right)\le f\left({\mathbf{x}}^{\ast }\right)+⟨\nabla f\left({\mathbf{x}}_k\right),{\mathbf{x}}_k-{\mathbf{x}}^{\ast }⟩+⟨\nabla f\left({\mathbf{x}}_k\right),{\mathbf{x}}_{k+1}-{\mathbf{x}}_k⟩+\frac{L}{2}{\Vert {\mathbf{x}}_k-{\mathbf{x}}_{k+1}\Vert }^2.$$
根据第二投影定理
$$⟨{\mathbf{x}}_k-\bar{t}\nabla f\left({\mathbf{x}}_k\right)-{\mathbf{x}}_{k+1},{\mathbf{x}}^{\ast }-{\mathbf{x}}_{k+1}⟩\le 0$$
于是
$$⟨\nabla f\left({\mathbf{x}}_k\right),{\mathbf{x}}_{k+1}-{\mathbf{x}}^{\ast }⟩\le \frac{1}{\bar{t}}⟨{\mathbf{x}}_k-{\mathbf{x}}_{k+1},{\mathbf{x}}_{k+1}-{\mathbf{x}}^{\ast }⟩$$
因为$\bar{t}\le \frac{1}{L}$
$$\begin{array}{rl}f\left({\mathbf{x}}_{k+1}\right)& \le f\left({\mathbf{x}}^{\ast }\right)+⟨\nabla f\left({\mathbf{x}}_k\right),{\mathbf{x}}_k-{\mathbf{x}}^{\ast }⟩+⟨\nabla f\left({\mathbf{x}}_k\right),{\mathbf{x}}_{k+1}-{\mathbf{x}}_k⟩+\frac{L}{2}{\Vert {\mathbf{x}}_k-{\mathbf{x}}_{k+1}\Vert }^2\\ & =f\left({\mathbf{x}}^{\ast }\right)+⟨\nabla f\left({\mathbf{x}}_k\right),{\mathbf{x}}_{k+1}-{\mathbf{x}}^{\ast }⟩+\frac{L}{2}{\Vert {\mathbf{x}}_k-{\mathbf{x}}_{k+1}\Vert }^2\\ & \le f\left({\mathbf{x}}^{\ast }\right)+\frac{1}{\bar{t}}⟨{\mathbf{x}}_k-{\mathbf{x}}_{k+1},{\mathbf{x}}_{k+1}-{\mathbf{x}}^{\ast }⟩+\frac{L}{2}{\Vert {\mathbf{x}}_k-{\mathbf{x}}_{k+1}\Vert }^2\\ & \le f\left({\mathbf{x}}^{\ast }\right)+\frac{1}{\bar{t}}⟨{\mathbf{x}}_k-{\mathbf{x}}_{k+1},{\mathbf{x}}_{k+1}-{\mathbf{x}}^{\ast }⟩+\frac{1}{2\bar{t}}{\Vert {\mathbf{x}}_k-{\mathbf{x}}_{k+1}\Vert }^2\\ & =f\left({\mathbf{x}}^{\ast }\right)+\frac{1}{2\bar{t}}\left({\Vert {\mathbf{x}}_k-{\mathbf{x}}^{\ast }\Vert }^2-{\Vert {\mathbf{x}}_{k+1}-{\mathbf{x}}^{\ast }\Vert }^2\right)\end{array}$$
(b)
对(a)的结论进行累加
$$\begin{array}{rl}\sum _{k=0}^{n-1}\left({\Vert {\mathbf{x}}_{k+1}-{\mathbf{x}}^{\ast }\Vert }^2-{\Vert {\mathbf{x}}_k-{\mathbf{x}}^{\ast }\Vert }^2\right)& \le \sum _{k=0}^{n-1}2\bar{t}\left(f\left({\mathbf{x}}^{\ast }\right)-f\left({\mathbf{x}}_{k+1}\right)\right)\\ {\Vert {\mathbf{x}}_n-{\mathbf{x}}^{\ast }\Vert }^2-{\Vert {\mathbf{x}}_0-{\mathbf{x}}^{\ast }\Vert }^2& \le 2n\bar{t}\left(f\left({\mathbf{x}}^{\ast }\right)-f\left({\mathbf{x}}_n\right)\right)\end{array}$$
因此
$$f\left({\mathbf{x}}_n\right)-f^{\ast }\le \frac{{\Vert {\mathbf{x}}_0-{\mathbf{x}}^{\ast }\Vert }^2-{\Vert {\mathbf{x}}_n-{\mathbf{x}}^{\ast }\Vert }^2}{2\bar{t}n}\le \frac{{\Vert {\mathbf{x}}_0-{\mathbf{x}}^{\ast }\Vert }^2}{2\bar{t}n}$$

引理2

在刚才的条件下
产生的序列 { x k } k ≥ 0 \{\mathbf{x}_k\}_{k\ge 0} {xk​}k≥0​，对于$\forall {\mathbf{x}}^{\ast }\in X^{\ast },k\ge 0$,有
$$\Vert {\mathrm{x}}_{k+1}-{\mathrm{x}}^{\ast }\Vert \le \Vert {\mathrm{x}}_k-{\mathrm{x}}^{\ast }\Vert$$
证明：
利用(a)的结论，显然成立

定理7

在刚才的条件下
设 { x k } k ≥ 0 \{\mathbf{x}_k\}_{k\ge 0} {xk​}k≥0​是梯度投影法用固定步长$\bar{t}\in (0,\frac{1}{L}]$产生的序列，
则这个序列收敛到最优解

证明：
摸了

稀疏约束问题

$$\begin{array}{lll}& \min & f(\mathbf{x})\\ \text{ (S) }& \text{ s.t. }& \Vert \mathbf{x}{\Vert }_0\le s\end{array}$$
其中$f:{\mathbb{R}}^n\to \mathbb{R}$是一个连续可微的有下界的函数，并且梯度Lipschitz常数为$L_f$，$s>0$
∥ x ∥ 0 = ∣ { i : x i ≠ 0 } ∣ . \|\mathbf{x}\|_{0}=\left|\left\{i: x_{i} \neq 0\right\}\right| . ∥x∥0​=∣{i:xi​​=0}∣.

令
I 1 ( x ) ≡ { i : x i ≠ 0 } I_{1}(\mathbf{x}) \equiv\left\{i: x_{i} \neq 0\right\} I1​(x)≡{i:xi​​=0}
I 0 ( x ) ≡ { i : x i = 0 } I_{0}(\mathbf{x}) \equiv\left\{i: x_{i} = 0\right\} I0​(x)≡{i:xi​=0}
C s = { x : ∥ x ∥ 0 ≤ s } C_{s}=\left\{\mathbf{x}:\|\mathbf{x}\|_{0} \leq s\right\} Cs​={x:∥x∥0​≤s}
于是问题(S)可以写成
min ⁡ { f ( x ) : x ∈ C s } \min\left\{f(\mathbf{x}):\mathbf{x}\in C_s\right\} min{f(x):x∈Cs​}
接着
$M_i(\mathbf{x})$表示$\mathbf{x}$分量中绝对值最大的
现在我们来解这个问题

L-稳定

前面正交投影算子要求是一个凸集，但是这个$C_s$并不是一个凸集，所以，最优解不唯一。
P C s ( x ) = argmin ⁡ y { ∥ y − x ∥ : y ∈ C s } P_{C_{s}}(\mathbf{x})=\operatorname{argmin}_{\mathbf{y}}\left\{\|\mathbf{y}-\mathbf{x}\|: \mathbf{y} \in C_{s}\right\} PCs​​(x)=argminy​{∥y−x∥:y∈Cs​}
因为目标函数依然是强制函数，$C_s$是闭集，所以一定是有解的

L-稳定点

${\mathbf{x}}^{\ast }\in C_s$如果满足
$$\left[{\mathrm{N}\mathrm{C}}_L\right]{\mathrm{x}}^{\ast }\in P_{{\mathrm{C}}_s}\left({\mathrm{x}}^{\ast }-\frac{1}{L}\nabla f\left({\mathrm{x}}^{\ast }\right)\right)$$
则称为问题(S)的L-稳定点(L-stationarity point)

引理3

$\forall L>0,{\mathbf{x}}^{\ast }\in C_s$,满足$\left[N{C}_L\right]$当且仅当
$$\left|\frac{\partial f}{\partial x_i}\left({\mathbf{x}}^{\ast }\right)\right|\{\begin{array}{ll}\le L{M}_s\left({\mathbf{x}}^{\ast }\right)& \text{ if }i\in I_0\left({\mathbf{x}}^{\ast }\right),\\ =0& \text{ if }i\in I_1\left({\mathbf{x}}^{\ast }\right).\end{array}$$

证明：
必要性：${\mathbf{x}}^{\ast }$满足$\left[N{C}_L\right]$
注意到$P_{{\mathrm{C}}_s}\left({\mathrm{x}}^{\ast }-\frac{1}{L}\nabla f\left({\mathrm{x}}^{\ast }\right)\right)$中的分量要么为0，要么为${\mathbf{x}}_j-\frac{1}{L}\frac{\partial f}{\partial x_j}({\mathbf{x}}^{\ast })$
因为${\mathrm{x}}^{\ast }\in P_{{\mathrm{C}}_s}\left({\mathrm{x}}^{\ast }-\frac{1}{L}\nabla f\left({\mathrm{x}}^{\ast }\right)\right)$
所以如果$i\in I_1\left({\mathbf{x}}^{\ast }\right)$,则
$x_i^{\ast }=x_i^{\ast }-\frac{1}{L}\frac{\partial f}{\partial x_i}\left({\mathbf{x}}^{\ast }\right)$
如果$i\in I_0\left({\mathbf{x}}^{\ast }\right)$,则$\left|x_i^{\ast }-\frac{1}{L}\frac{\partial f}{\partial x_i}\left({\mathbf{x}}^{\ast }\right)\right|\le M_s\left({\mathbf{x}}^{\ast }\right)$
又因为$x_i^{\ast }=0$，所以$\left|\frac{\partial f}{\partial x_i}\left({\mathbf{x}}^{\ast }\right)\right|\le L{M}_s\left({\mathbf{x}}^{\ast }\right)$

充分性：
如果$\Vert {\mathbf{x}}^{\ast }{\Vert }_0<s$,则$M_s({\mathbf{x}}^{\ast })=0$,进而$\nabla f({\mathbf{x}}^{\ast })=0$
这种情况 P C s ( x ∗ − 1 L ∇ f ( x ∗ ) ) = P C s ( x ∗ ) = { x ∗ } P_{\mathrm{C}_{s}}\left(\mathrm{x}^{*}-\frac{1}{L} \nabla f\left(\mathrm{x}^{*}\right)\right)=P_{C_s}(\mathbf{x}^*)=\left\{\mathbf{x}^*\right\} PCs​​(x∗−L1​∇f(x∗))=PCs​​(x∗)={x∗}

如果$\Vert {\mathbf{x}}^{\ast }\Vert =s$,则
$$\left|x_i^{\ast }-\frac{1}{L}\frac{\partial f}{\partial x_i}\left({\mathbf{x}}^{\ast }\right)\right|\{\begin{array}{ll}=\left|x_i^{\ast }\right|,& i\in I_1\left({\mathbf{x}}^{\ast }\right),\\ \le M_s\left({\mathbf{x}}^{\ast }\right),& i\in I_0\left({\mathbf{x}}^{\ast }\right).\end{array}$$

引理4

假设$f\in C_{L_f}^{1,1}({\mathbb{R}}^n),L>L_f$,则对于$\forall \mathbf{x}\in C_s,y\in {\mathbb{R}}^n$,且满足
$$\mathrm{y}\in P_{C_s}\left(\mathrm{x}-\frac{1}{L}\nabla f(\mathrm{x})\right)$$
有
$$f(\mathbf{x})-f(\mathbf{y})\ge \frac{L-L_f}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2$$

证明：
因为
$$\mathrm{y}\in {\mathrm{argmin}}_{\mathrm{z}\in {\mathrm{C}}_s}{\Vert \mathrm{z}-\left(\mathrm{x}-\frac{1}{L}\nabla f(\mathrm{x})\right)\Vert }^2$$
$$\begin{array}{rl}{h}_L(\mathbf{z},\mathbf{x})& =f(\mathbf{x})+⟨\nabla f(\mathbf{x}),\mathbf{z}-\mathbf{x}⟩+\frac{L}{2}\Vert \mathbf{z}-\mathbf{x}{\Vert }^2\\ & =\frac{L}{2}{\Vert \mathbf{z}-\left(\mathbf{x}-\frac{1}{L}\nabla f(\mathbf{x})\right)\Vert }^2+\underset{\text{constant w.r.t. }z}{\underbrace{f(\mathbf{x})-\frac{1}{2L}\Vert \nabla f(\mathbf{x}){\Vert }^2}},\end{array}$$
所以
$$\mathrm{y}\in {\mathrm{argmin}}_{\mathrm{z}\in {\mathrm{C}}_s}{h}_L(\mathrm{z},\mathrm{x})$$
所以
$$h_L(\mathbf{y},\mathbf{x})\le h_L(\mathbf{x},\mathbf{x})=f(\mathbf{x})$$
根据下降引理
$$f(\mathbf{x})-f(\mathbf{y})\ge f(\mathbf{x})-h_{L_f}(\mathbf{y},\mathbf{x})$$
根据
$$h_{L_f}(\mathbf{x},\mathbf{y})=h_L(\mathbf{x},\mathbf{y})-\frac{L-L_f}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2$$
有
$$f(\mathbf{x})-f(\mathbf{y})\ge \frac{L-L_f}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2$$

定理8

设$f\in C_{L_f}^{1,1}({\mathbb{R}}^n),L>L_f$
设${\mathbf{x}}^{\ast }$是问题(S)的最优解，则
(i)${\mathbf{x}}^{\ast }$是一个L-稳定点
(ii)$P_{{\mathrm{C}}_s}\left({\mathrm{x}}^{\ast }-\frac{1}{L}\nabla f\left({\mathrm{x}}^{\ast }\right)\right)$只有一个元素
证明：
假设$\mathbf{y}\in P_{{\mathrm{C}}_s}\left({\mathrm{x}}^{\ast }-\frac{1}{L}\nabla f\left({\mathrm{x}}^{\ast }\right)\right)$
且${\mathbf{x}}^{\ast }\ne \mathbf{y}$
根据引理3
$$f\left({\mathbf{x}}^{\ast }\right)-f(\mathbf{y})\ge \frac{L-L_f}{2}{\Vert {\mathbf{x}}^{\ast }-\mathbf{y}\Vert }^2$$
与${\mathbf{x}}^{\ast }$是最优解矛盾

IHT方法

输入$L>L_f$
选择起点${\mathbf{x}}_0\in C_s$
迭代${\mathbf{x}}^{k+1}\in P_{C_s}({\mathbf{x}}^k-\frac{1}{L}\nabla f({\mathbf{x}}^k)),k=0,1,\cdots$

引理5

设$f\in C_{L_f}^{1,1}({\mathbb{R}}^n)$,且有下界
设${\left\{{\mathbf{x}}^k\right\}}_{k\ge 0}$是IHT方法用固定步长$\frac{1}{L}$产生的序列，则
(a)$f\left({\mathrm{x}}^k\right)-f\left({\mathrm{x}}^{k+1}\right)\ge \frac{L-L_f}{2}{\Vert {\mathrm{x}}^k-{\mathrm{x}}^{k+1}\Vert }^2$
(b)${\left\{f\left({\mathbf{x}}^k\right)\right\}}_{k\ge 0}$单调不增
$(c)$$\Vert {\mathbf{x}}^k-{\mathbf{x}}^{k+1}\Vert \to 0$
(d)对于$\forall k=0,1,2,\cdots$,如果${\mathbf{x}}^k\ne {\mathbf{x}}^{k+1}$,则$f\left({\mathbf{x}}^{k+1}\right)<f\left({\mathbf{x}}^k\right)$

证明：
(a)由引理4显然成立
(b)由(a)，显然
$(c)$${\left\{f\left({\mathbf{x}}^k\right)\right\}}_{k\ge 0}$单调递减有下界，收敛，
所以由(a)成立
(d)显然

定理8

设${\left\{{\mathbf{x}}^k\right\}}_{k\ge 0}$是IHT方法用固定步长$\frac{1}{L}$产生的序列
其中$L>L_f$
则${\left\{{\mathbf{x}}^k\right\}}_{k\ge 0}$的任何聚点都是L-稳定点

证明：摸了