哎，刚刚submit上paper比较心虚啊，无心学习，还是好好码码文字吧。

subgradient介绍

subgradient中文名叫次梯度，和梯度一样，完全可以多放梯度使用，至于为什么叫子梯度，是因为有一些凸函数是不可导的，没法用梯度，所以subgradient就在这里使用了。注意到，子梯度也是求解凸函数的，只是凸函数不是处处可导。

是一个凸函数，是一个凸集。
若是f在处可导，考虑一阶泰勒展开式：

能够得到的一个下届（f(x)是一个凸函数）
若是在处不可导，仍然，可以得到一个的下届

这个就叫做的子梯度，
很明显，在一个点会有不止一个次梯度，在点所有的次梯度集合叫做此微分
优化中的subgradient方法

我们可以看出，当是凸集并且在附近有界时，是非空的，并且是一个闭凸集。

次梯度性质

满足：
1）scaling：

2）addition：

3）point-wise maximum:并且是可微的，那么：

即所有该点函数值等于最大值的函数的梯度的凸包。
在非约束最优化问题中，要求解一个凸函数的最小值

很显然，若是f可导，那么我们只需要求解导数为0的点

当f不可导的时候，上述条件就可以一般化成

也即满足次梯度的定义

下面是次梯度法的一般方法：

1.选择有限的正的迭代步长
2.计算一个次梯度
3.更新
4.若是算法没有收敛，则返回第二步继续计算

次梯度方法性质：

1.简单通用性：就是说第二步中，任何一个次梯度都是可以的.
2.收敛性：只要选择的步长合适，总会收敛的
3.收敛慢：需要大量的迭代才能收敛
4.非单调收敛：不需要是下降方向，在这种情况下，不能使用线性搜索选择合适的
5.没有很好的停止准则

对于不同步长的序列的收敛结果

不妨设是t次迭代中的最优结果
1.步长和不可消时（Non-summable diminishing step size）：
并且
这种情况能够收敛到最优解：
2.Constant step size:

收敛到次优解：
3.Constant step length:
(i.e. )，
能够收敛到次优解
4.Polyak’s rule:
若是最优值可知则可以用这种方法。

不等式约束的凸二次优化问题

问题formulate

一个不等式约束的凸二次优化问题可以表示为：

注意到,而且当目标函数取得最优的时候，这里的等号是成立的，所以可以进行代替:

所以就可以将这个二次悠哈问题改写成一个非约束凸优化问题

问题求解

因为

是可微的,并且

函数是一个点最大值，所以其次微分可以写作，所有active function的梯度的convex combination

-th function
		0

所以次微分可以写作可以使用参数话的表示方法，设,所以就有

优化中的subgradient方法