Projected Gradient Descent

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$