【课程笔记】中科大凸优化(二)

仿射集

  • 定义
    【课程笔记】中科大凸优化(二)
    文章图片
    • 等价定义:线性方程组的解集\(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\)
    • 子空间有更好的性质,只要是线性组合都在该空间内
    任何空间都满足\(\forall \alpha, \beta \in V, k_{1}, k_{2} \in P, k_{1} \alpha+k_{2} \beta \in V\),因此一定是一个仿射集
    • 空间一定包含原点\((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\)的情况,描述范围更窄,凸锥一定是凸集
      (条件里面加任意,其实是条件更严苛,对应的往往范围更小)
  • 凸锥包:包含集合所有点以及原点的最小冰淇淋
相互比较以及特殊的集合
基本框架都是满足:对于任意\(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)\),非负系数(构成射线)
【【课程笔记】中科大凸优化(二)】特殊的集合
  • 单点集:仿射集、凸集、仅当原点时是凸锥
  • 空集:仿射集、凸集、凸锥

    推荐阅读