【知识总结】 凸集

仿射集合和凸集

直线与线段

• • • 空间中两个点
  • • 穿越的直线
  • • 之间的闭线段
  • • 另一种理解形式

仿射集合

• 仿射集合基本定义
  • 对任意
• 仿射集合拓展定义
  • 仿射组合在集合中
• 子空间
  • 定义
    • ，其中是仿射集合且为中某已知点
  • 性质
    • 关于加法和数乘封闭，即
    • 与仿射集合关联的子空间与的选取无关
  • 理解
    • 这个子空间就是指线性子空间
    • 仿射空间（不一定有原点）可以看成线性子空间（一定有原点）的平移
    • 在仿射空间上任选一点，将仿射空间进行平移，使得到原点，此时仿射空间就平移成了线性空间
• 仿射集合的维数
  • 定义为对应子空间的维数
• 集合的仿射包
  • 定义
  • 性质
    • 仿射包是包含的最小的仿射集合

仿射维数与相对内部

• 集合仿射维度
  • 仿射包的维数
• 集合的相对内部
• 集合的相对边界
  • • 是的闭包

凸集

• 凸集基本定义
  • 集合中任意两点间线段仍在集合中
  • 对任意
• 凸集拓展定义
  • 凸组合在集合中
• 集合的仿射包
  • 定义
  • 性质
    • 凸包是包含的最小的凸集

锥

• 锥的定义（非负齐次）
• 凸锥基本定义
• 凸锥拓展定义
  • 锥组合（非负线性组合）在集合中
• 集合的锥包
  • 定义
  • 性质
    • 锥包是包含的最小的凸锥

凸集例子

• 超平面
  • 超平面将划分成两个半空间
• 半空间
  • • 边界是
    • 内部是
  • 半空间是凸的，但不是仿射的
• Euclid球和椭球
  • 球
    • 另一个形式
    • 是凸集
  • 椭球
    • （是正定对称矩阵）
    • 半轴长度是的特征值
• 范数锥
• 多面体
  • 有限个等式和不等式的解集，有限个半空间和超平面的交集
  • • 可以使用紧凑表达式
• 半正定锥
  • • 对称矩阵的集合
  • • 对称半正定矩阵的集合
    • 是凸锥
  • • 对称正定矩阵的集合

保凸运算

• 交集
  • 两个凸集的交集是凸集
• 仿射函数
  • 函数是仿射的它是一个线性函数和一个常数的和
    • 即形式为
  • 仿射函数的逆函数也是保凸的

凸集的证明

• 证明该集合可以从简单凸集例子，通过保凸运算得来

线性分式和透视函数

透视函数

• • 透视函数对向量伸缩规范化，使得最后一维分量是，并舍弃
  • 原理类似为小孔成像
• 透视函数是保凸的
  • 可以理解成：用小孔观察凸的物体，象也是凸的

线性分式函数

• 由透视函数和仿射函数复合而成

广义不等式

• 称锥为正常锥，若满足下面条件
  • 是凸的
  • 是闭的
  • 是实的，具有非空内部
  • 是尖的，不包含直线
    • 如果
• 基于正常锥定义的广义不等式
  • • 不严格的广义不等式
  • • 严格的偏序关系
    • 严格的广义不等式
• 广义不等式的性质
  • 加法保序
  • 传递性
  • 非负数乘保序
  • 自反性
  • 反对称性
  • 极限运算保序
• 广义不等式的性质
• 最小元和极小元
  • 最小元
    • ，则是关于广义不等式的最小元
    • 类似的可以定义最大元
  • 极小元
    • ，则是关于广义不等式的极小元
    • 类似的可以定义极大元

分离与支撑超平面

• 超平面分离定理
  • 是两个不相交的凸集，则存在使得
    • 超平面称为分离超平面
  • 如果上面的等号去掉，那么就是严格分离
• 支撑超平面
  • 边界
  • 边界点
  • 支撑超平面
    • ，则在的支撑超平面为
  • 支撑超平面定理
    • 任意非空凸集的任意边界点上存在该凸集的支撑超平面

对偶锥与广义不等式

• 对偶锥
  • 设是一个锥，则是的对偶锥
• 对偶锥的性质
  • 是闭凸锥
  • 若有非空内部，那么是尖的
  • 若的闭包是尖的，那么有非空内部
  • 是的凸包的闭包
    • 若本身就是凸的、闭的，那么
  • 若是正常锥，则也是正常锥
    • 此时
• 广义不等式的对偶
  • 正常锥导出广义不等式
  • 对偶锥导出广义不等式
  • 两个广义不等式互为对偶
• 广义不等式及其对偶的性质
  • ，有
  • ，有
• 对偶不等式求解最小元和极小元
  • 最小元
    • 是上关于的最小元是上极小化的唯一最优解
  • 极小元
    • 是极小元是上极小化的解
    • 若是凸集，则是极小元且，使得是上极小化的解