【非线性优化理论】凸集

七彩极 · 发表于 2022-8-22 17:48

凸集在凸优化问题中起着重要的作用，若一个优化问题是凸优化问题，那么约束条件组成的集合必须是凸集，那么如何判断一个集合是凸集呢？优化问题的约束条件往往是多个的，而且复杂，可能是经过某种运算得到，那么凸集的哪些代数运算仍能保持凸性？凸集的拓扑性质又有哪些呢？

1. 凸集的定义

定义1：如果集合 C \subseteq \mathbb{R}^n 中的任意两点 \mathbf{x},\mathbf{y} ，对 \lambda \in [0,1] 满足 \lambda \mathbf{x}+(1-\lambda)\mathbf{y} \in C ，则称集合 C 为凸集
直观上，如果一个集合是凸集，则集合内任意两点的连线仍在该集合内。以二维平面举例

二维平面中的一些凸集与非凸集

2. 常见的凸集

2.1 超平面、半空间及开半空间

设 \mathbb{a} \in \mathbb{R}^n \{0\},b \in \mathbb{R}
1.超平面： H=\{\mathbf{x} \in \mathbb{R}^n : \mathbf{a}^{\top}\mathbf{x}=b\}
2.半空间： H^{-}=\{\mathbf{x} \in \mathbb{R}^n:\mathbf{a}^{\top}\mathbf{x} \leq b\} ， H^{+}=\{\mathbf{x} \in \mathbb{R}^n:\mathbf{a}^{\top}\mathbf{x} \geq b\}
3.开半空间： H=\{\mathbf{x} \in \mathbb{R}^n:\mathbf{a}^{\top}\mathbf{x} < b\}
容易证明超平面、半空间、开半空间都是凸集，这里省略证明
2.2 开球与闭球

设 \mathbb{c} \in \mathbb{R}^n,r >0 ， \|.\| 是 \mathbb{R}^n 中的任意范数，则
1.开球： B(\mathbf{c},r)=\{\mathbf{x} \in \mathbb{R}:\|\mathbf{x}-c\| < r\}
2.闭球： B[\mathbf{c},r]=\{\mathbb{x} \in \mathbb{R}^n:\|\mathbf{x}-\mathbf{c}\| \leq r\}
证明开球和闭球是凸集是容易的，并且证明是凸集只需要利用范数的三角不等式即可，因此可以是任意范数
2.3 椭球

