第二讲 子空间、仿射集、凸集和锥

2020年09月28日 凸分析笔记

张伦传 明德新闻楼0203

子空间

• 记号：对于线性空间 $X$ 的非空子集 $A,B$，定义

  $$A \pm B \triangleq \{a \pm b| a \in A,b \in B\}, \lambda A \triangleq \{\lambda a | a \in A,\lambda \in \mathbb{R}\}.$$

• 对于 $X$ 的非空子集 $Y$，若

  $$\forall x,y \in Y,x+y \in Y; \forall \lambda \in \mathbb{R}, \lambda \cdot x \in Y.$$

  则 $Y$ 是 $X$ 的线性子空间，简称子空间（subspace）.

• $X = \mathbb{R}^2$ 的子空间：平凡的零向量空间 $\{0\}$，全空间 $\mathbb{R}^2$，经过原点的直线.

• 子空间的平移是仿射集.

仿射集

• 记号

  • 线段 $[x,y]=\{(1-\lambda)x+\lambda y=x+\lambda(y-x)|\lambda \in [0,1]\}$，其中 $(1-\lambda)x+\lambda,\lambda \in [0,1]$ 被称为凸组合，因此线段关于凸组合封闭.
  • 射线 $\overrightarrow{xy}=\{(1-\lambda)x+\lambda y=x+\lambda(y-x)|\lambda \in [0,+\infty)\}$.

• 直线 $\overline{xy}=\{(1-\lambda)x+\lambda y=x+\lambda(y-x)|\lambda \in \mathbb{R} \}$，其中 $(1-\lambda)x+\lambda,\lambda \in \mathbb{R}$ 被称为仿射组合，因此直线关于仿射组合封闭.

  • 线性组合 $\lambda x+\mu y,\lambda,\mu \in \mathbb{R}$ 全体是 $x,y$ 张成的线性空间.

• 定义：对于线性空间 $X$ 的非空子集，若存在子空间 $Y$，及 $a_0 \in X$ 使得 $A=a_0+Y$，则称 $A$ 为仿射集（affine set）.

• 线性空间的非空子集 $A$ 是仿射集当且仅当

  $$\forall x_1,x_2 \in A, \overline{x_1x_2} \subset A.$$

  证明：$\Rightarrow:$ 若 $A$ 是仿射集，则存在子空间 $Y$ 及 $x_0$ 满足 $A=x_0+Y$.

  $\forall x_1,x_2 \in A, \forall \lambda \in \mathbb{R}$，下面证明

  $$(1-\lambda)x_1+\lambda x_2 \in A.$$

  不难发现 $(1-\lambda)(x_1-x_0)+\lambda (x_2-x_0) \in Y = A-x_0$.

  定义 $\bar{x}=(1-\lambda)x_1 +\lambda x_2$，则 $\bar{x}-x_0 \in A-x_0$，即 $\bar{x} \in A$.

  $\Leftarrow:$ 若 $A$ 关于仿射组合封闭，即

  $$\forall x_0,x_1 \in A, \forall \lambda \in \mathbb{R}, (1-\lambda)x_0 + \lambda x_1 \in A.$$

  对于任意 $\mu \in \mathbb{R}$ 以及任意 $x_2 \in A$，再次利用对仿射组合的封闭性，

  $$(1-\mu)[(1-\lambda)x_0 + \lambda x_1]+\mu x_2 \in A.$$

  定义 $\nu = \lambda(1-\mu)$，整理得 $(1-\mu-\nu)x_1+\nu x_2+\mu x_3 \in A$，即

  $$\nu(x_1-x_0)+\mu (x_2-x_0) \in A-x_0.$$

  注意到 $\mu,\nu$ 均可自由取遍全部实数，故 $A-x_0$ 是线性子空间.

• $A$ 是仿射集，$a_1,a_2 \in A$，则 $A-a_1,A-a_2$ 是同一个子空间吗？

  分析：对于任意 $y \in A-a_1$，即存在 $x_1$ 满足 $y=x_1-a_1$ 且 $x_1 \in A$.

  下证 $y \in A-a_2$，即存在 $x_2$ 满足 $y=x_2-a_2$ 且 $x_2 \in A$.

  不妨令 $x_2=x_1+(a_2-a_1)$，显然 $x_2-a_2=x_1-a_1=y$.

  $a_1-a_2$ 是 $a_1,a_2$ 的一个仿射组合，则 $a_2-a_1 \in A$.

  那么，$x_1+(a_2-a_1)=x_2 \in A$.

  $A-a_1 \subset A- a_2$ 得证.

  同理可证，$A- a_2\subset A-a_1$.

