机器学习笔记之最优化理论与方法(六)无约束优化问题——最优性条件

引言

本节将介绍无约束优化问题，主要介绍无约束优化问题最优解的相关性质。

本节是关于以优化算法——无约束算法概述为首，优化算法——线搜索方法(二~九)的理论补充。

无约束优化问题

无约束优化问题的数学符号表示如下：
仅需要对目标函数进行最小化，没有可行域的条件限制。
$$\min f(x)$$
在实际问题中，很多问题可以被建模成无约束优化问题。例如：线性回归方法中的最小二乘估计问题。对应数学符号表示如下：
很明显，最小二乘函数$\Vert \mathcal{A}x-b{\Vert }_2^2$明显是一个凸函数：其二次型系数矩阵${\mathcal{A}}^T\mathcal{A}$必然是半正定矩阵。
$$\begin{array}{rl}f(x)& =\Vert \mathcal{A}x-b{\Vert }_2^2\\ & =(\mathcal{A}x-b{)}^T(\mathcal{A}x-b)\\ & =x^T[{\mathcal{A}}^T\mathcal{A}]x+b^T\mathcal{A}x-x^T{\mathcal{A}}^{T}b+b^{T}b\end{array}$$
因而该问题可以更精确地描述为无约束凸优化问题。
$$\min \Vert \mathcal{A}x-b{\Vert }_2^2$$

可以采用适当方法将约束优化问题转换为无约束优化问题。例如最优化问题概述中提到的罚函数法。

无约束优化问题最优解的定义

• 局部最优解 ：假设$\bar{x}$是关于目标函数$f(\cdot )$无约束优化问题的局部最优解，对于$\forall x\in {\mathcal{N}}_{ϵ}(\bar{x})$，必然有：
  其中${\mathcal{N}}_{ϵ}(\bar{x})$表示包含点$\bar{x}$，并且使用$ϵ$表示范围的邻域。例如:$(\bar{x}-ϵ,\bar{x}+ϵ)$
  $$f(x)\ge f(\bar{x})$$
• 全局最优解：相比于局部最优解，假设$x^{\ast }$是关于目标函数$f(\cdot )$无约束优化问题的全局最优解，对于$\forall x\in {\mathbb{R}}^n$，必然有：
  $$f(x)\ge f(x^{\ast })$$
