本文是一个总结一下投影梯度法（Projected Gradient Method）的核心内容。梳理一下其理论依据，适合解决的问题，以及优缺点。

1. 投影梯度法解决什么问题

投影梯度法用于求解带约束的优化问题：

其中 $\mathcal{C}$ 是一个闭凸约束集。

对于无约束问题，梯度下降直接更新 $\mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} - \alpha_k \nabla f(\mathbf{x}^{(k)})$ 即可。但一旦加上约束，这个更新不保证可行——新的点可能跑到约束集外面。投影梯度法的核心思想是：先沿负梯度方向走一步，再将结果投影回可行集：

其中 $\mathcal{P}_{\mathcal{C}}(\cdot)$ 是到集合 $\mathcal{C}$ 的欧几里得投影。当 $\mathcal{C} = \mathbb{R}^n$（无约束）时，投影是恒等映射，投影梯度法退化为普通梯度下降。

典型适用场景：

• 盒约束 $a \le x_i \le b$：投影是逐元素截断
• 单纯形约束 $\sum x_i = 1,\; x_i \ge 0$
• 范数球约束 $|\mathbf{x}| \le r$：投影是缩放到球面
• 半正定锥约束：特征值截断

2. 为什么要有投影梯度法

2.1 对标方法一览

2.2 投影梯度法的优势

投影梯度法是约束优化中最直接、最轻量的一阶方法：

1. 概念最简单——”先走梯度，再拉回来”，是无约束梯度下降到约束场景的最自然推广。
2. 每步代价低——只需要一次梯度计算 + 一次投影，不需要求解线性方程组（对比内点法）或调罚参数（对比罚函数法）。
3. 投影有闭式解时极其高效——盒约束（截断）、球约束（缩放）、单纯形等常见约束的投影都是 $O(n)$ 或 $O(n\log n)$。

投影梯度基于目标函数的梯度，相比其他优化算法，几乎没有其他额外运算（因为梯度对于迭代优化算法来讲是必须的）。

3. 投影梯度法的局限性

投影梯度法的迭代由两个动作组成：梯度下降 + 投影。它的局限性也对应地从这两方面产生。

3.1 梯度方面：一阶方法的收敛瓶颈

投影梯度法本质上是一阶方法——只利用梯度（一阶导数）信息。这决定了它在高精度需求下的天然劣势。

精度与收敛速度

“精度”指当前解 $\mathbf{x}^{(k)}$ 与最优解 $\mathbf{x}^{\ast}$ 之间的目标函数值差距 $f(\mathbf{x}^{(k)}) - f(\mathbf{x}^{\ast})$。”收敛速度”决定了达到某个精度需要多少步迭代。不同方法的对比如下：

当精度要求从 $10^{-3}$ 提高到 $10^{-6}$（提高 1000 倍）时：

• 一阶方法（投影梯度）：迭代次数增加 1000 倍
• 二阶方法（内点法）：迭代次数可能只增加 几步

直觉

• 一阶方法只知道”哪个方向是下坡”（梯度），每步走固定大小。接近最优点时，梯度变小，步子越来越碎，最后一点距离要走很久。
• 二阶方法还知道”地形的曲率”（Hessian），能精准判断最低点的位置，到了附近几步就能跳到极高精度。

对比：为什么内点法能做到二阶收敛

内点法处理约束的方式是引入障碍函数：

对于每一个固定的 $t$，用牛顿法求解上面这个无约束问题。牛顿法的更新公式为：

其中 $\nabla^2 \phi$ 是 Hessian 矩阵（二阶导数信息）。用到了二阶导数，所以是二阶方法。二次收敛意味着：误差从 $10^{-1} \to 10^{-2} \to 10^{-4} \to 10^{-8}$，几步就到机器精度。当然，代价是每步需要计算 Hessian 并求解线性方程组（$O(n^3)$），所以内点法是”每步贵但步数少”，投影梯度法是”每步便宜但步数多”。

3.2 投影方面：投影本身可能很难算

投影梯度法”每步轻量”的前提是投影 $\mathcal{P}_\mathcal{C}(\cdot)$ 容易计算。然而并非所有约束集都满足这个条件。

容易的投影

盒约束 $\mathcal{C} = \lbrace\mathbf{x} : a_i \le x_i \le b_i\rbrace$，投影是逐元素截断：

计算量 $O(n)$，就很舒服。

困难的例子：半正定锥约束

约束 $\mathcal{C} = \lbrace\mathbf{X} : \mathbf{X} \succeq 0\rbrace$（半正定），投影需要：

1. 对矩阵做特征值分解：$\mathbf{X} = \sum_i \lambda_i \mathbf{v}_i \mathbf{v}_i^T$
2. 把负特征值截为零：$\mathcal{P}_{\mathcal{C}}(\mathbf{X}) = \sum_i \max(\lambda_i, 0)\, \mathbf{v}_i \mathbf{v}_i^T$