• 非空集合 $A$ 是仿射集当且仅当

  $$\forall \lambda_1,\lambda_2,\cdots,\lambda_n \in \mathbb{R}, \sum_{i=1}^n \lambda_i=1, \\ \forall x_1,x_2,\cdots,x_n \in A, \sum_{i=1}^n \lambda_i x_i \in A.$$

  分析：取 $n=2$ 可知充分性显然成立，下证必要性，即已知 $n=2$ 的情况成立，证明一般情形.

  显然 $n=1$ 和 $n=2$ 时成立.

  下面采用数学归纳法，假设 $n=k$ 的情况成立，即

  $$\forall \lambda_1,\lambda_2,\cdots,\lambda_k \in \mathbb{R}, \sum_{i=1}^k \lambda_i=1, \\ \forall x_1,x_2,\cdots,x_k \in A, \sum_{i=1}^k \lambda_i x_i \in A.$$

  利用 $n=1$ 时的结论有

  $$\frac{\sum_{i=1}^k \lambda_i x_i}{\sum_{i=1}^k \lambda_i} =\sum_{i=1}^k \frac{\lambda_i}{\sum_{i=1}^k \lambda_i} x_i \in A.$$

  再利用 $n=2$ 时的结论有

  $$\sum_{i=1}^k \lambda_i \frac{\sum_{i=1}^k \lambda_i x_i}{\sum_{i=1}^k \lambda_i}+(1-\sum_{i=1}^k \lambda_i)x_{k+1} \in A.$$

  整理得

  $$\sum_{i=1}^k \lambda_i x_i+(1-\sum_{i=1}^k \lambda_i)x_{k+1} \in A.$$

  只需定义 $\lambda'_i=\lambda_i(i=1,\cdots,k),\lambda'_{k+1}=1-\sum_{i=1}^k \lambda_i$（取值任意）即可得证 $n=k+1$ 的情形.

凸集

• 定义：线性空间 $X$ 的非空子集 $A$ 是凸集（convex sets）当且仅当

  $$\forall x_1,x_2 \in A,[x_1,x_2] \subset A.$$

• 若 $A,B$ 均为凸集，则 $A \cup B$ 不一定是凸集，$\lambda A+B$ 一定是凸集.

  分析：$A \cup B$，举反例发现 $\mathbb{R}^2$ 空间中两个不重合的圆的并不是凸集.

  $$\lambda A+B=\{\lambda x + y: x \in A,y \in B\}, \forall \lambda \in \mathbb{R}.$$

  对于 $\mu \in \mathbb{R}$，凸组合

  $$(1-\mu)(\lambda x_1 + y_1)+\mu (\lambda x_2+y_2)=\lambda [(1-\mu)x_1 +x_2)+[(1-\mu)y_1+y_2] \in \lambda A+B.$$

  得证.

• $A=\{(x_1,x_2)|x_1^2+x_2^2 \leq 1\},B=\{(x_1,x_2)|x_2=2x_1\}$. 证明 $A+B$ 是一个凸集且绘图.

  分析一：由上面的命题知 $A+B$ 是一个凸集.

  $A+B$ 的图为单位圆 $A$ 的两条切线 $\ell_1,\ell_2$ 之间的全部元素，其中

  $$\ell_1: x_2+\frac{\sqrt{2}}{2}=2(x_1-\frac{\sqrt{2}}{2}),\ell_2: x_2-\frac{\sqrt{2}}{2}=2(x_1+\frac{\sqrt{2}}{2}).$$

  即

  $$A+B=\{(x_1,x_2): x_2+\frac{\sqrt{2}}{2}\ge 2(x_1-\frac{\sqrt{2}}{2}),x_2-\frac{\sqrt{2}}{2}\leq 2(x_1+\frac{\sqrt{2}}{2})\} \\ =\{(x_1,x_2): x_2-2x_1\ge -\frac{3\sqrt{2}}{2},x_2-2x_1\leq \frac{3\sqrt{2}}{2}\}.$$

  分析二：$A=\{(x_1,x_2)|x_1+x_2 \leq 1\},B=\{(y_1,y_2)|y_2=2y_1\}$.

  令 $(z_1,z_2) \in A+B, z_1 =x_1+y_1,z_2=x_2+y_2$，即

  $$x_1=z_1-y_1,x_2=z_2-y_2=z_2-2y_1.$$

  代入单位圆方程得 $(z_1-y_1)^2+(z_2-2y_1)^2 \leq 1$.

  可知 $A+B$ 为圆心在 $y=2x$ 上半径为1的所有圆覆盖的区域.

• 若 $A$ 为凸集，则 $A+A=2A$. 进而 $\lambda A+\mu A=(\lambda+\mu)A,\ \forall \lambda, \mu \ge 0$. 反之亦成立.

  分析：只证明一般情形.

  假设 $A$ 为凸集.

  当 $\lambda,\mu$ 任意一个等于零的时候，显然成立，下面只针对均为正数的情况.

  对于任意 $y \in \lambda A+\mu A$，总存在 $x_1 \in A,x_2 \in A$，满足 $y=\lambda x_1 + \mu x_2$.

  对于正实数 $\lambda,\mu$，不难发现 $\lambda/(\lambda+\mu),\mu/(\lambda+\mu) \in (0,1)$.

  于是凸组合

  $$\frac{\lambda}{\lambda+\mu} x_1+\frac{\mu}{\lambda+\mu}x_2=\frac{1}{\lambda+\mu} y \in A.$$

  即 $y \in (\lambda+\mu)A$.

  对于任意 $y \in (\lambda+\mu)A$，总存在 $x \in A$，满足 $y=(\lambda+\mu)x=\lambda x + \mu x \in \lambda A+\mu A$.

   

  下面证明逆命题成立.

  假设 $\lambda,\mu$ 不同时为零，则 $\lambda/(\lambda+\mu),\mu/(\lambda+\mu)$ 可取遍 $[0,1]$ 上的全部实数.

  则由 $\lambda A+\mu A=(\lambda+\mu)A$ 知，$\frac{\lambda}{\lambda+\mu} A+\frac{\mu}{\lambda+\mu} A= A$.

  故 $A$ 是对凸组合封闭的凸集.