椭球可以用如下集合表示 E=\{\mathbb{x} \in \mathbb{R}^n:\mathbb{x}^{\top}Q\mathbb{x}+2\mathbb{b}^{\top}\mathbb{x}+c \leq 0\}\\
其中 Q \in \mathbb{R}^{n \times n} 是正定的， b \in \mathbb{R}^n,c \in \mathbb{R} 。椭球是一个凸集。令 f(\mathbb{x})=\mathbb{x}^{\top}Q\mathbb{x}+2\mathbb{b}^{\top}\mathbb{x}+c \\则集合 E 等价于 E=\{\mathbb{x} \in \mathbb{R}^n:f(\mathbb{x}) \leq 0\} ，按照凸集的定义去证明椭球是一个凸集，取 \mathbf{x},\mathbf{y} \in E,\lambda \in [0,1] ，则 f(\mathbf{x}) \leq 0,f(\mathbf{y}) \leq 0 ，令 \mathbf{z} =\lambda \mathbf{x}+(1-\lambda)\mathbf{y} ，则 \begin{aligned} \mathbf{z}^{\top}Q\mathbf{z}&=(\lambda \mathbf{x}+(1-\lambda)\mathbf{y})^{\top}Q(\lambda \mathbf{x}+(1-\lambda)\mathbf{y})\\ &=\lambda^2\mathbf{x}^{\top}Q\mathbf{x}+(1-\lambda)^2\mathbf{y}^{\top}Q\mathbf{y}+2\lambda(1-\lambda)\mathbf{x}^{\top}Q\mathbf{y}\quad(1) \end{aligned} \\
已知的条件中都没有交叉的项 \mathbf{x}^{\top}Q\mathbf{y} ，因此要想办法将这一项去掉。因为 Q 是正定的，因此有\mathbf{x}^{\top}Q\mathbf{y}=(Q^{1/2}\mathbf{x})^{\top}(Q^{1/2}\mathbf{y})\\利用柯西-施瓦茨不等式可以得到
\mathbf{x}^{\top}Q\mathbf{y} \leq \|Q^{1/2}\mathbf{x}\|\|Q^{1/2}\mathbf{y}\|=\sqrt{\mathbf{x}^{\top}Q\mathbf{x}}\sqrt{\mathbf{y}^{\top}Q\mathbf{y}}\leq \frac{1}{2}(\mathbf{x}^{\top}Q\mathbf{x}+\mathbf{y}^{\top}Q\mathbf{y})\quad(2)\\其中最后一个不等式由 \sqrt{ac} \leq \frac{1}{2}(a+c) 得到。将 (2) 式代入 (1) 式可以得到 \mathbf{z}^{\top}Q\mathbf{z} \leq \lambda \mathbf{x}^{\top}Q\mathbf{x}+(1-\lambda)\mathbf{y}^{\top}Q\mathbf{y}\\ 因此 \begin{aligned} f(\mathbf{z}) &=\mathbf{z}^{\top}Q\mathbf{z}+2\mathbf{b}^{\top}\mathbf{z}+c\\ &\leq \lambda \mathbf{x}^{\top}Q\mathbf{x}+(1-\lambda)\mathbf{y}^{\top}Q\mathbf{y}+2\lambda\mathbf{b}^{\top}\mathbf{x}+2(1-\lambda)\mathbf{b}^{\top}\mathbf{y}+c\\ &=\lambda(\mathbf{x}^{\top}Q\mathbf{x}+2\mathbf{b}^{\top}\mathbf{x}+c)+(1-\lambda)(\mathbf{y}^{\top}Q\mathbf{y}+2\mathbf{b}^{\top}\mathbf{y}+c)\\ &=\lambda f(\mathbf{x})+(1-\lambda)f(\mathbf{y}) \leq 0 \end{aligned}\\ 即 \mathbf{z} \in E ， E 是凸集
3. 保凸运算

凸性在交、加法、笛卡尔乘积、线性映射运算下保持不变，有如下定理
定理1：设 C_i \subseteq \mathbb{R}^n,i \in I 是凸集，其中 I 是指标集，可以是有限集，则 \cap_{i \in I}C_i 是凸集
证明过程也很简单，这里省略。凸集的交仍是凸集的一个典型的例子就是凸多面体，凸多面体是线性不等式组成的集合，如 P=\{\mathbf{x}\in \mathbb{R}^n:A\mathbf{x} \leq \mathbf{b}\}\\其中 A \in \mathbb{R}^{m \times n},\mathbf{b} \in \mathbb{R}^{m} 。 P 可以看成是 m 个线性不等式的交，即 P=\cap_{i=1}^{m}\{\mathbb{x} \in \mathbb{R}^n:A_i\mathbb{x} \leq b_i\}\\其中 A_i 是 A 的第 i 行，而 A_i\mathbb{x} \leq b_i 是半空间是凸的，因此 P 是凸集
定理2：设 C_1,C_2,...,C_k \subseteq \mathbb{R}^n 是凸集， \mu_1,\mu_2,...,\mu_k \in \mathbb{R} ，则集合 \mu_1C_1+\mu_2C_2+...+\mu_kC_k=\{\sum_{i=1}^{k}{u_i\mathbf{x}_i}:\mathbf{x}_i \in C_i,i=1,2,...,k\}\\
是凸集
考虑两个集合的加法， C \subseteq \mathbb{R}^n 是凸集， \mathbf{b} \in \mathbb{R}^n ，则集合 C+\mathbf{b}=\{\mathbf{x}+\mathbf{b}:\mathbf{x} \in C\}\\
是凸集，可以理解为沿着某个方向做了平移
定理3：设 C_i \subseteq \mathbb{R}^k,i=1,2,...,k 是凸集，则笛卡尔乘积组成的集合 C_1 \times C_2 \times ... \times C_m=\{(\mathbf{x}_1,\mathbf{x}_2,...,\mathbf{x}_m):\mathbf{x}_i \in C_i,i=1,2,...,m\}\\是凸集
定理4：设 M \subseteq \mathbb{R}^n 是一个凸集， A \in \mathbb{R}^{m \times n} ，则集合 A(M)=\{A\mathbf{x}:\mathbf{x} \in M\}\\
是凸集
定理5：设 D \subseteq \mathbb{R}^n 是一个凸集， A \in \mathbb{R}^{m \times n} ，则集合 A^{-1}(D)=\{\mathbf{x} \in \mathbb{R}^n:A\mathbf{x} \in D\}\\是凸集
定理2-4的证明都是非常简单的，这里也将省略
4. 凸包

