全局最优的充分与必要条件

---

---

定理

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

证明

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

因此，

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

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

但$\bigtriangledown f\left ( \bar{x} \right )=0$且$\beta\left ( \bar{x}, \lambda d \right )\rightarrow 0$当$\lambda \rightarrow 0$

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

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

定理

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

证明

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

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

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

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

定理

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

那么

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

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

证明

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

由于$\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} \right )< \frac{1}{2} f\left (\bar{x}\right )+\frac{1}{2} f\left (\hat{x}\right )=f\left (\hat{x}\right )$

这是矛盾的。

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

推论

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

证明

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

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

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

其中$\alpha \left ( \bar{x},x-\bar{x} \right )\rightarrow 0$当$x \rightarrow \bar{x}$

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

推论

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

例子

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

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

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

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

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

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

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

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

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

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