六、梯度分析与最优化问题

最优化问题是信息科学中经常遇到的一类问题，无约束最优化问题：

\[\min_{x \in R}f(x)\]

目标函数的极小化

定义1.1点$x^{*}$称为函数$f(x)$的全局极小点，若

\[f(x^{*}) \leq f(x),\forall x \in R\]

大多数最优化算法只能求出局部极小点，也就是说求得函数在该邻域内的最小值。

定义1.2给定一个点$\overline{x} \in R$，则点$\overline{x}$的（闭）邻域是满足$|x - \overline{x}| \leq \delta(\delta > 0)$的所有点$x$的集合。

推广到向量$x \in R^{n}$的$\Delta$邻域。

定义1.3点$x^{*}$称为函数$f(x)$的局部极小点，若存在某个标量$\delta > 0$，使得$f(x^{*}) \leq f(x)$对所有满足$0 < \parallel x - x^{*} \parallel \leq \delta$的邻域$x$均成立。

定义1.4点$x^{*}$称为函数$f(x)$的严格局部极小点，若存在某个标量$\delta > 0$，使得$f(x^{*}) < f(x)$对所有满足$0 < \parallel x - x^{*} \parallel \leq \delta$的邻域$x$均成立。

局部极小点和严格局部极小点有时也分别称为函数$f(x)$的弱局部极小点(weak local minimizer)和强局部极小点(strong local minimizer)。

如果函数具有连续的二阶导数，那么在$x$的一个很小的邻域$\Delta x$内，就可以用Taylor级数展开

\[f(x + \Delta x) = f(x) + f^{\prime}(x)\Delta x + \frac{1}{2}f^{\prime\prime}(x)(\Delta x)^{2} + \ldots\]

作为函数$f(x + \Delta x)$的逼近，其中$f^{\prime}(x) = \frac{df(x)}{dx}$和$f^{\prime\prime}(x) = \frac{d^{2}f(x)}{dx^{2}}$分别表示$f(x)$的一阶和二阶导数。由于$\Delta x$很小，式中忽略了$\Delta x$的高阶项。

满足$f^{\prime}(x) = 0$的点$x$称为函数$f(x)$的平稳点，它有可能是极小（大）点或拐点。

如果函数$f(x)$是二阶连续可微的，求该函数的局部极小点最基本的方法是逐次联合求解

\[f^{\prime}(x) = \frac{df(x)}{dx} = 0\]

\[f^{\prime\prime}(x) = \frac{d^{2}f(x)}{dx^{2}} \geq 0\]

若没有第二个方程，则第一个方程的解只是平稳点。以上两个方程只是目标函数取局部极小点的充分条件，而不是必要条件（求局部极大值类似）。

设$f(x)$是实值函数，则有以下定义：

函数$f(x)$称为凸函数，对任意选择的点$x_{1},x_{2}$及标量$\alpha \neq 0$，满足$f(\alpha x_{1} + (1 - \alpha)x_{2}) \leq \alpha f(x_{1}) + (1 - \alpha)f(x_{2})$
函数$f(x)$称为严格凸函数，对任意选择的点$x_{1},x_{2}$及标量$\alpha \neq 0$，满足$f(\alpha x_{1} + (1 - \alpha)x_{2}) < \alpha f(x_{1}) + (1 - \alpha)f(x_{2})$
函数$f(x)$称为(严格)凹函数，若$- f(x)$为(严格)凸函数。

实值函数相对于实向量的梯度

以$n \times 1$实向量$x$为变元的实标量函数$f(x)$相对于$x$的梯度为一$n \times 1$列向量，定义为

\[\Delta_{x}f(x) = \lbrack\frac{\partial f(x)}{\partial x_{1}},\frac{\partial f(x)}{\partial x_{2}},\ldots,\frac{\partial f(x)}{\partial x_{n}}\rbrack^{T} = \frac{\partial f(x)}{\partial x}\]

