EE364a Lecture2

凸集

1. 仿射集：集合内任意两不同点构成的直线集

• 直线：$x=\theta x_1+(1-\theta )x_2,\theta \in Rx=\backslash theta\; x\_1+(1-\backslash theta)x\_2,\backslash \; \backslash theta\backslash in\; R$

  • 从方向向量角度理解直线的形成：如上式，$x_{2}x\_2$作为一点，$x_1-x_{2}x\_1-x\_2$构成一个方向向量

  • $OC=\alpha OB+(1-\lambda )OAOC=\backslash alpha\; OB+(1-\backslash lambda)OA$的推导：点$\mathcal{C}\backslash mathcal\{C\}$在线段AB内，点$\mathcal{O}\backslash mathcal\{O\}$为直线AB外一点

    • $\mathcal{A}\mathcal{C}=\mathcal{O}\mathcal{C}-\mathcal{O}\mathcal{A}\backslash mathcal\{AC=OC-OA\}$
    • $\mathcal{A}\mathcal{B}=\mathcal{O}\mathcal{B}-\mathcal{O}\mathcal{A}\backslash mathcal\{AB=OB-OA\}$
    • $\mathcal{A}\mathcal{C}=\lambda \mathcal{A}\mathcal{B}\Rightarrow \mathcal{O}\mathcal{C}-\mathcal{O}\mathcal{A}=\lambda (\mathcal{O}\mathcal{B}-\mathcal{O}\mathcal{A})\backslash mathcal\{AC=\backslash lambda\; AB\}\backslash Rightarrow\; \backslash mathcal\{OC-OA\}=\backslash lambda(\backslash mathcal\{OB-OA\})$
    • $\mathcal{O}\mathcal{C}=\lambda \mathcal{O}\mathcal{B}+(1-\lambda )\mathcal{O}\mathcal{A}\backslash mathcal\{OC\}=\backslash lambda\; \backslash mathcal\{OB\}+(1-\backslash lambda)\backslash mathcal\{OA\}$
    • $\mathcal{O}\mathcal{C}\backslash mathcal\{OC\}$等向量可以看成C的向量坐标

  • 二维平面上的直线是一维的，但是直线方程是二维的（从$x_{i}x\_i$的下标看），所以n维空间的直线是$n-1n-1$维的，但方程是到$x_{n}x\_n$的；

• 仿射集可以表示成一个线性方程组的解（从定义出发思考）

2. 凸集

