可微拟凸函数

定理

设 S 为 $\mathbb{R}^n$ 中的非空凸集，且 $f:S ightarrow \mathbb{R}$ 在 S 上可微，则 f 为拟凸当且仅当对于任何 $x_1,x_2 \in S$ 且 $f\left ( x_1 ight )\leq f\left ( x_2 ight )$，我们有 $\bigtriangledown f\left ( x_2 ight )^T\left ( x_2-x_1 ight )\leq 0$

证明

设 f 为拟凸函数。

设 $x_1,x_2 \in S$ 使得 $f\left ( x_1 ight ) \leq f\left ( x_2 ight )$

通过 f 在 $x_2, \lambda \in \left ( 0, 1 ight )$处的可微性

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

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

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

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

但由于 f 是准凸的，$f \left ( \lambda x_1+ \left ( 1- \lambda ight )x_2 ight )\leq f \left (x_2 ight )$

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

但 $\alpha \left ( x_2,\lambda \left ( x_1,x_2 ight ) ight ) ightarrow 0$ 等于 $\lambda ightarrow 0$

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

逆

设对于 $x_1,x_2 \in S$ 和 $f\left ( x_1 ight )\leq f\left ( x_2 ight )$，$\bigtriangledown f\left ( x_2 ight )^T \left ( x_1,x_2 ight ) \leq 0$

证明 f 是拟凸的，即 $f\left ( \lambda x_1+\left ( 1-\lambda ight )x_2 ight )\leq f\left ( x_2 ight )$

矛盾证明

假设存在一个 $x_3= \lambda x_1+\left ( 1-\lambda ight )x_2$，使得对于某个 $ \lambda \in \left ( 0, 1 ight )$，$f\left ( x_2 ight )< f \left ( x_3 ight )$

对于 $x_2$ 和 $x_3，\bigtriangledown f\left ( x_3 ight )^T \left ( x_2-x_3 ight ) \leq 0$

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

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

对于 $x_1$ 和 $x_3，\bigtriangledown f\left ( x_3 ight )^T \left ( x_1-x_3 ight ) \leq 0$

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

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

因此，从上述方程式可知， $\bigtriangledown f\left ( x_3 ight )^T \left ( x_1-x_2 ight )=0$

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

因此我们可以找到 $x_0 \in U$ 使得 $x_0 = \mu_0 x_2= \mu x_2+\left ( 1- \mu ight )x_3$，其中 $\mu _0 \in \left ( 0,1 ight )$ 最接近 $x_3$ 和 $\hat{x} \in \left ( x_0,x_1) ight )$，根据均值定理，

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

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

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

由于$x_0$是$x_1$和$x_2$的组合，且$f\left(x_2 ight)< f\left(\hat{x} ight)$

重复起始步骤，$\bigtriangledown f \left(\hat{x} ight)^T \left(x_1-x_2 ight)=0$

因此，结合上述方程，我们得到：

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

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

因此，矛盾。

示例

步骤 1 − $f\left ( x ight )=X^3$

$设 f \left ( x_1 ight )\leq f\left ( x_2 ight )$

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

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

因此，$f\left ( x ight )$是准凸的。

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

设 $\hat{x_1}=\left ( 2, -2 ight )$ 且 $\hat{x_2}=\left ( 1, 0 ight )$

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

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

因此 $f\left ( x ight )$ 不是拟凸的。