当前位置：文档之家 › SubGradient

SubGradient

  • 格式：pdf
  • 大小：813.19 KB
  • 文档页数：5

次梯度(SubGradient)
吴有光写于2014年2月20日，仅用于学术交流，请勿用于商业用途。

摘要：详细解释次导数和次梯度法
关键字：次导数，次微分，次导数法，凸函数
Abstract: A brief introduction of subgradient
Keywords: Subderivative, Subdifferential, Subgradient method, Convex Function
引言之引言：优化问题中寻找极值点时常有一句话“往负梯度方向走”，那当梯度不存在的时候，该如何走？答案是“往次梯度反方向走”。

一、引言
网上关于次梯度的资料很少，很多做数据分析、信号处理的同学并没有系统的学过凸优化，这里做一个简单介绍，希望能够对大家有用。

打开百度，大概能搜到的次梯度介绍是这一段（限于本文写作之时）
这个定义非常的抽象，我们唯一能够得到的信息就是次梯度大概是这样定义的。

设为在出的次梯度，则需满足
(1)
或者有另外的写法为
能够明显感觉的是：次梯度好像是一个小于等于梯度的东西。

这是国内从教材到课件都喜欢故弄玄虚、生搬硬套的结果。

下面我希望能有用稍微简单但又详细的过程来介绍一下次梯度这个奇怪的东西。

二、次导数与次微分
先回忆一下导数的定义。

设函数，要定义它的导数，可以这么来做：在任意一点，有
这里和分别表示从的左边和右边来逼近它。

我们知道，如果，即左右极限存在且相等，则称为在处
的导数，即
但函数往往并不是那么的“好”。

如下图的函数，其在处是没有导数的。

函数如图1中的蓝线所示。

此函数在处，左右极限不相
等。

图1 次导数示意图
回顾一下函数导数的意义，导数值表示函数在某点的切线斜率。

由于函数
的凸性，其实在处我们可以做很多条切线，如图中红色线为其中的一条。

根据前述的计算，我们知道这些切线的斜率满足。

上面定义的切线好像跟我们以前的定义既相似又不同（相同点：与原函数都只有一个点重合；不同点：在某点，有很多条切线），但很有用，所以称之为次导数。

另外，我们将斜率的两个边界值也包含进来，认为次导数为中
的任意一个值。

我们重新整理如定义1所述。

定义1（次导数）对于凸函数在点的次导数定义为
(2)
次导数是针对凸函数中的不可导点定义，那么对于可导点呢？可导点的次导数当然就是导数本身啦。

推论1（次导数）函数在可导点的导数即为次导数。

次导数显然取值是一个区间，于是将此区间定义为次微分。

定义2（次微分）所有次导数的集合称为函数在处的次微分，
记为。

同样道理，对于可导点，次微分就不是一个区间，而只是一个值了。

推论2（次微分）函数在可导点的次微分为单元素集合。

三、次导数和次微分的性质
说明1：次导数是考虑了不可导点的广义导数，在可导点的次导数退化为导数。

说明2：次导数只针对凸函数，非凸函数则式(2)无法满足。

根据前面的分析，可以总结次导数和次微分的性质如下[2]：
1）函数在处可导，当且仅当次微分只由一个点组成，这个点
就是函数在的导数。

2）点是凸函数的最小值点，当且仅当次微分中包含零。

也就是说，在上
面的图中，我们可以作一条水平的“次切线”。

这个性质是“可导函数在极小值的导数是零”的事实的推广。

3）次微分为凸的紧集，一般为单元素集合或者闭区间。

四、次梯度及其性质
次梯度是次导数在高维函数上的推广，虽然只是简单的增加维数，但情况变得稍微复杂。

当学习了次导数和次微分之后，我们再回头来看文章一开始那个对次梯度的
定义（见式(1)），好像理解了一点。

下面做更为详细的介绍。

定义3（次梯度）如果是一个实变量凸函数，定义域为上的
凸集，如果对于所有内的，都有：
(3)
则该空间内的向量称为函数在点的次梯度。

定义4（次微分）所有次梯度的集合称为次微分，用表示。

结合前面一维变量的情况，对于次梯度的理解应该很简单，这里不再啰嗦。

性质1次微分非空，且为凸紧集。

可以类比一维变量情况来理解，一维时，因为为凸函数，所以定义域
为凸集（连续区间），即不会出现中间断裂。

