无约束问题的最优性条件-二阶条件

考虑二阶泰勒展开（假设$f(x)$是两次连续的，二阶可导的）
$$f(x+td)=f(x)+t\nabla f(x)d+\frac{1}{2}{t}^2{d}^T{\nabla }^{2}f(x)d+o(t^2)t\to 0$$
当一阶必要条件（FONC）$\nabla f(x)=0$ 成立时，我们有：
$$f(x+td)=f(x)+\frac{1}{2}{t}^2{d}^T{\nabla }^{2}f(x)d+o(t^2)t\to 0$$

为了使$x$成为一个局部极小点，我们还需要$t^2{d}^T{\nabla }^{2}f(x)d$对于每个$d\in R^n$是非负的。

二阶必要条件（SONC）

如果$x^{\star }$是$f$的局部最小化点，那么它保持：
1.$\nabla f(x^{\star })=0$；
2.对于所有的$d\in R^n：d^{\mathrm{T}}{f}^2(x^{\star })d\ge 0$。
此处我们引入一个半定矩阵的概念：

定义：我们称对称矩阵为正(负）半定（PSD/NSD）$M$当且仅当$M$ 所有$x$都有$x^{\mathrm{T}}Mx\ge (\le )0$

备注：因此，二阶必要条件要求在$x^{\star }$处的海森矩阵为PSD。在一维情况下，这相当于$f^{{}^{\prime \prime }}(x^{\star })\ge 0$

这里有一些关于PSD矩阵的有用的事实：

1. 我们通常只讨论对称矩阵的PSD性质。
2. 如果一个矩阵A不是对称的，我们使用 $\frac{1}{2}(A+A^T)$ 来定义PSD属性（因为$x^{T}Ax=\frac{1}{2}{x}^T(A+A^T)x$）。
3. 当且仅当所有特征值均为非负时，A对称矩阵是PSD。
4. 对于任何矩阵A，$A^{T}A$是一个（对称的）PSD矩阵。

$f(x)=x^4-9x^2+4x-1$二阶条件为：
$$f^{{}^{\prime \prime }}(x^{\star })=12x^2-18\ge 0$$
只有$x_2=-1-\frac{\sqrt{6}}{2},x_3=2$满足上述条件。也就是说$x_1$不是局部最小值点。

在最小二乘问题的例子中，我们有
$$\begin{array}{r}\underset{\beta }{\min }\Vert X\beta -y{\Vert }^2\end{array}$$

我们使用以下事实：
如果 $f(x)=x^{T}Mx$（$M$是对称的）${\nabla }^{2}f(x)=2M$

因此，该问题中的黑森矩阵是$2X^{T}X$，它一直是一个PSD矩阵。因此，SONC始终成立。

二阶必要条件（SONC）仍然还不够充分

然而，即使一阶和二阶必要条件都成立，我们仍然不能保证候选条件是一个局部最小值。
示例：考虑在$x=0$处的$f(x)=x^3$

$f^{{}^{\prime }}(x)=f^{{}^{\prime \prime }}(x)=0$ 一阶二阶必要条件都成立，但$x=0$并不是一个局部的最小值。

一个满足$\nabla f(x)=0$的点 $x$ 被称为临界点（critical point）或静止点（stationary point）。SONC可以用来进一步去除一些不是局部最小化点的平稳点。

二阶充分条件（SOSC）

假设$f$二阶连续可导。如果$x^{\star }$满足：

1. $\nabla f(x^{\star })=0$
2. 对所有的d∈Rn\{0}dT∇2f(x)d>0d \in R^n \backslash \{0\} \quad d^T\nabla^2 f(x)d > 0d∈Rn\{0}dT∇2f(x)d>0;

PD矩阵必须是PSD（因此PD是一个更强的概念）。
对称矩阵是PD $\iff$ 它的特征值都是正的。

证明 对称矩阵是PD $\iff$ 它的特征值都是正的。

我们需要以下引理

引理：边界和特征值设$A\in R^{m\times n}$ 为对称矩阵。然后
$${\lambda }_{min}(A)\Vert x{\Vert }^2\le x^{T}Ax\le {\lambda }_{max}(A)\Vert x{\Vert }^2\forall x\in R^n$$

${\lambda }_{min}(A)$ 和${\lambda }_{max}(A)$是A中最小、最大的特征值。

证明再次通过泰勒展开，即：

$$f(x+d)=f(x)+\frac{1}{2}{t}^2{d}^T{\nabla }^{2}f(x)d+o(\Vert d{\Vert }^2)\Vert d\Vert \to 0$$

当${\nabla }^{2}f(x^{\star })$是一个正定矩阵，我们能发现$d^T{\nabla }^{2}f(x^{\star })d\ge \mu \Vert d{\Vert }^2$, $\mu >0$ 是A的最小特征值。
因此，我们发现
$$f(x+d)\ge f(x)+\frac{1}{2}\mu \Vert d{\Vert }^2+o(\Vert d{\Vert }^2)=f(x)+\Vert d{\Vert }^2(\frac{\mu }{2}+\frac{o(\Vert d{\Vert }^2)}{\Vert d{\Vert }^2})$$

既然 $\Vert d\Vert \to 0$ 我们发现 $\frac{o(\Vert d{\Vert }^2)}{\Vert d{\Vert }^2}\ge -\frac{\mu }{4}$ 也就证明了$f(x^{\star })>f(x^{\star }+d)$

对于最大化问题

我们推导出了最小化问题的条件。对于最大化问题，我们只是改变不等式。设 $f\in C^2$（二阶连续可导）。

定理：最大化的FONC:
如果$x^{\star }$是一个局部的（无约束的）最大化点，那么我们必须有$\nabla f(x^{\star })=0$

定理： 最大化的SONC:
如果$x^{\star }$是一个局部最大化点，那么我们必须有1. $\nabla f(x^{\star })=0$; 2.${\nabla }^{2}f（x^{\star }）$是负半定的。

定理：最大化SOSC:
如果$x^{\star }$ 满足1. $\nabla f(x^{\star })=0$; 2.${\nabla }^{2}f（x^{\star }）$是负定的，那么$x^{\star }$是一个严格的局部极大值点。

无约束问题的最优性条件

无约束问题的最优性条件：一阶必要条件（FONC）。二阶必要条件（SONC）。二阶充分条件（SOSC）（对于严格的局部最小值）。
在某些情况下，我们可以利用这些条件来确定局部和全局最优解。
一般策略：
使用FONC和SONC来确定所有可能的候选。然后，利用充分条件进行验证。如果一个问题只有一个平稳点，并且可以推断这个问题必须有一个有限的最优解，那么这个点必须是全局最优解。

例子

在示例$f(x)=x^4-9x^2+4x-1$中，点x1和x3满足二阶充分条件（$f^{{}^{\prime \prime }}(x)>0$），是严格的局部极小点。

在最小二乘问题中，如果$X^{T}X$是正定的（或者它是可逆的），那么FONC $X^{T}X\beta =Xy$的解 $\beta$ 是唯一的，并且它满足二阶充分条件（严格局部极小化）

不确定性和鞍点

定义：

1. 一个满足$\nabla f(x)=0$的点 $x$ 被称为临界点（critical point）或静止点（stationary point）。
2. 如果一个平稳点既不是局部极小化，也不是局部极大化，则称为鞍点。

推论：鞍点
假设$x^{\star }$是一个平稳点（$\nabla f(x^{\star })=0$），海森矩阵${\nabla }^{2}f(x^{\star })$是不定的，那么$x^{\star }$是一个鞍点。
注：不定指非正（负）半定

实例二

我们考虑二维优化问题：
$$\begin{array}{r}\underset{x\in R^2}{\min }f(x)=x_1^2{x}_2+x_1{x}_2^3-5x_1{x}_2\end{array}$$

找到$f$的所有局部最小化、局部极大化和鞍点

第一步： 计算所有平稳点

$$\begin{array}{c}\nabla f(x)=\left[\begin{array}{c}2x_1{x}_2+x_2^3+5x_2\\ x_1^2+3x_1{x}_2^2-5x_1\end{array}\right]\end{array}$$

让 $\nabla f(x)=0$，我们得到6个平稳点$\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]$

