前面我们回顾了一些线性代数的基本理论，包括最小二乘、范数、矩阵正交化、PCA、SVD等。在正式进入最优化理论的学习之前，我们还需要补充一些向量微积分的知识。也可以看作多元微积分回顾

向量微分

  • 在一元微积分中，可微函数f:R→Rf:\R\to\R对xx的导函数dfdx:R→R\dfrac{\mathrm{d}f}{\mathrm{d}x}:\R\to\R定义为 dfdx(x)=lim⁡h→0f(x+h)−f(x)h.\frac{\mathrm{d}f}{\mathrm{d}x}(x)=\lim_{h\to 0}\frac{f(x+h)-f(x)}{h}. 而本节我们主要会讨论以下两种函数的微分：
    1. 多元函数f:Rn→Rf:\R^n\to\R，比如f(x⃗)=∥x⃗∥pf(\vec{x})=\|\vec{x}\|_p；
    2. 向量值函数f⃗:Rn→Rm\vec{f}:\R^n\to\R^m，比如f⃗(x⃗)=Ax⃗\vec{f}(\vec{x})=A\vec{x}。
  • 一元微积分中我们计算复合函数的导数使用的是链式法则，即： dhdx(x)=dfdg(g(x))⋅dgdx(x)\frac{\mathrm{d}h}{\mathrm{d}x}(x) = \frac{\mathrm{d}f}{\mathrm{d}g}(g(x)) \cdot \frac{\mathrm{d}g}{\mathrm{d}x}(x) 或者其简化形式： h′(x)=f′(g(x))⋅g′(x).h'(x)=f'(g(x))\cdot g'(x).
    • 将其推广至多元复合函数：设f:Rn→Rf : \mathbb{R}^n \to \mathbb{R}和g⃗:R→Rn\vec{g} : \mathbb{R} \to \mathbb{R}^n为可微函数，定义函数h:R→Rh : \mathbb{R} \to \mathbb{R}为：h(x)=f(g⃗(x))h(x) = f(\vec{g}(x))，则hh可微，且其导数为 dhdx(x)=∑i=1n∂f∂gi(g⃗(x))⋅dgidx(x).\frac{\mathrm{d}h}{\mathrm{d}x}(x) = \sum_{i=1}^n \frac{\partial f}{\partial g_i}(\vec{g}(x)) \cdot \frac{\mathrm{d}g_i}{\mathrm{d}x}(x). 直观理解就是先列出函数ff到xx的各条复合路径，对每条路径使用链式法则，再进行相加。

