01预备知识

Lingfeng2024-09-19

01预备知识

1. 向量函数的微分

1.1 方向导数与梯度

Definition (方向导数)

设可微函数 $f:\mathbb{R}^{n}\to \mathbb{R}$ ，其在点 $\boldsymbol{x}$ 任意单位向量 $\boldsymbol{u}$ 方向上的一阶方向导数定义

\frac{ \partial f(\boldsymbol{x}) }{ \partial \boldsymbol{u} }= \lim_{ h \to 0 } \frac{f(\boldsymbol{x}+h\boldsymbol{u})-f(\boldsymbol{x})}{h}

一阶方向导数表示函数在给定方向

\boldsymbol{u}

上的变化率。当

f:\mathbb{R}\to \mathbb{R}

时，一阶方向导数即一阶导数。同理可定义二阶方向导数。

Definition (梯度)

设可微函数 $f:\mathbb{R}^{n}\to \mathbb{R}$ ，在点 $\boldsymbol{x}=\begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}$ 处的梯度是一个向量，记为 $\nabla f(\boldsymbol{x})$ 或 $\mathrm{grad}f(\boldsymbol{x})$ ，其每个分量是函数 $f$ 在该点关于各个坐标轴的偏导数，即

\nabla f(\boldsymbol{x})=\frac{ \partial f(\boldsymbol{x}) }{ \partial \boldsymbol{x} } =\begin{pmatrix} \frac{ \partial f }{ \partial x_1 } \\ \frac{ \partial f }{ \partial x_2 } \\ \vdots \\ \frac{ \partial f }{ \partial x_n } \end{pmatrix}

Theorem (方向导数与梯度向量关系)

如果 $f$ 在点 $\boldsymbol{x}$ 处可微，则在单位向量 $\boldsymbol{u}$ 上的一阶方向导数可表示为单位向量 $\boldsymbol{u}$ 与梯度的点积，即

\frac{ \partial f(\boldsymbol{x}) }{ \partial \boldsymbol{u} }=\nabla f(\boldsymbol{x})\cdot \boldsymbol{u}=\nabla f(\boldsymbol{x})^{T}\boldsymbol{u}

二阶方向导数可表示为

\frac{ \partial^{2} f(\boldsymbol{x}) }{ \partial \boldsymbol{u}^{2} }= \boldsymbol{u}^{T}H(\boldsymbol{x})\boldsymbol{u}

其中

H(\boldsymbol{x})

为Hessian矩阵，定义为

H(\boldsymbol{x})=\frac{ \partial( \nabla f(\boldsymbol{x})^{T}) }{ \partial \boldsymbol{x} } = \frac{ \partial^{2} f(\boldsymbol{x}) }{ \partial \boldsymbol{x}\partial \boldsymbol{x}^{T} } = \left( \begin{matrix} \frac{ \partial^{2} f }{ \partial x_{1}^{2} } & \frac{ \partial^{2} f }{ \partial x_{1}\partial x_{2} } & \dots & \frac{ \partial^{2} f }{ \partial x_{1}\partial x_{n} } \\ \frac{ \partial^{2} f }{ \partial x_{2}\partial x_{1} } & \frac{ \partial^{2} f }{ \partial x_{2}^{2} } & \dots & \frac{ \partial^{2} f }{ \partial x_{2}\partial x_{n} } \\ \vdots & \vdots & \ddots & \vdots \\ \frac{ \partial^{2} f }{ \partial x_{n}\partial x_{1} } & \frac{ \partial^{2} f }{ \partial x_{n}\partial x_{2} } & \dots & \frac{ \partial^{2} f }{ \partial x_{n}^{2} } \end{matrix} \right)

证明
注意到有以下引理：

Lemma (多元链式法则)

设可微函数 $f(\boldsymbol{x}):\mathbb{R}^{n}\to \mathbb{R}$ ， $\boldsymbol{x}(t):\mathbb{R}\to \mathbb{R}^{n}$ ，链式法则扩展为：

