凸优化专题1

多变量函数的求导与求梯度/矩阵求导

1. 导数

定义: 设$$\begin{gathered} f:{\mathbb{R}}^n\to {\mathbb{R}}^m,且x\in \mathbf{int}\mathbf{dom}f,则f在点x的导 \\ 数(或称Jacobian)记为矩阵Df(x)\in {\mathbb{R}}^{m\times n} \end{gathered}$$, 定义如下
$$Df(x{)}_{ij}=\frac{\partial f_i(x)}{\partial x_j},i=1,...,m,j=1,...,n\text{\hspace{1em}(1)}$$

$Df(x{)}_{ij}表示矩阵Df(x)的第i行第j列元素$

2. 梯度

定义: 如果$f$是一个实值函数(即$f:{\mathbb{R}}^n\to \mathbb{R}$), 易知其在点$x$导数$Df(x)$是一个行向量, 定义$Df(x)$的转置为其在点$x$处的梯度, 即

$$\nabla f(x)=Df(x{)}^T\text{\hspace{1em}(2)}$$
易知梯度为一个列向量.

注1: 梯度是针对实值函数的, 且其定义是基于Jacobian的, 也就是说现有导数才有梯度. 梯度的定义可以拓展到$f:S^n\to \mathbb{R}$, $S^n$指n阶实对称矩阵, 此处不再赘述.

注2:对于一般的$f:{\mathbb{R}}^n\to {\mathbb{R}}^m$, $f$在点$x$附近的一阶近似记作:
$$f(x)+Df(x)(z-x),z\in {\delta }_{ϵ}(x)\text{\hspace{1em}(3)}$$
这和单变量函数的情形是一致的.
与之相对应, 对于一般的实值函数$f:{\mathbb{R}}^n\to \mathbb{R}$, 用梯度表示其一阶近似, 则有:
$$f(x)+\nabla f(x{)}^T(z-x),z\in {\delta }_{ϵ}(x)\text{\hspace{1em}(4)}$$

3. 链式法则

考虑$$\begin{gathered} f:{\mathbb{R}}^n\to {\mathbb{R}}^m,且f在x处可微,x\in \mathbf{int}\mathbf{dom}f,并有g:{\mathbb{R}}^n\to {\mathbb{R}}^p \\ 在f(x)处可微,f(x)\in \mathbf{int}\mathbf{dom}g,定义符合复合函数h:{\mathbb{R}}^n\to {\mathbb{R}}^p,其 \\ 中h(z)=g(f(z)),则有h在点x处可微,且其在点x处的导数为 \end{gathered}$$:
$$Dh(x)=Dg(f(x))Df(x)\text{\hspace{1em}(5)}$$
特别地, 若$$\begin{gathered} f:{\mathbb{R}}^n\to \mathbb{R},g:\mathbb{R}\to \mathbb{R},则可以考虑h的梯度,只要取转置 \\ 即可,根据定义有 \end{gathered}$$:
$$\nabla h(x)=g^{\prime }(f(x))\nabla f(x)\text{\hspace{1em}(6)}$$
这是很显然的结果, 只需要略加思索即可知道这是正确答案.

