原文链接： 次梯度方法
首发于 凸优化学习笔记 写文章1.问题引入
2.次梯度的定义
3.次梯度优化条件（Subgradient optimality condition）
4.次梯度迭代算法
5.次梯度方法求解lasso问题
对于可导的凸函数，我们通常使用常规的梯度下降法处理，但当目标函数不可导（在某些点上导数不存在）时，我们就没法使用常规的梯度下降法处理。于是引入次梯度（Subgradient）用于解决此类目标函数并不总是处处可导的问题。
次梯度方法的优势是比传统方法能够处理的问题范围更大，不足之处就是算法收敛速度慢。2.1 回顾
对于凸函数 ，如果它可导，那么对 ，都有：
此即凸函数的一阶条件，简单讲就是对于凸函数，其切线总是在函数的下方。具体可参考 【凸优化笔记2】-第1.2节。2.2 次梯度定义
类比凸函数的一阶条件，给定函数 ，对 ，如果满足：
则称 是函数 在点 处的次梯度（Subgradient）。
无论是凸函数还是非凸函数（非凸函数包括凹函数和非凸也非凹的函数），对所有满足上述条件的 都称为 在 处的次梯度，因此次梯度不一定唯一，也可能不存在。 从不等式条件中也可以看出次梯度是在函数凸的区域上加以定义的。将 在 处所有次梯度构成的集合称为 在 处的次微分（Subdifferential），记作 。
凸函数总有次梯度，非凸函数即使可微也不一定有次梯度。凸函数的次微分总是非空，凹函数的次微分是空集。
对于凸函数，我们总能找到一个 ，使得上述对次梯度定义的条件成立。例如，如果凸函数在 处可导，取 即可；如果凸函数在 处不可导，取 为在该点处的左导数或者右导数都可以，过该点以 为斜率的“切线”总在函数的下方。因而凸函数总有次梯度，次微分总是非空。 对于非凸函数，在凸的区域 有可能找到这样的“切线”，而在凹的区域总是找不到这样的“切线”，使其位于函数的下方，因而非凸函数的次梯度不一定存在。在凹的区域更不可能存在次梯度也就不存在次微分。 对于优化问题，我们通常只考虑目标函数是凸函数的情况。2.3 次梯度计算
设函数 在点 处不一定可导，以一维情况为例，按高等数学中我们对导数的定义可以求出:
在 处的左导数：
在 处的右导数：
凸函数 的次微分等于闭区间 ， 中任何一个取值都是次梯度。
如果凸函数 在点 处是可导的，即 ，次微分中只有一个元素，此时次梯度就是梯度，即 就等于 ； 如果凸函数 在点 处是不可导的，即 ，此时次梯度是次微分中的任意一个取值，它是不唯一的。 例如 ，则 ，其中 为符号函数， 表示任意一个元素。点 是函数 （无论是否是凸的）的最优解，当且仅当次微分中包含 。即：
证明：我们可以把 代入到 2.2 节对次梯度定义的式子中，即，对于 ,都有 。
类似于梯度下降算法，只是将梯度更换成了次梯度，初始化 ，重复：
其中 为步长， ，即从次微分中随机选择一个次梯度作为梯度。
从这个算法中可以看出次梯度算法并不总是下降的，这也就解释了为什么将其称作次梯度算法而非次梯度下降算法。为了使更新的参数呈递减的趋势，对第 次的参数更新同步使用如下策略：
即在第 次更新参数时，如果使用次梯度算法计算得到的 能够使 更小，则 ，否则 。
次梯度算法使用如下步长选择准则：
i. 固定的步长。 ;
ii. 衰减的步长。 满足如下条件:
例如，取 ，则 （为 p 级数且 p>1）收敛且 （为调和级数，即 p=1）发散，因而是满足条件的。 【关于 p 级数的敛散性可自行参考高等数学中级数敛散性相关内容】。
衰减的步长能够保证步长在逐步减小趋近于 的同时变化的幅度不会太大，次梯度算法不像梯度下降算法那样可以自适应地计算当前次的步长，其步长是预先指定的。
只要选择的步长合适，算法总会收敛，只是算法收敛速度比较慢。
lasso问题：
由次梯度优化条件， 是这个目标函数在最优解上次微分的一个元素，即：
根据次梯度的计算方式，得到 的第 个分量满足：
为简单起见，我们假设 ， 为单位矩阵，则由 (1) 式有：
综合 (2) 和 (3)，有以下推论：
i. 当 时， ， ， ;
ii. 当 时， ， ， ;
iii. 当 时， ， ;
即当 时最优解 ，其每一个分量满足：
称为软阈值（Soft-thresholding ）公式， 被称为阈值，可以参考 【凸优化笔记4】-4.3软阈值算子。
参考文献：
CMU凸优化课件-次梯度
【机器学习】次梯度（subgradient）方法
编辑于 01-19 凸优化 最优化 机器学习 赞同 29 添加评论 分享 喜欢 收藏 赞同 29 分享