梯度方向的负方向称为变元$x$的梯度流，记作

\[\dot{x} = - \Delta_{x}f(x) = - \frac{\partial f(x)}{\partial x}\]

从梯度的定义可以看出：

一个以向量为变元的标量函数的梯度为一向量；
梯度的每个分量给出了标量函数在该分类方向上的变化率；

类似地，实值函数$f(x)$相对于$1 \times n$行向量$x^{T}$的梯度为$1 \times n$行向量，定义为:

\[\frac{\partial f(x)}{\partial x^{T}} = \lbrack\frac{\partial f(x)}{\partial x_{1}},\frac{\partial f(x)}{\partial x_{2}},\ldots,\frac{\partial f(x)}{\partial x_{n}}\rbrack\]

$m$维行向量函数$F(x) = \lbrack f_{1}(x),f_{2}(x),\ldots,f_{m}(x)\rbrack_{1 \times m}$相对于$n$维实向量$x$的梯度为一$n \times m$矩阵，定义为：

\[\frac{\partial F(x)}{\partial x} = \begin{bmatrix} \frac{\partial f_{1}(x)}{\partial x_{1}} & \frac{\partial f_{2}(x)}{\partial x_{1}} & \ldots & \frac{\partial f_{m}(x)}{\partial x_{1}} \\ \frac{\partial f_{1}(x)}{\partial x_{2}} & \frac{\partial f_{2}(x)}{\partial x_{2}} & \ldots & \frac{\partial f_{m}(x)}{\partial x_{2}} \\ \vdots & \vdots & \vdots & \vdots \\ \frac{\partial f_{1}(x)}{\partial x_{n}} & \frac{\partial f_{2}(x)}{\partial x_{n}} & \ldots & \frac{\partial f_{m}(x)}{\partial x_{n}} \\ \end{bmatrix}_{n \times m}\]

向量函数的两个特例：

若$m \times 1$向量函数$f(x) = y = \lbrack y_{1},y_{2},\ldots,y_{m}\rbrack^{T}$，其中$y_{1},y_{2},\ldots,y_{m}$是$x$的标量函数，则一阶梯度为

\[\frac{\partial y}{\partial x^{T}} = \begin{bmatrix} \frac{\partial y_{1}}{\partial x_{1}} & \frac{\partial y_{1}}{\partial x_{2}} & \ldots & \frac{\partial y_{1}}{\partial x_{n}} \\ \frac{\partial y_{2}}{\partial x_{1}} & \frac{\partial y_{2}}{\partial x_{2}} & \ldots & \frac{\partial y_{2}}{\partial x_{n}} \\ \vdots & \vdots & \vdots & \vdots \\ \frac{\partial y_{m}}{\partial x_{1}} & \frac{\partial y_{m}}{\partial x_{2}} & \ldots & \frac{\partial y_{m}}{\partial x_{n}} \\ \end{bmatrix}_{m \times n}\]

称为向量函数$\lbrack y_{1},y_{2},\ldots,y_{m}\rbrack^{T}$的Jacobi矩阵。
若$f(x) = (x_{1},x_{2},\ldots,x_{m})^{T}$，则$\frac{\partial f(x)}{\partial x} = \frac{\partial x^{T}}{\partial x} = I$

实值函数$f(x)$相对于列向量$x$的下述一些常用的梯度公式：

若$f(x) = c$为常数，则梯度$\frac{\partial c}{\partial x} = 0$;
线性法则: 若$f(x)$和$g(x)$都是向量$x$的实值函数，$c_{1},c_{2}$为实常数，则

\[\frac{\partial\lbrack c_{1}f(x) + c_{2}g(x)\rbrack}{\partial x} = c_{1}\frac{\partial f(x)}{\partial x} + c_{2}\frac{\partial g(x)}{\partial x}\]

.
乘法法则：若$f(x)$和$g(x)$都是向量$x$的实值函数，则