特征值分解的复杂度是 $O(n^3)$。若 $n = 1000$，每一步投影就要做 $10^9$ 量级的运算，而投影梯度法可能需要成百上千步迭代。

投影困难时的替代方案：黎曼梯度法

当投影难以计算时，一个自然的问题是：能不能绕开投影？ 对于一类重要的约束——约束集本身是一个光滑流形（如球面、正交矩阵、低秩矩阵等等式约束），答案是可以，用黎曼梯度法。

投影梯度法把约束集视为欧氏空间中的一个子集，先在外部空间走一步再拉回来。黎曼梯度法则转换视角：把约束集本身视为一个弯曲的空间（流形），直接在流形上移动，从一开始就不离开可行集，因此根本不需要投影。

以球面 $\lVert\mathbf{x}\rVert = 1$ 为例来说明两者的差异：

投影梯度：

1. 站在球面上，按欧氏梯度方向走一步——飞离球面进入三维空间
2. 从空间中把点投影（拉回）到最近的球面上

黎曼梯度：

1. 站在球面上，计算切平面上的梯度分量——方向从一开始就贴着球面
2. 沿切方向走一步，用回缩映射映回流形

对于某些简单流形，两者实际上等价或近似等价。例如球面约束上，黎曼梯度 = 欧氏梯度投影到切空间 $\text{grad}_\mathcal{M} f = (\mathbf{I} - \mathbf{x}\mathbf{x}^T)\nabla f$，回缩 = 归一化 $\mathcal{R}_\mathbf{x}(\mathbf{v}) = \frac{\mathbf{x}+\mathbf{v}}{\lVert\mathbf{x}+\mathbf{v}\rVert}$。但黎曼方法真正的价值体现在投影困难的流形约束上：

关键例子：Stiefel 流形 $\mathbf{X}^T\mathbf{X} = \mathbf{I}$（正交矩阵约束）。投影梯度需要做 SVD（$O(n^3)$），且本质上是在解一个隐式优化子问题；黎曼梯度用 QR 分解做回缩，常数更小且数值更稳定。

总结一下两者的适用场景：

一句话概括：投影梯度是”在外面走，拉回来”；黎曼梯度是”一直在里面走”。约束定义的是凸集时用投影，定义的是光滑流形时用黎曼。

4. 投影梯度法的完整收敛性理论

这里讨论一个问题：为什么投影梯度法能work。

4.0 问题设定

假设：

• $\mathcal{C} \subseteq \mathbb{R}^n$ 是非空闭凸集
• $f$ 是凸函数
• $\nabla f$ 是 $L$-Lipschitz 连续的：$\lVert\nabla f(\mathbf{x}) - \nabla f(\mathbf{y})\rVert \le L\lVert\mathbf{x} - \mathbf{y}\rVert$

投影梯度法的迭代可以写成

4.1 投影算子的基本性质

4.1.1 投影的存在唯一性

对闭凸集 $\mathcal{C}$ 和任意 $\mathbf{y} \in \mathbb{R}^n$，投影定义为：

$\lVert\cdot - \mathbf{y}\rVert^2$ 是强凸函数，$\mathcal{C}$ 是闭凸集，所以最小化问题有唯一解。

4.1.2 投影的变分刻画

$\hat{\mathbf{x}} = \mathcal{P}_\mathcal{C}(\mathbf{y})$ 当且仅当：

证明： $\hat{\mathbf{x}}$ 是 $\min_{\mathbf{z} \in \mathcal{C}} \frac{1}{2}\lVert\mathbf{z} - \mathbf{y}\rVert^2$ 的解。由凸优化的一阶最优性条件（方向导数非负）：

几何含义： 从 $\hat{\mathbf{x}}$ 出发，指向 $\mathbf{y}$ 的方向和指向可行集内任何点 $\mathbf{z}$ 的方向，夹角 $\ge 90°$。

4.1.3 非扩张性

由 (P1) 可推出：

证明： 记 $\hat{\mathbf{x}} = \mathcal{P}_\mathcal{C}(\mathbf{x})$，$\hat{\mathbf{y}} = \mathcal{P}_\mathcal{C}(\mathbf{y})$。由 (P1)：

两式相加：

由 Cauchy-Schwarz 不等式：

两边除以 $\lVert\hat{\mathbf{x}} - \hat{\mathbf{y}}\rVert$ 即得 $\lVert\hat{\mathbf{x}} - \hat{\mathbf{y}}\rVert \le \lVert\mathbf{x} - \mathbf{y}\rVert$。$\blacksquare$

4.1.4 推论：到可行点的距离不增

若 $\mathbf{z} \in \mathcal{C}$，则 $\mathcal{P}_\mathcal{C}(\mathbf{z}) = \mathbf{z}$，所以：

