凸优化|学习笔记(2)：凸集基础

前言

实际工作中大量的决策问题，如计算广告中的部分机制策略问题、物流行业的路径规划问题甚至机器学习中的优化问题，都可以表示为数学优化问题，或者数学优化问题的变化形式如多目标优化问题。因此，接下来一段时间将会持续更新数学优化中的凸优化问题和整数规划问题相关知识总结

本篇是《凸优化读书笔记》系列的第二篇，主要讲述凸集相关的基本概念以及几种常见的凸集类型

一、相关概念

1.1 仿射集合

1.1.1 仿射集合的概念

零空间：在数学中，一个算子的零空间是方程所有解的集合，也叫做的核空间

仿射集合：如果是一个仿射集合，那它满足：如果且，那么仍然在集合中

子空间：如果是一个仿射集合且，那么集合是一个子空间

仿射包：集合中的点的所有仿射组合组成的集合称作的仿射包，记为aff C。仿射包是包含的最小仿射集合

1.1.2 线性方程组的解集

线性方程组的解集是一个仿射集合，这个结论很容易证明。设，即。对于任意有：

这说明任意的仿射组合也在集合中，且与仿射集合相关联的子空间就是的零空间

反之任意仿射组合都可以表示为一个线性方程组的解集

1.1.3 仿射维度和相对内部

仿射维数：集合的仿射维数是其仿射包的维数。举个例子说明，上的单位圆环，它的仿射包是全空间，所以其仿射维数是2

闭包：当一个集合 S    在某个运算下不闭合的时候，我们通常可以找到包含 S 的最小的闭合集合。这个最小闭合集合被称为 S 的（关于这个运算的）闭包

相对内部：集合的相对内部定义如下：

其中，即半径为r，中心为x并有范数定义的球  

相对边界：集合的相对边界为，其中是集合C的闭包

1.1.4 三维空间中的相对边界

考虑中处于平面的一个正方形，即：

其仿射包为所在平面，相对内部为：

的边界是其自身，相对边界是其边框：

1.2 凸集的概念

凸集：如果中任意两点间的线段仍然在中，即对于任意和有：

那么就是凸集

凸组合：点为点的一个凸组合，其中。一个集合是凸集等价于集合包含其中所有点的凸组合

凸包：集合中所有凸组合的集合为其凸包：

凸包总是凸的，它是包含的最小凸集

1.3 锥的概念

锥：如果对于任意和都有，则集合是锥或非负齐次

凸锥：如果几个是锥，并且是凸的，则它是凸锥

锥组合：具有形式的点称为的锥组合。集合是凸锥的重要条件是它包含其元素的所有锥组合

锥包：集合的锥包是中元素所有锥组合的集合，它是包含的最小凸锥

二、几种常见的凸集类型

2.1 超平面与半空间

超平面是具有下面形式的集合：

因此，超平面可看作是关于的线性方程的解空间，也是一个仿射集合

一个超平面把划分为两个半空间。半空间可看作线性不等式的解空间：

半空间是凸的，但不是仿射的

2.2 Euclid球和椭球

Euclid球的公式表达如下：

它表示由距离球心距离不超过的所有点。Euclid球很容易证明是凸集，设有，那么：

与Euclid球相关的是椭球，形式如下：

其中是对称正定矩阵，它决定了椭球从向各个方向扩展的幅度

2.3 范数球和范数锥

范数球的形式如下：

范数球是凸的

范数锥是集合：

范数锥是凸锥

2.4 多面体

多面体是指有限个线性等式和不等式的解集：

多面体是有限个半空间和超平面的交集，是凸集，仿射集合、射线、线段和半空间都是多面体

单纯形是一类重要的多面体。设个点仿射独立，也就是线性独立，这些点决定了一个单纯形：

这个单纯形的仿射维数是k，也叫做空间的k维单纯形。一维单纯形是一条线段，二维单纯形是一个三角形，三维单纯形是一个四面体

2.5 半正定锥

首先用表示堆成矩阵的集合：

用表示对称半正定矩阵的集合：

集合是一个凸锥：如果并且，那么