\[\frac{\partial\lbrack f(x)g(x)\rbrack}{\partial x} = g(x)\frac{\partial f(x)}{\partial x} + f(x)\frac{\partial g(x)}{\partial x}\]

商法则：若$g(x) \neq 0$，则

\[\frac{\partial\lbrack f(x)/g(x)\rbrack}{\partial x} = \frac{1}{g^{2}(x)}\lbrack g(x)\frac{\partial f(x)}{\partial x} - f(x)\frac{\partial g(x)}{\partial x}\rbrack\]

链式法则：若$y(x)$是$x$的向量值函数，则

\[\frac{\partial f(y(x))}{\partial x} = \frac{\partial y^{T}(x)}{\partial x}\frac{\partial f(y)}{\partial y}\]

式中$\frac{\partial y^{T}(x)}{\partial x}$为$n \times n$矩阵。
若$n \times 1$向量$a$是常量向量，与向量$x$无关，则

\[\frac{\partial a^{T}x}{\partial x} = a,\frac{\partial x^{T}a}{\partial x} = a\]

若$n \times 1$向量$a$是常数向量，与向量$x$无关，则

\[\frac{\partial a^{T}y(x)}{\partial x} = \frac{\partial y^{T}(x)}{\partial x}a,\frac{\partial y^{T}(x)a}{\partial x} = \frac{\partial y^{T}(x)}{\partial x}a\]

To be continued...

迹函数的梯度矩阵

二次型目标函数的迹等于函数本身，即$f(x) = x^{T}Ax = tr(x^{T}Ax)$.利用迹的性质，又可以将目标函数进一步表示成

\[f(x) = x^{T}Ax = tr(x^{T}Ax) = tr(Axx^{T})\]

迹的梯度矩阵的常用公式：

单个矩阵的迹的梯度矩阵，

$W$是 $m \times m$矩阵时，有$\frac{\partial tr(W)}{\partial W} = I_{m}$

$W$是$m \times m$可逆矩阵时，$\frac{tr(W^{- 1})}{\partial W} = - (W^{- 2})^{T}$

对于两个向量的外积，有

\[\frac{\partial tr(xy^{T})}{\partial x} = \frac{\partial tr(y^{T}x)}{\partial x} = y\]

两个矩阵乘积的迹的梯度，若$W \in R^{m \times n},A \in R^{n \times m,}$则

\[\frac{\partial tr(WA)}{\partial W} = \frac{\partial tr(AW)}{\partial W} = A^{T}\]

特别地当$W$为对称矩阵，有

\[\frac{\partial tr(WA)}{\partial W} = \frac{\partial tr(AW)}{\partial W} = A + A^{T} - diag(A)\]

若$W \in R^{m \times n},A \in R^{n \times m,}$则

\[\frac{\partial tr(W^{T}A)}{\partial W} = \frac{\partial tr(AW^{T})}{\partial W} = A\]

若$W \in R^{m \times n}$，则$\frac{\partial tr(WW^{T})}{\partial W} = \frac{\partial tr(W^{T}W)}{\partial W} = 2W$

若$W \in R^{m \times m}$，则$\frac{\partial tr(W^{2})}{\partial W} = \frac{\partial tr(WW)}{\partial W} = 2W^{T}$

若$W,A \in R^{m \times m}$，并且$W$非奇异，则

\[\frac{\partial tr(AW^{- 1})}{\partial W} = - (W^{- 1}AW^{- 1})^{T}\]

三个矩阵乘积的迹的矩阵

若$W \in R^{m \times n},A \in R^{m \times m},$则$\frac{\partial tr(W^{T}AW)}{\partial W} = (A + A^{T})W$

特别地，当$A$为对称矩阵时，有$\frac{\partial tr(W^{T}AW)}{\partial W} = 2AW$.

若$W \in R^{m \times n},A \in R^{n \times n},$则