梯度（Gradient）

  • 下面我们对多元函数的梯度进行定义：对于可微函数f:Rn→Rf:\R^n\to\R，其梯度（函数）∇f:Rn→Rn\nabla f:\R^n\to\R^n定义为 ∇f(x⃗)=[∂f∂x1(x⃗)∂f∂x2(x⃗)⋮∂f∂xn(x⃗)]\nabla f(\vec{x})=\begin{bmatrix} \dfrac{\partial f}{\partial x_1}(\vec{x})\\[10pt] \dfrac{\partial f}{\partial x_2}(\vec{x})\\[10pt] \vdots\\ \dfrac{\partial f}{\partial x_n}(\vec{x})\\[10pt] \end{bmatrix} 由此可知梯度就是向量微分的转置。
  • 梯度具有以下两条性质：
    1. 梯度方向是函数变化最快的方向，且在此方向上函数变化速率为∥∇f(x⃗)∥2\|\nabla f(\vec{x})\|_2；
      简单证明

      设单位向量u⃗\vec{u}表示函数ff变化的方向，那么ff在x⃗\vec{x}上沿u⃗\vec{u}的方向导数可表示为u⃗⊤∇f(x⃗)\vec{u}^\top\nabla f(\vec{x})。【即方向向量与梯度向量的内积】
      于是由柯西-施瓦茨不等式，

      u⃗⊤∇f(x⃗)≤∥u⃗∥2∥∇f(x⃗)∥2=∥∇f(x⃗)∥2.\vec{u}^\top\nabla f(\vec{x})\leq \|\vec{u}\|_2\|\nabla f(\vec{x})\|_2=\|\nabla f(\vec{x})\|_2.

      而取到等号时，u⃗\vec{u}与∇f(x⃗)\nabla f(\vec{x})恰好同向，故u⃗=∇f(x⃗)∥∇f(x⃗)∥2\vec{u}=\dfrac{\nabla f(\vec{x})}{\|\nabla f(\vec{x})\|_2}，即沿梯度方向函数变化最快。

    2. 设x⃗∈Rn,f(x⃗)=α\vec{x}\in\R^n,f(\vec{x})=\alpha，则函数在x⃗\vec{x}处的梯度∇f(x⃗)\nabla f(\vec{x})与过x⃗\vec{x}的α\alpha等值切面相垂直。

      解释：α\alpha等值面的定义为

      Lα(f)={x⃗∈Rn∣f(x⃗)=α}L_\alpha(f)=\{\vec{x}\in\R^n\mid f(\vec{x})=\alpha\}

      而过x⃗\vec{x}的α\alpha等值切面即为包含x⃗\vec{x}的Lα(f)L_\alpha(f)在x⃗\vec{x}处的切超平面。

  • 一些常见函数梯度的计算：
    • f1(x⃗)=∥x⃗∥22⟹∇f1(x⃗)=2x⃗f_1(\vec{x})=\|\vec{x}\|_2^2\Longrightarrow \nabla f_1(\vec{x})=2\vec{x}；
    • f2(x⃗)=a⃗⊤x⃗⟹∇f2(x⃗)=a⃗f_2(\vec{x})=\vec{a}^\top\vec{x}\Longrightarrow \nabla f_2(\vec{x})=\vec{a}；
    • f3(x⃗)=x⃗⊤Ax⃗⟹∇f2(x⃗)=(A+A⊤)x⃗f_3(\vec{x})=\vec{x}^\top A\vec{x}\Longrightarrow \nabla f_2(\vec{x})=(A+A^\top)\vec{x}。

