Projected Gradient Descent
受限优化问题
- $C \subseteq R^d$：受限凸集
投影梯度下降：采用后处理的方式，将迭代位置拉回到约束条件内
使用一般下降算法进行位置更新，新位置$x_{t+1}^{‘}$可能 不再满足约束条件
为使新位置$x{t+1}^{‘}$符合受限集合，可以选择在$L_2$范数 下距离受限集合$C$最近的的点 $x{t+1}=\arg\min{x \in C} |x - x{t+1}^{‘}|$作为下步 真正迭代位置
线性约束
Projection Matrix
- 投影矩阵：矩阵$P \in R^{n*n}$，若满足$P^T = P, P^2 = P$
- 若$A \in R^{m*n}$为行满秩矩阵，则$A$的零空间为 $L_A = {x \in R^{n} | Ax = 0}$，对应正交空间为 $L_A^{\perp} = {A^T y | y \in R^m}$
对$\forall x \in R^n$进行正交分解
- $P_A = I - A^T (A A^T)^{-1} A$：$A$的投影矩阵
- 投影矩阵$P_A$可由点对线性约束的投影定义，利用拉格朗日 求解
证明
- 投影矩阵$P$对值应用多次线性变换和只应用一次结果相同， 保持像不变
Projection Operator
设$x^{k}$为当前迭代点，记$A{11}$、$A{12}$分别为紧、松 约束，即
记$M = [A_{1,1}^T, A_2^T]^T$，则$s \in L_M$时是可行方向
对负梯度$\nabla f(x^k)$，通过$M$的投影矩阵$P_M$将其投影 至$L_M$上即得可行下降方向$s^k = -P_M \nabla f(x^k)$
- $s^k \neq 0$：为$x^k$处可行下降方向
- $s^k = 0$：作如下讨论
投影方向为0
记$w = [u, v]^T = -(M M^T)^{-1}M \nabla f(x^k)$，则有
若$u \geq 0$，则$x^{k}$是KKT点
否则若$u$中有负分量，可设$u0 < 0$，记$\bar M$为$M$中 去除对应列矩阵，则$\bar s^k = -P{\bar M}\nabla f(x^k)$ 为$x^k$可行下降方向
先反证法证明$\bar s^k \neq 0$，若$\bar s^k = 0$
考虑到
- $\alpha_0$：$M$中$u_0$对应行
则有
与$M$行满秩条件矛盾，故$\bar s^k \neq 0$
证明$\bar s^k$为下降方向
证明$\bar s^k$方向可行（满足约束）
由$P{\bar M}$定义：$\bar M P{\bar M} = 0$，则
则只需证明$\alpha_0^T \bar s^k < 0$
考虑到$u_0 < 0$，则$\alpha_0^T \bar s^k < 0$
- 即此时有紧约束变为松约束
算法
- 初始化：初始点$x^0$、$k=0$、精度参数$\epsilon > 0$
构造$M = [A_{1,1}^T, A_2^T]^T$
- 若$M=0$（在可行域内），令$s^k = -\nabla f(x^k)$为 迭代方向
- 否则令$s^k = -P_M \nabla f(x^k)$为迭代方向
若$|s^k|_2^2 \geq \epsilon$
- 若$M$为空（无可下降方向），停止
- 若$M$非空、$u > 0$，停止
- 否则，构建$M = \bar M$继续
若$|s^k|_2^2 > \epsilon$，确定步长$\lambda_k$
显然只需保证$A_2 x_k + \lambda_k A_2 d_k \leq b_2$ 即可
若$A_2 d_k < 0$，则$\lambda_k$无约束，否则
- 即单纯型法中确定步长方法
得到新迭代点$x^{k+1} = x^k + \lambda_k s^k$、$k=k+1$