全域性最優的充分與必要條件

---

---

定理

設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}$是嚴格凸的。