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

ainatipen · 发表于 2022-5-25 08:56

2.1范数

定义（范数）称一个从向量空间  到实数域 $\mathbb {R}$ 的非负函数  为范数（在度量空间中也被称为度量），如果它满足：
（1）正定性：对于所有的  ，有 $\|v\|\geq0$ ，且 $\|v\|=0$ 当且仅当 $v=0$ ；
（2）齐次性：对于所有的  和 $\alpha\in\mathbb {R}$ ，有 $\|\alpha{v}\|=\left| \alpha \right|\|v\|$ ；
（3）三角不等式：对于所有的 $v,w\in\mathbb {R}^{n}$ ，有 $\|v+w\|\leq\|v\|+\|w\|$ 。

向量范数

1）最常用的向量范数为 （ $p\geq1$ ）范数 ：
$\|v\|_p=(|v_1|^{p}+|v_2|^{p}+···+|v_n|^{p})^{\frac{1}{p}}\\$

$p=1,2,\infty$ 为最常遇见的情形，分别记为 $\|·\|_1,\|·\|_2$ 和 $\|·\|_\infty$ ，其中， $\|v\|_\infty=\mathop{max}\limits_{i}|v_{i}|$ .
而在不引起歧义的情况下，会省去  范数的角标，记为  .
对于  范数，有如下命题成立：
命题（Cauchy不等式）设 $a,b\in\mathbb {R}^{n}$ ，则有 $|a^{T}b|\leq\|a\|_2\|b\|_2$ 成立，等号成立当且仅当 $a$ 与 $b$ 线性相关。
2）由正定矩阵A诱导的范数：
$\|x\|_A\xlongequal{def}\sqrt{x^{T}Ax}\\$
矩阵范数

1）由向量 范数推广得到的矩阵 范数：
当 $p=1$ 时，矩阵 $a\in\mathbb {R}^{m\times{n}}$ 的 $l_1$ 范数定义为 $\|A\|_1=\sum_{i=1}^{m}{\sum_{j=1}^{n}{|a_{ij}|}}$ ，即  中所有元素的绝对值之和；
当 $p=2$ 时，得到矩阵的Frobenius范数（简称为F范数），记为 $\|A\|_F$ ，其满足 $\|A\|_F=\sqrt{tr(AA^T)}=\sqrt{\sum_{i,j}{a_{ij}^{2}}}\\$
F范数还具有正交不变性，即对于任意的正交矩阵 $U\in\mathbb {R}^{m\times{m}},V\in\mathbb {R}^{n\times{n}}$ ，有 $\|UAF\|^{2}_F=\|A\|^{2}_F$ 成立（根据F范数的定义得出）
2）由向量范数诱导而来的算子范数（矩阵范数的一种）：
先给出算子范数的相容性的定义：设  是  上的向量范数，  是 $\mathbb {R}^{m\times{n}}$ 上的矩阵范数，且有
$\|Ax\|_{(m)}\leq\|A\|_{(m,n)}\|x\|_{(n)}\\$
成立，则称  为与向量范数  相容的矩阵范数。但并非所有的矩阵范数都与给定的向量范数相容，只有满足该定义的矩阵范数才可以说与给定的向量范数相容。
然后给出算子范数的定义：
给定矩阵  ，及 $m$ 维和 $n$ 维空间的向量范数  和  ，则
$\|A\|_{(m,n)}=\mathop{max}\limits_{x\ne0}\frac{\|Ax\|_{(m)}}{\|x\|_{(n)}\\}=\mathop{max}\limits_{x\in\mathbb {R}^{n},\|x\|_{(n)}=1}\|Ax\|_{(m)}\\$
是与向量范数  相容的矩阵范数，我们称该矩阵范数为由向量范数  诱导出的算子范数。
如果将  和  都取为相应向量空间的  范数，则可得到矩阵的 $p$ 范数，如矩阵的 $2$ 范数为
$\|A\|_{2}=\mathop{max}\limits_{x\in\mathbb {R}^{n},\|x\|_{2}=1}\|Ax\|_{2}\\$
也就是该矩阵的最大奇异值.(因为 $\|Ax\|_{2}^2={(Ax)}^TAx=x^T\lambda{x}=\lambda\|x\|_{2}^2$ ，所以 $\lambda=\frac{\|Ax\|_{2}^2}{\|x\|_{2}^2}=\sigma^{2}$ )
3）核范数：
给定矩阵  ，其核范数定义为 $\|A\|_{*}=\sum_{i=1}^{r}{\sigma_i}$ ，其中 $r=rank(A)$ ， $\sigma_i$ 为  的所有非零奇异值。我们常常通过限制矩阵的核范数（因为核范数能凸近似矩阵的秩）来保证矩阵的低秩性，矩阵的低秩性表明该矩阵的各行或各列存在相似性，因此易利用相似性来对缺失数据进行恢复。
矩阵内积

