1、最优化理论的基础

以下的内容是关于多元函数知识，也是最优化理论的基础，仅仅是需要《数学分析》的知识。

1、梯度与黑塞矩阵

定义1：设 $~n~$ 元函数 $~f(x)~$ 对自变量 $~x=(x_1,x_2,\dots,x_n)^T~$ 各自分量 $~x_i~$ 的一阶偏导数为
$\frac{\partial f(x)}{\partial x_i},~~~i=1,2,\dots,n$
那么称向量
$\nabla f(x)=(\frac{\partial f(x)}{\partial x_1},\frac{\partial f(x)}{\partial x_2},\dots,\frac{\partial f(x)}{\partial x_n})^T$
为函数 $~f(x)~$ 在 $~x~$ 处的一阶导数或梯度

定义2：设 $~n~$ 元函数 $~f(x)~$ 对自变量 $~x=(x_1,x_2,\dots,x_n)^T~$ 各自分量 $~x_i~$ 的二阶偏导数为
$\frac{\partial^2 f(x)}{\partial x_i x_j},~~~i,j=1,2,\dots,n$
那么称矩阵
$\nabla^2 f(x)=\begin{pmatrix} \frac{\partial^2 f(x)}{\partial x_1^2 }&\frac{\partial^2 f(x)}{\partial x_1 x_2}&\dots&\frac{\partial^2 f(x)}{\partial x_i x_n}\\ \frac{\partial^2 f(x)}{\partial x_2 x_1}&\frac{\partial^2 f(x)}{\partial x_2^2 }&\dots&\frac{\partial^2 f(x)}{\partial x_2 x_n}\\ \vdots&\vdots&&\vdots\\ \frac{\partial^2 f(x)}{\partial x_n x_1 }&\frac{\partial^2 f(x)}{\partial x_n x_2 }&\cdots&\frac{\partial^2 f(x)}{\partial x_n ^2 } \end{pmatrix}$
为函数 $~f(x)~$ 在 $~x~$ 处的二阶导数矩阵或 $~Hessen~$ 矩阵

定义3：如果 $~f(x)~$ 梯度的所有分量函数在 $~x~$ 都连续，则称 $~f(x)~$ 在 $~x~$ 连续可微；如果 $~f(x)~$ 的 $~Hessen~$ 矩阵的各个分量函数都连续，则 $~f(x)~$ 在 $~x~$ 二阶连续可微。

定义4：如果 $~f~$ 在开集 $~D~$ 上每一点都连续可微，则称 $~f~$ 在 $~D~$ 上一阶连续可微；如果如果 $~f~$ 在开集 $~D~$ 上每一点上二阶连续可微，则称 $~f~$ 在 $~D~$ 上二阶连续可微

注：(1)、定义4中之所以选择开集 $~D~$ ，而不是闭集，是因为闭集的边界不可微
(2)、如果 $~f(x)~$ 在 $~x~$ 二阶连续可微，则
$\frac{\partial^2 f(x)}{\partial x_i x_j }=\frac{\partial^2 f(x)}{\partial x_j x_x }$
即表明 $~\nabla^2 f(x)~$ 是一个对称矩阵

例1：设 $A\in\mathbb{R}^{nxn}$ , $~b\in\mathbb{R}^n~$ ,求二次函数
$f(x)=\frac{1}{2}x^TAx+b^Tx$
在 $~x~$ 的梯度和 $~Hesse~$ 矩阵
解：由于 $\begin{aligned} f(x)&=\frac{1}{2}\sum_{i=1}^{i=n}\sum_{j=1}^{j=n}a_{ij}x_ix_j+\sum_{i=1}^{i=n}b_ix_i\\ \end{aligned}$
则 $~k=1,2,\cdots,n~$ 时
$\begin{aligned} \frac{\partial f(x)}{\partial x_k}&=\frac{1}{2}\sum_{j=1,j\neq k}^{j=n}a_{kj}x_j+\frac{1}{2}\sum_{i=1,i\neq k}^{i=n}a_{ik}x_i+a_{kk}x_k+b_k\\ &=\frac{1}{2}\sum_{j=1}^{j=n}a_{kj}x_j+\frac{1}{2}\sum_{i=1}^{i=n}a_{ik}x_i+b_k \end{aligned}$
故 $~\frac{\partial f(x)}{\partial x}=\frac{1}{2}(A+A^T)x+b~$
和上面的分析类似，我们可以证明 $~\nabla^2f(x)=\frac{1}{2}(A+A^T)~$