\[\frac{\partial tr(W^{T}AW)}{\partial W} = W(A + A^{T})\]

当$A$为对称矩阵时，$\frac{\partial tr(W^{T}AW)}{\partial W} = 2WA$

若$W,A,B \in R^{m \times m}$，并且$W$非奇异时，则有

\[\frac{\partial tr(AW^{- 1}B)}{\partial W} = - (W^{- 1}BAW^{- 1})^{T}\]

Hessian矩阵

实值函数$f(x)$相对于$n \times 1$实向量$x$的二阶梯度是一个由$n^{2}$个二阶梯度组成的矩阵(称为Hessian矩阵)，定义为

\[\frac{\partial^{2}f(x)}{\partial x\partial x^{T}} \triangleq \frac{\partial}{\partial x}\lbrack\frac{\partial f(x)}{\partial x^{T}}\rbrack\]

或者简写为梯度的梯度

\[\nabla_{x}^{2}f(x) = \nabla_{x}(\nabla_{x^{T}}f(x))\]

其中$(i,j)$元素是

\[\lbrack\frac{\partial^{2}f(x)}{\partial x\partial x^{T}}\rbrack_{ij} = \frac{\partial^{2}f(x)}{\partial x_{i}\partial x_{j}}\]

所以当$x$是$n \times 1$的向量时，$f(x)$的二阶导数矩阵，也就是Hessian矩阵是$n \times n$的对称的。

局部极小点的条件

如果$\parallel \Delta x \parallel^{2} = (\Delta x)^{T}(\Delta x)$，则函数$f(x)$的Taylor级数展开为

\[f(x + \Delta x) \approx f(x) + (\Delta x)^{T}\nabla_{x}f(x) + \frac{1}{2}(\Delta x)^{T}\nabla_{x}^{2}f(x)(\Delta x)\]

下面介绍判断一个局部极小点的条件。

定理8.1(一阶必要条件) 若$x^{*}$是一个局部极小点，并且$f(x)$在点$x^{*}$的一个开邻域$\Delta x$里是连续可微分的，则$\nabla_{x}f(x^{*}) = 0$.

定理6.2(二阶必要条件)若$x^{*}$是$f(x)$的局部极小点，并且$\nabla_{x}^{2}f(x)$在$x^{*}$的开邻域$\Delta x$内连续，则

\[\nabla_{x}f(x^{*}) = 0,\nabla_{x}^{2}f(x^{*}) \geq 0\]

其中$\nabla_{x}^{2}f(x^{*}) \geq 0$表示矩阵$\nabla_{x}^{2}f(x^{*})$半正定。

定理6.3(二阶充分条件)假设$f(x)$在$x^{*}$的开邻域内连续，并且

\[\nabla_{x}f(x^{*}) = 0,\nabla_{x}^{2}f(x^{*}) > 0\]

则$x^{*}$是函数$f(x)$的严格局部极小点。

定理6.4凸函数$f(x)$的任何局部极小点$x^{*}$都是该函数的一个全局极小点。若凸函数$f(x)$是可微分，则满足$\nabla_{x}f(x) = 0$的平稳点$x^{*}$是$f(x)$的一个全局极小点。

当$A$是$n$阶对称正定矩阵时，函数$f(x) = x^{T}Ax$是严格凸函数。

考虑一个特殊的优化问题，所谓线性约束的二次规划问题

\[\min_{x \in R^{n}}J(x) = \frac{1}{2}x^{T}Gx + x^{T}d\]

满足约束条件

\[Ax = b\]

其中$A \in R^{m \times n},rank(A) = m,$若$G \in R^{n \times n}$为对称正定，这成为正定二次规划问题。

利用Lagrange乘子法，定义目标函数

\[q(x) = \frac{1}{2}x^{T}Gx + x^{T}d + \lambda^{T}(b - Ax)\]

则有$\frac{\partial q(x)}{\partial x} = 0$和$\frac{\partial q(x)}{\partial\lambda} = 0$，得到线性方程组

