次梯度法是求解凸函数最优化(凸优化)问题的一种迭代法。次梯度法能够用于不可微的目标函数。当目标函数可微时,对于无约束问题次梯度法与梯度下降法具有同样的搜索方向。
虽然在实际的应用中,次梯度法比内点法和牛顿法慢得多,但是次梯度法可以直接应用于更广泛的问题,次梯度法只需要很少的存储需求。然而,通过将次梯度法与分解技术结合,有时能够开发出问题的简单分配算法。
基本次梯度算法
记
为定义在
上的凸函数。次梯度算法使用以下的迭代格式
![{\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/74b27669f0798ab15d71cd3a4a002fed80577801)
其中
表示函数
在
的次梯度. 如果
可微,他的次梯度就是梯度向量
,有时
不是函数
在
处的下降方向。因此采用一系列可能的
来追踪目标函数的极小值点,即
。
步长的选取
次梯度方法有许多可采用的步长。以下为5种能够保证收敛性的步长规则
- 恒定步长,
。
- 恒定间隔,
,得出
。
- 步长平方可加,但步长不可加,即步长满足
。
。
- 间隔不可加但间隔递减,即
,其中
。注意:上述步长是在算法执行前所确定的,不依赖于算法运行过程中产生的任何数据。这是与标准梯度下降法的显著区别。
收敛结果
对于恒定间隔的步长以及恒定步长,次梯度算法收敛到最优值的某个邻域,即
。基本次梯度算法的性能较差,因此一般的优化问题并不推荐使用。
有约束最优化
投影次梯度算法
次梯度法的一个扩展版本是投影次梯度法,该方法用于求解有约束最优化问题
- 最小化
![{\displaystyle f(x)\ \quad x\in {\mathcal {C}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87eea9469091b60e59c4c3e6c0fbb2ec022a76f1)
其中
为凸集。投影次梯度算方法的迭代公式为
![{\displaystyle x^{(k+1)}=P\left(x^{(k)}-\alpha _{k}g^{(k)}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/243d11f56cb22ca2899e56c85a507a75a33e3777)
其中
是在
上的投影,
是在点
处
的次梯度。
一般约束问题
次梯度法可扩展到求解不等式约束问题
- 最小化
![{\displaystyle f_{0}(x)\quad f_{i}(x)\leq 0,\quad i=1,\dots ,m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65f945c598ee5f576843dbab82efbcc665cd2e33)
其中
为凸函数。该算法与无约束优化问题具有相同的形式
![{\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/74b27669f0798ab15d71cd3a4a002fed80577801)
其中
是步长,
是目标函数或约束函数在
处的次梯度
![{\displaystyle g^{(k)}={\begin{cases}\partial f_{0}(x)&{\text{ if }}f_{i}(x)\leq 0\;\forall i=1\dots m\\\partial f_{j}(x)&{\text{ for some }}j{\text{ such that }}f_{j}(x)>0\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7717279e41b04388383e1cadddbf0c7aa13af9e)
其中
代表
的次微分。如果当前点为可行点,算法采用目标函数的次梯度,否则采用任一违反约束的函数的次微分。
参考资料
外部链接