范数与导数

向量范数

定义：
称一个从向量空间$R^n$到实数域$R$的非负函数$||\cdot ||$为范数，如果它满足：
(1) 正定性：对于所有的$v\in R^n$，有$||v||\ge 0$，且$||v||=0$当且仅当$v=0$；
(2) 齐次性：对于所有的$v\in R^n$和$\alpha \in R$，有$||\alpha v||=|\alpha |||v||$；
(3) 三角不等式：对于所有的$v,w\in R^n$，有$||v+w||\le ||v||+||w||$。
$l_p(p\ge 1)$范数：
$$||v|{|}_p=(|v_1{|}^p+|v_2{|}^p+...+|v_n{|}^p{)}^{\frac{1}{p}}\text{\hspace{1em}(1)}$$
当$p=\infty$时，$l_{\infty }$范数定义为：
$$||v|{|}_{\infty }=ma{x}_i|v_i|\text{\hspace{1em}(2)}$$

在不引起歧义的情况下，我们有时省略$l_2$范数的角标，记为$||\cdot ||$。

对向量的$l_2$范数，我们有常用的柯西（$Cauchy$）不等式：
设$a,b\in R^n$，则：
$$|a^{T}b|\le ||a|{|}_2||b|{|}_2\text{\hspace{1em}(3)}$$
等号成立当且仅当$a$与$b$线性相关。

矩阵范数

和向量范数类似，矩阵范数是定义在矩阵空间上的非负函数，并且满足正定性、齐次性和三角不等式。向量的$l_p$范数可以比较容易地推广到矩阵的$l_p$范数。
当$p=1$时，矩阵$A\in R^{m\times n}$的$l_1$范数定义为：
$$||A|{|}_1=\sum _{i=1}^m\sum _{j=1}^n|a_{ij}|\text{\hspace{1em}(4)}$$
即$||A|{|}_1$为$A$中所有元素绝对值的和。当$p=2$时，此时得到的是矩阵的$Frobenius$范数，记为$||A|{|}_F$。它可以看成是向量的$l_2$范数的推广，即所有元素平方和开根号：
$$||A|{|}_F=\sqrt{Tr(A{A}^T)}=\sqrt{\sum _{i,j}{a}_{ij}^2}\text{\hspace{1em}(5)}$$
这里，$Tr(X)$表示方阵$X$的迹（矩阵主对角线所有元素之和）。
矩阵的$F$范数具有正交不变性，即对于任意的正交矩阵$U\in R^{m\times m}$，$V\in R^{n\times n}$，我们有：
$$\begin{gathered} ||UAV|{|}_F^2=Tr(UAV{V}^T{A}^T{U}^T)=Tr(UA{A}^T{U}^T) \\ =Tr(A{A}^T{U}^{T}U)=Tr(A{A}^T)=||A|{|}_F^2\text{\hspace{1em}(6)} \end{gathered}$$
其中第三个等号成立是因为：
$$Tr(AB)=Tr(BA)\text{\hspace{1em}(7)}$$
这里将$U$看作$A$，将$A{A}^T{U}^T$看作$B$。
矩阵范数还可以由向量范数诱导出来，一般称为这种范数为算子范数。给定矩阵$A\in R^{m\times n}$，以及$m$维和$n$维空间的向量范数$||\cdot |{|}_{(m)}$和$||\cdot |{|}_{(n)}$，其诱导的矩阵范数定义如下：
$$||A|{|}_{(m,n)}=ma{x}_{x\in R^n,||x|{|}_{(n)}=1}||Ax|{|}_{(m)}\text{\hspace{1em}(8)}$$
容易验证$||\cdot |{|}_{(m,n)}$满足范数的定义。如果将$||\cdot |{|}_{(m)}$和$||\cdot |{|}_{(n)}$都取为相应向量空间的$l_p$范数，我们可以得到矩阵的$p$范数。
$$||A|{|}_2=ma{x}_{x\in R^n,||x|{|}_2=1}||Ax|{|}_2\text{\hspace{1em}(9)}$$
矩阵的2-范数是该矩阵的最大奇异值。
奇异值的解释：
设$A$为$m\ast n$阶矩阵，$A^{\ast }A$的$n$个特征值的非负平方根叫作$A$的奇异值。$A^{\ast }$表示$A$的共轭转置矩阵，如果把$A^{\ast }A$的特征值记为${\lambda }_i(A^{\ast }A)$，则：
$${\sigma }_i(A)=\sqrt{{\lambda }_i(A^{\ast }A)}\text{\hspace{1em}(10)}$$
根据算子范数的定义，所有算子范数都满足如下性质（相容性）：
$$||Ax|{|}_{(m)}\le ||A|{|}_{(m,n)}||x|{|}_{(n)}\text{\hspace{1em}(11)}$$
即$||\cdot |{|}_{(m,n)}$与$||\cdot |{|}_{(m)}$和$||\cdot |{|}_{(n)}$是相容的。
核范数：
给定矩阵$A\in R_{m\times n}$，其核范数定义为：
$$||A|{|}_{\ast }=\sum _{i=1}^r{\sigma }_i\text{\hspace{1em}(12)}$$
其中${\sigma }_i,i=1,2,...,r$为$A$的所有非零奇异值，$r=rank(A)$。