\[\left\{ \begin{matrix} Gx - A^{T}\lambda = - d \\ Ax = b \\ \end{matrix} \right.\ \]

也就是最优解$x^{*},\lambda^{*}$满足方程组

\[\begin{bmatrix} G & - A^{T} \\ A & 0 \\ \end{bmatrix}\begin{bmatrix} x^{*} \\ \lambda^{*} \\ \end{bmatrix} = \begin{bmatrix} - d \\ b \\ \end{bmatrix}\]

令$x$是$Ax = b$的任一解，则取$x^{*} = x + p$，则得

$$\begin{bmatrix} G & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} -p \\ \lambda^* \end{bmatrix} = \begin{bmatrix} h \\ c \end{bmatrix} \tag{7.4}$$

其中$c = Ax - b,h = d + Gx,p = x^{*} - x$

这里矩阵

$$K = \begin{bmatrix} G & A^T \\ A & 0 \end{bmatrix} \tag{7.6}$$

称为Karush-Kuhn-Tucker(KKT)矩阵，方程组(7.4)称为KKT系统，有时也称为鞍点问题（系统）。所以解二次规划问题的核心就转化为如何求解对称不定问题（7.4）。

主要介绍以下几种方法

秩空间方法

假设系数矩阵$K$和子矩阵$G$均非奇异，则根据分块矩阵求逆的公式可以求出KKT矩阵的逆矩阵为

\[\begin{bmatrix} G & A^{T} \\ A & 0 \\ \end{bmatrix}^{- 1} = \begin{bmatrix} C & E \\ E^{T} & F \\ \end{bmatrix}\]

其中

\[C = G^{- 1} - G^{- 1}A^{T}(AG^{- 1}A^{T})^{- 1}AG^{- 1}\]

\[E = G^{- 1}A^{T}(AG^{- 1}A^{T})^{- 1},F = - (AG^{- 1}A^{T})^{- 1}\]

解方程组(1)即得$p = - (Ch + Ec)$ 从而得到二次规划问题的解为$x^{*} = p + x$，$x$为$Ax = b$的任一解。这个方法的缺点是需要多次矩阵求逆和矩阵相乘。

由于假设$G$非奇异，$A$行满秩，故$AGA^{T}$非奇异，这样我们用$AG^{- 1}$左乘(7.4)的第一个方程，然后减去第二个方程得

\[(AG^{- 1}A^{T})\lambda = (AG^{- 1})h - c\]

解得$\lambda^{*}$，然后代入第一个方程得到

\[Gp = A^{T}\lambda^{*} - h\]

解得向量$p$. 这一方法称为秩空间方法。

对称不定分解方法

由于KKT系统的系数矩阵$K$是非奇异的对称不定矩阵，这时有对称不定矩阵分解，$P^{T}KP = LBL^{T}$

其中$P$为排列矩阵，$L$为单位下三角矩阵，$B$为块对角矩阵，其每个子块为$1 \times 1$或者$2 \times 2$矩阵。这样

\[K = PLBL^{T}P^{T}\]

原方程组就变为$PLBL^{T}P^{T}\begin{bmatrix} - p \\ \lambda \\ \end{bmatrix} = \begin{bmatrix} h \\ c \\ \end{bmatrix}$

这样，得到用对称不定分解求KKT系统的算法：
1. 利用（7.6）构造矩阵$K$，对$K$作对称不定分解，得到排列矩阵$P$，单位下三角矩阵$L$，对角块矩阵$B$，使得

\[P^{T}KP = LBL^{T}\]

解$Ly = P^{T}\begin{bmatrix} h \\ c \\ \end{bmatrix}$，得到$y$;
解$B\overline{y} = y,$得到$\overline{y}$;
解$L^{T}y^{*} = \overline{y},$得到$y^{*}$;
KKT系统的解为$\begin{bmatrix} - p \\ \lambda^{*} \\ \end{bmatrix} = Py^{*}$