例题: 考虑$f:{\mathbb{R}}^n\to \mathbb{R},\mathbf{dom}f={\mathbb{R}}^n$, 且
$$f(x)=\ln \sum _{i=1}^m\exp (a_i^{T}x+b_i)$$
其中$a_i\in {\mathbb{R}}^n,b_i\in \mathbb{R}$
请求出$f(x)$的梯度.
解:
设$z(x)={\sum }_{i=1}^m\exp (a_i^{T}x+b_i)$, 则根据链式法则, 有
$$Df(x)=D\ln z(x)=\frac{1}{z}Dz(x)$$
设$y(x):{\mathbb{R}}^n\to {\mathbb{R}}^m,y_i=\exp (a_i^{T}x+b_i)$, 则有$$\begin{gathered} z=1^{T}y,其中1\in {\mathbb{R}}^m,且 \\ 每个元素均为1 \end{gathered}$$
所以
$$\begin{array}{r}y=\exp (A^{T}x+b)\end{array}$$
其中
$$A^T=\left[\begin{array}{c}{a}_1^T\\ a_2^T\\ ⋮\\ a_m^T\end{array}\right]$$
所以
$$\begin{array}{rl}Df(x)& =\frac{1}{z}Dz(x)\\ & =\frac{1}{z}{1}^{T}Dy(x)\end{array}$$
其中$Dy(x)$为
$$Dy(x)=\left[\begin{array}{cccc}\frac{\partial y_1}{x_1}& \frac{\partial y_1}{x_2}& \cdots & \frac{\partial y_1}{x_n}\\ \frac{\partial y_2}{x_1}& \frac{\partial y_2}{x_2}& \cdots & \frac{\partial y_2}{x_n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{\partial y_m}{x_1}& \frac{\partial y_m}{x_2}& \cdots & \frac{\partial y_m}{x_n}\end{array}\right]\in {\mathbb{R}}^{m\times n}$$
易知
$$Dy(x{)}_{ij}=\frac{\partial y_i}{x_j}=\exp (a_i^{T}x+b_i)\cdot a_{ij}$$
其中$a_{ij}为a_i^T的第j个元素$
$Dy(x)$也可写作
Dy(x)=diag{y1,y2,⋯,ym}⋅[a1Ta2T⋮amT]Dy(x) = diag\{ y_{1}, y_{2}, \cdots, y_{m} \} \cdot \begin{bmatrix} a_{1}^T \\ a_{2}^T \\ \vdots \\ a_{m}^T \\ \end{bmatrix} Dy(x)=diag{y1​,y2​,⋯,ym​}⋅​a1T​a2T​⋮amT​​​
所以
Df(x)=1z1T⋅diag{y1,y2,⋯,ym}⋅[a1Ta2T⋮amT]=1z1T⋅diag{y1,y2,⋯,ym}⋅AT\begin{split} Df(x) &= \frac{1}{z} \mathbf{1}^T \cdot diag\{ y_{1}, y_{2}, \cdots, y_{m} \} \cdot \begin{bmatrix} a_{1}^T \\ a_{2}^T \\ \vdots \\ a_{m}^T \\ \end{bmatrix} \\ &= \frac{1}{z} \mathbf{1}^T \cdot diag\{ y_{1}, y_{2}, \cdots, y_{m} \} \cdot A^T \end{split} Df(x)​=z1​1T⋅diag{y1​,y2​,⋯,ym​}⋅​a1T​a2T​⋮amT​​​=z1​1T⋅diag{y1​,y2​,⋯,ym​}⋅AT​
所以
∇f(x)=1zA⋅diag{y1,y2,⋯,ym}⋅1=1zA⋅[exp⁡(a1Tx+b1)exp⁡(a2Tx+b2)⋮exp⁡(amTx+bm)]其中z=∑i=1mexp⁡(aiTx+bi)\begin{split} \nabla f(x) &= \frac{1}{z} A \cdot diag\{ y_{1}, y_{2}, \cdots, y_{m} \} \cdot \mathbf{1} \\ &=\frac{1}{z} A \cdot \begin{bmatrix} \exp(a_1^T x + b_1) \\ \exp(a_2^T x + b_2) \\ \vdots \\ \exp(a_m^T x + b_m) \\ \end{bmatrix} \\ 其中z &= \sum_{i=1}^m \exp(a_i^T x+b_i) \end{split} ∇f(x)其中z​=z1​A⋅diag{y1​,y2​,⋯,ym​}⋅1=z1​A⋅​exp(a1T​x+b1​)exp(a2T​x+b2​)⋮exp(amT​x+bm​)​​=i=1∑m​exp(aiT​x+bi​)​

4. 二阶导数

对于实值函数$$\begin{gathered} f:{\mathbb{R}}^n\to \mathbb{R},且x\in \mathbf{int}\mathbf{dom}f,则f在点x的二阶导 \\ 数(或称Hessian]matrix)记为矩阵{\nabla }^{2}f(x)\in {\mathbb{R}}^{n\times n},其中 \end{gathered}$$
$${\nabla }^{2}f(x{)}_{ij}=\frac{{\partial }^{2}f(x)}{\partial x_i\partial x_j},i,j=1,...,n\text{\hspace{1em}(7)}$$
易知对于一般的实值函数$f:{\mathbb{R}}^n\to \mathbb{R}$, 用hessian matrix表示其二阶近似, 则有:
$$\begin{gathered} \hat{f}(z)=f(x)+\nabla f(x{)}^T(z-x)+\frac{1}{2}(z-x{)}^T{\nabla }^{2}f(x)(z-x) \\ z\in {\delta }_{ϵ}(x) \end{gathered}$$
易知下列关系式成立
$$D\nabla f(x)={\nabla }^{2}f(x)\text{\hspace{1em}(8)}$$