PGD

• 迫近梯度算法
• 非平滑函数的平滑优化，将一个非平滑函数，使用平滑函数袋贴

• proximal gradient descent 也可以说是 subgradient 的升级版，proximal 通过对原问题的拆分并利用 proximal mapping，能够解决 subgradient descent 无法解决的问题（如上面的一般化 lasso 问题）。

* PGD

• 目标函数前半部分为凸且连续可微，但后半部分为凸但不连续可微。因此，proximal算法就是用于求解目标函数形如
• $f(x)=g(x)+h(x)$
• 其中g(x)可微而h(x)不可微,形式无约束问题的下降算法。

* 直接使用次梯度，计算复杂度高

* Proximal Mapping

• 对于:

$f(x)=g(x)+h(x)$的目标函数

• 如果g(x)为连续可导的凸函数（导数为Lipschitz连续），而h(x)仅为凸函数，通过proximal mapping将函数映射为

$prox_t(x)=argmin_z \frac{1}{2t}||x-z||^2+h(z)$

转换为求prox函数的解

* 无约束问题：

$f(x)=g(x)+h(x)f(x)=g(x)+h(x)$

• 无约束优化的PGD是

$x^{(k)}=prox_{\mu_k,g}(x^{(k-1)}-\mu_k\triangledown f(x^{(k-1)}))$

* 证明

• 如果ff为可微的凸函数，那么我们可以采用梯度下降算法更新梯度

$x^{+}=x-t\triangledown f(x)=argmin_x f(x)$

• 对f(x)二阶泰勒展开，则梯度下降算法更新：

$x^{+}=argmin_x f(x) +\triangledown f(x)^T (z-x) +\frac{1}{2t}||z-x||_2^2$

• 对于 PGD算法，保持 $f(x)=g(x)+h(x)$中的h(x)不动，仅对g(x)泰勒展开

* PGD 算法的梯度更新

* 常见无约束优化,pgd算法

* $h(x)=0$

退化为，普通的梯度算法

$x^{(k)}=x^{(k-1)}-\mu_k \triangledown f(x^{(k-1)})$

* 梯度投影

• x有约束，则$prox_g(x)=P_C(x)$

$x^{(k)}=P_C(x^{(k-1)}-\mu_k \triangledown f(x^{(k-1)}))$

= $argmin_{x\in C}||u-x^{(k-1)}+\mu_k\triangledown f(x^{(k-1)})||_2^2$

* 迭代软阈值

• $h(x)=||x||_1$的时候，最小化问题变为无约束最小化

$min f(x)+||x||_1$

• 此时，PGD算法

$x^{(k)}=prox_{\mu_k, g}(x^{(k-1)}-\mu_k \triangledown f(x^{(k-1)}))$

* 例子