【课程笔记】中科大凸优化（三）

2022-03-06

上节课知识补充凸锥的几何解释
不断改变形状的平行四边形

文章图片
仿射集、凸锥、凸组合的关系
因为凸集的条件是其余两个条件的并集，因此

为什么不是条件越多的，表示范围越小？
因为在定义仿射集、凸集的时候，要求的是“任意的\(\theta\)组合满足“。“任意”的限制越少，反而约束的对象越多（举例：任意人>任意男性>任意男孩），也就越严格（对任意人满足，必然对任意男性、男孩满足）。也就是只要对任意\(\theta_1+\cdots+\theta_k=1\)满足，也就对任意\(\theta_1+\cdots+\theta_k=1,\theta_1,\cdots,\theta_k\ge 0\)满足，因此仿射集必为凸集。
总结：条件的范围越小，结论越弱，越容易成为推论

【课程笔记】中科大凸优化（三）

文章图片
几种重要的凸集有集合解释的集合
超平面与半空间

超平面

文章图片
- 超平面不一定是平面，因此不一定是2维，是比\(x\)维度低一维的集合
半空间

文章图片
- 原空间被超平面所划分后的空间

球和椭球

球

文章图片
- 二范数表示向量长度（欧氏距离）
- 【【课程笔记】中科大凸优化（三）】证明球是凸集：
  - 三角不等式：两边之和不小于第三边
    
    \[\|x+y\|_{2}\le\|x\|_{2}+\|y\|_{2} \]
    向量相加时考虑三角不等式
  - 柯西不等式：最大的平行四边形是矩形
    
    \[\left|x^{T} y\right| \leq\|x\|_{2}\|y\|_{2} \]
    向量内积时考虑柯西不等式
椭球

文章图片
- 正定矩阵\(P\)
  - 只有方阵才能定义特征值（\(Ax=\lambda x\)因此横纵维度必须一致），为了推广到一般矩阵，就有了奇异值，也就是将原矩阵先转换成一个方阵\(A^T A\)
  - 由于对称矩阵特征值非负，因此定义奇异值为新矩阵特征值开根号\(\sqrt{\text{eig}(A^T A)}\)
- 当\(P\)为单位阵的时候，退化为球
- 当\(P\)为对角阵的时候，长短半轴刚好在坐标轴上
多面体

文章图片
- 有限个半空间（线性不等式）和半平面（线性等式）的交集
单纯形

文章图片

文章图片
- 单纯形是\(k\)个构成线性无关向量的点的凸包
- 单纯性维度不能超过空间维度（二维中是三角形，三维中是四面体）
- 证明：任一单纯形一定是一个多面体
  思路：构造法，将单纯形内点的表示转化为多面体的表示
  【还没完全看懂，之后更新】

抽象集合

对称矩阵集合：\(\mathbf{S}^{n}=\left\{X \in \mathbf{R}^{n \times n} \mid X=X^{T}\right\}\)
对称半正定矩阵集合：\(\mathbf{S}_{+}^{n}=\left\{X \in \mathbf{S}^{n} \mid X \succeq 0\right\}\)
- 证明：是凸锥
  用正定的定义：任意\(x\in\mathcal{R}^2\)，有\(x^TAX\ge 0\)
对称正定矩阵集合：\(\mathbf{S}_{++}^{n}=\left\{X \in \mathbf{S}^{n} \mid X \succ 0\right\}\)

推荐阅读

上一篇：笔试题|字节跳动2021春招研发第二场笔试编程题（三）

下一篇：小白文-SpringMVC-解读DispatcherServlet源码