【课程笔记】中科大凸优化(二)
仿射集
- 定义
文章图片
- 等价定义:线性方程组的解集\(C=\{x \mid A x=b\}\)是仿射集,对应的子空间是\(A\)的化零空间
- 理解
- 仿射集内任意两点的所在的直线也在仿射集内
- 仿射集内多个点的仿射组合\(\theta_{1} x_{1}+\cdots+\theta_{k} x_{k},\theta_{1}+\cdots+\theta_{k}=1\)也在放射集内
证明思路:先将两个点用放射组合构成一个新的点,该点在仿射集内;依次组合下去,则最新的点同时满足1)是原有若干点的仿射组合;2)在仿射集内
- “仿射”的含义就是任意两点连接成直线的并集
- 仿射集内任意两点的所在的直线也在仿射集内
- 特殊的仿射集:仿射集\(C\)的子空间 \(V=C-x_{0}=\left\{x-x_{0} \mid x \in C\right\},\alpha v_{1}+\beta v_{2} \in V\)
- 证明\(V\)也是仿射集且任意\(\alpha,\beta\)有\(\alpha v_{1}+\beta v_{2} \in V\):\(\alpha v_{1}+\beta v_{2}+x_{0}=\alpha\left(v_{1}+x_{0}\right)+\beta\left(v_{2}+x_{0}\right)+(1-\alpha-\beta) x_{0} \in C\)
- 子空间有更好的性质,只要是线性组合都在该空间内
- 空间一定包含原点\((0,0)\)(原仿射集中的\(x_0\))
- 注意\(x_0\)也要在仿射集内
- 给定任意集合\(C \subseteq \mathbf{R}^{n}\),构造尽可能小的仿射集:仿射包(the set of all affine combinations of points)
\[\operatorname{aff} C=\left\{\theta_{1} x_{1}+\cdots+\theta_{k} x_{k} \mid x_{1}, \ldots, x_{k} \in C, \theta_{1}+\cdots+\theta_{k}=1\right\} \]
- 定义:
文章图片
一个集合是凸集,当任意两点之间的线段仍在集合内
- 理解
- 相较于仿射集增加了\(0 \leq \theta \leq 1\)的条件,因此表述范围更小(是子集),凸集\(\sub\)仿射集
- 凸包:(the set of all convex combinations of points)
\[\operatorname{conv} C=\left\{\theta_{1} x_{1}+\cdots+\theta_{k} x_{k} \mid x_{i} \in C, \theta_{i} \geq 0, i=1, \ldots, k, \theta_{1}+\cdots+\theta_{k}=1\right\} \]
- 定义:
文章图片
- 理解:
- 锥的定义没有元素的组合,只有\(\theta x \in C\)
- 锥可以看成头集中在原点的若干火柴的拼接(无穷多组原点起点的射线组成)
- 凸锥=锥+凸集
凸锥的定义是任意的\(\theta_1,\theta_2\),因此包含了\(\theta_1+\theta_2=1\)的情况,描述范围更窄,凸锥一定是凸集
(条件里面加任意,其实是条件更严苛,对应的往往范围更小)
- 锥的定义没有元素的组合,只有\(\theta x \in C\)
- 凸锥包:包含集合所有点以及原点的最小冰淇淋
基本框架都是满足:对于任意\(x_1,x_2\in C\),则\(\theta_1 x_1+\theta_2 x_2 \in C\)(线性组合仍属于集合)
区别是系数的条件(越来越苛刻)
- 仿射集:\(\theta_1+\theta_2+\cdots+\theta_k=1\),系数和为1(构成直线)
- 凸集:\(\theta_1+\theta_2+\cdots+\theta_k=1\),\(\theta_1,\theta_2,\cdots,\theta_k\in[0,1]\),系数和为1,每个系数在0到1之间(构成线段)
- 凸锥:\(\theta_1,\theta_2,\cdots,\theta_k\in[0,+\infty)\),非负系数(构成射线)
- 单点集:仿射集、凸集、仅当原点时是凸锥
- 空集:仿射集、凸集、凸锥
推荐阅读
- 应用工具|【长期更新】盘一盘那些 uTools 高质量插件,让你的工作效率瞬间提升N倍!
- 【Docker Desktop】在 Windows上安装 Docker Desktop
- C语言实现简单的五子棋游戏
- 《C++要笑着学》|【C++要笑着学】认识C++ | C++的发展史 | 学习方法建议
- 《C++要笑着学》|【C++要笑着学】缺省参数 | 函数重载
- 《C++要笑着学》|【C++要笑着学】内联函数 | 关键字auto | 范围for | 关键字 nullptr
- 指针|【发际线大作战】C++学习记录之用户自定义数据类型
- 小问C++笔记|C++之Big Three(拷贝构造、拷贝赋值、析构函数探究)
- 【发际线大作战】C++学习记录之数组(发际线-1cm)
- 【矩阵基础与维度分析】【公式细节推导】矩阵非线性最小二乘法泰勒展开