本文的收敛性证明针对于可行集为凸集的场景。
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∗∥
收敛性得证。
