凸优化 - 凸集

设 $S\subseteq \mathbb{R}^n$ 如果连接集合 S 中任意两点的线段也属于 S，则集合 S 被称为凸集，即，如果 $x_1,x_2 \in S$，则 $\lambda x_1+\left ( 1-\lambda ight )x_2 \in S$，其中 $\lambda \in\left ( 0,1 ight )$。

注意 −

• 两个凸集的并集可能是也可能不是凸集。
• 两个凸集的交集总是凸集。

证明

设 $S_1$ 和$S_2$ 是两个凸集。

设 $S_3=S_1 \cap S_2$

设 $x_1,x_2 \in S_3$

由于 $S_3=S_1 \cap S_2$，因此 $x_1,x_2 \in S_1$ 和 $x_1,x_2 \in S_2$

由于 $S_i$ 是凸集，$\forall$ $i \in 1,2,$

因此 $\lambda x_1+\left ( 1-\lambda ight )x_2 \in S_i$ 其中 $\lambda \in \left ( 0,1 ight )$

因此，$\lambda x_1+\left ( 1-\lambda ight )x_2 \in S_1\cap S_2$

$\Rightarrow \lambda x_1+\left ( 1-\lambda ight )x_2 \in S_3$

因此，$S_3$是凸集。

• 形式为$\displaystyle\sum\limits_{i=1}^k \lambda_ix_i$的加权平均值，其中$\displaystyle\sum\limits_{i=1}^k \lambda_i=1$且$\lambda_i\geq 0,\forall i \in \left [ 1,k ight ]$的加权平均值称为$x_1,x_2,....x_k.$的圆锥组合。

• 形式为$\displaystyle\sum\limits_{i=1}^k \lambda_ix_i$，其中 $\displaystyle\sum\limits_{i=1}^k \lambda_i=1$ 称为 $x_1,x_2,....x_k.$ 的仿射组合

• 形式为 $\displaystyle\sum\limits_{i=1}^k \lambda_ix_i$ 的加权平均值称为 $x_1,x_2,....x_k.$ 的线性组合

示例

步骤 1 −证明集合 $S=\left \{ x \in \mathbb{R}^n:Cx\leq \alpha ight \}$ 是凸集。

解答

设 $x_1$ 和 $x_2 \in S$

$\Rightarrow Cx_1\leq \alpha$ 和 $\:and \:Cx_2\leq \alpha$

证明：$\:\:y=\left ( \lambda x_1+\left ( 1-\lambda ight )x_2 ight )\in S \:\forall \:\lambda \in\left ( 0,1 ight )$

$Cy=C\left ( \lambda x_1+\left ( 1-\lambda ight )x_2 ight )=\lambda Cx_1+\left ( 1-\lambda ight )Cx_2$

$\Rightarrow Cy\leq \lambda \alpha+\left ( 1-\lambda ight )\alpha$

$\Rightarrow Cy\leq \alpha$

$\Rightarrow y\in S$

因此，$S$ 是凸集。

步骤 2 −证明集合 $S=\left \{ \left ( x_1,x_2 ight )\in \mathbb{R}^2:x_{1}^{2}\leq 8x_2 ight \}$ 是凸集。

解决方案

设 $x,y \in S$

设 $x=\left ( x_1,x_2 ight )$ 和 $y=\left ( y_1,y_2 ight )$

$\Rightarrow x_{1}^{2}\leq 8x_2$ 和 $y_{1}^{2}\leq 8y_2$

为了证明 − $\lambda x+\left ( 1-\lambda ight )y\in S\Rightarrow \lambda \left ( x_1,x_2 ight )+\left (1-\lambda ight )\left ( y_1,y_2 ight ) \in S\Rightarrow \left [ \lambda x_1+\left ( 1- \lambda)y_2] \in S ight ) ight ]$

$现在，\left [\lambda x_1+\left ( 1-\lambda ight )y_1 ight ]^{2}=\lambda ^2x_{1}^{2}+\left ( 1-\lambda ight )^2y_{1}^{2}+2 \lambda\left ( 1-\lambda ight )x_1y_1$

但 $2x_1y_1\leq x_{1}^{2}+y_{1}^{2}$

因此，

$\left [ \lambda x_1 +\left ( 1-\lambda ight )y_1 ight ]^{2}\leq \lambda ^2x_{1}^{2}+\left ( 1- \lambda ight )^2y_{1}^{2}+2 \lambda\left ( 1- \lambda ight )\left ( x_{1}^{2}+y_{1}^{2} ight )$

$\Rightarrow \left [ \lambda x_1+\left ( 1-\lambda ight )y_1 ight ]^{2}\leq \lambda x_{1}^{2}+\left ( 1- \lambda ight )y_{1}^{2}$

$\Rightarrow \left [ \lambda x_1+\left ( 1-\lambda ight )y_1 ight ]^{2}\leq 8\lambda x_2+8\left ( 1- \lambda ight )y_2$

$\Rightarrow \left [ \lambda x_1+\left ( 1-\lambda ight )y_1 ight ]^{2}\leq 8\left [\lambda x_2+\left ( 1- \lambda ight )y_2 ight ]$

$\Rightarrow \lambda x+\left ( 1- \lambda ight )y \in S$

步骤 3 − 证明集合 $S \in \mathbb{R}^n$ 是凸集当且仅当对于每个整数 k，$S$ 中任意 k 个点的每个凸组合都在 $S$ 中。

解决方案

设 $S$ 为凸集。然后，显示；

$c_1x_1+c_2x_2+.....+c_kx_k \in S, \displaystyle\sum\limits_{1}^k c_i=1,c_i\geq 0, \forall i \in 1,2,....,k$

通过归纳证明

对于 $k=1,x_1 \in S, c_1=1 \Rightarrow c_1x_1 \in S$

对于 $k=2,x_1,x_2 \in S, c_1+c_2=1$ 并且由于 S 是凸集

$\Rightarrow c_1x_1+c_2x_2 \in S.$

让 S 的 m 个点的凸组合在 S 中即，

$c_1x_1+c_2x_2+...+c_mx_m \in S,\displaystyle\sum\limits_{1}^m c_i=1 ,c_i \geq 0, \forall i \in 1,2,...,m$

现在，设 $x_1,x_2....,x_m,x_{m+1} \in S$

设 $x=\mu_1x_1+\mu_2x_2+...+\mu_mx_m+\mu_{m+1}x_{m+1}$

设 $x=\left ( \mu_1+\mu_2+...+\mu_m ight )\frac{\mu_1x_1+\mu_2x_2+\mu_mx_m}{\mu_1+\mu_2+.........+\mu_m}+\mu_{m+1}x_{m+1}$

设 $y=\frac{\mu_1x_1+\mu_2x_2+...+\mu_mx_m}{\mu_1+\mu_2+.........+\mu_m}$

$\Rightarrow x=\left ( \mu_1+\mu_2+...+\mu_m ight )y+\mu_{m+1}x_{m+1}$

现在 $y \in S$ 因为系数之和为 1。

$\Rightarrow x \in S$ 因为 S 是凸集，并且 $y,x_{m+1} \in S$

因此通过归纳证明。