凸最佳化 - 凸集

---

---

設 $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$

因此，用數學歸納法證明。