次梯度方法
次梯度方法(subgradient method)是传统的梯度下降方法的拓展，用来处理不可导的凸函数。它的优势是比传统方法处理问题范围大，劣势是算法收敛速度慢。但是，由于它对不可导函数有很好的处理方法，所以学习它还是很有必要的。
次梯度（subgradient）
1.定义
所谓次梯度，定义是这样的：
ps.花括号不知道为什么打不出来，，用中括号代替吧。
用图片表示，即为
也就是，在(x_0)处所有的支撑超平面的超平面的法向量(g^T)的转置(g)构成的集合。即(g in partial f)。
一维次梯度称为次导数，通过求函数在点的每一分量的次导数可以求出函数在该点的次梯度。
可以证明，在点(x_0)的次导数的集合是一个非空闭区间([a,b])，其中a和b是单侧极限，(a = lim limits_{x o x_0^-} {{f(x) - f(x_0)} over {x - x_0}},b = lim limits_{x o x_0^+} {{f(x) - f(x_0)} over {x - x_0}}) ，它们一定存在，且满足(a≤b)。所有次导数的集合([a,b])称为函数(f)在(x_0)的次导数。
举例：(y=|x|)在(x=0)的次梯度为([-1,1])
注： 如果(f)可导，那么它的次梯度等于它的梯度。如果不可导，在最优点处，(0 in partial f)
2. 性质
- 数乘不变性。(forall alpha ge 0,partial (alpha f)(x)=alpha partial f(x))
- 加法不变性。(f=f_1+ldots+f_m,partial f(x)=partial f_1(x)+ldots+partial f_m(x))
- 仿射特性。如果(f)是凸函数，那么(partial f(Ax+b)=A^T partial f(Ax+b))
3. 扩展
对于一个凸优化问题，
对偶问题为
那么，由全局扰动不等式，我们有
其中，假设Slater条件成立，且在(x=hat x,y=hat y)处满足强对偶性。
从上式可以看出，(-（lambda^ * ,v^ * ）in partial f(hat x,hat y))
也就是说(（lambda^ * ,v^ * ）^T)是((hat x,hat y))处的一个支持超平面的法线。
次梯度方法
首先，我们想到的方法是推广一下梯度下降法。
其中，(g^{(k)} in partial f(x^{(k)}))
然而，(-g^{(k)})可能不再是下降方向。所以常用的方式是一直保留最小的函数值，直到结果收敛。
注：步长选择和收敛性分析在这里不再赘述。（回头有精力再写）
应用（duality+subgradient method）
用法1
对于凸优化问题
对偶问题为
其中，(g(lambda)=inf limits_x L(x,lambda)=f_0(x^ * (lambda))+sum limits_{i=1}^{m} lambda_i f_i(x^ * (lambda)))
假设Slater条件成立，那么我们可以通过解决对偶问题求得原问题的解。
那么，使用次梯度方法时，需要使得
也就是，
用法2
对比原来的$
abla L(x,lambda ^ * ) = 0 $
这里经常用的是 $0 in
abla L(x,lambda ^ * ) $