强拟凸函数

---

设 $f:S\rightarrow \mathbb{R}^n$ 且 S 是 $\mathbb{R}^n$ 中的非空凸集，则 f 是强拟凸函数，如果对于 S 中的任何 $x_1,x_2 \ $ 与 $\left ( x_1 \right ) \neq \left ( x_2 \right )$，我们有 $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )< max \:\左 \{ 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 不是强拟凸函数。

在 S$ 中存在 $x_1,x_2 \ 且 $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\左 ( 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\左 ( u \右 )$$

这是一个矛盾。

因此，只存在一种全局最优解。

评论

• 强拟凸函数也是严格拟凸函数。
• 严格凸函数可能是强拟凸函数，也可能不是强拟凸函数。
• 可微的严格凸是强拟凸。