投影梯度法

投影梯度法在梯度下降每一步后，把暂时走出可行域的点拉回约束集合。设 $C\subseteq {ℝ}^d$ 非空、闭且凸，要最小化可微函数 $f$。欧氏投影 $P_C(z)$ 是 $C$ 中距离 $z$ 最近的点；算法一步为 $$z_k=x_k-{\alpha }_k\mathrm{\nabla }f(x_k),x_{k+1}=P_C(z_k),{\alpha }_k>0.$$ 闭凸性保证每个 $z_k$ 有唯一投影。若只做普通梯度下降而不投影，下一步可能根本不符合资源或概率范围的约束。

一个被边界挡住的最小值

在 $C=[0,1]$ 上最小化 $f(x)=(x-3{)}^2$。无约束极小点 3 不在区间中；从 $x_0=0.5$、步长 $\alpha =0.1$ 开始，梯度 $f^{\prime }(0.5)=2(0.5-3)=-5$，先走到 $z_0=0.5-0.1(-5)=1$，投影后 $x_1=1$。下一步有 $f^{\prime }(1)=-4$，暂定 $z_1=1.4$，但 $P_{[0,1]}(1.4)=1$，所以 $x_2=1$。区间投影就是把数夹在左右端点之间： $$P_{[a,b]}(z)=min\{b,max\{a,z\}\}.$$ 这里停在边界并非“梯度为零”：$f^{\prime }(1)=-4$；原因是所有可以继续减少函数的方向都指向区间外。

投影不等式与停止条件

令 $p=P_C(z)$。对任意 $y\in C$，线段 $p+t(y-p)$ 仍在 $C$。函数 $\Vert z-[p+t(y-p)]{\Vert }^2$ 在 $t=0$ 取得单侧最小值，因此右导数 $-2(z-p)\cdot (y-p)\ge 0$，即 $$(z-p)\cdot (y-p)\le 0(y\in C).$$ 反过来，展开距离平方也说明满足这条不等式的 $p$ 就是最近点。把 $z=x^{\ast }-\alpha \mathrm{\nabla }f(x^{\ast })$、$p=x^{\ast }$ 代入，得到固定点条件 $$x^{\ast }=P_C(x^{\ast }-\alpha \mathrm{\nabla }f(x^{\ast }))⟺\mathrm{\nabla }f(x^{\ast })\cdot (y-x^{\ast })\ge 0(\mathrm{\forall }y\in C).$$ 如果 $f$ 是凸的，切平面不等式进一步给 $f(y)\ge f(x^{\ast })$，故固定点是全局最优。这也解释了凸优化词条中边界最优点为何可以有非零梯度。若 $f$ 非凸，固定点只满足一阶必要条件，不能当作全局最优证书。

在多维中，投影不一定能逐坐标截断。例如两个权重必须非负且总和为一，构成集合 $C=\{(x,y):x,y\ge 0,x+y=1\}$。把暂定点 $z=(0.8,0.7)$ 的每个坐标分别截到 $[0,1]$ 仍是 $(0.8,0.7)$，总和为 1.5，根本不可行。令 $y=1-x$，在 $0\le x\le 1$ 上最小化 $$(x-0.8{)}^2+(1-x-0.7{)}^2=(x-0.8{)}^2+(x-0.3{)}^2.$$ 求导得 $4x-2.2=0$，故真正的欧氏投影是 $(0.55,0.45)$。它沿着法向量 $(1,1)$ 从暂定点回到总和为一的直线，而不是独立修剪两个坐标。一般约束集的投影可能本身就是一个需要求解的优化问题。

若希望得到每步下降的量化保证，可再假定梯度满足某个 $L>0$ 的 Lipschitz 条件，即 $\Vert \mathrm{\nabla }f(u)-\mathrm{\nabla }f(v)\Vert \le L\Vert u-v\Vert$。设一步投影后的位移为 $d=x_{k+1}-x_k$，投影不等式取 $y=x_k$ 给 $\mathrm{\nabla }f(x_k)\cdot d\le -\Vert d{\Vert }^2/{\alpha }_k$。光滑性给目标变化的上界，把这两个不等式接起来就是 $$\begin{array}{cc}f(x_{k+1})& \le f(x_k)+\mathrm{\nabla }f(x_k)\cdot d+\frac{L}{2}\Vert d{\Vert }^2\\ & \le f(x_k)-(\frac{1}{{\alpha }_k}-\frac{L}{2})\Vert d{\Vert }^2.\end{array}$$ 特别当 $0<{\alpha }_k\le 1/L$ 时，除非这一步没有移动，函数值会下降。这是函数值下降的条件；收敛到全局最优还要结合凸性、解的存在及迭代论证。

可复算的 Python 实现

代码处理一维闭区间；调用者提供导数函数，返回最后的可行点和各次迭代值。投影只读边界，不改写任何输入对象。

Python 3

def projected_gradient_interval(grad, left, right, start,
                                rate, steps):
    if left > right or rate <= 0 or steps < 0:
        raise ValueError("invalid interval, rate, or step count")
    project = lambda z: min(right, max(left, z))
    x = project(start)
    history = [x]
    for _ in range(steps):
        x = project(x - rate * grad(x))
        history.append(x)
    return x, history


if __name__ == "__main__":
    point, path = projected_gradient_interval(
        lambda x: 2 * (x - 3), 0, 1, 0.5, 0.1, 2
    )
    assert path == [0.5, 1.0, 1.0]
    assert point == 1.0

每一步只求一次导数和一次区间投影，故运行 $T$ 步用 $O(T)$ 时间、保存历史用 $O(T)$ 空间；若只留最终点，额外空间为常数。步长不能任意放大。例如 $f(x)=(x-\frac{1}{2}{)}^2$、$C=[0,1]$、$\alpha =2$ 时，从零出发会依次投影到一、零、一，永远在两端来回；真正最优点是 $1/2$。多维约束若投影本身难算，每一步的成本也可能比求梯度高，不能只数迭代次数。

参考资料

• MIT 15.084J 非线性规划讲义，含投影方法与约束优化。
• Stanford EE364b《Subgradient Methods》，第5—6节说明投影与投影次梯度法。
• Boyd、Vandenberghe《Convex Optimization》，第9章讨论光滑函数的下降估计与步长。