投影后离可行集内任何一点（包括最优解）只会更近，不会更远。

4.2 Descent Lemma

这是梯度下降理论的基础工具，和投影无关。

引理： 若 $\nabla f$ 是 $L$-Lipschitz 的，则：

含义：$f$ 可以被一个二次函数从上方控制住。梯度 Lipschitz 意味着函数不会弯曲得太厉害。

4.3 最优性条件等价于不动点

命题： $\mathbf{x}^{\ast}$ 是 $\min_\mathcal{C} f(\mathbf{x})$ 的最优解 $\Leftrightarrow$ 对任意 $\alpha > 0$：

证明：

$\mathbf{x}^{\ast}$ 是凸问题的最优解 $\Leftrightarrow$ 一阶最优性条件：

由 (P1)，$\mathbf{x}^{\ast} = \mathcal{P}_\mathcal{C}(\mathbf{x}^{\ast} - \alpha \nabla f(\mathbf{x}^{\ast}))$ 当且仅当

这正是 (OPT)。$\blacksquare$

意义： 投影梯度法的迭代找的就是不动点，而不动点恰好就是 KKT 最优解。

4.4 核心收敛证明

记 $\mathbf{x}^{\ast}$ 为最优解，步长 $\alpha = 1/L$。

目标： 证明 $f(\mathbf{x}^{(K)}) - f(\mathbf{x}^{\ast}) \le \frac{L\lVert\mathbf{x}^{(0)} - \mathbf{x}^{\ast}\rVert^2}{2K}$。

步骤 A：单步函数值下降

记 $\mathbf{x}^+ = \mathbf{x}^{(k+1)}$，$\mathbf{x} = \mathbf{x}^{(k)}$，$\mathbf{g} = \nabla f(\mathbf{x})$。由 Descent Lemma (DL) 取 $\mathbf{y} = \mathbf{x}^+$：

步骤 B：利用投影的性质

$\mathbf{x}^+ = \mathcal{P}_\mathcal{C}(\mathbf{x} - \alpha\mathbf{g})$，由 (P1) 对所有 $\mathbf{z} \in \mathcal{C}$：

取 $\mathbf{z} = \mathbf{x}^{\ast}$ 并整理：

步骤 C：利用凸性

$f$ 是凸函数，所以：

步骤 D：组合

由 (S1)：

将 $\langle \mathbf{g},\; \mathbf{x}^+ - \mathbf{x} \rangle = \langle \mathbf{g},\; \mathbf{x}^+ - \mathbf{x}^{\ast} \rangle + \langle \mathbf{g},\; \mathbf{x}^{\ast} - \mathbf{x} \rangle$ 代入，利用 (S3)：

由 (S2)，取 $\alpha = 1/L$：

利用恒等式 $\langle \mathbf{a}, \mathbf{b} \rangle = \frac{1}{2}(\lVert\mathbf{a}\rVert^2 + \lVert\mathbf{b}\rVert^2 - \lVert\mathbf{a}-\mathbf{b}\rVert^2)$ 展开并化简，得到关键的单步不等式：

步骤 E：求和得收敛速率

对 $k = 0, 1, \ldots, K-1$ 求和 (Key)：

右边是伸缩和（telescoping sum），大量项对消。因为 $\lVert\mathbf{x}^{(K)} - \mathbf{x}^{\ast}\rVert^2 \ge 0$：

由 (Key) 知函数值递减，左边最小项是最后一项，因此：

4.5 强凸情况下的线性收敛

若 $f$ 还是 $\mu$-强凸的（$\nabla^2 f \succeq \mu \mathbf{I}$），强凸给出更紧的下界：

将这个更强的条件代入上面的推导，最终得到：

这是线性收敛（R-linear）：每步误差乘以常数 $(1 - \mu/L) < 1$。比值 $\kappa = L/\mu$ 称为条件数，$\kappa$ 越小收敛越快。

5. 完整逻辑链

投影的存在唯一性（闭凸集 + 强凸距离函数）
        │
        ▼
投影的变分刻画 (P1)
        │
        ├──► 非扩张性 (P2)/(P3)：投影不破坏进展
        │
        └──► 不动点 = KKT 最优解 (FP)：迭代方向正确
                │
                ▼
      Descent Lemma (DL)：L-光滑给出函数值上界
                │
                ▼
     单步不等式 (Key)：每步距离 x* 更近 + 函数值下降
                │
                ▼
      伸缩求和 ──► O(1/K) 收敛速率（凸）
                    或 线性收敛（强凸）

投影梯度法的理论核心可以归结为一句话：凸集投影的非扩张性保证投影不破坏梯度下降的进展，而最优解恰好是迭代的不动点，两者结合使得无约束梯度下降的收敛性分析几乎原封不动地搬到约束情况。