\frac{d}{dt}f(\boldsymbol{x}(t))=\nabla f(\boldsymbol{x}(t))\cdot \frac{d\boldsymbol{x}(t)}{dt}

设 $\boldsymbol{x}(t)=\begin{pmatrix} x_{1}(t) \\ x_{2}(t) \\ \vdots \\ x_{n}(t) \end{pmatrix}$ ，由多元函数链式法则

\frac{d}{dt}f(\boldsymbol{x}(t))=\sum_{i = 1}^{n} \frac{ \partial f(\boldsymbol{x}(t)) }{ \partial x_{i}(t) }\cdot \frac{dx_{i}(t)}{dt}

即

\frac{d}{dt}f(\boldsymbol{x}(t))=\nabla f(\boldsymbol{x}(t))\cdot \frac{d\boldsymbol{x}(t)}{dt}

故引理证毕。此时设

\gamma(t)=\boldsymbol{x}+t\boldsymbol{u}

，由引理有

\begin{align*} \frac{d}{dt}f(\gamma(t)) & =\nabla f(\gamma(t))\cdot \frac{d\gamma(t)}{dt} \\ & = \nabla f(\boldsymbol{x}+t\boldsymbol{u})\cdot \boldsymbol{u} \end{align*}

因此

\frac{ \partial f(\boldsymbol{x}) }{ \partial \boldsymbol{u} } = \frac{d}{dt}f(\gamma(t))\Big|_{t=0}=\nabla f(\boldsymbol{x})\cdot \boldsymbol{u}

此时继续求导

\begin{align*} \frac{ d^{2} f(\gamma(t)) }{ d t^{2} } & =\frac{ d }{ d t } \left( \frac{ d f(\gamma(t)) }{ d t } \right) \\ & = \frac{d(\nabla f(\gamma(t))^{T})}{dt}\boldsymbol{u} \end{align*}

由链式法则

\begin{align*} \frac{d(\nabla f(\gamma(t))^{T})}{dt} & = \frac{d\gamma(t)^{T}}{dt} \frac{ \partial( \nabla f(\gamma(t))^{T}) }{ \partial \gamma(t) } \\ & = \boldsymbol{u}^{T}H(\boldsymbol{x}+t\boldsymbol{u}) \end{align*}

因此

\frac{ d^{2} f(\gamma(t)) }{ d t^{2} }=\boldsymbol{u}^{T}H(\boldsymbol{x}+t\boldsymbol{u})\boldsymbol{u}

故

\frac{ \partial^{2} f(\boldsymbol{x}) }{ \partial \boldsymbol{u}^{2} } =\frac{ d^{2} f(\gamma(t)) }{ d t^{2} }\Big|_{t=0}=\boldsymbol{u}^{T}H(\boldsymbol{x})\boldsymbol{u}

Corollary (梯度性质)

梯度指向函数增长最快的方向，其大小为函数变化率的最大值。

1.2 向量函数的中值定理与泰勒展开

Theorem (向量函数的Lagrange中值定理)

设函数 $f:\mathbb{R}^{n}\to \mathbb{R}$ 在闭球 $\overline{B}(\boldsymbol{a},\boldsymbol{b})$ 上连续，开球 $B(\boldsymbol{a},\boldsymbol{b})$ 内可微，则存在 $\boldsymbol{c}$ 在 $\boldsymbol{a}$ 和 $\boldsymbol{b}$ 之间的连线上，使得

f(\boldsymbol{b})-f(\boldsymbol{a})=\nabla f(\boldsymbol{c})\cdot(\boldsymbol{b}-\boldsymbol{a})

证明
定义 $g:[0,1]\to \mathbb{R}$ ，有

g(t)=f(\boldsymbol{a}+t(\boldsymbol{b}-\boldsymbol{a}))

显然

g

在区间

[0,1]

上连续，

(0,1)

内可微。由一元中值定理，存在

\theta \in(0,1)

使得

g(1)-g(0)=g'(\theta)(1-0)

