凸优化 - 凸集

---

---

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

注意 -

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

证明

设 $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 \right )x_2 \in S_i$，其中 $\lambda \in \left ( 0,1 \right )$

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

$\Rightarrow \lambda x_1+\left ( 1-\lambda \right )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 \right ]$，称为 $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 \right \}$ 是凸集。

解答

设 $x_1$ 和 $x_2 \in S$

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

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

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

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

$\Rightarrow Cy\leq \alpha$

$\Rightarrow y\in S$

因此，$S$ 是凸集。

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

解答

设 $x,y \in S$

设 $x=\left ( x_1,x_2 \right )$ 且 $y=\left ( y_1,y_2 \right )$

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

要证明 - $\lambda x+\left ( 1-\lambda \right )y\in S\Rightarrow \lambda \left ( x_1,x_2 \right )+\left (1-\lambda \right )\left ( y_1,y_2 \right ) \in S\Rightarrow \left [ \lambda x_1+\left ( 1- \lambda)y_2] \in S\right ) \right ]$

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

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

因此，

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

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

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

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

$\Rightarrow \lambda x+\left ( 1- \lambda \right )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 \right )\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 \right )y+\mu_{m+1}x_{m+1}$

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

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

因此，用数学归纳法证明。