Convex sets and functions¶
basic concepts¶
convex set¶
所谓凸集，就是要求取集合中任意两点，而连接这两点的线段全部落在集合内部。从二维空间上去想象是一件非常形象的事情。
convex combination¶
凸组合，实际上就是一个线性组合，但是和线性代数中所学的略有不同，要求每个变量的分量的组合系数都非负，并且和为1。
convex hull of set C¶
一个集合C的凸包是依赖于凸组合的定义产生的，对于一个普通的集合，我们希望找到一个能包含它的最小的凸集，这个凸集就是这个集合的一个凸包。如果该集合本身就是一个凸集，那么他的凸包应该就是自身。
cone¶
这个圆锥和我们所学的三维欧式空间中的圆锥有点不一样，相当于是对我们曾经认为的圆锥的一个抽象。可以想象，我们在空间中有一系列点，然后从原点作好多条射线，这些射线要经过这些点，最后所有的这些射线构成的点集就是一个圆锥。所以比如说，我们最初在(1, 1), (-1, 1)处有两个点，那么由他们和原点构成的圆锥就是两条射线（y=x 与 y=-x）。
convex cone¶
如果不仅是一个圆锥，还是一个凸集，那么就是一个凸圆锥。比如上述例子中的两条射线就不是凸圆锥。或者你可以想象，两个三维空间中的圆锥（无限延伸）头碰头（延伸的方向相反），那么构成的集合也是一个圆锥，但是不是凸圆锥
conic combination¶
圆锥组合，和之前的凸组合类似，但是现在只要求各系数非负
conic hull of set C¶
圆锥包，和之前凸包的定义差不多，只不过把凸组合换成了圆锥组合
examples of convex sets¶
学习了基础概念之后，我们需要知道一些具体的例子，这些例子基本都是后面的分析中需要用到的。 以下例子都是凸集，都可以用定义去验证。
empty set, point, line¶
这一类属于是平凡的或者是简单情况，不过多赘述
norm ball¶
范数球，对于任意一个范数（范数的定义请回顾线性代数），指定半径r，满足范数小于r的所有范数。常用的范数就是p-范数，p-范数中1范数、2范数以及无穷范数（用最基础的微积分知识就能证明无穷范数就是向量中最大的分量）会比较常用。
hyperplane¶
超平面，一个线性方程就代表了一个超平面。
halfspace¶
半空间，单纯地将超平面中的线性方程的等于号改为大于等于或者小于等于号。可以理解成超平面分割出来的半个空间。
Q: 不取等号还是凸集吗？
affine space¶
仿射空间（对于仿射的定义请回顾线性代数），比如一条shifted line 或者 一个shifted plane。验证凸性的时候，实际上就是线性变换可以把自变量的系数提到变换的外面。
polyhedron¶
多面体，注意这里用到的小于号是针对向量的分量之间的小于号。实际上就是一个线性方程组，可以理解为由多个超平面（每一个线性方程都是一个超平面）切割出来的一个多面体（在二维空间中就是一个多边形）。还有就是要注意，如果有些方程不是取小于等于号，而是取等于号，同样也是多边形，因为一个等于号的线性方程可以被改写为两个小于等于号的线性方程。
simplex¶
constructing...
convex cones¶
norm cone¶
范数锥，如果我们取二维空间（指x只有两个分量，但是整个范数锥还包括了t分量，所以范数锥是三维的）中的2-范数，那么这个范数锥，就应该是我们通常意义理解下的圆锥，他的顶点是原点，轴线和t轴正方向重合
normal cone¶
法锥，这个定义就变得非常神奇了。我们的集合C是一个任意的集合，他可以杂乱无章，但是神奇的是，由法锥定义得到的不仅是一个圆锥，更是一个凸圆锥。注意，在凸集内部的点的法锥就是零向量。
remark：一个凸集的示性函数的在凸集中的某一点的次梯度就对应这个点对应于这个凸集的法锥
positive semidefinite cone¶
半正定锥，这个锥就和我们直观感受上的圆锥有很大区别了，但是他仍然符合定义。
key properties of convex sets¶
上面介绍了许多不同种类的凸集，接下来我们介绍一种针对所有凸集都成立的性质
separating hyperplane theorem¶
分离超平面定理，对于两个互不相交的凸集，我们一定能找到一个超平面，将他们两个隔开，也就是令两个集合分别落在超平面的两侧。 remark：我们要注意，我们不能时时找到严格分隔两个凸集的超平面，比如\(A = \left\{(x,y): y < 0\right\}\) 和\(B = \left\{(x,y): y \ge 0\right\}\)这两个集合就不能被严格分隔。而且我们注意到这两个凸集有一个是开的，对于两个都是闭的凸集，我们同样不一定找得到严格分隔的超平面，比如\(A = \left\{(x,y): y \le 0\right\}\),\(A = \left\{(x,y): y \ge 1/x\right\}\)
supporting hyperplane theorem¶
支撑超平面定理，对于一个凸集的边界点，我们都能找到经过这个点的一个凸集支撑超平面。
operations preserving convexity¶
intersection¶
凸集之间的交仍然是凸集，任意取两个集合A,B的交的两个点，连接他们的线段全体肯定即落在A中，又落在B中。
scaling and translation¶
缩放和平移也是保凸的
affine images and primages(useful)¶
仿射变换和缩放平移变换不同之处在于，仿射变换是允许旋转的，还允许降维（或者我们来比较线性变换和仿射变换的区别，会发现仿射变换就是线性变换加上平移操作）。关于仿射变换值得一提的事情就是，如果我们将一个集合D，经过某个仿射变换得到了集合C，这个C如果是凸的，那么对应的集合D一定也是凸的，不管这个变换是不是一一映射。换个角度思考，当我们要验证一个集合是凸集，我们可以找任意一个仿射变换，将其映射到一个凸集上去，就能完成证明。
convex functions¶
凸函数只需要满足两条性质，首先他的定义域是凸集，其次凸函数上任意两点连接的线段落在对应的函数值上方
strictly convex¶
严格凸的，也就是不等号无法取等的情况
strongly convex¶
强凸的，函数凸的程度至少和二次函数相当
remark： strongly convex => strictly convex => convex
quadratic functions¶
开口朝上的二次函数或者一次函数是凸的（当然一次函数也是凹的），这里需要提醒的就是要习惯用矩阵的二次型来表示二次函数，矩阵是半正定的就意味着这将是一条开口朝上的抛物线，或者是一条直线
least square loss¶
最小二乘法损失函数是凸的，原因是我们展开之后，就得到了上文的对应矩阵是半正定矩阵的二次函数（展开之后的二次型矩阵是\(A^TA\)的形式，这永远是半正定的）。
norm¶
求范数也是一个凸函数，注意1-范数就是曼哈顿距离，2-范数就是欧几里得距离，无穷范数就是向量x的最大分量（绝对值最大）。范数是有三角不等式的，这直接依赖于范数的定义，所以对于任意范数都成立。
indicator function¶
指示函数，如果指示函数指示的区域是个凸集，那么这个指示函数是凸函数
support function¶
支撑函数，也和指示函数类似，需要规定一个区域C
key properties of convex functions¶
epigraph characterization¶
上镜图，这个性质非常重要，因为他将函数和集合联系来了，甚至说明两者是等价的。
convex sublevel sets¶
一个凸函数的子水平集一定是凸的，但是反之不成立，即一个函数哪怕所有的子水平集都是凸的，也无法保证这个函数是凸的，例如\(f(x) = -e^x\)。
first-order characterization¶
一阶特征，对于可微函数来说，一个函数是凸的当且仅当他在任意点的切线都落在整个函数下方，并且他的定义域是凸的
second-order characterization¶
二阶特征，如果函数f是二阶可微的，这个函数是凸的当且仅当他在任意点的Hessian阵都是半正定的。
remark：一个函数是严格凸的，不意味着他每一点的hessian阵都是正定的，比如\(x^4\)
nonegative linear combination¶
如果一个函数能被写成一系列凸函数的线性组合且组合系数均非负，那么这个函数是凸的。
pointwise maximization¶
我们有一系列函数，每个函数都是凸的，那么对他们逐点取最大值，得到的函数仍然是一个凸函数（注意这个函数的定义域应该是那一系列函数的定义域的交）。
partial minimization¶
这个定理告诉我们对于一个函数g，我们把他的定义域分成两个空间的直和，那么自变量相应地被写成两个分量的组（x,y），对于第一个分量(x)给定，我们限定在某一个凸集C中变化第二个分量(y)，得到的最小值作为一个新的函数f的函数值（那么这个定义的新的函数f应当是关于第一个分量的函数），那么个这个函数f仍然是凸的。
affine composition¶
非常常用的变换。一个函数如果本来就是凸的，那么将他的自变量经过仿射变换之后，得到的新函数，仍然是凸的。
general composition¶
关于函数复合的凸性变化。这可以用对一元函数求二阶导的形式来记住。