无约束优化问题
定义
无约束优化问题，可以以下列形式表示：即查找一个函数 $f$, 使得
- 当自变量为标量时，函数 $f: \mathbb{R} \rightarrow \mathbb{R}$ \(min f(x), \quad x \in \mathbb{R}\) 最小
- 自变量为微量时，函数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ \(min f(\boldsymbol{x}), \quad x \in \mathbb{R}^n\) 最小
什么是鞍点(saddle point)?
梯度和 Hessian 矩阵
- 一阶层数和梯度(gradient vector)
\(f'(x): g(\boldsymbol{x}) = \nabla f(\boldsymbol{x}) = \frac{\partial f(\boldsymbol{x})}{\partial \boldsymbol{x}} = \begin{bmatrix} \frac{\partial f(x)}{\partial x_1} \\ \vdots \\ \frac{\partial f(x)}{\partial x_n} \end{bmatrix}\)
- 二阶层数和 Hessian 矩阵
观察可知，Hessian 矩阵是对称矩阵，例如第一行第二列和第二行第一列的值相同，但未必是正定矩阵。
二次型
- 给定矩阵 $\boldsymbol {A} \in \mathbb{R}^{n \times n}$, 函数
被称为二次型。例如尝试将$f(x) = x^2_1 + x^2_2 + x^2_3 $ 写成二次型的形式。
- 给定对称矩阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$, 如果对于所有 $\boldsymbol{x} \in \mathbb{R}$, 有 $\boldsymbol{x^T Ax} \ge 0$，则称其为半正定矩阵(positive semidefinite)，此时特征值 $\lambda(\boldsymbol{A}) \ge 0$.
- 如果对于所有 $\boldsymbol{x} \in \mathbb{R}^n, \boldsymbol{x} \ne 0$, 有 $\boldsymbol{x^T Ax} \gt 0$，则称其为正定矩阵(positive definite).
- 负定矩阵，不定矩阵
从上面看出，矩阵 $ \boldsymbol{A}$ 是否正定，其实是为了判断矩阵是否是大于 0 的，由于矩阵本身无法衡量是否大于 0，所以通过 $\boldsymbol{x^T Ax}$ 将矩阵表示为一个数字，再计算其是否大于 0 即可。
其计算过程如下：
- 向量 $\boldsymbol{a}$ 和 $\boldsymbol{x}$ 无关，则 $\nabla (\boldsymbol{a^T x}) = \boldsymbol{a}, \nabla^2 (\boldsymbol{a^T x}) = 0$，可用标量的形式去理解，如一次函数 $ax + b$ 求导得到 $a$, 再求一次导结果为 0
- 对称矩阵 $\boldsymbol{A}$ 与 $\boldsymbol{x}$ 无关，则 $\nabla (\boldsymbol{x^T Ax}) = \boldsymbol{2Ax}, \nabla^2 (\boldsymbol{x^T Ax}) = \boldsymbol{2A}$，同时用二次函数去理解，xax 一阶导数为 $2ax$, 二阶导数为 $2a$
- 最小二乘, 将 $\boldsymbol{b^T Ax}$ 和 $\boldsymbol{x^T A^T b}$ 分别展开计算，可知两者相等，则有
从而有
\[\nabla f(\boldsymbol{x}) = \boldsymbol{2A^T Ax - 2A^T b}\]- 标准二次型式子可表示为: $f(\boldsymbol{x}) = \boldsymbol{x^T Ax + 2b^T x + c}$
泰勒级数
- 输入为标量的泰勒级数展开
- 输入为向量的泰勒级数展开
标量情况
- 输入为标量的泰勒级数展开有: $f(x_k + \delta) \approx f(x_k) + f’(x_k) \delta + \frac{1}{2} f’‘(x_k) \delta^2$
- 严格局部极小点指：$f(x_k + \delta) \gt f(x_k)$
- 称满足 $f’(x_k) = 0$ 的点为平稳点，也称为候选点。
- 函数在 $x_k$ 有严格局部极小值的条件为：$f’(x_k) = 0$ 且 $f’‘(x_k) \gt 0$
向量情况
- 输入为向量的泰勒级数展开有: $f(\boldsymbol{x_k + \delta}) \approx f(\boldsymbol{x_k}) + \boldsymbol{g^T} (\boldsymbol{x_k}) \boldsymbol{\delta} + \frac{1}{2} \boldsymbol{\delta^T} H(\boldsymbol{x_k}) \boldsymbol{\delta}$
- 对于满足 $g(\boldsymbol{x}) = 0$ 的平稳点(候选点)，此时如果有
- $H(\boldsymbol{x}) \succ 0$, 则 $\boldsymbol{x_k}$ 为一个严格局部极小点(反之，则为局部极大点)
- 如果 $H(\boldsymbol{x_k})$ 是不定矩阵，则 $\boldsymbol{x_k}$ 是一个鞍点(saddle point)
梯度为 0 求解的局限性
大部分情况无法通过梯度为 0 求解！