• 线段：凸集的定义就是两点之间的点仍在该集合内，$x=\theta x_1+(1-\theta )x_2,\theta \in [0,1]x=\backslash theta\; x\_1+(1-\backslash theta)x\_2,\backslash \; \backslash theta\; \backslash in\; [0,1]$；
• 凸组合：全部系数和为1且非负；
• 凸包：凸集内点构成的全部凸组合集合；
• 锥：$x=\theta x_0,\theta \ge 0x=\backslash theta\; x\_0,\; \backslash theta\backslash geq\; 0$；
• 锥组合：每个点系数非负构成的组合；
• 凸锥：系数和为1；
• 超平面：仿射且凸，$\{x\mathrm{\mid }{a}^{T}x=b\}(a\mathrm{\ne }0)\backslash \{x|a^Tx=b\backslash \}(a\backslash neq0)$，向量$aa$定义平面的法向（也可以看做平面的方向）
• 半空间：$\{x\mathrm{\mid }{a}^{T}x\le b\}(a\mathrm{\ne }0)\backslash \{x|a^Tx\backslash leq\; b\backslash \}(a\backslash neq0)$
• 欧几里得球：$B(x_c,r)=\{x\mathrm{\mid }\mathrm{\mid }\mathrm{\mid }x-x_c\mathrm{\mid }{\mathrm{\mid }}_2\le r\}B(x\_c,r)=\backslash \{x|\backslash \; ||x-x\_c||\_2\backslash leq\; r\backslash \}$
• 椭球：$\{x\mathrm{\mid }(x-x_0{)}^T{P}^{-1}(x-x_0)\le 1\}\backslash \{x|(x-x\_0)^TP^\{-1\}(x-x\_0)\backslash leq\; 1\backslash \}$，$P\in S_{++}^{n}P\backslash in\; S\_\{++\}^n$，即对称正定
• 范数球：可以看成欧球的推广，$NB(x_c,r)=\{x\mathrm{\mid }\mathrm{\mid }\mathrm{\mid }x-x_c\mathrm{\mid }\mathrm{\mid }\le r\}NB(x\_c,r)=\backslash \{x|\backslash \; ||x-x\_c||\backslash leq\; r\backslash \}$
• 范数锥：$\{(x,t)\mathrm{\mid }\mathrm{\mid }\mathrm{\mid }x\mathrm{\mid }\mathrm{\mid }\le t\}\backslash \{(x,t)|\backslash \; ||x||\backslash leq\; t\backslash \}$，欧几里得范数锥也称二阶锥
• 多面体：有限个线性不等式（半空间）和等式（超平面）构成的集合
• 半正定锥${\mathbf{S}}_{+}^n\backslash mathbf\{S\}^n\_+$：关于矩阵对象的凸性研究

  • ${\mathbf{S}}^n\backslash mathbf\{S\}^n$表示一个对称的$n\ast nn*n$矩阵

  • 半正定的$n\ast nn*n$矩阵为一个凸锥：${\mathbf{S}}_{+}^n=\{X\in {\mathbf{S}}^n\mathrm{\mid }X\ge 0\}\backslash mathbf\{S\}^n\_+=\backslash \{X\backslash in\; \backslash mathbf\{S\}^n|X\backslash geq\; 0\backslash \}$

  • 正定：${\mathbf{S}}_{++}^n=\{X\in {\mathbf{S}}^n\mathrm{\mid }X>0\}\backslash mathbf\{S\}^n\_\{++\}=\backslash \{X\backslash in\; \backslash mathbf\{S\}^n|X>0\backslash \}$

3. 保凸运算

• 如何构建一个凸集：从常见凸集结合保凸运算构造；
• 任意凸集的交
• 基于凸集的前提下，其仿射函数的像或原像都是凸的；
  • 线性矩阵不等式
  • 放缩变换、投影
  • 双曲锥
• 透视函数：$P:R^{n+1}\to R^{n}P:\; R^\{n+1\}\backslash rightarrow\; R^n$
  • $P(x,t)=x\mathrm{/}tdom(P)=\{(x,t)\mathrm{\mid }t>0\}P(x,t)=x/t\; \backslash \; \backslash \; dom(P)=\backslash \{(x,t)|t>0\backslash \}$
• 线性分数函数：$f:R^n\to R^{m}f:R^n\backslash rightarrow\; R^m$
  • $f(x)=\frac{Ax+b}{c^{T}x+d}dom(f)=\{x\mathrm{\mid }{c}^{T}x+d>0\}f(x)=\backslash frac\{Ax+b\}\{c^Tx+d\}\backslash \; \backslash \; dom(f)=\backslash \{x|c^Tx+d>0\backslash \}$
• 凸集的透视函数和线性分数函数的像或原像都是凸的；
• 适当锥(广义不等性)
  • 非负多项式
  • 每个元素非负的向量集合${\mathbf{R}}_{+}^n\backslash mathbf\{R\}^n\_+$
  • 最小值和极小值

4. 分离超平面定理：两个非空的不相交凸集，存在超平面可以分开两个凸集；注意更严格划分的要求

5. 支撑超平面定理：凸集的每个边界点都存在一个支撑超平面，考虑平滑凸和分段线性凸的场景；

   • 边界点$x_{0}x\_0$，有$x\mathrm{\mid }{a}^T=a^T{x}_0\{x|a^T=a^Tx\_0\}$且对凸集内的所有$xx$有$a^{T}x\le a^T{x}_0,a\mathrm{\ne }0a^Tx\backslash leq\; a^Tx\_0,\; a\backslash neq\; 0$

6. 对偶锥与广义不等性