《最优化：建模、算法与理论》笔记|2.1范数，2.2导数

ainatipen

2.1范数

定义（范数）称一个从向量空间  到实数域 的非负函数  为范数（在度量空间中也被称为度量），如果它满足：
（1）正定性：对于所有的  ，有 ，且 当且仅当 ；
（2）齐次性：对于所有的  和 ，有 ；
（3）三角不等式：对于所有的 ，有 。

向量范数

1）最常用的向量范数为 （ ）范数 ：


为最常遇见的情形，分别记为 和 ，其中， .
而在不引起歧义的情况下，会省去  范数的角标，记为  .
对于  范数，有如下命题成立：
命题（Cauchy不等式）设 ，则有 成立，等号成立当且仅当 与 线性相关。
2）由正定矩阵A诱导的范数：

矩阵范数

1）由向量 范数推广得到的矩阵 范数：
当 时，矩阵 的 范数定义为 ，即  中所有元素的绝对值之和；
当 时，得到矩阵的Frobenius范数（简称为F范数），记为 ，其满足
F范数还具有正交不变性，即对于任意的正交矩阵 ，有 成立（根据F范数的定义得出）
2）由向量范数诱导而来的算子范数（矩阵范数的一种）：
先给出算子范数的相容性的定义：设  是  上的向量范数，  是 上的矩阵范数，且有

成立，则称  为与向量范数  相容的矩阵范数。但并非所有的矩阵范数都与给定的向量范数相容，只有满足该定义的矩阵范数才可以说与给定的向量范数相容。
然后给出算子范数的定义：
给定矩阵  ，及 维和 维空间的向量范数  和  ，则

是与向量范数  相容的矩阵范数，我们称该矩阵范数为由向量范数  诱导出的算子范数。
如果将  和  都取为相应向量空间的  范数，则可得到矩阵的 范数，如矩阵的 范数为

也就是该矩阵的最大奇异值.(因为 ，所以 )
3）核范数：
给定矩阵  ，其核范数定义为 ，其中 ， 为  的所有非零奇异值。我们常常通过限制矩阵的核范数（因为核范数能凸近似矩阵的秩）来保证矩阵的低秩性，矩阵的低秩性表明该矩阵的各行或各列存在相似性，因此易利用相似性来对缺失数据进行恢复。
矩阵内积

范数一般用来衡量矩阵模的大小，而内积一般用来表征两个矩阵（或其张成的空间）之间的夹角。
这里，我们只介绍一种常用的内积——Frobenius内积： 的矩阵  和  的Frobenius内积定义为

即两个矩阵逐分量相乘的和，当 时， 等于矩阵  的F范数的平方。
我们还有矩阵范数对应的Cauchy不等式，如下：
命题（矩阵范数的Cauchy不等式）设 ，则有 成立，其中，等号成立当且仅当  和  线性相关。
2.2导数

我们可以利用函数值和导数信息，来构造容易求解的且具有很好的逼近原问题效果的子问题，从而构造各种有效的算法。
多元可微函数

我们先给出梯度和Hessian矩阵的定义：
定义（梯度）给定函数  ，且  在点  的一个邻域内有意义，若存在向量 满足

其中，  是任意的向量范数，就称  在点  处可微（或Frechet可微）。此时， 称为  在点  处的梯度，记作  。如果对区域  上的每一个点  都有  存在，则称  在  上可微。
可知，
如果我们只关心对一部分变量的梯度，那么可以在 下加下标，如 表示当把  视为常数时，  关于  的梯度。
定义（Hessian矩阵）如果函数  在点  处的二阶偏导数 都存在，则

称为  在点  处的Hessian矩阵。
当  在区域  上的每个点  处都存在时，称  在  上二阶可微；当  在  上的每个点都存在且在  上连续时，则称  在  上二阶连续可微，此时，Hessian矩阵是一个对称矩阵。
然后给出如下形式的泰勒展开：
定理（多元函数的泰勒展开）设  是连续可微的， 为向量，那么

其中，  。进一步地，如果  是二阶连续可微的，则

其中，  。
最后，我们将介绍一种特殊的可微函数——梯度利普希茨(Lipschitz)连续的函数，该类函数在很多优化算法的收敛性证明中起着关键作用。
定义（梯度Lipschitz连续）给定可微函数  ，若存在 ，对任意的 （函数  的定义域）有 成立，则称  是梯度利普希茨(Lipschitz)连续的，  为利普希茨常数。有时也简记为梯度 -利普希茨连续或 -光滑。
梯度Lipschitz连续表明  的变化受  的变化的控制。满足梯度Lipschitz连续的函数具有很多很好的性质，如下面的二次上界：
引理（二次上界）设可微函数  的定义域 ，且为梯度Lipschitz连续的，则函数  有二次上界：

证明. 构造辅助函数 ，则有 成立，所以

该引理表明  可以被一个二次函数上界所控制，即要求  的增长速度不超过二次。
当对该引理中  的定义域的要求减弱为凸集时，该引理也成立，因为定义域是凸集可以保证 当 时是有定义的。
如果  是梯度Lipschitz连续的，且有一个全局极小点  ，那么我们可以利用二次上界来估计 的大小：
推论 设可微函数  的定义域为  ，且存在一个全局极小点  ，若  为梯度Lipschitz连续的，则对任意的  有 成立。
证明. 固定  ，对任意的  应用二次上界，得
那么我们有 成立，最后一步应用了二次函数的性质：当 时取到最小值。
向量值函数

当 是向量值函数时，我们可以定义它的Jacobi矩阵 ，它的第 行是分量 的梯度的转置，即

可以看出，梯度  的Jacobi矩阵就是  的Hessian矩阵。
矩阵变量函数

我们将多元函数梯度的定义加以推广，得到变量是矩阵的情形：
对于以  的矩阵  为自变量的函数  ，若存在矩阵  满足

其中，  是任意的矩阵范数，就称矩阵变量函数  在  Frechet可微，称  为  在Frechet可微意义下的梯度。
类似于向量情形，矩阵变量函数  的梯度可以用其偏导数表示为

但在实际的应用中，矩阵Frechet可微的定义和使用往往比较繁琐，因此，我们将介绍另一种定义，该定义实际上是方向导数的某种推广：
定义（Gateaux可微）设  为矩阵变量函数，如果存在矩阵  ，对任意方向 满足

则称  关于  是Gateaux可微的，称  为  在  处在Gateaux可微意义下的梯度。
（？）可以看出，若  是Frechet可微的，则  也是Gateaux可微的，且二者意义下的梯度相等；但这一命题反过来不一定成立。
自动微分

自动微分是使用计算机计算导数的算法。它有两种方式：前向模式和后向模式。
在前向模式中，我们依次计算每个中间变量的值和中间变量对其父变量的偏导数值，然后根据链式法则，可以求得每个中间变量对自变量的偏导数值，直到得到目标函数值和目标函数对自变量的偏导数值。可以看出，在该模式下，变量的求值和偏导的计算是同时进行的。
而后向模式则是先利用前向模式计算各个变量的值，再逆向计算目标函数对各个变量的偏导数值。
后向模式的梯度计算代价至多为函数值计算代价的5倍，但前向模式的计算代价可能多达函数值计算代价的n（n为自变量维数）倍，因此，后向模式在实际中更为流行。对于神经网络中的优化问题，其自动微分采用的是后向模式。