定义2：给定 k 个向量 \mathbf{x}_1,\mathbf{x}_2,...,\mathbf{x}_k \in \mathbb{R}^{n} ，其凸组合为 \lambda_1\mathbf{x}_1+\lambda_2\mathbf{x}_2+...+...+\lambda_k\mathbf{x}_k\\其中 \lambda_1,\lambda_2,...,\lambda_k 非负且满足 \lambda_1+\lambda_2+...+\lambda_k=1
有了凸组合的定义可以得到如下定理
定理6：设 C \subseteq \mathbb{R}^n 是凸集， \mathbf{x}_1,\mathbf{x}_2,...,\mathbf{x}_m \in C ，则对任意 \lambda \in \Delta_{m} 都有 \sum_{i=1}^{m}\lambda_i\mathbf{x}_i \in C ，其中 \Delta_{m} 是单纯形
这个定理告诉我们凸集中的任意 k 个点的凸组合仍在凸集中，这个证明过程比较巧妙，使用的是归纳法证明，证明如下：
证明：当 m=1 时，显然成立，假设对 m 成立，即 \mathbf{x}_1,\mathbf{x}_2,...,\mathbf{x}_m \in C,\lambda \in \Delta_m,\sum_{i=1}^{m}{\lambda_i\mathbf{x}_i} \in C 。假设 \mathbf{x}_1,\mathbf{x}_2,...,\mathbf{x}_{m+1} \in C,\lambda \in \Delta_{m+1} ，下证 \mathbf{z}=\sum_{i=1}^{m+1}{\lambda_i\mathbf{x}_i} \in C ，即对 m+1 个向量也成立。如果 \lambda_{m+1}=1  ，则 \mathbf{z}=\mathbf{x}_{m+1} \in C ，则结论成立，如果 \lambda_{m+1} < 1 ，则 \begin{aligned} \mathbf{z}&=\sum_{i=1}^{m+1}\lambda_i\mathbf{x}_i\\ &=\sum_{i=1}^{m}\lambda_i\mathbf{x}_i+\lambda_{m+1}\mathbf{x}_{m+1}\\  &=(1-\lambda_{m+1})\underbrace{\sum_{i=1}^{m}\frac{\lambda_i}{1-\lambda_{m+1}}\mathbf{x}_i}_{\mathbf{v}}+\lambda_{m+1}\mathbf{x}_{m+1} \end{aligned}\\
因为 \sum_{i=1}^{m}\frac{\lambda_i}{1-\lambda_{m+1}}=\frac{1-\lambda_{m+1}}{1-\lambda_{m+1}}=1 ，并且 \sum_{i=1}^{m}\frac{\lambda_i}{1-\lambda_{m+1}}\mathbf{x}_i 是 C 中 m 个点的凸组合，由假设 \mathbf{v} \in C ，又有凸集的定义可以得到 \mathbf{z}=(1-\lambda_{m+1})\mathbf{v}+\lambda_{m+1}\mathbf{x}_{m+1} \in C
定义3：设 S \subseteq \mathbb{R}^n ， S 的凸包表示为 {\rm conv}(S) ，由 S 中的向量的所有凸组合组成，即 {\rm conv}(S)=\{\sum_{i=1}^{k}\lambda_i\mathbf{x}_i:\mathbf{x}_1,\mathbf{x}_2,...,\mathbf{x}_k \in S,\lambda \in \Delta_{k},k \in \mathbb{N}\}\\凸包 {\rm conv}(S)是包含 S 的最小凸集，即如果 S 包含于凸集 T 中，则 {\rm conv}(S) \subseteq T ，可以得到如下性质
性质1：设 S \subseteq \mathbb{R}^n ，如果 T 是凸集，且 S \subseteq T ，则 {\rm conv}(S) \subseteq T
这个性质的证明是简单的，这里跳过。下面介绍一个非常重要的定理
定理7【Caratheodory定理】：设 S \subseteq \mathbb{R}^n,\mathbf{x} \in {\rm conv}(S) ，则存在 \mathbf{x}_1,\mathbf{x}_2,...,\mathbf{x}_{n+1} \in S 使得 \mathbf{x} \in {\rm conv}({\mathbf{x}_1,\mathbf{x}_2,...,\mathbf{x}_{n+1}}) ，即存在 \lambda \in \Delta_{n+1} 使得 \mathbf{x} = \sum_{i=1}^{n+1}\lambda_i\mathbf{x}_i\\Caratheodory定理告诉我们凸包中的任一元素至多可由 S 中的 n+1 个元素进行凸组合得到，给出了凸包中元素的表示方法，这个定理在证明凸集的拓扑性质中经常用到
证明：设 \mathbf{x} \in {\rm conv}(S) ，由凸包的定义可得，存在 \mathbf{x}_1,\mathbf{x}_2,...,\mathbf{x}_k \in S,\lambda \in \Delta_{k+1} 使得 \mathbf{x}=\sum_{i=1}^{k}\lambda_i\mathbf{x}_i\\不妨设 \lambda_i>0,i=1,2,...,k 。如果 k \leq n+1 ，则结论成立。如果 k \geq n+2 ，则向量 \mathbf{x}_2-\mathbf{x}_1,\mathbf{x}_3-\mathbf{x}_1,...,\mathbf{x}_k-\mathbf{x}_1 是线性相关的，因为设 \mathbf{a}_1=\mathbf{x}_2-\mathbf{x}_1,\mathbf{a}_2=\mathbf{x}_3-\mathbf{x}_1,...,\mathbf{a}_{k-1}=\mathbf{x}_k-\mathbf{x}_1\\ y_1\mathbf{a}_1+y_2\mathbf{a}_2+...+y_k\mathbf{a}_k=0 可以写成线程方程组的形式，方程组的个数(n)小于未知量的个数(k-1)，因此方程组存在非零解，即存在不全为0的 \mu_2,\mu_3,...,\mu_k 使得 \sum_{i=2}^{k}\mu_i(\mathbf{x}_i-\mathbf{x}_1)=0\\ 令 \mu_1=-\sum_{i=2}^{k}\mu_i ，则上式变为 \sum_{i=1}^{k}{\mu_i\mathbf{x}_i}=0\\其中 \mu_1,\mu_2,...,\mu_k 不全为0，又因为 \sum_{i=1}^{k}{\mu_i}=0 ，因此必存在一个 \mu_i < 0 (可用反证法证明)。设 \alpha \in \mathbb{R}_{+} ，则有 \mathbf{x}=\sum_{i=1}^{k}{\lambda_i\mathbf{x}_i}=\sum_{i=1}^{k}{\lambda_i\mathbf{x}_i}+\alpha\sum_{i=1}^{k}{\mu_i\mathbf{x}_i}=\sum_{i=1}^{k}({\lambda_i+\alpha \mu_i)\mathbf{x}_i} \quad(3)\\ 因为 \sum_{i=1}^{k}({\lambda_i+\alpha \mu_i})=1 ，因此 (3) 式是 \mathbf{x} 的一个凸组合当且仅当 \lambda_i+\alpha \mu_i \geq 0,i=1,...,k \quad(4)\\ 因为 \lambda_i >0,i=1,...,k ，因此当 \alpha \in [0,\varepsilon] 时， (4) 式成立，其中 \varepsilon=\min_{i,u_i < 0}\{- \frac{\lambda_i}{\mu_i}\}  ，并且 \varepsilon 是良定义的，因为由前面的分析一定存在一个 \mu_i <0 。用 \varepsilon 替换 \alpha ，则 \lambda_j+\varepsilon \mu_j=0\\
j \in \arg \min_{i,u_i < 0}\{- \frac{\lambda_i}{\mu_i}\}  ，因此得到了 \mathbf{x} 的一个用 k-1 个向量表示的凸组合，这个过程可以一直进行下去，直到\mathbf{x} 可以用不超过 n+1 个向量的凸组合表示出
5. 极点