2、方向导数

定义5：设 $~f:\mathbb{R}^n\rightarrow\mathbb{R}~$ 在开集 $~D~$ 上连续可微，对于 $~x\in\mathbb{R}^n,d\in\mathbb{R}^n~$ ,则 $~f~$ 在点 $~x~$ 关于方向 $~d~$ 的方向导数定义为
$\frac{\partial f}{\partial d}(x)=\lim_{\theta\rightarrow0}\frac{f(x+\theta d)-f(x)}{\theta}$
上述定义的方向导数等于 $~\nabla f(x)^Td~$ ,其中 $~\nabla f(x)~$ 表示 $~f~$ 在 $~x~$ 处的梯度， $~d~$ 为方向.

注：(1)、显然方向导数是偏导数的推广，偏导数刻画的函数沿着特定方向的微商,而方向导数是任意方向的微商
(2)、就是关于这里方向导数的定义，采用的我后面参考的几本书上其中的定义，不过我当时一看觉得有问题，我当时认为方向导数应该这样定义
$\frac{\partial f}{\partial d}(x)=\lim_{\theta\rightarrow0}\frac{f(x+\theta d)-f(x)}{\theta \Vert d\Vert}$
上面的范数我们就取欧式范数，或者原始的定义方向选取的是单位方向。后来在维基百科发现方向导数的定义，它认为两者都可以，仔细一想，才是我狭隘了。如果有人留意此贴，希望大家思考一下。

3、多元函数的泰勒公式

定义6：若 $~f(x)~$ 在 $~D~$ 上一阶连续可微，对任何 $~x,x+d\in D~$ 则有
$f(x+d)=f(x)+\nabla f(x)^Td+o(\Vert d\Vert)~~~~~~~麦克劳林余项$
$f(x+d)=f(x)+\nabla f(x+td)^Td,~~t\in(0,1)~~~柯西余项$
$f(x+d)=f(x)+\int_{0}^{1}\nabla f(x+td)^Tddt~~~~积分余项$
定义7：若 $~f(x)~$ 在 $~D~$ 上二阶连续可微，对任何 $~x,x+d\in D~$ 则有
$f(x+d)=f(x)+\nabla f(x)^Td+\frac{1}{2}d^T\nabla^2f(x)d+o(\Vert d\Vert^2)~~~~~~~麦克劳林余项$
$f(x+d)=f(x)+\nabla f(x)^Td+\frac{1}{2}d^T\nabla^2f(x+td)d~~t\in(0,1)~~~柯西余项$
$f(x+d)=f(x)+\nabla f(x)^Td+\int_{0}^{1}(1-t)[d^T\nabla^2 f(x+td)d]dt~~~~积分余项$
证明：因为这个不是很显然
我们利用一元函数的泰勒展开证明，令 $~\phi(t)=f(x+td)~$
则 $~\phi'(t)=\nabla f(x+td)^Td~$ , $~\phi''(t)=d^T\nabla ^2f(x+td)d~$ ，由 $~\phi(1)-\phi(0)=\int_{0}^{1}\phi'(t)dt~$ 知
$\begin{aligned} f(x+d)-f(x)&=\int_{0}^{1}[\nabla f(x+td)^Td]dt=-\int_{0}^{1}[\nabla f(x+td)^Td]d(1-t)\\ &=(t-1)\nabla f(x+td)^Td|_0^1+\int_0^1(1-t)d[\nabla f(x+td)^Td]\\ &=\nabla f(x)^Td+\int_0^1(1-t)[d^T\nabla f(x+td)^Td]dt \end{aligned}$

4、两个普通公式的证明