又因为函数为凸，所以必有左极限小于等于右极限，因而次微分必然为一个连续闭区间，这就是最简单的凸紧集的例子。

详细证明这里不再给出。

性质2对于有
上式中第一个等式左边表示函数沿方向的方向导数，第二个等式右边
表示方向导数等于方向与次微分内积最大值。

性质3若，且均为凸函数，则下述
次微分关系成立
这条性质说明凸函数的线性组合之次微分为原各凸函数次微分之组合。

性质4若，其中为矩阵，则
五、次梯度法
优化中的次梯度法将会解决梯度法中遇到不可导点的问题。

在如何找极值点问题时，做法是：在可导点，就按梯度反方向走，在不可导点，就按次梯度的反方向走。

总结一句话：总是按次梯度的反方向走。

次梯度法的迭代算法必然为
因为在不可导点的次梯度有多个值，所以极值的计算为
上面迭代中的步长可以取定值，也可以根据当前步骤的参数动态调整，这与一
般梯度法差别不大，这里不再叙述。

最最后说一句：次梯度迭代法由于收敛非常之慢，实际计算中很少用它。

参考文献
[1] Subderivative, Online available: /wiki/Subderivative.
[2]次导数, Online available: /wiki/%E6%AC%A1%E5%AF%BC%E6%95%B0
[3] Subgradient_method, Online available: /wiki/Subgradient_method
[4]次梯度法, Online available: /wiki/%E6%AC%A1%E6%A2%AF%E5%BA%A6%E6%B3%95。

合集下载

《松弛算法》PPT课件

《松弛算法》PPT课件