范数一般用来衡量矩阵模的大小，而内积一般用来表征两个矩阵（或其张成的空间）之间的夹角。
这里，我们只介绍一种常用的内积——Frobenius内积：的矩阵  和  的Frobenius内积定义为
$\left \langle A,B \right\rangle\xlongequal{def}tr(AB^T)=\sum_{i=1}^{m}{\sum_{j=1}^{n}{a_{ij}b_{ij}}}\\$
即两个矩阵逐分量相乘的和，当 $A=B$ 时， $\left \langle A,B \right\rangle$ 等于矩阵  的F范数的平方。
我们还有矩阵范数对应的Cauchy不等式，如下：
命题（矩阵范数的Cauchy不等式）设 $A,B\in\mathbb {R}^{m\times{n}}$ ，则有 $|\left \langle A,B \right\rangle|\leq\|A\|_F\|B\|_F$ 成立，其中，等号成立当且仅当  和  线性相关。
2.2导数

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

我们先给出梯度和Hessian矩阵的定义：
定义（梯度）给定函数  ，且  在点  的一个邻域内有意义，若存在向量 $g\in\mathbb {R}^{n}$ 满足
$\lim_{p \rightarrow 0}{\frac{f(x+p)-f(x)-g^Tp}{\|p\|}}=0\\$
其中，  是任意的向量范数，就称  在点  处可微（或Frechet可微）。此时， $g$ 称为  在点  处的梯度，记作  。如果对区域  上的每一个点  都有  存在，则称  在  上可微。
可知， $\nabla{f(x)}=\left[ \frac{\partial f(x)}{\partial x_1}, \frac{\partial f(x)}{\partial x_2},···,\frac{\partial f(x)}{\partial x_n}\right]^T$
如果我们只关心对一部分变量的梯度，那么可以在 $\nabla$ 下加下标，如 $\nabla_xf(x,y)$ 表示当把  视为常数时，  关于  的梯度。
定义（Hessian矩阵）如果函数  在点  处的二阶偏导数 $\frac{\partial ^{2}f(x)}{\partial x_i\partial x_j} ,i,j=1,2,···,n$ 都存在，则
$\nabla^2{f(x)}= \begin{bmatrix} \frac{\partial ^{2}f(x)}{\partial x^{2}_1} &\frac{\partial ^{2}f(x)}{\partial x_1\partial x_2} &\frac{\partial ^{2}f(x)}{\partial x_1\partial x_3} &\cdots &\frac{\partial ^{2}f(x)}{\partial x_1\partial x_n} \\ \frac{\partial ^{2}f(x)}{\partial x_2\partial x_1} &\frac{\partial ^{2}f(x)}{\partial x^{2}_2} &\frac{\partial ^{2}f(x)}{\partial x_2\partial x_3} &\cdots &\frac{\partial ^{2}f(x)}{\partial x_2\partial x_n} \\ \vdots &\vdots&\vdots&&\vdots\\ \frac{\partial ^{2}f(x)}{\partial x_n\partial x_1} &\frac{\partial ^{2}f(x)}{\partial x_n\partial x_2} &\frac{\partial ^{2}f(x)}{\partial x_n\partial x_3} &\cdots &\frac{\partial ^{2}f(x)}{\partial x^{2}_n} \\ \end{bmatrix}\\$
称为  在点  处的Hessian矩阵。
当  在区域  上的每个点  处都存在时，称  在  上二阶可微；当  在  上的每个点都存在且在  上连续时，则称  在  上二阶连续可微，此时，Hessian矩阵是一个对称矩阵。
然后给出如下形式的泰勒展开：
定理（多元函数的泰勒展开）设  是连续可微的， $p\in\mathbb {R}^{n}$ 为向量，那么
$f(x+p)=f(x)+\nabla{f(x+tp)^Tp}\\$
其中，  。进一步地，如果  是二阶连续可微的，则
$\nabla{f(x+p)}=\nabla{f(x)}+\int_{0}^{1}\nabla^{2}{f(x+tp)p dt}\\ f(x+p)=f(x)+\nabla{f(x)^Tp}+\frac{1}{2}p^{T}\nabla^{2}{f(x+tp)p}\\$
其中，  。
最后，我们将介绍一种特殊的可微函数——梯度利普希茨(Lipschitz)连续的函数，该类函数在很多优化算法的收敛性证明中起着关键作用。
定义（梯度Lipschitz连续）给定可微函数  ，若存在 $L>0$ ，对任意的 $x,y\in{dom}f$ （函数  的定义域）有 $\|\nabla{f(x)}-\nabla{f(y)}\|\leq{L}\|x-y\|$ 成立，则称  是梯度利普希茨(Lipschitz)连续的，  为利普希茨常数。有时也简记为梯度 -利普希茨连续或 -光滑。
梯度Lipschitz连续表明  的变化受  的变化的控制。满足梯度Lipschitz连续的函数具有很多很好的性质，如下面的二次上界：
引理（二次上界）设可微函数  的定义域 $domf=\mathbb {R}^{n}$ ，且为梯度Lipschitz连续的，则函数  有二次上界：
$f(y)\leq{f(x)}+\nabla{f(x)}^T(y-x)+\frac{L}{2}\|y-x\|^2,\forall{x,y\in{domf}}\\$
证明. 构造辅助函数 $g(t)=f((1-t)x+ty),t\in\left[ 0,1 \right]$ ，则有 $g^{'}(t)=\nabla{f(x+t(y-x))^T(y-x)}$ 成立，所以
$\begin{align} &\quad f(y)-{f(x)}-\nabla{f(x)}^T(y-x)\\ &=g(1)-g(0)-g^{'}(0)\\ &=\int_{0}^{1}g^{'}(t)dt-g^{'}(0)\\ &=\int_{0}^{1}(g^{'}(t)-g^{'}(0))\\ &=\int_{0}^{1}(\nabla{f(x+t(y-x))-\nabla{f(x)})^T(y-x)}dt\\ &\leq\int_{0}^{1}\|\nabla{f(x+t(y-x))-\nabla{f(x)}\|\|y-x\|}dt\\ &\leq\int_{0}^{1}L\|y-x\|^{2}tdt\\ &=\frac{L}{2}\|y-x\|^2 \end{align}\\$
该引理表明  可以被一个二次函数上界所控制，即要求  的增长速度不超过二次。
当对该引理中  的定义域的要求减弱为凸集时，该引理也成立，因为定义域是凸集可以保证 $g(t)$ 当 $t\in\left[ 0,1 \right]$ 时是有定义的。
如果  是梯度Lipschitz连续的，且有一个全局极小点  ，那么我们可以利用二次上界来估计 $f(x)-f(x^{*})$ 的大小：
推论设可微函数  的定义域为  ，且存在一个全局极小点  ，若  为梯度Lipschitz连续的，则对任意的  有 $\frac{1}{2L}\|\nabla{f(x)}\|^2\leq{f(x)-f(x^*)}$ 成立。
证明. 固定  ，对任意的  应用二次上界，得 $f(x^*)\leq{f(y)}\leq{f(x)}+\nabla{f(x)^T(y-x)+\frac{L}{2}\|y-x\|^2}$
那么我们有 $f(x^*)\leq \inf\limits_{y\in\mathbb {R}^{n}}\left\{ {f(x)}+\nabla{f(x)^T(y-x)+\frac{L}{2}\|y-x\|^2} \right\}=f(x)-\frac{1}{2L}\|\nabla{f(x)}\|^2$ 成立，最后一步应用了二次函数的性质：当 $y=x-\frac{\nabla{f(x)}}{L}$ 时取到最小值。
向量值函数

当 $f:\mathbb {R}^{n}\rightarrow\mathbb {R}^{m}$ 是向量值函数时，我们可以定义它的Jacobi矩阵 $J(x)\in\mathbb {R}^{m\times{n}}$ ，它的第 $i$ 行是分量 $f_i(x)$ 的梯度的转置，即
$J(x)= \begin{bmatrix} \frac{\partial f_1(x)}{\partial x_1} &\frac{\partial f_1(x)}{\partial x_2} &\cdots &\frac{\partial f_1(x)}{\partial x_n}\\ \frac{\partial f_2(x)}{\partial x_1} &\frac{\partial f_2(x)}{\partial x_2} &\cdots &\frac{\partial f_2(x)}{\partial x_n}\\ \vdots &\vdots&&\vdots\\ \frac{\partial f_m(x)}{\partial x_1} &\frac{\partial f_m(x)}{\partial x_2} &\cdots &\frac{\partial f_m(x)}{\partial x_n}\\ \end{bmatrix}\\$
可以看出，梯度  的Jacobi矩阵就是  的Hessian矩阵。
矩阵变量函数

我们将多元函数梯度的定义加以推广，得到变量是矩阵的情形：
对于以  的矩阵  为自变量的函数  ，若存在矩阵  满足
$\lim_{V \rightarrow 0}{\frac{f(X+V)-f(X)-\left \langle G,V \right\rangle}{\|V\|}}=0\\$
其中，  是任意的矩阵范数，就称矩阵变量函数  在  Frechet可微，称  为  在Frechet可微意义下的梯度。
类似于向量情形，矩阵变量函数  的梯度可以用其偏导数表示为
$\nabla{f(x)}= \begin{bmatrix} \frac{\partial f}{\partial x_{11}} &\frac{\partial f}{\partial x_{12}} &\cdots &\frac{\partial f}{\partial x_{1n}}\\ \frac{\partial f}{\partial x_{21}} &\frac{\partial f}{\partial x_{22}} &\cdots &\frac{\partial f}{\partial x_{2n}}\\ \vdots &\vdots&&\vdots\\ \frac{\partial f}{\partial x_{m1}} &\frac{\partial f}{\partial x_{m2}} &\cdots &\frac{\partial f}{\partial x_{mn}}\\ \end{bmatrix}\\$
但在实际的应用中，矩阵Frechet可微的定义和使用往往比较繁琐，因此，我们将介绍另一种定义，该定义实际上是方向导数的某种推广：
定义（Gateaux可微）设  为矩阵变量函数，如果存在矩阵  ，对任意方向 $V\subset\mathbb {R}^{m\times{n}}$ 满足
$\lim_{t \rightarrow 0}{\frac{f(X+tV)-f(X)-t\left \langle G,V \right\rangle}{t}}=0\\$
则称  关于  是Gateaux可微的，称  为  在  处在Gateaux可微意义下的梯度。
（？）可以看出，若  是Frechet可微的，则  也是Gateaux可微的，且二者意义下的梯度相等；但这一命题反过来不一定成立。
自动微分

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

		自动登录	找回密码
密码			立即注册