步骤二：
$$\begin{array}{c}\nabla f(x)=\left[\begin{array}{c}2x_2,2x_1+3x_2^2-5\\ 2x_1+3x_2^2-5,6x_1{x}_2\end{array}\right]\end{array}$$

示例三–鞍点

函数$f(x)=x_1^2-x_2^2$图像

梯度为$\nabla f(x)=(2x_1，-2x_2{)}^T，x^{\star }=(0,0{)}^T$为$f$的单个平稳点。由于${\nabla }^{2}f(x^{\star })$是不定的，所以$x^{\star }$必须是一个鞍点。
注： 鞍点不一定有一个不定的海森矩阵，例如$f(x)=x^3$

示例四

是否存在局部最小化点满足SONC而不满足SOSC的情况？是的。实际上，任何非严格的局部极小化器都会是这样的情况。考虑以下函数：

我们有SONC满足所有的$-1\le x\le 1$，但SOSC不满足。然而，很清楚地看到$-1\le x\le 1$上的所有点都是（非严格）局部极小点。

总结

1. 所有的平稳点（FONC）都是局部极小化器的候选点。（不充分）
2. SONC可以进一步去除一些非局部极小化的平稳点，包括局部极大点和具有不定海森矩阵的鞍点。
3. SOSC可以用来充分识别严格的局部极小值。
4. 对于具有PSD Hessian的非严格局部极小值和鞍点（考虑$x=0$处的$x_3$），SONC在两种情况下都满足。到目前为止，我们还没有足够的条件来识别它们。

到目前为止，我们研究了无约束问题的最优性条件。下一节课，我们将开始研究受约束问题的最优性条件。

内容来自cuhksz mat3007的ppt Professor Li Xiao，翻译为中文，修改了小部分，加入了一些笔者自己的理解。