本文的收敛性证明针对于可行集为凸集的场景。
https://zhuyulab.blog.csdn.net/article/details/119084135 在这篇中我们证明了， 无约束的梯度下降法，可以有：
∥
x
k
+
1
−
x
⋆
∥
≤
M
∥
x
k
−
x
⋆
∥
\|x_{k+1}-x^\star\|\le M\|x_k-x^\star\|
∥xk+1−x⋆∥≤M∥xk−x⋆∥ 即每次迭代后的点 相比于迭代前， 离最优值
x
⋆
x^\star
x⋆更接近。 而投影梯度法的收敛性核心在于证明：
∥
x
^
k
+
1
−
x
⋆
∥
≤
M
∥
x
k
−
x
∗
∥
\| \hat{x}_{k+1}- x^\star\|\le M\|x_k-x^*\|
∥x^k+1−x⋆∥≤M∥xk−x∗∥ 其中，
x
^
k
+
1
\hat{x}_{k+1}
x^k+1是将
x
k
+
1
x_{k+1}
xk+1投影到可行集
S
S
S中的点。 
首先，我们明确下投影的定义。 寻找一点
z
z
z凸集
S
S
S内的投影
z
∗
z^*
z∗， 就是找到一点：
z
∗
=
arg
min
z
∗
∈
S
∥
z
−
z
∗
∥
2
z^*=\arg\min_{z^*\in S}\|z-z^*\|^2
z∗=argminz∗∈S∥z−z∗∥2,即
S
S
S中离
z
z
z距离最短的一点。 大家可以想象一下， 如果
z
z
z在某个平面上方， 那么离他距离最近的点， 不就是过
z
z
z对
S
S
S做垂线得到的垂足嘛。 但如果平面比较小，
z
z
z的垂足落在了平面外呢？ 那就出现了上图中的黑色的
z
∗
z^*
z∗的情况， 应该位于
S
S
S的边界上。 但无论如何， 下式是一定成立的：
⟨ z ∗ − z , z ∗ − x ⟩ ≤ 0 (1) \langle z^* - z, z^* - x\rangle\le 0\tag{1} ⟨z∗−z,z∗−x⟩≤0(1)
几何意义很容易理解： S S S上任一点和 z ∗ z^* z∗连线与 z z ∗ zz^* zz∗成直角或钝角。 直角就是之前垂足在 S S S上的场景。 钝角就是垂足在 S S S外的场景。
可以这样证明， 由于 S S S是凸集， 因此存在 t > 0 t>0 t>0， z ∗ + t ( x − z ∗ ) ∈ S z^* + t(x-z^*)\in S z∗+t(x−z∗)∈S。又根据投影的定义，有：
∥ z ∗ + t ( x − z ∗ ) − z ∥ 2 ≥ ∥ z ∗ − z ∥ 2 \|z^* + t(x-z^*) - z\|^2\ge \|z^* - z\|^2 ∥z∗+t(x−z∗)−z∥2≥∥z∗−z∥2 将左边展开， 有： ⟨ z ∗ − z , x − z ∗ ⟩ + t ∥ x − z ∗ ∥ 2 ≥ 0 \langle z^* - z, x-z^* \rangle+t\|x-z^*\|^2\ge 0 ⟨z∗−z,x−z∗⟩+t∥x−z∗∥2≥0 由于上式对于 t → 0 t\rightarrow0 t→0也成立， 因此： ⟨ z ∗ − z , x − z ∗ ⟩ ≥ 0 \langle z^* - z, x-z^* \rangle\ge 0 ⟨z∗−z,x−z∗⟩≥0 也即(1).
接下来， 假设空间中任意两点 z z z 和 y y y 在 S S S上的投影分别为 z ∗ z^* z∗ 和 y ∗ y^* y∗， 因为 z ∗ z^* z∗和 y ∗ y^* y∗显然是 S S S上的两点，因此我们有： ⟨ z − z ∗ , y ∗ − z ∗ ⟩ ≤ 0 , ⟨ y − y ∗ , z ∗ − y ∗ ⟩ ≤ 0 \langle z-z^*, y^*-z^*\rangle\le 0, \quad \langle y-y^*, z^*-y^*\rangle\le 0 ⟨z−z∗,y∗−z∗⟩≤0,⟨y−y∗,z∗−y∗⟩≤0 右边也可以写作： ⟨ y − y ∗ , y ∗ − z ∗ ⟩ ≥ 0 \langle y-y^*, y^*-z^*\rangle\ge 0 ⟨y−y∗,y∗−z∗⟩≥0 因此， ⟨ y − y ∗ − ( z − z ∗ ) , y ∗ − z ∗ ⟩ ≥ 0 ⇒ ⟨ y − z − ( y ∗ − z ∗ ) , y ∗ − z ∗ ⟩ ≥ 0 ⇒ ⟨ y ∗ − z ∗ , y ∗ − z ∗ ⟩ ≤ ⟨ y − z , y ∗ − z ∗ ⟩ ⇒ ∥ y ∗ − z ∗ ∥ 2 ≤ ⟨ y − z , y ∗ − z ∗ ⟩ ≤ ∥ y − z ∥ ∥ y ∗ − z ∗ ∥ ⇒ ∥ y ∗ − z ∗ ∥ ≤ ∥ y − z ∥ \langle y - y^* - (z-z^*), y^*-z^*\rangle\ge 0\\ \Rightarrow\langle y - z - (y^*-z^*), y^*-z^*\rangle\ge 0\\ \Rightarrow \langle y^*-z^*, y^*-z^*\rangle\le\langle y-z, y^*-z^*\rangle\\ \Rightarrow\|y^*-z^*\|^2\le \langle y-z, y^*-z^*\rangle\le \|y-z\|\|y^*-z^*\|\\ \Rightarrow\|y^*-z^*\|\le \|y-z\| ⟨y−y∗−(z−z∗),y∗−z∗⟩≥0⇒⟨y−z−(y∗−z∗),y∗−z∗⟩≥0⇒⟨y∗−z∗,y∗−z∗⟩≤⟨y−z,y∗−z∗⟩⇒∥y∗−z∗∥2≤⟨y−z,y∗−z∗⟩≤∥y−z∥∥y∗−z∗∥⇒∥y∗−z∗∥≤∥y−z∥
也就是说： 两点的距离大于两点在凸集上投影点间的距离。
根据这个结论， 由于 x ⋆ x^\star x⋆在 S S S上的投影就是 x ⋆ x^\star x⋆本身，因此： ∥ x ^ k + 1 − x ⋆ ∥ ≤ ∥ x k + 1 − x ⋆ ∥ ≤ M ∥ x k − x ∗ ∥ \| \hat{x}_{k+1}- x^\star\|\le \|x_{k+1}-x^\star\|\le M\|x_k-x^*\| ∥x^k+1−x⋆∥≤∥xk+1−x⋆∥≤M∥xk−x∗∥
收敛性得证。
