AI 与工程数学 / 系统课时

用投影梯度保持解始终可行

用投影梯度保持解始终可行

普通梯度下降只关心目标函数下降,更新一步后可能直接跑出约束集合。投影梯度法在每次梯度更新后增加一次“投影回可行域”的操作,使迭代点始终合法,尤其适合盒约束、球约束等投影计算简单的凸集合。

学习目标

  • 写出投影梯度法的一次完整迭代
  • 对盒约束和欧氏球约束计算投影
  • 区分未投影目标值下降与约束可行性之间的关系

梯度下降后为什么还要投影

考虑约束优化问题

min⁡x∈Cf(x),\min_{x\in C} f(x),

其中 CC 是可行集合。普通梯度下降先计算

yk=xk−αk∇f(xk).y_k=x_k-\alpha_k\nabla f(x_k).

即使 xk∈Cx_k\in C,新的 yky_k 也未必仍在 CC 中。投影梯度法因此再执行

xk+1=PC(yk),x_{k+1}=P_C(y_k),

其中 PC(y)P_C(y) 表示在集合 CC 中寻找距离 yy 最近的点。完整更新可以合写为

xk+1=PC(xk−αk∇f(xk)).x_{k+1}=P_C\left(x_k-\alpha_k\nabla f(x_k)\right).

投影梯度一次迭代

投影不是简单地“撤销非法更新”,而是在当前梯度方向与可行集合之间做一个最近点修正。只要初始点可行,并且每轮都完成投影,后续迭代点就始终位于 CC 中。

盒约束可以直接逐坐标裁剪

若约束为

li≤xi≤ui,l_i\le x_i\le u_i,

投影非常简单:每个坐标小于下界就拉回下界,大于上界就压回上界,其余保持不变。也就是

[PC(y)]i=min⁡{ui,max⁡{li,yi}}.[P_C(y)]_i=\min\{u_i,\max\{l_i,y_i\}\}.

考虑目标函数 f(x,y)=(x−3)2+(y+1)2f(x,y)=(x-3)^2+(y+1)^2,并要求 0≤x≤20\le x\le2、0≤y≤20\le y\le2。从 (0.5,1.5)(0.5,1.5) 出发,取步长 α=0.5\alpha=0.5,下面完成一次投影梯度更新。代码仅使用 Python 标准语法,可直接运行。

python
def objective(point):
    x, y = point
    return (x - 3.0) ** 2 + (y + 1.0) ** 2


def gradient(point):
    x, y = point
    return [2.0 * (x - 3.0), 2.0 * (y + 1.0)]


def project_box(point, lower, upper):
    # 盒约束的欧氏投影等价于逐坐标裁剪。
    return [
        min(hi, max(lo, value))
        for value, lo, hi in zip(point, lower, upper)
    ]


x = [0.5, 1.5]
alpha = 0.5
grad = gradient(x)
raw = [value - alpha * g for value, g in zip(x, grad)]
projected = project_box(raw, [0.0, 0.0], [2.0, 2.0])

raw_feasible = all(0.0 <= value <= 2.0 for value in raw)
projected_feasible = all(0.0 <= value <= 2.0 for value in projected)

print(f"before: {x}, f={objective(x):.2f}")
print(f"raw: {raw}, f={objective(raw):.2f}, feasible={raw_feasible}")
print(f"projected: {projected}, f={objective(projected):.2f}, feasible={projected_feasible}")

预期输出

text
before: [0.5, 1.5], f=12.50
raw: [3.0, -1.0], f=0.00, feasible=False
projected: [2.0, 0.0], f=2.00, feasible=True

这个例子刻意展示了一个容易误解的现象:未投影点 (3,−1)(3,-1) 的目标值是 00,甚至就是无约束最优点,但它不可行,所以不能作为约束问题的答案。投影后的 (2,0)(2,0) 虽然目标值变成 22,却满足约束,并且恰好是这个盒约束问题的最优解。

球约束的投影沿半径缩回

对于以原点为中心、半径为 RR 的欧氏球

C={x∣∥x∥2≤R},C=\{x\mid \|x\|_2\le R\},

若临时点已经位于球内,就无需修改;若位于球外,则沿着从原点指向该点的方向缩放到球面:

PC(y)={y,∥y∥2≤R,Ry∥y∥2,∥y∥2>R.P_C(y)=\begin{cases} y,&\|y\|_2\le R,\\ R\dfrac{y}{\|y\|_2},&\|y\|_2>R. \end{cases}

因此投影梯度法是否实用,很大程度上取决于 PCP_C 是否便宜。盒约束和简单球约束的投影都有闭式解;若每次投影本身都要再求一个昂贵优化问题,整体算法的优势就会明显减弱。

判断是否已经停在约束最优点

在无约束梯度下降中,常用 ∇f(x)=0\nabla f(x)=0 判断一阶驻点;有约束时,边界最优点的梯度通常并不为零。更合适的量是投影梯度映射

Gα(x)=1α[x−PC(x−α∇f(x))].G_\alpha(x)=\frac{1}{\alpha}\left[x-P_C\left(x-\alpha\nabla f(x)\right)\right].

如果 Gα(x)=0G_\alpha(x)=0,说明先沿负梯度走一步再投影,仍然回到原点 xx。这正表示在当前约束集合内已经没有可通过该一阶更新继续前进的方向。

以刚才的最优点 (2,0)(2,0) 为例,普通梯度步骤仍会尝试走向 (3,−1)(3,-1),但投影之后又回到 (2,0)(2,0)。所以不能因为边界点上的梯度非零就认为算法尚未收敛,应检查“梯度更新加投影”这一整个操作是否还会改变当前点。

投影梯度法的核心并不是让每个临时梯度步骤都可行,而是保证真正进入下一轮的 xk+1x_{k+1} 可行。对于投影容易计算的凸集合,这种“先按目标函数前进,再按几何约束纠正”的结构既简单,也能把目标优化与可行性维护清楚地分开。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用投影梯度保持解始终可行

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通