雅可比矩阵（Jacobian）

  • 下面我们将上述多元函数微分推广到向量值函数f⃗:Rn→Rm\vec{f}:\R^n\to\R^m上。
    • 首先定义向量值函数的雅可比矩阵：f⃗\vec{f}的雅可比矩阵Df⃗:Rn→Rm×nD\vec{f}:\R^n\to\R^{m\times n}定义为 Df⃗(x⃗)=[∇f1(x⃗)⊤⋮∇fm(x⃗)⊤]=[∂f1∂x1(x⃗)⋯∂f1∂xn(x⃗)⋮⋱⋮∂fm∂x1(x⃗)⋯∂fm∂xn(x⃗)].D\vec{f}(\vec{x}) = \begin{bmatrix} \nabla f_1(\vec{x})^\top \\ \vdots \\ \nabla f_m(\vec{x})^\top \end{bmatrix} = \begin{bmatrix} \dfrac{\partial f_1}{\partial x_1}(\vec{x}) & \cdots & \dfrac{\partial f_1}{\partial x_n}(\vec{x}) \\ \vdots & \ddots & \vdots \\ \dfrac{\partial f_m}{\partial x_1}(\vec{x}) & \cdots & \dfrac{\partial f_m}{\partial x_n}(\vec{x}) \end{bmatrix}. 例：f⃗(x⃗)=Ax⃗\vec{f}(\vec{x})=A\vec{x}时，Df⃗(x⃗)=AD\vec{f}(\vec{x})=A。
      特别地，当m=1m=1时，得到的雅可比矩阵是1×n1\times n行向量，即为上述定义梯度的转置。
    • 类似多元函数，向量值函数的雅可比矩阵也有链式法则：设f⃗:Rp→Rm\vec{f}: \mathbb{R}^p \to \mathbb{R}^m和g⃗:Rn→Rp\vec{g}: \mathbb{R}^n \to \mathbb{R}^p为可微函数。定义h⃗:Rn→Rm\vec{h}: \mathbb{R}^n \to \mathbb{R}^m为h⃗(x⃗)=f⃗(g⃗(x⃗))\vec{h}(\vec{x}) = \vec{f}(\vec{g}(\vec{x}))（x⃗∈Rn\vec{x} \in \mathbb{R}^n）。则h⃗\vec{h}可微，且有 Dh⃗(x⃗)=[Df⃗(g⃗(x⃗))][Dg⃗(x⃗)].D\vec{h}(\vec{x}) = [D\vec{f}(\vec{g}(\vec{x}))][D\vec{g}(\vec{x})]. 其中Df⃗(g⃗(x⃗))D\vec{f}(\vec{g}(\vec{x}))表示先计算Df⃗D\vec{f}算子，再将其作用于g(x⃗)g(\vec{x})上。
      简单证明

      基于偏导数与多元复合函数链式法则的推导如下：

      [Dh⃗(x⃗)]k,i=∂fk∂xi(x⃗)=∑j=1p∂fk∂gj(g⃗(x⃗))⋅∂gj∂xi(x⃗)=∑j=1p[Df⃗(g⃗(x⃗))]k,j⋅[Dg⃗(x⃗)]j,i={[Df⃗(g⃗(x⃗))][Dg⃗(x⃗)]}k,i.\begin{align*} [D\vec{h}(\vec{x})]_{k,i} &= \frac{\partial f_k}{\partial x_i}(\vec{x}) \\ &= \sum_{j=1}^p \frac{\partial f_k}{\partial g_j}(\vec{g}(\vec{x})) \cdot \frac{\partial g_j}{\partial x_i}(\vec{x}) \\ &= \sum_{j=1}^p [D\vec{f}(\vec{g}(\vec{x}))]_{k,j} \cdot [D\vec{g}(\vec{x})]_{j,i} \\ &= \{[D\vec{f}(\vec{g}(\vec{x}))][D\vec{g}(\vec{x})]\}_{k,i}. \end{align*}
      • 推论：当m=1m=1时，可以得到梯度的链式法则 ∇h(x⃗)=[Dg(x⃗)]⊤∇f(g(x⃗)).\nabla h(\vec{x})=[Dg(\vec{x})]^\top\nabla f(g(\vec{x})).
  • 使用雅可比矩阵和梯度的链式法则可以求解许多复合函数的求导问题，比如神经网络的反向传播【会在之后详细阐述】。

黑塞矩阵（Hessian）

上面我们已经解决了向量值函数一阶导数的表示方法，下面我们继续考虑二阶导数。

  • 对于向量值函数f⃗:Rn→Rm\vec{f}:\R^n\to\R^m，要表示其所有二阶导数需要m×n×nm\times n\times n矩阵，但我们只需要考虑m=1m=1的情形，因为f⃗\vec{f}的每个分量对应的二阶导数都是n×nn\times n矩阵。【不失一般性】
  • 于是我们定义二阶可微多元函数f⃗:Rn→R\vec{f}:\R^n\to\R的二阶导数矩阵，即黑塞矩阵∇2f(x⃗):Rn→Rn×n\nabla^2 f(\vec{x}):\R^n\to\R^{n\times n}为 ∇2f(x⃗)=D(∇f)(x⃗)=[∂2f∂x12(x⃗)⋯∂2f∂xn∂x1(x⃗)⋮⋱⋮∂2f∂x1∂xn(x⃗)⋯∂2f∂xn2(x⃗)].\nabla^2 f(\vec{x}) = D(\nabla f)(\vec{x}) = \begin{bmatrix} \dfrac{\partial^2 f}{\partial x_1^2}(\vec{x}) & \cdots & \dfrac{\partial^2 f}{\partial x_n \partial x_1}(\vec{x}) \\ \vdots & \ddots & \vdots \\ \dfrac{\partial^2 f}{\partial x_1 \partial x_n}(\vec{x}) & \cdots & \dfrac{\partial^2 f}{\partial x_n^2}(\vec{x}) \end{bmatrix}. 例：f⃗(x⃗)=x⃗⊤Ax⃗\vec{f}(\vec{x})=\vec{x}^\top A\vec{x}时，∇2f(x⃗)=A+A⊤\nabla^2 f(\vec{x})=A+A^\top。
  • 对于黑塞矩阵，有以下定理（也称为克莱罗定理）：当多元函数f⃗:Rn→R\vec{f}:\R^n\to\R有连续二阶偏导数，那么其对应的黑塞矩阵是对称矩阵。
    • 后续我们讨论的绝大多数多元函数（向量值函数）都满足这一定理。

