最优化算法C++实现:Proximal gradient descent

背景

近似梯度法 (Proximal gradient method)是一种广义投影形式,用于解决不可微的凸优化问题。这样就可以使得很多问题能够用梯度下降法解出来。

内容

----_20221102150423
----_20221102150517
ps:零范数是所有非0元素数量 一范数是所有元素绝对值之和 二范数是所有元素平方之和的开方

公式中的二范数是矩阵二范数,可以看成形如AT*A 的形式,这里注意一下倒数第二行变到倒数第一行,它这个不是直接等于的,看我下面写的把最后一行那个二范数平方打开:
----_20221102154909

它们实际上不相等,但是,整个式子关心的是对z求最小值,其余的元素都看作常数,对常数加减不影响z取多少时整个式子最小!所以我们可以将配不上的最后一项直接改成g(x),这样就能得到二阶展开的式子。
将上面最后一行的式子用proxt(x)替换,我们可以得到一个迭代公式!用这个迭代公式就能不断迭代出解。
----_20221102164029

下图是一个标准的lasso例子,它的Prox Mapping如图所示:
----_20221107095219

根据最优化算法学习-Soft Thresholding这里的介绍,我们发现lasso 的Prox Mapping刚好等于soft-thresholding 算子!于是我们可以得到一个用soft-thresholding的迭代公式:
3bbb546568723b67de1b1abe4e1a511
不需要求矩阵的逆!

展示评论