可微拟凸函数

---

---

定理

设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 )$不是拟凸的。