可微擬凸函式

---

---

定理

設S是$\mathbb{R}^n$中的一個非空凸集，且$f:S \rightarrow \mathbb{R}$在S上可微，則f是擬凸的當且僅當對於任意$x_1,x_2 \in S$且$f\left ( x_1 \right )\leq f\left ( x_2 \right )$，有$\bigtriangledown f\left ( x_2 \right )^T\left ( x_2-x_1 \right )\leq 0$

證明

設f為擬凸函式。

設$x_1,x_2 \in S$使得$f\left ( x_1 \right ) \leq f\left ( x_2 \right )$

由f在$x_2$處的可微性，$\lambda \in \left ( 0, 1 \right )$

$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )=f\left ( x_2+\lambda \left (x_1-x_2 \right ) \right )=f\left ( x_2 \right )+\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )$

$+\lambda \left \| x_1-x_2 \right \|\alpha \left ( x_2,\lambda \left ( x_1-x_2 \right ) \right )$

$\Rightarrow f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )-f\left ( x_2 \right )-f\left ( x_2 \right )=\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )$

$+\lambda \left \| x_1-x_2 \right \|\alpha \left ( x2, \lambda\left ( x_1-x_2 \right )\right )$

但由於f是擬凸的，$f \left ( \lambda x_1+ \left ( 1- \lambda \right )x_2 \right )\leq f \left (x_2 \right )$

$\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )+\lambda \left \| x_1-x_2 \right \|\alpha \left ( x_2,\lambda \left ( x_1,x_2 \right ) \right )\leq 0$

但$\alpha \left ( x_2,\lambda \left ( x_1,x_2 \right )\right )\rightarrow 0$ as $\lambda \rightarrow 0$

因此，$\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right ) \leq 0$

逆命題

設對於$x_1,x_2 \in S$且$f\left ( x_1 \right )\leq f\left ( x_2 \right )$，$\bigtriangledown f\left ( x_2 \right )^T \left ( x_1,x_2 \right ) \leq 0$

要證明f是擬凸的，即，$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq f\left ( x_2 \right )$

反證法

假設存在一個$x_3= \lambda x_1+\left ( 1-\lambda \right )x_2$使得$f\left ( x_2 \right )< f \left ( x_3 \right )$對於某個$ \lambda \in \left ( 0, 1 \right )$

對於$x_2$和$x_3,\bigtriangledown f\left ( x_3 \right )^T \left ( x_2-x_3 \right ) \leq 0$

$\Rightarrow -\lambda \bigtriangledown f\left ( x_3 \right )^T\left ( x_2-x_3 \right )\leq 0$

$\Rightarrow \bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_2 \right )\geq 0$

對於$x_1$和$x_3,\bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_3 \right ) \leq 0$

$\Rightarrow \left ( 1- \lambda \right )\bigtriangledown f\left ( x_3 \right )^T\left ( x_1-x_2 \right )\leq 0$

$\Rightarrow \bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_2 \right )\leq 0$

因此，根據以上等式，$\bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_2 \right )=0$

定義$U=\left \{ x:f\left ( x \right )\leq f\left ( x_2 \right ),x=\mu x_2+\left ( 1-\mu \right )x_3, \mu \in \left ( 0,1 \right ) \right \}$

因此，我們可以找到$x_0 \in U$使得$x_0 = \mu_0 x_2= \mu x_2+\left ( 1- \mu \right )x_3$對於某個$\mu _0 \in \left ( 0,1 \right )$，它最接近$x_3$，並且$\hat{x} \in \left ( x_0,x_1 \right )$使得根據中值定理，

$$\frac{f\left ( x_3\right )-f\left ( x_0\right )}{x_3-x_0}= \bigtriangledown f\left ( \hat{x}\right )$$

$$\Rightarrow f\left ( x_3 \right )=f\left ( x_0 \right )+\bigtriangledown f\left ( \hat{x} \right )^T\left ( x_3-x_0 \right )$$

$$\Rightarrow f\left ( x_3 \right )=f\left ( x_0 \right )+\mu_0 \lambda f\left ( \hat{x}\right )^T \left ( x_1-x_2 \right )$$

由於$x_0$是$x_1$和$x_2$的組合，並且$f\left (x_2 \right )< f\left ( \hat{x}\right )$

透過重複起始過程，$\bigtriangledown f \left ( \hat{x}\right )^T \left ( x_1-x_2\right )=0$

因此，結合上述等式，我們得到

$$f\left ( x_3\right )=f\left ( x_0 \right ) \leq f\left ( x_2\right )$$

$$\Rightarrow f\left ( x_3\right )\leq f\left ( x_2\right )$$

因此，這是一個矛盾。

例子

步驟1 − $f\left ( x\right )=X^3$

$設 f \left ( x_1\right )\leq f\left ( x_2\right )$

$\Rightarrow x_{1}^{3}\leq x_{2}^{3}\Rightarrow x_1\leq x_2$

$\bigtriangledown f\left ( x_2 \right )\left ( x_1-x_2 \right )=3x_{2}^{2}\left ( x_1-x_2 \right )\leq 0$

因此，$f\left ( x\right )$是擬凸的。

步驟2 − $f\left ( x\right )=x_{1}^{3}+x_{2}^{3}$

設$\hat{x_1}=\left ( 2, -2\right )$和$\hat{x_2}=\left ( 1, 0\right )$

因此，$f\left ( \hat{x_1}\right )=0,f\left ( \hat{x_2}\right )=1 \Rightarrow f\left ( \hat{x_1}\right )\setminus < f \left ( \hat{x_2}\right )$

因此，$\bigtriangledown f \left ( \hat{x_2}\right )^T \left ( \hat{x_1}- \hat{x_2}\right )= \left ( 3, 0\right )^T \left ( 1, -2\right )=3 >0$

因此，$f\left ( x\right )$不是擬凸的。