Con(Q {x Rn | Ax b}) Con(Con(Q) {x Rn | Ax b})
Con(Q) {x Rn | Ax b}
再由定理7.2.2: zIP
min cT x
xCon(Q{xRn |Axb})
zLD
min cT x
xCon(Q){xRn |Axb}
若对任何c有 zIP zLD
,其凸
包定义Co为n(:Q) {P iPi | i R1, i 1}
i
i
显然Con(Q)为凸集.
定理7.2.2 若拉格朗日对偶问题的目标值有限,
则
zLD min{cT x | Ax b, x Con(Q)}
其中：Q {x | Bx d, x Zn}
证明:
zLR
()
min(cT
17 17
7
, 2 2
( 4 , 1 )T 1
53 6 5 2 53 6 5 2 17 17
9
综合有:
zLR
(
)
29
28 8
0 1
9
1
9
zLD
1 zLR (9)
28 1 9
例7.2.2(继7.2.1)
例7.2.1中
Q {(2, 2)T , (2,3)T , (2, 4)T , (3,1)T , (3, 2)T , (3,3)T , (3, 4)T , (4, 0)T }
,则问题得
例7.2.1
假设整数规划问题IP
zIP min{7x1 2x2}
x1 2x2 4
5x1 x2 20
s.t.
2x1 2x2 7 x1 2
x2 4
x
Z
2
7.2.2
Convex Analysis and Nonlinear Optimization 第三章习题解答

Convex Analysis and Nonlinear Optimization 第三章习题解答


¯ ¯ ) = { ∥x i .e . ∂ f ( x ¯∥ } x
I can’t do it at this moment. 9.Proof 10.proof note: I think this function should be defined on the cone Rn ≥ ∀φ ∈ ∂ < µ, [.] > (0) < φ, y − 0 >≤< µ, y > − < µ, 0 >, ∀ y ∈ E < µ − φ, y >≥ 0. by the Schur-convexity property, we have y ∈ conv (Pn µ)
(iii) The only thing we should deduce is that: ¯ ⊂ lin q, which is obvious from (i) x lin p ⊂ lin q ∀d ∈ l i n p
t ↓0 ¯ + t d )− p ( x ¯) p (x − q (d ) = − lim t t ↓0
¯ +t d ∥−∥x ¯∥ ¯ , d ) = lim ∥x < φ, d >≤ f (x t t ↓0 ¯ ,d >+t 2 <d ,d > 2t <x ¯ x = lim t (∥x ¯ +t d ∥+∥x ¯ ∥) =< ∥x ¯∥ , d t ↓0
>
∀d ∈ E
so φ = (2)
¯ x ¯∥ ∥x
(b) To deduce convex, we should consider the following cases: (1) x and y are both nonnegitive, (2) otherwise {d ≤ 0}, x = 0 ∂ f (x ) = {0}, x >0 , x <0 (c)
l1范数的次微分

l1范数的次微分

l1范数的次微分介绍在数学中，l1范数（也称为L1正则化）是一种常用的正则化方法，用于在优化问题中增加稀疏性。

l1范数则是指向量中所有元素的绝对值之和。

l1范数的次微分，也称为subgradient，是对l1范数的变化率的描述。

在本文中，我们将详细讨论l1范数的次微分及其应用。

l1范数介绍l1范数定义如下：||x||1=∑|x i|i其中x是向量，x i是向量中的元素。

l1范数有着很多优良的性质，其中最重要的就是能够产生稀疏解。

通过最小化l1范数的优化问题，可以促使向量中的一些元素变为零，从而产生稀疏向量。

l1范数的次微分l1范数的次微分，也称为subgradient，是指定函数在某一点的切线集合。

对于l1范数而言，它的次微分定义如下：∂||x||1={v|v=sgn(x),x≠0}其中sgn(x)是元素级符号函数，把向量中的非零元素替换为它们的符号。

l1范数的次微分的作用是描述了l1范数在不同点处的变化率，对于在优化问题中使用l1范数作为正则化项的情况下，次微分可以帮助我们找到梯度的一个替代来进行优化。

l1范数正则化的应用l1范数正则化在机器学习和统计学中有着广泛的应用，以下是一些常见的应用场景：特征选择特征选择是机器学习和统计学中的一个重要问题，其目标是从原始特征中选择出具有较高预测能力的特征。

l1范数正则化可以通过将某些特征的系数变为零来实现特征选择。

通过优化问题中的l1范数正则化项，可以鼓励模型选择更少的特征，从而降低了模型的复杂性，并且能够更好地处理高维数据。

压缩感知压缩感知是一种信号处理技术，其目标是通过在相对较少的测量下恢复原始信号。

l1范数正则化在压缩感知中起着重要作用。

通过在优化问题中使用l1范数正则化项，可以促使生成的稀疏解，从而实现高效的信号恢复。

线性回归在线性回归中，l1范数正则化也被称为LASSO回归。

LASSO回归能够使得一些系数变为零，因此可以用于变量选择和模型压缩。

从-sgd-到-adam--深度学习优化算法概览(一)

从-sgd-到-adam--深度学习优化算法概览(一)

从SGD 到Adam ——深度学习优化算法概览(一)楔子前些日在写计算数学课的期末读书报告，我选择的主题是「分析深度学习中的各个优化算法」。

在此前的工作中，自己通常就是无脑「Adam 大法好」，而对算法本身的内涵不知所以然。

一直希望能抽时间系统的过一遍优化算法的发展历程，直观了解各个算法的长处和短处。

这次正好借着作业的机会，补一补课。

本文主要借鉴了@Juliuszh 的文章[1]思路，使用一个general 的框架来描述各个梯度下降变种算法。

实际上，本文可以视作对[1]的重述，在此基础上，对原文描述不够详尽的部分做了一定补充，并修正了其中许多错误的表述和公式。

另一主要参考文章是Sebastian Ruder 的综述[2]。

该文十分有名，大概是深度学习优化算法综述中质量最好的一篇了。

建议大家可以直接阅读原文。

本文许多结论和插图引自该综述。

对优化算法进行分析和比较的文章已有太多，本文实在只能算得上是重复造轮，旨在个人学习和总结。

希望对优化算法有深入了解的同学可以直接查阅文末的参考文献。

引言最优化问题是计算数学中最为重要的研究方向之一。

而在深度学习领域，优化算法的选择也是一个模型的重中之重。

即使在数据集和模型架构完全相同的情况下，采用不同的优化算法，也很可能导致截然不同的训练效果。

梯度下降是目前神经网络中使用最为广泛的优化算法之一。

为了弥补朴素梯度下降的种种缺陷，研究者们发明了一系列变种算法，从最初的SGD (随机梯度下降) 逐步演进到NAdam。

然而，许多学术界最为前沿的文章中，都并没有一味使用Adam/NAdam 等公认“好用”的自适应算法，很多甚至还选择了最为初级的SGD 或者SGD with Momentum 等。

本文旨在梳理深度学习优化算法的发展历程，并在一个更加概括的框架之下，对优化算法做出分析和对比。

Gradient Descent梯度下降是指，在给定待优化的模型参数和目标函数后，算法通过沿梯度的相反方向更新来最小化。