优化中的subgradient步骤
优化中的subgradient方法
f(x)≥f(x′)+∇(f(x′)T(x−x′),∀x∈X
能够得到f(x) 的一个下届(f(x)是一个凸函数)
若是f(x) 在x′ 处不可导,仍然,可以得到一个f(x) 的下届
f(x)≥f(x′)+gT(x−x′),∀x∈X
这个g 就叫做f(x) 的子梯度,g∈Rn
很明显,在一个店会有不止一个次梯度,在点x 所有f(x) 的次梯度集合叫做此微分∂f(x)
我们可以看出,当f(x) 是凸集并且在x 附近有界时,∂f(x) 是非空的,并且∂f(x) 是一个闭凸集。
∂f(x)={g}⇔f(x)可微并且g=∇f(x)
满足:
1)scaling:∂(αf(x))=α∂f(x),if α>0
2)addition:∂(f1(x)+f2(x))=∂fz(x)+∂f2(x)
3)point-wise maximum:f(x)=maxi=1,...,mfi(x) 并且fi(x) 是可微的,那么:
∂f(x)=Co{∇fi(x)∣fi(x)=f(x)}
即所有该点函数值等于最大值的函数的梯度的凸包。
在非约束最优化问题中,要求解一个凸函数f:Rn→R 的最小值
x∗∈argminx∈Rnf(x)
很显然,若是f可导,那么我们只需要求解导数为0的点
f(x∗=minx∈Rn⇔0=∇f(x∗)
当f不可导的时候,上述条件就可以一般化成
f(x∗)=minx∈Rn⇔0∈∇f(x∗)
也即0 满足次梯度的定义
f(x)≥f(x′)+0T(x−x′),∀x∈Rn
下面是次梯度法的一般方法:
1.t=1 选择有限的正的迭代步长{αt}∞t=1
2.计算一个次梯度g∈∂f(xt)
3.更新xt+1=xt−αtgt
4.若是算法没有收敛,则t=t+1 返回第二步继续计算
性质:
1.简单通用性:就是说第二步中,∂f(xt) 任何一个次梯度都是可以的.
2.收敛性:只要选择的步长合适,总会收敛的
3.收敛慢:需要大量的迭代才能收敛
4.非单调收敛:−gt 不需要是下降方向,在这种情况下,不能使用线性搜索选择合适的αt
5.没有很好的停止准则
哎,刚刚submit上paper比较心虚啊,无心学习,还是好好码码文字吧。
subgradient中文名叫次梯度,和梯度一样,完全可以多放梯度使用,至于为什么叫子梯度,是因为有一些凸函数是不可导的,没法用梯度,所以subgradient就在这里使用了。注意到,子梯度也是求解凸函数的,只是凸函数不是处处可导。
若是f在
能够得到
若是
这个
很明显,在一个店会有不止一个次梯度,在点
我们可以看出,当
满足:
1)scaling:
2)addition:
3)point-wise maximum:
即所有该点函数值等于最大值的函数的梯度的凸包。
在非约束最优化问题中,要求解一个凸函数
很显然,若是f可导,那么我们只需要求解导数为0的点
当f不可导的时候,上述条件就可以一般化成
也即
下面是次梯度法的一般方法:
1.
2.计算一个次梯度
3.更新
4.若是算法没有收敛,则
性质:
1.简单通用性:就是说第二步中,
2.收敛性:只要选择的步长合适,总会收敛的
3.收敛慢:需要大量的迭代才能收敛
4.非单调收敛:
5.没有很好的停止准则
对于不同步长的序列的收敛结果
不妨设
1.步长和不可消时(Non-summable diminishing step size):
这种情况能够收敛到最优解:
2.Constant step size:
收敛到次优解:
3.Constant step length:
能够收敛到次优解
4.Polyak’s rule:
若是最优值