• 严格最优解：与凸函数：定义与基本性质中提到的严格凸函数类似，其核心是消除掉取等的情况。关于严格最优解，同样可以分为严格局部最优解与严格全局最优解。对应数学符号表示如下：
  $$\{\begin{array}{l}\forall x\in {\mathbb{R}}^n,x\ne x^{\ast }\Rightarrow f(x)>f(x^{\ast })\\ \forall x\in {\mathcal{N}}_{ϵ}(\bar{x}),x\ne \bar{x}\Rightarrow f(x)>f(\bar{x})\end{array}$$
  对应图像表示如下：
  
  根据凸函数的定义可以看出，$f(\cdot ),\mathcal{G}(\cdot )$都是凸函数。其中$f(\cdot )$中描述的红色点是严格最优解；而红色点$\mathcal{G}(x^{\ast })$是最优解的条件下，$\exists x\ne x^{\ast }\Rightarrow f(x)=f(x^{\ast })$。那么该函数的最优解不是严格最优解。

无约束优化问题的最优性条件

针对无约束优化问题 $\Rightarrow \min f(x)$：

无约束优化问题的充要条件

如果目标函数$f(x)$是凸函数，则存在如下等价条件：
关于无约束凸优化问题,详细解释见最优化理论与方法——凸优化问题(上),这里不再赘述。
$$x^{\ast }\text{ is Optimal }\iff \nabla f(x^{\ast })=0$$

无约束优化问题的必要条件

如果目标函数$f(x)$不是凸函数，只是一般函数，上述的充要条件不一定成立，但一定满足如下必要条件：

• 如果$x^{\ast }$是最优解，那么它一定是平稳点；
• 如果$f(\cdot )$在$x^{\ast }$位置的$\text{Hessian Matrix}\Rightarrow {\nabla }^{2}f(x^{\ast })$存在，那么该矩阵至少是半正定矩阵；如果将$f(\cdot )$退化成一元函数,必然有：$f^{\prime \prime }(x^{\ast })\ge 0$。
  $$x^{\ast }\text{ is Optimal }\Rightarrow \{\begin{array}{l}\nabla f(x^{\ast })=0\\ {\nabla }^{2}f(x^{\ast })\succcurlyeq 0\end{array}$$

证明：

• 已知$x^{\ast }$是最优解，不妨设：$\nabla f(x^{\ast })\ne 0$，必然存在负梯度方向：$d=-\nabla f(x^{\ast })$。
  以$x^{\ast }$为起始点，沿着负梯度方向前进较小的一段距离：$f(x^{\ast }+\lambda \cdot d)$，并将其进行泰勒展开：
  思路：前进一小段距离后，必然会导致目标函数值下降;从而$x^{\ast }$不是最优解了，产生矛盾。
  $$f(x^{\ast }+\lambda \cdot d)=f(x^{\ast })+\frac{1}{1!}\lambda [\nabla f(x^{\ast }){]}^{T}d+\mathcal{O}(\lambda \Vert d\Vert )\lambda \in (0,1)$$
  经过整理，有：
  关于$\lambda$范围后面不再赘述。
  $$\frac{f(x^{\ast }+\lambda \cdot d)-f(x^{\ast })}{\lambda }=[\nabla f(x^{\ast }){]}^{T}d+\frac{\mathcal{O}(\lambda \Vert d\Vert )}{\lambda }$$
  将$d=-\nabla f(x^{\ast })$代入，必然有：
  $$[\nabla f(x^{\ast }){]}^{T}d=-||\nabla f(x^{\ast })|{|}^2<0$$
  当$\lambda \Rightarrow 0$时，有：
  $$\underset{\lambda \Rightarrow 0}{\lim }\frac{f(x^{\ast }+\lambda \cdot d)-f(x^{\ast })}{\lambda }=\underset{\lambda \Rightarrow 0}{\lim }\left\{\underset{<0}{\underbrace{[\nabla f(x^{\ast }){]}^{T}d}}+\underset{=0}{\underbrace{\frac{\mathcal{O}(\lambda \cdot \Vert d\Vert )}{\lambda }}}\right\}<0$$
  从而：
  $$\underset{\lambda \Rightarrow 0}{\lim }\frac{f(x^{\ast }+\lambda \cdot d)-f(x^{\ast })}{\lambda }<0\Rightarrow \underset{\lambda \Rightarrow 0}{\lim }f(x^{\ast }+\lambda \cdot d)<f(x^{\ast })$$
  此时，发现了存在比$f(x^{\ast })$还要小的函数值$f(x^{\ast }+\lambda \cdot d)$，这意味着：$x^{\ast }$不是最优解。与条件矛盾，得证。也将$\nabla f(x^{\ast })=0$称作一般函数$f(\cdot )$$x^{\ast }$是最优解的一阶必要条件。
• 二阶必要条件证明：已知$x^{\ast }$是最优解，必然有：$\nabla f(x^{\ast })=0$。假设$x^{\ast }$位置的$\text{Hessian Matrix}\Rightarrow {\nabla }^{2}f(x^{\ast })$低于半正定矩阵，必然有：
  $$\exists d\ne 0\Rightarrow d^T{\nabla }^{2}f(x^{\ast })d<0$$
  以$x^{\ast }$为起始点，$d$为下降方向前进较小的一段距离：$f(x^{\ast }+\lambda \cdot d)$，并将其进行泰勒展开：
  与平稳点的证明相似，只不过需要二阶泰勒展开~
  $$\begin{array}{rl}f(x^{\ast }+\lambda \cdot d)& =f(x^{\ast })+\frac{1}{1!}\lambda \cdot \underset{=0}{\underbrace{[\nabla f(x^{\ast }){]}^T}}d+\frac{1}{2!}\lambda \cdot d^T{\nabla }^{2}f(x^{\ast })d+\mathcal{O}({\lambda }^2\cdot \Vert d{\Vert }^2)\\ & =f(x^{\ast })+\frac{1}{2!}\lambda \cdot d^T{\nabla }^{2}f(x^{\ast })d+\mathcal{O}({\lambda }^2\cdot \Vert d{\Vert }^2)\end{array}$$
  经过整理，并令$\lambda \Rightarrow 0$，有：
  $$\underset{\lambda \Rightarrow 0}{\lim }\frac{f(x^{\ast }+\lambda \cdot d)-f(x^{\ast })}{{\lambda }^2}=\frac{1}{2}\underset{<0}{\underbrace{d^T{\nabla }^{2}f(x^{\ast })d}}+\underset{=0}{\underbrace{\frac{\mathcal{O}({\lambda }^2\cdot \Vert d{\Vert }^2)}{{\lambda }^2}}}<0$$
  从而$f(x^{\ast }+\lambda \cdot d)<f(x^{\ast })$，从而与条件矛盾。因此：最优解$x^{\ast }$对应的${\nabla }^{2}f(x^{\ast })\succcurlyeq 0$恒成立。

相反，如果存在某点$x^{\ast }$，使得：$\nabla f(x^{\ast })=0$且${\nabla }^{2}f(x^{\ast })\succcurlyeq 0$，那么点$x^{\ast }$是否为最优解$?$不一定。例如：$f(x)=x^3$，其函数图像表示如下：

在$x=0$处的梯度$\nabla f(x){|}_{x=0}=0$；二阶梯度${\nabla }^{2}f(x){|}_{x=0}=0$，均满足条件；但该点是一个鞍点，而不是最优解点。

无约束优化问题的充分条件

如果$f(\cdot )$不是凸函数，只是一般函数，如果存在某点$x^{\ast }$，满足：$\nabla f(x^{\ast })=0,{\nabla }^{2}f(x^{\ast })\succ 0$，那么$x^{\ast }$是严格最优解；

• 其中${\nabla }^{2}f(x^{\ast })\succ 0$表示函数$f(\cdot )$在$x^{\ast }$点处的$\text{Hessian Matrix}$是正定矩阵。
• 需要注意的是，这里的严格最优解可能是严格局部最优解或者严格全局最优解。

证明：
要证上式，即证：$\forall x\in {\mathcal{N}}_{ϵ}(x^{\ast }),f(x^{\ast })<f(x)$。

• 以$x^{\ast }$为起始点，朝着任意方向$d$前进较小的距离，得到新的函数结果：$f(x^{\ast }+\lambda \cdot d)$。观察：$f(x^{\ast }+\lambda \cdot d)$与$f(x^{\ast })$之间的大小情况。使用泰勒公式展开：
  为了简单起见，仅关注$d$的方向，而令$d$大小$\Vert d\Vert =1$
  $$f(x^{\ast }+\lambda \cdot d)=f(x^{\ast })+\frac{1}{1!}\lambda \cdot \underset{=0}{\underbrace{[\nabla f(x^{\ast }){]}^T}}d+\frac{1}{2!}{\lambda }^2{d}^T\underset{\succ 0}{\underbrace{{\nabla }^{2}f(x^{\ast })}}d+\mathcal{O}({\lambda }^2)\Vert d{\Vert }^2=1$$
  整理上式，观察$f(x^{\ast }+\lambda \cdot d)-f(x^{\ast })$结果：
  $$\underset{\lambda \Rightarrow 0}{\lim }\frac{f(x^{\ast }+\lambda \cdot d)-f(x^{\ast })}{{\lambda }^2}=\frac{1}{2}{d}^T{\nabla }^{2}f(x^{\ast })d>0$$
  从而$f(x^{\ast }+\lambda \cdot d)>f(x^{\ast })$。这意味着：在$x^{\ast }$范围的小的邻域内，$f(x^{\ast })$是最小值，并且是严格最小值，得证。

$\text{Reference}$：
最优化理论与方法-第五讲-无约束优化问题（一）