次梯度法

次梯度法是求解凸函数最优化（凸优化）问题的一种迭代法。次梯度法能够用于不可微的目标函数。当目标函数可微时，对于无约束问题次梯度法与梯度下降法具有同样的搜索方向。

虽然在实际的应用中，次梯度法比内点法和牛顿法慢得多，但是次梯度法可以直接应用于更广泛的问题，次梯度法只需要很少的存储需求。然而，通过将次梯度法与分解技术结合，有时能够开发出问题的简单分配算法。

记${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$为定义在${\displaystyle \mathbb {R} ^{n}}$上的凸函数。次梯度算法使用以下的迭代格式

${\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }$

其中${\displaystyle g^{(k)}}$表示函数${\displaystyle f\ }$在${\displaystyle x^{(k)}\ }$的次梯度. 如果 ${\displaystyle f\ }$可微，他的次梯度就是梯度向量${\displaystyle \nabla f}$ ，有时${\displaystyle -g^{(k)}}$不是函数${\displaystyle f\ }$在${\displaystyle x^{(k)}}$处的下降方向。因此采用一系列可能的${\displaystyle f_{\rm {best}}\ }$来追踪目标函数的极小值点，即

${\displaystyle f_{\rm {best}}^{(k)}=\min\{f_{\rm {best}}^{(k-1)},f(x^{(k)})\}}$。

次梯度方法有许多可采用的步长。以下为5种能够保证收敛性的步长规则

• 恒定步长，${\displaystyle \alpha _{k}=\alpha }$。
• 恒定间隔，${\displaystyle \alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2}}$，得出${\displaystyle \lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma }$。
• 步长平方可加，但步长不可加，即步长满足

${\displaystyle \alpha _{k}\geq 0,\qquad \sum _{k=1}^{\infty }\alpha _{k}^{2}<\infty ,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty }$。

• 步长不可加但步长递减，即步长满足

${\displaystyle \alpha _{k}\geq 0,\qquad \lim _{k\to \infty }\alpha _{k}=0,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty }$。

• 间隔不可加但间隔递减，即${\displaystyle \alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2}}$，其中

${\displaystyle \gamma _{k}\geq 0,\qquad \lim _{k\to \infty }\gamma _{k}=0,\qquad \sum _{k=1}^{\infty }\gamma _{k}=\infty }$。注意：上述步长是在算法执行前所确定的，不依赖于算法运行过程中产生的任何数据。这是与标准梯度下降法的显著区别。

对于恒定间隔的步长以及恒定步长，次梯度算法收敛到最优值的某个邻域，即

${\displaystyle \lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon }$。基本次梯度算法的性能较差，因此一般的优化问题并不推荐使用。

次梯度法的一个扩展版本是投影次梯度法，该方法用于求解有约束最优化问题

最小化${\displaystyle f(x)\ \quad x\in {\mathcal {C}}}$

其中${\displaystyle {\mathcal {C}}}$为凸集。投影次梯度算方法的迭代公式为

${\displaystyle x^{(k+1)}=P\left(x^{(k)}-\alpha _{k}g^{(k)}\right)}$

其中${\displaystyle P}$是在${\displaystyle {\mathcal {C}}}$上的投影，${\displaystyle g^{(k)}}$是在点${\displaystyle x^{(k)}}$处${\displaystyle f\ }$的次梯度。

次梯度法可扩展到求解不等式约束问题

最小化${\displaystyle f_{0}(x)\quad f_{i}(x)\leq 0,\quad i=1,\dots ,m}$

其中${\displaystyle f_{i}}$为凸函数。该算法与无约束优化问题具有相同的形式

${\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }$

其中${\displaystyle \alpha _{k}>0}$是步长，${\displaystyle g^{(k)}}$是目标函数或约束函数在${\displaystyle x}$处的次梯度

${\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}}}$

其中${\displaystyle \partial f}$代表${\displaystyle f\ }$的次微分。如果当前点为可行点，算法采用目标函数的次梯度，否则采用任一违反约束的函数的次微分。

• Bertsekas, Dimitri P. Nonlinear Programming. Cambridge, MA.: Athena Scientific. 1999. ISBN 1-886529-00-0. 

• Shor, Naum Z. Minimization Methods for Non-differentiable Functions. Springer-Verlag. 1985. ISBN 0-387-12763-1. 

• EE364a （页面存档备份，存于互联网档案馆） and EE364b （页面存档备份，存于互联网档案馆）, a Stanford course homepage