定义4：设 S \subseteq \mathbb{R}^n ， \mathbf{x} \in S 称为 S 的极点如果存在 \mathbf{x}_1,\mathbf{x}_{2} \in S(\mathbf{x}_1 \neq \mathbf{x}_2),\lambda \in (0,1) 使得 \mathbf{x}=\lambda \mathbf{x}_1+(1-\lambda)\mathbf{x}_2 。 S 的极值点的集合表示为 {\rm ext}(S)
即极值点不能用两个不同的点的凸组合表示。极值点在线性规划中解集的刻画中起着重要的作用，本篇文章中只介绍极值点与凸包的关系，关于极值点与凸包的关系有如下重要的定理
定理8【Krein-Milman定理】：设 S \subseteq \mathbb{R}^n 是紧凸集，则 S={\rm conv}({\rm ext}(S))
这个定理说明紧凸集可由其极点的所有凸组合表示出(即极点的凸包)
6. 凸集的拓扑性质

首先证明凸集的闭包仍是凸集
定理9：设 C \subseteq \mathbb{R}^n 是一个凸集，则 {\rm cl}(C) 是凸集。其中 {\rm cl}(C) 表示集合 C 的闭包
证明：根据凸集的定义去证明，取 \mathbf{x},\mathbf{y} \in {\rm cl}(C),\lambda \in [0,1] ，去证明 \lambda \mathbf{x}+(1-\lambda)\mathbf{y} \in {\rm cl}(C) 。因为 \mathbf{x},\mathbf{y} \in {\rm cl}(C) ，因此存在点列 \{\mathbf{x}_k\}_{k \geq 0} \subseteq C,\{\mathbf{y}_k\}_{k \geq 0} \subseteq C ，且 \mathbf{x}_k \to \mathbf{x},\mathbf{y}_k \to \mathbf{y} 。因为 C 为凸集，则有 \lambda \mathbf{x}_k+(1-\lambda)\mathbf{y}_k \in C ，且 \lambda \mathbf{x}_k+(1-\lambda)\mathbf{y}_k \to \lambda \mathbf{x}+(1-\lambda)\mathbf{y} ，因此存在 C 中的点列 \{\lambda \mathbf{x}_k+(1-\lambda)\mathbf{y}_k\}_{k \geq 0} ，且 \lambda \mathbf{x}_k+(1-\lambda)\mathbf{y}_k \to \lambda \mathbf{x}+(1-\lambda)\mathbf{y} ，由此得到 \lambda \mathbf{x}+(1-\lambda)\mathbf{y} \in {\rm cl}(C)
凸集的内点也构成凸集，但是证明过程比前面一个定理难一些，首先证明一个引理
引理1【线段原则】：设 C 是凸集，假设 {\rm int}(C) \neq \emptyset ，假设 \mathbf{x} \in {\rm int}(C),\mathbf{y} \in {\rm cl}(C) ，则对任意\lambda \in (0,1)有 (1-\lambda)\mathbf{x}+\lambda \mathbf{y} \in {\rm int}(C) 。其中 {\rm int}(C) 表示 C 的内点
证明：因为 \mathbf{x} \in {\rm int}(C)  ，则由内点的定义可以得到， B(\mathbf{x},\varepsilon) \subseteq C 。设 \mathbf{z}=(1-\lambda)\mathbf{x}+\lambda \mathbf{y} ，要证 \mathbf{z} \in {\rm int}(C) ，即证明 B(\mathbf{z},(1-\lambda)\varepsilon) \subseteq C ，也等同于证明如果 \mathbf{w} 满足 \|\mathbf{w}-\mathbf{z}\| <(1-\lambda)\varepsilon ，那么 \mathbf{w} \in C 。因为 \frac{(1-\lambda)\varepsilon-\|\mathbf{w}-\mathbf{z}\|}{\lambda} > 0 ，因此可以找到一个 \mathbf{w}_1 \in C 使得 \|\mathbf{w}_1-\mathbf{y}\| < \frac{(1-\lambda)\varepsilon-\|\mathbf{w}-\mathbf{z}\|}{\lambda}\quad(5)\\至于为什么需要满足这样的不等式是为了后面凑出 \mathbf{w}=\lambda \mathbf{w}_1+(1-\lambda)\mathbf{w}_2 \in C
设 \mathbf{w}_2=\frac{1}{1-\lambda}(\mathbf{w}-\lambda \mathbf{w}_1) ，则 \begin{aligned} \|\mathbf{w}_2-\mathbf{x}\| &= \left\|\frac{\mathbf{w}-\lambda \mathbf{w}_1}{1-\lambda}-\mathbf{x}\right\|\\ &=\frac{1}{1-\lambda}\|(\mathbf{w}-\mathbf{z})+\lambda(\mathbf{y}-\mathbf{w}_1)\|\\ & \leq \frac{1}{1-\lambda}(\|(\mathbf{w}-\mathbf{z})\|+\|\lambda(\mathbf{y}-\mathbf{w}_1)\|)\\ &<\varepsilon \end{aligned}\\其中最后一个不等式由 (5)  式得到，因此可以得到 \mathbf{w}_2 \in B(\mathbf{x},\varepsilon) \subseteq C ，即 \mathbf{w}_2 \in \in C 。设 \mathbf{w}=\lambda \mathbf{w}_1+(1-\lambda)\mathbf{w}_2 ，因为 \mathbf{w}_1,\mathbf{w}_2 \in C ，且 C 是凸集，可以得到 \mathbf{w} \in C ，即 \mathbf{z} \in {\rm int}(C)
有了引理1可以马上得到如下定理
定理10：设 C \subseteq \mathbb{R}^n 是凸集，则 {\rm int}(C)  是凸集
证明：如果 {\rm int}(C)=\emptyset ，则由公约空集是凸集，结论成立。如果 {\rm int}(C) \neq \emptyset ，因为 {\rm int}(C) \subseteq {\rm cl}(C) ，设 \mathbf{x}_1,\mathbf{x}_2 \in {\rm int}(C),\lambda \in (0,1)  则由线段原则可得 \lambda\mathbf{x}_1+(1-\lambda)\mathbf{x}_2 \in {\rm int}(C) ，因此{\rm int}(C) 是凸集
定理10可以理解为是线段原则中的一个特殊情况，由线段原则还可以得到如下定理
定理11：设 C 是凸集，且 {\rm int}(C) \neq \emptyset，则由
1. {\rm cl}({\rm int}(C))={\rm cl}(C)
2. {\rm int}({\rm cl}(C))={\rm int}(C)
证明：证明集合相等，即证明两个集合相互包含。首先证明1，左边包含于右边是显然的，因为 {\rm int}(C) \subseteq C ，两边同时取闭包可以得到 {\rm cl}({\rm int}(C))  \subseteq {\rm cl}(C) ，反过来，设 \mathbf{x} \in {\rm cl}(C),\mathbf{y} \in {\rm int}(C) ，设 \mathbf{x}_{k}=\frac{1}{k}\mathbf{y}+(1-\frac{1}{k})\mathbf{x} ，构造点列 \{\mathbf{x}_k \}_{k \geq 1} ，则由线段原则可得 \mathbf{x}_{k} \in {\rm int}(C) ，又因为 \mathbf{x}_k \to \mathbf{x} ，因此可得 \mathbf{x} \in {\rm cl}({\rm int}(C)) ，于是 {\rm cl}(C) \subseteq {\rm cl}({\rm int}(C)) 。下面证明2，左边包含于右边是显然的，因为 C \subseteq {\rm cl}(C) ，两边同时取 {\rm int} 即可，反过来即证任意 \mathbf{x} \in {\rm int}({\rm cl}(C)) ， \mathbf{x} \in {\rm int}(C)  ，因为 \mathbf{x} \in {\rm int}({\rm cl}(C)) ，则由内点的定义可以得到存在 \varepsilon > 0 使得 B(\mathbf{x},\varepsilon) \subseteq {\rm cl}(C) 。设 \mathbf{y} \in {\rm int}(C) ，如果 \mathbf{y}=\mathbf{x} ，则结论成立，否则定义 \mathbf{z}=\mathbf{x}+\alpha(\mathbf{x}-\mathbf{y})\\ 其中 \alpha=\frac{\varepsilon}{2\|\mathbf{x}-\mathbf{y}\|} 。因为 \|\mathbf{z}-\mathbf{x}\|=\frac{\varepsilon}{2} ，可以得到 \mathbf{z} \in {\rm cl}(C) 。因此由线段原则可以得到对任意 \lambda \in [0,1) ，有 (1-\lambda)\mathbf{y}+\lambda\mathbf{z} \in {\rm int}(C) ，特别地取 \lambda=\lambda_{\alpha}=\frac{1}{1+\alpha} ，且 (1-\lambda_{\alpha})\mathbf{y}+\lambda_{\alpha}\mathbf{z}=\mathbf{x} ，因此可以得到 \mathbf{x} \in {\rm int}(C) ，于是 {\rm int}({\rm cl}(C)) \subseteq {\rm int}(C)
2中反过来的证明是比较难想到的
一般来说，闭集的凸包不一定是闭集，比如由两个闭集的并组成的闭集 S=\{(0,0)^{\top}\}\cup\{(x,y)^{\top}:xy \geq 1,x \geq 0,y \geq 0\}\\其锥包由闭集和开集的并得到{\rm conv}(S)=\{(0,0)^{\top}\}\cup\mathbb{R}_{++}^{2}\\ 既不是开集又不是闭集。但是给闭集再加上一个有界的条件，就可以保证得到的凸包是闭集，可以得到如下性质
性质2：设 S \subseteq \mathbb{R}^n 是一个紧集，则 {\rm conv}(S) 是紧的
证明：首先证明 {\rm conv}(S) 是有界的，因为 S 是紧的，则存在 M >0 使得对任意 \mathbf{x} \in S 有 \|\mathbf{x}\| \leq M 。设 \mathbf{y} \in {\rm conv}(S) ，则由Caratheodory定理可得，存在 \mathbf{x}_1,\mathbf{x}_2,...,\mathbf{x}_{n+1} \in S,\lambda \in \Delta_{n+1}使得 \mathbf{y}=\sum_{i=1}^{n+1}\lambda_i\mathbf{x}_i ，因此可以得到 \|\mathbf{y}\| =\left\|\sum_{i=1}^{n+1}\lambda_i\mathbf{x}_i\right\| \leq \sum_{i=1}^{n+1}\lambda_i\|\mathbf{x}_i\| \leq M \sum_{i=1}^{n+1}\lambda_i=M \\ 因此{\rm conv}(S) 是有界的。下证{\rm conv}(S) 是闭集，设 \{\mathbf{y}_k\}_{k \geq 1} 是{\rm conv}(S) 中的一个点列，且 \mathbf{y}_k \to \mathbf{y} \in \mathbb{R}^n ，证明{\rm conv}(S) 是闭集，即证明 \mathbf{y} \in {\rm conv}(S) 。由Caratheodory定理可得，存在 \mathbf{x}_1^k,\mathbf{x}_2^k,...,\mathbf{x}_{n+1}^k\in S ， \lambda^k \in \Delta_{n+1}使得\mathbf{y}_{k}=\sum_{i=1}^{n+1}\lambda_i^k\mathbf{x}_i^k\\ 因为 S 和 \Delta_{n+1} 是紧集，紧集上的任意点列都存在一个收敛子列，因此 \{(\lambda^k,\mathbf{x}_1^k,\mathbf{x}_2^k,...,\mathbf{x}_{n+1}^k)\} 存在一个收敛子列 \{(\lambda^{k_j},\mathbf{x}_1^{k_j},\mathbf{x}_2^{k_j},...,\mathbf{x}_{n+1}^{k_j})\} ，设其极限为 (\lambda,\mathbf{x}_1,\mathbf{x}_2,...,\mathbf{x}_{n+1}) ，其中 \lambda \in \Delta_{n+1} ， \mathbf{x}_1,\mathbf{x}_2,...,\mathbf{x}_{n+1} \in S 。 \mathbf{y}_{k_j}=\sum_{i=1}^{n+1}\lambda_i^{k_j}\mathbf{x}_i^{k_j} ，两边同时取极限得到 \mathbf{y}=\sum_{i=1}^{n+1}\lambda_i\mathbf{x}_i\\ 因此可得 \mathbf{y} \in {\rm conv}(S)

		自动登录	找回密码
密码			立即注册

【非线性优化理论】凸集

本帖子中包含更多资源