可微拟凸函数


定理

设 S 为 $\mathbb{R}^n$ 中的非空凸集且 $f:S \rightarrow \mathbb{R}$ 在 S 上可微,则 f 为拟凸当且仅当对于任何 $x_1,x_2 \在 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 \右)^T\左 (x_1-x_2 \右)$

$+\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$ 为 $\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 \左 ( 0, 1 \右 )$

对于 $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 \左 ( 0,1 \右 ) \右 \}$

因此我们可以找到 $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 )$

$\右箭头 x_{1}^{3}\leq x_{2}^{3}\右箭头 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 \左(\帽子{x_2}\右)$

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

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