注意到由链式法则

g'(\theta)=\nabla f(\boldsymbol{a}+\theta(\boldsymbol{b}-\boldsymbol{a}))\cdot(\boldsymbol{b}-\boldsymbol{a})

因此有

f(\boldsymbol{b})-f(\boldsymbol{a})=\nabla f(\boldsymbol{c})\cdot(\boldsymbol{b}-\boldsymbol{a})

其中

\boldsymbol{c}=\boldsymbol{a}+\theta(\boldsymbol{b}-\boldsymbol{a})

。

Theorem (向量函数的Taylor展开)

在这里我们只给出二阶的形式。设可微函数 $f:\mathbb{R}^{n}\to \mathbb{R}$ ，则在 $\boldsymbol{x}+t\boldsymbol{u}$ 处的二阶泰勒展开式为

\begin{align*} f(\boldsymbol{x}+t\boldsymbol{u}) & =f(\boldsymbol{x})+t \frac{ \partial f(\boldsymbol{x}) }{ \partial \boldsymbol{u} } +\frac{t^{2}}{2!} \frac{ \partial^{2} f(\boldsymbol{x}) }{ \partial \boldsymbol{u}^{2} } +o(t^{2}) \\ & =f(\boldsymbol{x})+t \nabla f(\boldsymbol{x})^{T}\boldsymbol{u} +\frac{t^{2}}{2!}\boldsymbol{u} ^{T}H(\boldsymbol{x})\boldsymbol{u} +o(t^{2}) \end{align*}

证明
设 $g(t)=f(\boldsymbol{x}+t\boldsymbol{u})$ ，下面对 $g(h)$ 进行泰勒展开，有

g(t)=g(0)+g'(0)t+\frac{g''(0)}{2!}t^{2}+o(t^{2})

而已证

\begin{align*} g'(0) & =\frac{ \partial f(\boldsymbol{x}) }{ \partial \boldsymbol{u} }\\ g''(0) & =\frac{ \partial^{2} f(\boldsymbol{x}) }{ \partial \boldsymbol{u}^{2} } \end{align*}

故证毕。

Corollary (最优化条件)

（一阶必要条件）设 $f(\boldsymbol{x}) \in C^{1}$ ， $\boldsymbol{x}^{*}$ 为 $f(\boldsymbol{x})$ 的一个局部极小点，则

\nabla f(\boldsymbol{x}^{*})=0

（二阶必要条件）设

f(\boldsymbol{x})\in C^{2}

，

\boldsymbol{x}^{*}

为

f(\boldsymbol{x})

的一个局部极小点，则

H(\boldsymbol{x}^{*})

半正定。
（二阶充分条件）设

f(\boldsymbol{x})\in C^{2}

，在点

\boldsymbol{x}^{*}

有

g(\boldsymbol{x}^{*})=0

，且

H(\boldsymbol{x}^{*})

正定时，

\boldsymbol{x}^{*}

为

f(\boldsymbol{x})

的严格局部极小点。

证明
考虑反证法。若 $\nabla f(\boldsymbol{x}^{*})\neq 0$ ，则取 $\boldsymbol{d}=-\nabla f(\boldsymbol{x}^{*})$ ，有

\nabla f(\boldsymbol{x}^{*})\cdot \boldsymbol{d}=-\left\lVert \boldsymbol{d} \right\rVert<0

由

\nabla f(\boldsymbol{x})

连续性知，

\phi(\boldsymbol{x})=\nabla f(\boldsymbol{x})\cdot \boldsymbol{d}

也是连续的。由保号性知，存在

\delta>0

，当

h \in(0,\delta)

时有

\phi(x^{*}+h \boldsymbol{d})=\nabla f(\boldsymbol{x}^{*}+h \boldsymbol{d})\cdot \boldsymbol{d}<0

此时由中值定理，对于任意的

t\in(0,\delta)

，存在

h\in(0,t)

，使得