方向导数

  • 这里再补充方向导数的定义：令f:Rn→Rf: \mathbb{R}^n \to \mathbb{R}为可微函数，并固定单位向量u⃗∈Rn\vec{u} \in \mathbb{R}^n（即∥u⃗∥2=1\|\vec{u}\|_2 = 1）。则ff沿方向u⃗\vec{u}的方向导数函数Df(⋅)[u⃗]:Rn→RD f(\cdot)[\vec{u}] : \mathbb{R}^n \to \mathbb{R}的表达式为 Df(x⃗)[u⃗]=lim⁡h→0f(x⃗+h⋅u⃗)−f(x⃗)h.D f(\vec{x})[\vec{u}] = \lim_{h \to 0} \frac{f(\vec{x} + h \cdot \vec{u}) - f(\vec{x})}{h}. 而方向导数与梯度有着密切的联系，二者关系式为 Df(x⃗)[u⃗]=u⃗⊤[∇f(x⃗)].D f(\vec{x})[\vec{u}]=\vec{u}^\top[\nabla f(\vec{x})]. 特别地，Df(x⃗)[e⃗i]=∂f∂xi(x⃗)D f(\vec{x})[\vec{e}_i]=\dfrac{\partial f}{\partial x_i}(\vec{x})。

泰勒定理

