强凸函数的投影梯度下降

核心理论可视化

主定理

对于 L-Lipschitz、α-强凸函数，使用步长 ηₛ = 2/(α(s+1))，
定义二次加权平均 x̄ₜ = (2/[t(t+1)]) · Σₛ₌₁ᵗ s·xₛ
f(x̄ₜ) - f(x*) ≤ 2L²/(α(t+1)) = O(1/t)
相比仅 Lipschitz 的 O(1/√t)，收敛速度提升一个数量级！

1. 强凸性：二次下界的几何意义

强凸性定义

f(y) ≥ f(x) + ⟨gₓ, y-x⟩ + α/2 · ||y-x||²

下图展示了强凸函数的几何特性：函数曲线（蓝线）必须位于强凸下界（绿线）之上

蓝线：实际函数 f(y)
橙色虚线：f(x) + ⟨gₓ, y-x⟩（切线，凸性下界）
绿线：f(x) + ⟨gₓ, y-x⟩ + α/2·||y-x||²（强凸下界）
红点：参考点 x

💡 理论洞察

普通凸性：函数 f(y) 在切线 f(x) + ⟨gₓ, y-x⟩ 之上（橙色虚线）

强凸性：函数 f(y) 在强凸下界 f(x) + ⟨gₓ, y-x⟩ + α/2·||y-x||² 之上（绿线）

关键观察：蓝线（f(y)）始终在绿线之上，且绿线的"弯曲"由 α 控制

α 的作用：α 越大 → 绿线弯曲越明显 → 函数曲率越强 → 优化收敛越快

2. 递减步长：自适应的智慧

步长公式

ηₛ = 2/(α(s+1))

💡 理论洞察

早期（s小）：η 大，快速接近最优区域（探索）

后期（s大）：η 小，精细收敛到最优点（利用）

自适应：无需提前知道总迭代数 T，自动平衡探索与利用

α 调节：α 大 → 曲率强 → 允许更大步长 → η₁ = 1/α

3. 二次加权：质量导向的平均

加权平均公式

x̄ₜ = 2/(t(t+1)) · Σₛ₌₁ᵗ s·xₛ

💡 理论洞察

线性权重：w(s) = s，后期迭代权重更高

归一化：Σₛ₌₁ᵗ s = t(t+1)/2，故系数为 2/(t(t+1))

直观：xₜ 权重 = t，x₁ 权重 = 1，差距为 t 倍

原因：配合递减步长，后期迭代更接近 x*，理应获更高权重

4. 收敛速率：理论与实际的完美契合

条件 收敛速率 类型 达到 ε 需要步数
仅 Lipschitz O(1/√t) 次线性收敛 O(1/ε²) 步
强凸 + Lipschitz O(1/t) 次线性收敛（更快） O(1/ε) 步
蓝线：O(1/√t) 参考（仅 Lipschitz 速率）
橙线：理论上界 2L²/(α(t+1)) = O(1/t)
绿线：实际加权误差 f(x̄ₜ) - f(x*)
红线（虚线）：实际点误差 f(xₜ) - f(x*)（振荡）

📊 可视化验证定理

通过图表可以清晰看到强凸性带来的收敛速度提升

5. 完整优化过程：理论的实践验证

🎯 调整参数观察不同条件下的收敛行为，验证理论保证

蓝线：O(1/√t) Lipschitz 界
橙线：理论上界 2L²/(α(t+1))
绿线：加权平均误差 f(x̄ₜ) - f(x*)
理论上界（t=T）
2L²/(α(T+1))
-
实际误差（t=T）
f(x̄ₜ) - f(x*)
-
上界紧密度
实际/理论
-
加速因子
vs O(1/√t)
-

✅ 理论验证要点

✓ 1. 上界有效性：绿线（加权误差）始终在橙线（理论上界）之下

✓ 2. 收敛速率：绿线下降速度明显快于蓝线（O(1/√t) 参考）

✓ 3. 加权优势：加权平均保证单调收敛，比单点迭代更稳定

✓ 4. 参数影响：α↑ 或 L↓ → 条件数↓ → 收敛更快