全局最优的充分必要条件

定理

设 f 为二阶可微函数。如果 $\bar{x}$ 为局部最小值，则 $\bigtriangledown f\left ( \bar{x} ight )=0$，Hessian 矩阵 $H\left ( \bar{x} ight )$ 为半正定矩阵。

证明

设 $d \in \mathbb{R}^n$。由于 f 在 $\bar{x}$ 处二阶可微。

因此，

$f\left ( \bar{x} +\lambda d ight )=f\left ( \bar{x} ight )+\lambda \bigtriangledown f\left ( \bar{x} ight )^T d+\lambda^2d^TH\left ( \bar{x} ight )d+\lambda^2d^TH\left ( \bar{x} ight )d+$

$\lambda^2\left \| d ight \|^2\beta \left ( \bar{x}, \lambda d ight )$

但 $\bigtriangledown f\left ( \bar{x} ight )=0$ 且 $\beta\left ( \bar{x}, \lambda d ight ) ightarrow 0$ 等于 $\lambda ightarrow 0$

$\Rightarrow f\left ( \bar{x} +\lambda d ight )-f\left ( \bar{x} ight )=\lambda ^2d^TH\left ( \bar{x} ight )d$

由于 $\bar{x }$ 是局部最小值，因此存在一个 $\delta > 0$ 使得 $f\left ( x ight )\leq f\left ( \bar{x}+\lambda d ight ), \forall \lambda \in \left ( 0,\delta ight )$

定理

设 $f:S ightarrow \mathbb{R}^n$，其中 $S \subset \mathbb{R}^n$ 在 S 上是二阶可微分的。如果 $\bigtriangledown f\left ( x ight )=0$ 且 $H\left ( \bar{x} ight )$ 是半正定的，则​​对于所有 $x \in S$，$\bar{x}$ 是全局最优解。

证明

由于 $H\left ( \bar{x} ight )$ 是半正定的，因此 f 在 S 上是凸函数。由于 f 是可微分的并且在 $\bar{x}$ 处凸起

$\bigtriangledown f\left ( \bar{x} ight )^T \left ( x-\bar{x} ight ) \leq f\left (x ight )-f\left (\bar{x} ight ),\forall x \in S$

由于 $\bigtriangledown f\left ( \bar{x} ight )=0，f\left ( x ight )\geq f\left ( \bar{x} ight )$

因此，$\bar{x}$ 是全局最优解。

定理

假设 $\bar{x} \in S$ 是问题 $f:S ightarrow \mathbb{R}$ 的局部最优解，其中 S 是$\mathbb{R}^n$ 的非空子集且 S 是凸的。 $min \:f\left ( x ight )$ 其中 $x \in S$。

则：

• $\bar{x}$ 是全局最优解。

• 如果 $\bar{x}$ 是严格局部最小值或 f 是严格凸函数，则 $\bar{x}$ 是唯一的全局最优解，也是强局部最小值。

证明

设 $\bar{x}$ 是该问题的另一个全局最优解，使得 $x eq \bar{x}$ 且 $f\left ( \bar{x} ight )=f\left ( \hat{x} ight )$

由于 $\hat{x},\bar{x} \in S$ 且 S 是凸函数，则$\frac{\hat{x}+\bar{x}}{2} \in S$且 f 严格凸。

$\Rightarrow f\left ( \frac{\hat{x}+\bar{x}}{2} ight )< \frac{1}{2} f\left (\bar{x} ight )+\frac{1}{2} f\left (\hat{x} ight )=f\left (\hat{x} ight )$

这是矛盾的。

因此，$\hat{x}$是唯一的全局最优解。

推论

设 $f:S \subset \mathbb{R}^n ightarrow \mathbb{R}$ 为可微凸函数，其中 $\phi eq S\subset \mathbb{R}^n$ 为凸集。考虑问题 $min f\left (x ight ),x \in S$，如果 $\bigtriangledown f\left (\bar{x} ight )^T\left (x-\bar{x} ight ) \geq 0,\forall x \in S.$，则 $\bar{x}$ 为最优解

证明

设 $\bar{x}$ 为最优解，即 $f\left (\bar{x} ight )\leq f\left (x ight ),\forall x \in S$

$\Rightarrow f\left (x ight )=f\left (\bar{x} ight )\geq 0$

$f\left (x ight )=f\left (\bar{x} ight )+\bigtriangledown f\left (\bar{x} ight )^T\left (x-\bar{x} ight )+\left \| x-\bar{x} ight \|\alpha \left ( \bar{x},x-\bar{x} ight )$

其中 $\alpha \left ( \bar{x},x-\bar{x} ight ) ightarrow 0$ 为 $x ightarrow \bar{x}$

$\Rightarrow f\left (x ight )-f\left (\bar{x} ight )=\bigtriangledown f\left (\bar{x} ight )^T\left (x-\bar{x} ight )\geq 0$

推论

设 f 为 $\bar{x}$ 处可微凸函数，则当且仅当 $\bigtriangledown f\left 时，$\bar{x}$ 为全局最小值(\bar{x} ight )=0$

示例

• $f\left (x ight )=\left (x^2-1 ight )^{3}, x \in \mathbb{R}$.

  $\bigtriangledown f\left (x ight )=0 \Rightarrow x= -1,0,1$.

  $\bigtriangledown^2f\left (\pm 1 ight )=0, \bigtriangledown^2 f\left (0 ight )=6>0$.

  $f\left (\pm 1 ight )=0,f\left (0 ight )=-1$

  因此，$f\left (x ight ) \geq -1=f\left (0 ight )\Rightarrow f\left (0 ight ) \leq f \left (x ight)\forall x \in \mathbb{R}$

• $f\left (x ight )=x\log x$ 定义在 $S=\left \{ x \in \mathbb{R}, x> 0 ight \}$ 上。

  ${f}'x=1+\log x$

  ${f}''x=\frac{1}{x}>0$

  因此，此函数是严格凸的。

• $f \left (x ight )=e^{x},x \in \mathbb{R}$ 是严格凸的。