下面我们将标量函数的泰勒定理推广到多元函数与向量值函数。

  • 先给出标量函数的泰勒近似公式：当函数f:R→Rf:\R\to\R是kk阶可微函数，那么ff在点x0∈Rx_0\in\R上的kk阶泰勒近似可表示为 f^k(x;x0)=f(x0)+11!dfdx(x0)⋅(x−x0)+⋯+1k!dkfdxk(x0)⋅(x−x0)k=∑i=0k1i!difdxi(x0)⋅(x−x0)i.\begin{aligned} \widehat{f}_k(x;x_0)&=f(x_0) + \frac{1}{1!} \frac{\mathrm{d} f}{\mathrm{d} x}(x_0) \cdot (x - x_0) + \cdots + \frac{1}{k!} \frac{\mathrm{d}^k f}{\mathrm{d} x^k}(x_0) \cdot (x - x_0)^k\\ &= \sum_{i=0}^k \frac{1}{i!} \frac{\mathrm{d}^i f}{\mathrm{d} x^i}(x_0) \cdot (x - x_0)^i. \end{aligned} 而泰勒定理则给出了kk阶泰勒近似的误差估计，即： f(x)=f^k(x;x0)+o(∣x−x0∣k)f(x)=\widehat{f}_k(x;x_0)+o(|x-x_0|^k) 其中o(∣x−x0∣k)o(|x-x_0|^k)表示∣x−x0∣k|x-x_0|^k的高阶无穷小量。
  • 下面我们给出多元函数的泰勒近似：设f:Rn→Rf : \mathbb{R}^n \to \mathbb{R}，并固定x⃗0∈Rn\vec{x}_0 \in \mathbb{R}^n。
    • 若ff连续可微，则其在x⃗0\vec{x}_0附近的一阶泰勒近似函数f^1(⋅;x⃗0):Rn→R\hat{f}_1(\cdot; \vec{x}_0) : \mathbb{R}^n \to \mathbb{R}定义为 f^1(x⃗;x⃗0)=f(x⃗0)+[∇f(x⃗0)]⊤(x⃗−x⃗0).\hat{f}_1(\vec{x}; \vec{x}_0) = f(\vec{x}_0) + [\nabla f(\vec{x}_0)]^\top (\vec{x} - \vec{x}_0).

      由此可知一阶泰勒近似函数即为过(x0⃗,f⃗(x⃗0))(\vec{x_0},\vec{f}(\vec{x}_0))且与梯度向量垂直的切超平面。

    • 若ff二阶连续可微，则其在x⃗0\vec{x}_0附近的二阶泰勒近似函数f^2(⋅;x⃗0):Rn→R\hat{f}_2(\cdot; \vec{x}_0) : \mathbb{R}^n \to \mathbb{R}定义为 f^2(x⃗;x⃗0)=f(x⃗0)+[∇f(x⃗0)]⊤(x⃗−x⃗0)+12(x⃗−x⃗0)⊤[∇2f(x⃗0)](x⃗−x⃗0).\hat{f}_2(\vec{x}; \vec{x}_0) = f(\vec{x}_0) + [\nabla f(\vec{x}_0)]^\top (\vec{x} - \vec{x}_0) + \frac{1}{2} (\vec{x} - \vec{x}_0)^\top [\nabla^2 f(\vec{x}_0)] (\vec{x} - \vec{x}_0).

    当然我们也可以给出更高阶的泰勒近似，但这就需要定义高阶矩阵（即张量），这超出了本课程设计范围，故作略。【关于张量的使用可参见PyTorch教程】

    • 类似地，我们也可以给出多元函数的泰勒定理： f(x⃗)=f^k(x⃗;x⃗0)+o(∥x⃗−x⃗0∥2k).f(\vec{x}) = \hat{f}_k(\vec{x}; \vec{x}_0) + o(\|\vec{x} - \vec{x}_0\|_2^k).

      当然这里余项换为其他LpL_p范数也未尝不可，但使用L2L_2范数最方便。

  • 另外，有时我们也可以通过泰勒近似得到多元函数的梯度和黑塞矩阵。【先计算f(x⃗+δ⃗)f(\vec{x}+\vec{\delta})的泰勒近似，再与前两阶项进行匹配】
  • 最后我们给出向量值函数的一阶泰勒近似和泰勒定理：设f⃗:Rn→Rm\vec{f} : \mathbb{R}^n \to \mathbb{R}^m，并固定x⃗0∈Rn\vec{x}_0 \in \mathbb{R}^n。若f⃗\vec{f}连续可微，则其在x⃗0\vec{x}_0附近的一阶泰勒近似函数f⃗1^:Rn→Rm\hat{\vec{f}_1} : \mathbb{R}^n \to \mathbb{R}^m定义为 f⃗1^(x⃗;x⃗0)=f⃗(x⃗0)+[Df⃗(x⃗0)](x⃗−x⃗0).\hat{\vec{f}_1}(\vec{x}; \vec{x}_0) = \vec{f}(\vec{x}_0) + [D\vec{f}(\vec{x}_0)](\vec{x} - \vec{x}_0). 且对于任意x⃗∈Rn\vec{x}\in\R^n有 f⃗(x⃗)=f⃗1^(x⃗;x⃗0)+o⃗(∥x⃗−x⃗0∥2).\vec{f}(\vec{x})=\hat{\vec{f}_1}(\vec{x}; \vec{x}_0)+\vec{o}(\|\vec{x}-\vec{x}_0\|_2).

    注：上面所有x⃗0\vec{x}_0和x⃗−x⃗0\vec{x} - \vec{x}_0均可替换为x⃗+δ⃗\vec{x}+\vec{\delta}和δ⃗\vec{\delta}。