f(\boldsymbol{x}^{*}+t\boldsymbol{d})-f(\boldsymbol{x}^{*})=\nabla f(\boldsymbol{x}^{*}+h\boldsymbol{d})\cdot t\boldsymbol{d}<0

与

\boldsymbol{x}^{*}

为局部极小点矛盾，因而得到

\nabla f(\boldsymbol{x}^{*})=0

。

二阶必要条件类似的使用 Taylor 展开式 Lagrange 余项。假设存在 $\boldsymbol{d}\in\mathbb{R}^{n}$ ，使得 $\boldsymbol{d}^{T}H(\boldsymbol{x}^{*})\boldsymbol{d}<0$ ，同样由连续性知，存在 $\delta>0$ ，对任意 $h \in(0,\delta)$ 有

\boldsymbol{d^{T}}H(\boldsymbol{x}^{*}+h\boldsymbol{d})\boldsymbol{d}<0

此时对于任意

t\in(0,\delta)

，存在

h\in(0,t)

，有

f(\boldsymbol{x}^{*}+t\boldsymbol{d})=f(\boldsymbol{x^{*}})+ \frac{t^{2}}{2}\boldsymbol{d}^{T}H(\boldsymbol{x}^{*}+h\boldsymbol{d})\boldsymbol{d}

因此

f(\boldsymbol{x}^{*}+t\boldsymbol{d})<f(\boldsymbol{x}^{*})

与

\boldsymbol{x}^{*}

为局部极小值矛盾。

2. 凸集和凸函数

2.1 凸集

Definition (凸集)

设集合 $C\subset\mathbb{R}^{n}$ ，若对于任意 $\boldsymbol{x}$ ， $\boldsymbol{y} \in C$ ，有

\theta \boldsymbol{x}+(1-\theta)\boldsymbol{y} \in C, \quad\theta \in[0,1]

则称

C

为凸集。

2.2 凸函数

Definition (凸函数)

设集合 $C\subset \mathbb{R}^{n}$ 为非空凸集，函数 $f:C\to \mathbb{R}$ 。若对任意 $\boldsymbol{x}$ ， $\boldsymbol{y}\in C$ ，有

f(\theta \boldsymbol{x}+(1-\theta)\boldsymbol{y})\leq\theta f(\boldsymbol{x})+(1-\theta)f(\boldsymbol{y}),\quad\theta \in[0,1]

则称

f

为

C

上凸函数。若不等式对于

\boldsymbol{x}\neq \boldsymbol{y}

严格成立，则称为严格凸函数。

Theorem (凸函数的判定条件)

（一阶判定条件） $f(\boldsymbol{x})$ 为凸函数当且仅当对于任意 $\boldsymbol{x}$ ， $\boldsymbol{ y \in C}$ ，有

f(\boldsymbol{y})\geq f(\boldsymbol{x})+\nabla f(\boldsymbol{x})^{T}(\boldsymbol{y}-\boldsymbol{x})

（二阶判断条件）

f(\boldsymbol{x})

为凸函数当且仅当对于任意

\boldsymbol{x}\in C

，Hessian矩阵半正定。

Definition (强凸函数)

$f(x)$ 是 $\mu$ -强凸，如果满足

f(y)\geq f(x)+g(x)^{T}(y-x)+\frac{\mu}{2}\left\lVert y-x \right\rVert ^{2},\quad \forall x,y\in \mathbb{R}^{n}

2.3 凸函数与凸集的关系

Definition (上图)

设集合 $C\subset \mathbb{R}^{n}$ 为非空凸集，函数 $f:C\to \mathbb{R}$ 上图为

\mathrm{epi}(f)=\{ (\boldsymbol{x},t)\mid x \in C,t\in R,f(x) \leq t \}\subset \mathbb{R}^{n+1}

Theorem (凸函数与凸集的关系)

设集合 $C\subset \mathbb{R}^{n}$ 为非空凸集，函数 $f:C\to \mathbb{R}$ 是凸函数当且仅当它的上图是凸集。

01预备知识

ON THIS PAGE