锥

• 定义：线性空间 $X$ 的非空集合 $C$，对于给定 $x_1 \in X$ （$x_1$ 可能不是 $C$ 中的元素）. 若 $\forall x \in C$，满足 $\overrightarrow{x_1 x} \subset C$，则称 $C$ 为以 $x_1$ 为顶点的锥. 特别地，$x_1=0$，则称之为锥. 下面均默认 $x_1=0$.

• 若 $C$ 既是凸集，又是锥，则称之为凸锥.

• $C$ 是凸锥当且仅当

  $$\forall \lambda_1,\lambda_2 >0,\lambda_1 C+\lambda_2 C \subset C.$$

  分析：若 $C$ 是凸锥，则 $C$ 是凸集，因而

$$\forall \lambda_1,\lambda_2 >0,\frac{\lambda_1}{\lambda_1+\lambda_2} C+\frac{\lambda_2}{\lambda_1+\lambda_2} C \subset C.$$

又 $C$ 是锥，

$$\forall \lambda_1,\lambda_2 >0,(\lambda_1+\lambda_2)(\frac{\lambda_1}{\lambda_1+\lambda_2} C+\frac{\lambda_2}{\lambda_1+\lambda_2} C)=\lambda_1 C+\lambda_2 C \subset C.$$

反之，令 $\lambda_2 \rightarrow 0$，则

$$\forall \lambda_1>0,\lambda_1 C \subset C.$$

显然 $\lambda_1=0$ 时，也有 $\lambda_1 C =\{0\} \subset C.$

因而，$C$ 是锥.

将 $\lambda_1,\lambda_2$ 限制为 $\lambda_1+\lambda_2=1,\lambda_1,\lambda_2 \ge 0$ 可证 $C$ 也是凸集.

• $E$ 的线性包（仿射包、锥包、凸包）为包含 $E$ 的最小线性空间（仿射集、锥、凸集）

  • 令 $\{E_j,j \in J\}$ 为全体包含 $E$ 的线性空间：

    $$\text{lin} E =\bigcap_{j \in J} E_j = \{\sum_{i=1}^n \lambda_i x_i| \lambda_i \in \mathbb{R}, x_i \in E, i=1,\cdots,n\}.$$

  • 令 $\{E_j,j \in J\}$ 为全体包含 $E$ 的仿射集：

    $$\text{aff} E=\bigcap_{j \in J} E_j = \{\sum_{i=1}^n \lambda_i x_i| \lambda_i \in \mathbb{R}, \sum_{i=1}^n \lambda_i = 1, x_i \in E, i=1,\cdots,n\}.$$

  • 令 $\{E_j,j \in J\}$ 为全体包含 $E$ 的凸集：

    $$\text{conv} E =\bigcap_{j \in J} E_j = \{\sum_{i=1}^n \lambda_i x_i| \lambda_i \in [0,1], \sum_{i=1}^n \lambda_i = 1,x_i \in E, i=1,\cdots,n\}.$$

  • 令 $\{E_j,j \in J\}$ 为全体包含 $E$ 的锥：

    $$\text{cone} E =\bigcap_{j \in J} E_j = \{\lambda x| \lambda > 0, x \in E\}=\bigcup_{\lambda > 0} \lambda E.$$

• 证明 $E$ 的凸包为包含 $E$ 的最小凸集.

  首先证明 $\text{conv}E$ 是一个凸集.

  对于任意 $\mu \in [0,1]$，构造凸组合如下

  $$(1-\mu)\sum_{i=1}^{n} \lambda_i x_i+\mu \sum_{j=1}^{n} \lambda_j x_j.$$

  其中，

  $$(1-\mu)\sum_{i=1}^{n} \lambda_i +\mu \sum_{j=1}^{n} \lambda_j =1.$$

  因而，

  $$(1-\mu)\sum_{i=1}^{n} \lambda_i x_i+\mu \sum_{j=1}^{n} \lambda_j x_j \in \text{conv} E.$$

   

  若存在凸集 $E' \supset E$，下面证明 $E' \supset \text{conv}E$.

  $\forall \lambda_i \in [0,1], \sum_{i=1}^n \lambda_i = 1,x_i \in E \subset E', i=1,\cdots,n$，满足 $\sum_{i=1}^n \lambda_i x_i \in E'$.

  得证.