此处是我临时起意加上的，肯定很多书上也找不到，主要的是
定义8：若 $~f(x)~$ 在 $~开集D~\in\mathbb{R}^n$ 上二阶连续可微，对任何 $~x,x+td\in D~$ 则有
$\frac{d f(x+td)}{d t}=\nabla f(x+td)^Td$
$\frac{d^2 f(x+td)}{d t^2}=d^T\nabla^2 f(x+td)d$
这个公式我们在上面的证明中用到，但是看起来却不是那么显然，我来证明一下：
证明： $\begin{aligned} \frac{d f(x+td)}{d t}&=\frac{df(x_1+td_1,x_2+td_2,\cdots,x_n+td_n)}{dt}\\ &=\frac{\partial f(x+td)}{\partial (x_1+td_1)}d_1+\frac{\partial f(x+td)}{\partial (x_2+td_2)}d_2+\cdots+\frac{\partial f(x+td)}{\partial (x_n+td_n)}d_n\\ &=(\frac{\partial f(x+td)}{\partial (x_1+td_1)},\frac{\partial f(x+td)}{\partial (x_2+td_2)},\cdots,\frac{\partial f(x+td)}{\partial (x_n+td_n)})\begin{pmatrix} d_1\\d_2\\\vdots\\d_n \end{pmatrix}\\ &=(\frac{\partial f(x+td)}{\partial x_1},\frac{\partial f(x+td)}{\partial x_2},\cdots,\frac{\partial f(x+td)}{\partial x_n})\begin{pmatrix} d_1\\d_2\\\vdots\\d_n \end{pmatrix}\\ &=\nabla f(x+td)^Td \end{aligned}$
$\begin{aligned} \frac{d^2 f(x+td)}{d t^2}&=\frac{d^2f(x_1+td_1,x_2+td_2,\cdots,x_n+td_n)}{dt^2}\\ &=\frac{\partial^2 f(x+td)}{\partial^2(x_1+td_1)}d_1^2+\frac{\partial^2 f(x+td)}{\partial (x_1+td_1)\partial (x_2+td_2)}d_1d_2+\cdots+\frac{\partial^2 f(x+td)}{\partial (x_1+td_1)\partial (x_n+td_n)}d_1d_n\\ &+\frac{\partial^2 f(x+td)}{\partial(x_2+td_2)\partial(x_1+td_1)}d_2d_1+\frac{\partial^2f(x+td)}{\partial^2(x_2+td_2)}d_2^2+\cdots+\frac{\partial^2 f(x+td)}{\partial(x_2+td_2)\partial(x_n+td_n)}d_2d_n\\ &~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\vdots\\ &+\frac{\partial^2 f(x+td)}{\partial(x_n+td_n)\partial(x_1+td_1)}d_nd_1+\frac{\partial^2 f(x+td)}{\partial(x_n+td_n)\partial(x_2+td_2)}d_nd_2+\cdots+\frac{\partial^2 f(x+td)}{\partial^2(x_n+td_n)}d_2d_n\\ &=\begin{pmatrix} d_1&d_2&\cdots&d_n \end{pmatrix}\begin{pmatrix} \frac{\partial^2 f(x+td)}{\partial^2x_1}&\frac{\partial^2 f(x+td)}{\partial x_1\partial x_2}\cdots&\frac{\partial^2 f(x+td)}{\partial x_1\partial x_n}\\ \frac{\partial^2 f(x+td)}{\partial x_2\partial x_1}&\frac{\partial^2 f(x+td)}{\partial^2x_2}\cdots&\frac{\partial^2 f(x+td)}{\partial x_2\partial x_n}\\ \vdots&\vdots&\vdots&\\ \frac{\partial^2 f(x+td)}{\partial x_n\partial x_1}&\frac{\partial^2 f(x+td)}{\partial x_n\partial x_2}\cdots&\frac{\partial^2 f(x+td)}{\partial^2x_n} \end{pmatrix}\begin{pmatrix} d_1\\d_2\\\vdots\\d_n \end{pmatrix}\\ &=d^T\nabla^2f(x+td)d \end{aligned}$

此次内容参考书籍：
[1]、倪勤：最优化方法与程序设计
[2]、袁亚湘,孙文瑜：最优化理论与方法

1、最优化理论的基础