強擬凸函式

---

---

設$f:S\rightarrow \mathbb{R}^n$，且S是$\mathbb{R}^n$中的一個非空凸集，則f是強擬凸函式，如果對於任何$x_1,x_2 \in S$且$\left ( x_1 \right ) \neq \left ( x_2 \right )$，我們有$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )< max \:\left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \},\forall \lambda \in \left ( 0,1\right )$

定理

在$\mathbb{R}^n$中的非空凸集S上，擬凸函式$f:S\rightarrow \mathbb{R}^n$是強擬凸函式，如果它在連線S中任意兩點的線段上不恆定。

證明

設f是擬凸函式，並且它在連線S中任意兩點的線段上不恆定。

假設f不是強擬凸函式。

存在$x_1,x_2 \in S$且$x_1 \neq x_2$，使得

$$f\left ( z \right )\geq max\left \{ f\left ( x_1 \right ), f\left ( x_2 \right ) \right \}, \forall z= \lambda x_1+\left ( 1-\lambda \right )x_2, \lambda \in \left ( 0,1 \right )$$

$\Rightarrow f\left ( x_1 \right )\leq f\left ( z \right )$且$f\left ( x_2 \right )\leq f\left ( z \right )$

由於f在$\left [ x_1,z \right ]$和$\left [z,x_2 \right ] $上不恆定

因此存在$u \in \left [ x_1,z \right ]$和$v=\left [ z,x_2 \right ]$

$$\Rightarrow u= \mu_1x_1+\left ( 1-\mu_1\right )z,v=\mu_2z+\left ( 1- \mu_2\right )x_2$$

由於f是擬凸的，

$$\Rightarrow f\left ( u \right )\leq max\left \{ f\left ( x_1 \right ),f \left ( z \right ) \right \}=f\left ( z \right )\:\: 且 \:\:f \left ( v \right ) \leq max \left \{ f\left ( z \right ),f\left ( x_2 \right ) \right \}$$

$$\Rightarrow f\left ( u \right )\leq f\left ( z \right ) \:\: 且 \:\: f\left ( v \right )\leq f\left ( z \right )$$

$$\Rightarrow max \left \{ f\left ( u \right ),f\left ( v \right ) \right \} \leq f\left ( z \right )$$

但z是u和v之間的任意一點，如果其中任何一個相等，則f是常數。

因此，$max \left \{ f\left ( u \right ),f\left ( v \right ) \right \} \leq f\left ( z \right )$

這與f的擬凸性相矛盾，因為$z \in \left [ u,v \right ]$。

因此，f是強擬凸函式。

定理

設$f:S\rightarrow \mathbb{R}^n$，且S是$\mathbb{R}^n$中的一個非空凸集。如果$\hat{x}$是區域性最優解，則$\hat{x}$是唯一的全域性最優解。

證明

由於強擬凸函式也是嚴格擬凸函式，因此區域性最優解是全域性最優解。

唯一性 − 設f在兩點$u,v \in S$處取得全域性最優解

$$\Rightarrow f\left ( u \right ) \leq f\left ( x \right ).\forall x \in S\:\: 且 \:\:f\left ( v \right ) \leq f\left ( x \right ).\forall x \in S$$

如果u是全域性最優解，$f\left ( u \right )\leq f\left ( v \right )$且$f\left ( v \right )\leq f\left ( u\right )\Rightarrow f\left ( u \right )=f\left ( v\right )$

$$f\left ( \lambda u+\left ( 1-\lambda\right )v\right )< max \left \{f\left ( u \right ),f\left ( v \right ) \right \}=f\left ( u \right )$$

這是一個矛盾。

因此，只存在一個全域性最優解。

備註

• 強擬凸函式也是嚴格擬凸函式。
• 嚴格凸函式可能是也可能不是強擬凸的。
• 可微嚴格凸函式是強擬凸的。