矩阵的内积

对于矩阵空间$R^{m\times n}$的两个矩阵$A$和$B$，除了定义它们各自的范数以外，我们还可以定义它们之间的内积。范数一般用来衡量矩阵的模的大小，而内积一般用来表征两个矩阵（或其张成的空间）之间的夹角。
$Frobenius$内积：
$$<A,B>\stackrel{def}{=}Tr(A{B}^T)=\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}{b}_{ij}\text{\hspace{1em}(13)}$$
易知该内积为两个矩阵逐分量相乘的和，因而满足内积的定义。当$A=B$时，$<A,B>$等于矩阵$A$的$F$范数的平方。
矩阵范数的柯西不等式：
设$A,B\in R^{m\times n}$，则：
$$|<A,B>|\le ||A|{|}_F||B|{|}_F\text{\hspace{1em}(14)}$$
等号成立当且仅当$A$和$B$线性相关。

导数部分：
简介:
为了分析可微最优化问题的性质，我们需要知道目标函数和约束函数的导数信息．在算法设计中，当优化问题没有显式解时，我们也往往通过函数值和导数信息来构造容易求解的子问题．利用目标函数和约束函数的导数信息，可以确保构造的子问题具有很好的逼近性质，从而构造各种各样有效的算法．

梯度

给定函数$f:R^n\to R$，且$f$在点$x$的一个领域内有意义，若存在向量$g\in R^n$满足：
$$\underset{p\to 0}{\lim }\frac{f(x+p)-f(x)-g^{T}p}{||p||}=0\text{\hspace{1em}(1)}$$
其中$||\cdot ||$是任意的向量范数，就称$f$在点$x$处可微。此时$g$称为$f$在点$x$处的梯度，记作$▽f(x)$。如果对区域$D$上的每个点$x$都有$▽f(x)$存在，则称为$f$在$D$上可微。
若$f$在点$x$处的梯度存在，令$p=\epsilon e_i$，$e_i$是第$i$个分量为1的单位向量，可知$▽f(x)$的第$i$个分量为$\frac{\partial f(x)}{\partial x_i}$，因此，
$$▽f(x)=[\frac{\partial f(x)}{\partial x_1},\frac{\partial f(x)}{\partial x_2},...,\frac{\partial f(x)}{\partial x_n}{]}^T\text{\hspace{1em}(2)}$$
如果只关心对一部分变量的梯度，可以通过对$▽$加下标来表示。例如，${▽}_{x}f(x,y)$表示为$y$视为常数时$f$关于$x$的梯度。

海瑟矩阵

如果函数$f(x):R^n\to R$在点$x$处的二阶偏导数$\frac{{\partial }^{2}f(x)}{\partial x_i\partial x_j}i,j=1,2,...,n$都存在，则：
$${▽}^{2}f(x)=\left[\begin{array}{ccccc}\frac{{\partial }^{2}f(x)}{\partial x_1^2}& \frac{{\partial }^{2}f(x)}{\partial x_1\partial x_2}& \frac{{\partial }^{2}f(x)}{\partial x_1\partial x_3}& ...& \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}& ...& \frac{{\partial }^{2}f(x)}{\partial x_2\partial x_n}\\ ...& ...& ...& ...& ...\\ \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}& ...& \frac{{\partial }^{2}f(x)}{\partial x_n^2}\end{array}\right]$$
称为$f$在点$x$处的海瑟矩阵。