投影梯度法 投影梯度法是一种用于求解约束优化问题的迭代算法，特别适用于约束集具有简单几何结构（如闭凸集）的情况。其核心思想是将标准的梯度下降步骤与一个投影操作相结合，确保每次迭代后的解都落在可行域内。 问题背景与基本思想 考虑一个带约束的优化问题：minimize f(x)，满足 x ∈ C，其中 C 是一个闭凸集（例如，一个盒子约束、一个仿射空间、一个概率单纯形等）。 如果我们直接对 f(x) 使用梯度下降法：x_ {k+1} = x_ k - α_ k ∇f(x_ k)，新得到的点 x_ {k+1} 很可能落在可行域 C 之外，从而违反了约束。 投影梯度法的巧妙之处在于，在梯度下降步骤之后，立即将得到的新点“拉回”到可行域 C 中。这个“拉回”操作在数学上称为 投影 。 关键概念：投影 给定一个闭凸集 C，点 y 到 C 的 投影 定义为这样一个点： Proj_ C(y) = argmin_ {x ∈ C} ||x - y||² 这个定义直观上很好理解：在集合 C 中，寻找一个与 y 欧几里得距离最近的点。由于 C 是凸集，这个投影点是存在且唯一的。 投影算子 Proj_ C(·) 具有一个非常重要的性质： 非扩张性 。即对于任意两点 y1, y2，有 ||Proj_ C(y1) - Proj_ C(y2)|| ≤ ||y1 - y2||。这个性质保证了算法的稳定性。 算法步骤 投影梯度法的迭代格式非常简洁： 步骤1：梯度下降步 。在当前迭代点 x_ k，沿着负梯度方向移动一个步长 α_ k，得到一个中间点 y_ k： y_ k = x_ k - α_ k ∇f(x_ k) 步骤2：投影步 。将中间点 y_ k 投影回可行域 C，得到下一个迭代点： x_ {k+1} = Proj_ C(y_ k) 重复以上两步，直到满足收敛条件（例如，梯度映射的范数足够小，或者相邻迭代点的变化不大）。 步长选择与收敛性 和梯度下降法一样，步长 α_ k 的选择至关重要。常用的策略有： 固定步长 ：如果函数 f 的梯度是 Lipschitz 连续的（常数为 L），那么选择固定步长 α_ k ≡ α ∈ (0, 2/L) 可以保证算法收敛。 精确线搜索 ：在每一步，沿着搜索方向寻找使目标函数值下降最多的步长。虽然精确，但计算成本高。 回溯线搜索（Armijo准则） ：这是一种更实用的非精确线搜索。它从一个较大的初始步长开始，不断按比例缩小，直到满足一个简单的函数值下降条件。这是一种在保证收敛和计算效率之间很好的折衷。 在适当的条件下（如 f 是凸函数且可微），投影梯度法可以收敛到全局最优解。 与无约束梯度下降法的关系 投影梯度法可以看作是梯度下降法在约束问题上的自然推广。当约束集 C 是整个空间 R^n 时，投影操作 Proj_ C(y) = y，算法就退化为标准的梯度下降法。 算法的收敛速率也与梯度下降法类似。对于凸函数，收敛速率是 O(1/k)（次线性）；对于强凸函数，收敛速率是线性收敛 O(ρ^k) (0<ρ <1)。 优缺点与应用场景 优点 ： 概念直观，实现简单。 只要投影操作容易计算，算法就非常高效。对于许多简单约束集（如非负象限、球、仿射集、单纯形等），投影有解析解或高效算法。 缺点 ： 如果投影操作 Proj_ C(·) 本身计算复杂（例如，C 是一个一般的多面体），那么每一步迭代的成本会很高，可能不如其他方法（如内点法）高效。 收敛速度是线性的或次线性的，对于大规模问题可能较慢。 典型应用 ：广泛应用于信号处理、机器学习、图像重建等领域，特别是当约束具有简单结构时，例如非负矩阵分解、带约束的逻辑回归、压缩感知等。