矩阵微分

  • 以上我们讨论了设计向量（标量）输入/输出的函数微分，下面我们将其推广到矩阵输入函数f:Rm×n→Rf:\R^{m\times n}\to\R，即f(X)f(X)（X∈Rm×nX\in\R^{m\times n}）。典型的矩阵输入函数包括矩阵范数、行列式和迹。
  • 首先定义其梯度：设f:Rm×n→Rf : \mathbb{R}^{m \times n} \to \mathbb{R}为可微函数，则ff的梯度∇f:Rm×n→Rm×n\nabla f : \mathbb{R}^{m \times n} \to \mathbb{R}^{m \times n}定义为 ∇f(X)=[∂f∂X11(X)⋯∂f∂X1n(X)⋮⋱⋮∂f∂Xm1(X)⋯∂f∂Xmn(X)].\nabla f(X) = \begin{bmatrix} \dfrac{\partial f}{\partial X_{11}}(X) & \cdots & \dfrac{\partial f}{\partial X_{1n}}(X) \\ \vdots & \ddots & \vdots \\ \dfrac{\partial f}{\partial X_{m1}}(X) & \cdots & \dfrac{\partial f}{\partial X_{mn}}(X) \end{bmatrix}.
  • 然后是链式法则：设F:Rp×q→Rr×sF : \mathbb{R}^{p \times q} \to \mathbb{R}^{r \times s}和G:Rm×n→Rp×qG : \mathbb{R}^{m \times n} \to \mathbb{R}^{p \times q}为可微函数，H:Rm×n→Rr×sH : \mathbb{R}^{m \times n} \to \mathbb{R}^{r \times s}定义为H(X)=F(G(X))H(X) = F(G(X))，其中X∈Rm×nX \in \mathbb{R}^{m \times n}。则HH可微，并且对所有i,j,k,li, j, k, l，有 ∂Hij∂Xkl(X)=∑a∑b∂Fij∂Gab(G(X))∂Gab∂Xkl(X).\frac{\partial H_{ij}}{\partial X_{kl}}(X) = \sum_a \sum_b \frac{\partial F_{ij}}{\partial G_{ab}}(G(X)) \frac{\partial G_{ab}}{\partial X_{kl}}(X). 特别地，当r=s=1r=s=1时，有 ∂H∂Xkl(X)=∑a∑b[∇f(G(X))]ab∂Gab∂Xkl(X).\frac{\partial H}{\partial X_{kl}}(X) = \sum_a \sum_b [\nabla f(G(X))]_{ab} \frac{\partial G_{ab}}{\partial X_{kl}}(X).
  • 最后给出一阶泰勒近似：设f:Rm×n→Rf : \mathbb{R}^{m \times n} \to \mathbb{R}并固定X0∈Rm×nX_0 \in \mathbb{R}^{m \times n}。若ff连续可微，则其在X0X_0处的一阶泰勒近似f^1(⋅;X0):Rm×n→R\hat{f}_1(\cdot; X_0) : \mathbb{R}^{m \times n} \to \mathbb{R}定义为 f^1(X;X0)=f(X0)+tr⁡([∇f(X0)]⊤(X−X0)).\hat{f}_1(X; X_0) = f(X_0) + \operatorname{tr} \left( \left[ \nabla f(X_0) \right]^\top (X - X_0) \right).

优化定理

在本讲最后，介绍一个优化理论中的一个重要定理：
设f:Rn→Rf:\R^n\to\R为可微函数，Ω⊆Rn\Omega\subseteq\R^n为一开集，那么对于优化问题

min⁡x⃗∈Ωf(x⃗)\min_{\vec{x}\in\Omega}f(\vec{x})

设其最优解为x⃗∗\vec{x}^*，那么其满足∇f(x⃗∗)=0⃗\nabla f(\vec{x}^*)=\vec{0}。（这也是优化问题最优解的必要条件）