投影与既约梯度法

Views: --

约束条件挡住了普通负梯度。投影法把负梯度投到可行切空间；既约梯度法先消去一部分变量，再在自由变量空间里做下降。两者表达不同，几何本质相同。

等式约束上的投影梯度

考虑

min⁡f(x),Ax=b,\min f(x),\qquad Ax=b,

假设 AA 满行秩。可行方向满足 Ad=0Ad=0，即位于 AA 的零空间。到零空间的正交投影矩阵为

P=I−AT(AAT)−1A.P=I-A^T(AA^T)^{-1}A.

取

d=−P∇f(x).d=-P\nabla f(x).

由于 AP=0AP=0，方向可行；又因 PP 对称幂等，

∇fTd=−∇fTP∇f=−∥P∇f∥2≤0.\nabla f^Td=-\nabla f^TP\nabla f=-\lVert P\nabla f\rVert^2\le0.

若投影梯度为零，就有 ∇f+ATλ=0\nabla f+A^T\lambda=0，即等式约束 KKT 条件。

消元与既约梯度

把 A=(B,N)A=(B,N)，其中 BB 是可逆 m×mm\times m 基矩阵：

xB=B−1b−B−1NxN.x_B=B^{-1}b-B^{-1}Nx_N.

代入目标得到只依赖 xNx_N 的函数 F(xN)F(x_N)。链式法则给

rN=∇F(xN)=∇Nf−(B−1N)T∇Bf.r_N=\nabla F(x_N) =\nabla_Nf-(B^{-1}N)^T\nabla_Bf.

这就是既约梯度。取

dN=−rN,dB=−B−1NdN,d_N=-r_N,\qquad d_B=-B^{-1}Nd_N,

便有 Ad=0Ad=0 且

∇fTd=−∥rN∥2.\nabla f^Td=-\lVert r_N\rVert^2.

因此 rN≠0r_N\ne0 时得到严格下降可行方向，rN=0r_N=0 时达到等式约束 KKT 点。

加上非负边界

若还有 x≥0x\ge0，Wolfe 既约梯度法不直接取 dN=−rNd_N=-r_N，而是逐分量定义

dN,j={−xN,jrj,rj>0,−rj,rj≤0.d_{N,j}= \begin{cases} -x_{N,j}r_j,&r_j>0,\\ -r_j,&r_j\le0. \end{cases}

这个分段不是装饰。若 xN,j=0x_{N,j}=0：

  • rj>0r_j>0 时取 dN,j=0d_{N,j}=0，不会沿负方向越出边界；
  • rj≤0r_j\le0 时取 dN,j=−rj≥0d_{N,j}=-r_j\ge0，只会进入可行域内部。

若变量在内部，第一支用 xN,jx_{N,j} 缩放步幅。再令

dB=−B−1NdN,d_B=-B^{-1}Nd_N,

就同时保持线性等式的一阶可行性。它仍然是下降方向，因为

rNTdN=−∑rj>0xN,jrj2−∑rj≤0rj2<0r_N^Td_N =-\sum_{r_j>0}x_{N,j}r_j^2 -\sum_{r_j\le0}r_j^2<0

（只要允许移动的既约梯度不全为零）。

沿方向的最大可行步长由将要降到零的变量决定：

αˉ=min⁡i:di<0−xidi.\bar\alpha=\min_{i:d_i<0}\frac{-x_i}{d_i}.

若某个变量碰到边界，可更新基或活动集，再继续迭代。

计算时不要显式求逆

B−1NB^{-1}N 与 B−1bB^{-1}b 应通过解线性方程 BY=NBY=N、Bu=bBu=b 获得。显式求逆更慢、更不稳定。基更新时还可复用分解，这与单纯形法的数值实现相通。

一个结构化理解

完整梯度包含“想往哪里走”；约束梯度张成“不能离开的法向空间”。投影梯度去掉法向分量，既约梯度则换一组独立坐标描述切向分量。二者为零都意味着完整梯度完全可由约束法向量组合。

考试要点

  • 会推导 rNr_N，特别注意转置：(B−1N)T∇Bf(B^{-1}N)^T\nabla_Bf。
  • dB=−B−1NdNd_B=-B^{-1}Nd_N 用于保证 Ad=0Ad=0。
  • 无边界时下降性化成 −∥rN∥2-\lVert r_N\rVert^2；Wolfe 边界方向要按 rjr_j 符号分段。
  • 有非负约束时，既约梯度为零以外还要检查边界方向和乘子符号。

评论