对称不定矩阵的广义Cholesky分解

假设$G \in R^{n \times n}$是对称正定矩阵，$A \in R^{m \times n}$为行满秩矩阵，这时KKT系统的系数矩阵$K = \begin{bmatrix} G & A^{T} \\ A & 0 \\ \end{bmatrix}_{(m + n) \times (m + n)}$为对称不定矩阵。由于矩阵$G$为对称正定，故$G$有Cholesky分解

\[G = L_{11}L_{11}^{T}\]

，$L_{11}$为$n \times n$的下三角矩阵。

令$L_{21} = AL_{11}^{- T} \in R^{m \times n}$，故$rank(L_{21}) = m$.这就推得$L_{21}L_{21}^{T}$是$m \times m$对称正定矩阵，故存在Cholesky分解，即$L_{21}L_{21}^{T} = L_{22}L_{22}^{T}$，其中$L_{22}$是$m \times m$下三角矩阵。

综合起来得

\[\begin{bmatrix} G & A^{T} \\ A & 0 \\ \end{bmatrix} = \begin{bmatrix} L_{11} & 0 \\ L_{21} & L_{22} \\ \end{bmatrix}\begin{bmatrix} L_{11}^{T} & L_{21}^{T} \\ 0 & - L_{22}^{T} \\ \end{bmatrix}\]

这就称为对称不定矩阵的广义Cholesky分解.

完成以上的分解后，就能由下列两个步骤解方程组（7.4）：
1. 由$\begin{bmatrix} L_{11} & 0 \\ L_{21} & L_{22} \\ \end{bmatrix}\begin{bmatrix} y_{1} \\ y_{2} \\ \end{bmatrix} = \begin{bmatrix} h \\ c \\ \end{bmatrix}$解得$\begin{bmatrix} y_{1} \\ y_{2} \\ \end{bmatrix}$.
2. 由$\begin{bmatrix} L_{11}^{T} & L_{21}^{T} \\ 0 & - L_{22}^{T} \\ \end{bmatrix}\begin{bmatrix} - p \\ \lambda^{*} \\ \end{bmatrix} = \begin{bmatrix} y_{1} \\ y_{2} \\ \end{bmatrix}$,解得$\begin{bmatrix} - p \\ \lambda^{*} \\ \end{bmatrix}$
这个方法可以推广到更一般的情况，即

\[\overline{K} = \begin{bmatrix} G & A^{T} \\ A & - C \\ \end{bmatrix}\]

其中$G \in R^{n \times n},A \in R^{m \times n}$的假设与前面相同，$C \in R^{m \times m}$为对称正定矩阵。

类似前面的广义Cholesky分解，可以得到下列分解式

\[\begin{bmatrix} G & A^{T} \\ A & - C \\ \end{bmatrix} = \begin{bmatrix} {\overline{L}}_{11} & 0 \\ {\overline{L}}_{21} & {\overline{L}}_{22} \\ \end{bmatrix}\begin{bmatrix} {\overline{L}}_{11}^{T} & {\overline{L}}_{21}^{T} \\ 0 & - {\overline{L}}_{22}^{T} \\ \end{bmatrix}\]

由$G = {\overline{L}}_{11}{\overline{L}}_{11}^{T}$得到$n \times n$下三角矩阵${\overline{L}}_{11}$;

由${\overline{L}}_{21} = A{\overline{L}}_{11}^{- T}$得到${\overline{L}}_{21}$;

由对称正定矩阵$C + {\overline{L}}_{21}{\overline{L}}_{11}^{T}$的holesky分解得到$n \times n$的下三角矩阵${\overline{L}}_{22}$: $C + {\overline{L}}_{21}{\overline{L}}_{11}^{T} = {\overline{L}}_{22}{\overline{L}}_{22}^{T}$

可惜流光

6-梯度分析于最优化问题