凸优化的笔记：序
想学凸优化的伏笔应该是在大三的时候埋下的。那个时候啃着李航老师的《统计学习方法》，按书本里的先学了kNN和Decision Tree，感觉统计学习还怪有意思的，后来学到Naive Bayes时候开始有点智商捉急了，再后来的贝叶斯网络和SVM就已经开始对我幼小的心灵造成损害，看到拉格朗日对偶的推导那部分开始自闭，上网去搜，发现这是凸优化里面的理论——这是我第一次对这门学科产生印象。
到研究生阶段想划水的，奈何身边的人都太强了，有种不努力就会被社会抛弃的紧张感，所以想重新捡起《统计学习方法》看，争取把推导看懂吧……然后回忆起早年自闭的过程，想了想，算了，先去看看凸优化吧。
学习的参考教材是Stamford大学又帅又有魅力的Boyd教授的《Convex Optimation》（考虑到努力不给自己艰难的学习过程再下绊子，选择的是王书宁版的中译本），结合Boyd教授录制的授课视频与slides一起学习。笔记的篇章估计也会按书本的目录顺序来，除非我看到自闭打算删掉这些笔记装作一切都没发生过，否则我会努力把所有书本的重点都呈现到笔记中去。
另外，值得一提的是，现在深度学习打得火热，我也有看到有关统计学家与炼金术士之间因为神经网络非凸，效果又异常的好而相互看不起的说法出现，感觉还怪有意思的。可能有一天我会发现凸优化并没有我想象中那么好用，不过在学习过程中带来的痛并快乐的感觉确是实实在在的。不管怎么说，现在的我选择要开始这段旅程了。
是为序。
凸集
书本的第一章是绪论，没有讲太多实质性内容，合并到这里进行叙述：主要介绍了数学优化问题的通用形式，随后讲了最小二乘和线性规划的内容，并说明了它们是凸问题中比较典型的问题，而且最小二乘与线性规划问题是很容易识别的，然而凸问题很多时候非常难识别（就是说，有时候你觉得它和凸问题一点关系没有，但是稍微做个简单变换，忽然就发现变成凸问题了。书里面没有给出直接例子，但是我记得看视频的时候Boyd教授是讲过一个例子的）。最后简单总结：课程的主要目的就是为了教大家如何辨识一个凸问题并求解它——当然为了达到这个目的，首先会讲相当一部分枯燥的概念。
下面正式开始第二章：凸集的内容。也就是Boyd教授所说的枯燥的概念的部分。
除了基本的概念以外，我会努力阐述我的理解，不照着书本上面直接抄的（后者是我读不懂的时候会采取的让自己觉得自己学会了的方法）——但是为了不产生误导，所有我自己的理解我都会用斜体表示。
仿射集合和凸集
直线
设$x_1\neq x_2$是$R^n$空间中的两个点，那么具有下列形式的点会构成一条穿过$x_1, x_2$两点的直线
仿射集合
如果集合中任意两个点所构成的直线中的所有点都在这个集合中，就认为这个集合是仿射的。用数学语言表达就是，一个集合$C$是仿射的当且仅当：对于$\forall x_1, x_2\in C$以及$\theta\in R$，有$\theta x_1+(1-\theta)x_2\in C$。
（所以仿射集合中至少有两个点？）
另外书中提到，可以把结论推广到任意元素的情况，即对多个$x$进行加权，约束它们的系数和为1，获得的结果也在集合$C$中，那么这个集合就是仿射集合。
凸集
凸集就是把$\theta$的值约束了一下：仿射集合中$\theta\in R$，把$\theta$限制到$[0,1]$之间，以保证每个$x$前面的系数都$\in[0,1]$，就是凸集的定义了。换句话说，如果仿射集合中的两点确定的直线中的所有点都在集合中，那么凸集中的两点确定的线段中的所有点都在集合中。我就不抄数学公式了。
把$\theta_1 x_1+\theta_2 x_2+…+\theta_k x_k$称为是点$x_1, …, x_k$的一个凸组合，其中要求$\theta_1+\theta_2+…+\theta_k=1$，可以把凸组合看成是$x$的一个加权平均。凸组合的概念可以引出下面凸包的概念。
凸包
集合$C$中所有的点的凸组合称为凸包。换句话说，凸包是包含$C$的最小凸集。回想一下算法课上学的求凸包的方法（虽然已经忘记是什么方法了），可以想象出，凸包就是把一个集合最外面的点围起来构成的一个多边形。
凸锥
锥的定义是和仿射集、凸集有异曲同工之妙的：锥要求所有$x$的系数非负。而凸锥要求：对于$\forall x_1, x_2\in C, \theta_1 x_1+\theta_2 x_2\in C$。
另外，参照凸集、凸组合和凸包之间的关系，也有锥、锥组合与锥包的相对定义，在此不再赘述。
综合上面的叙述，大概总结这些概念就是：
- 不管是仿射集合与凸集，都有定义：对于$x_1, x_2\in C$，$y=\theta x_1+(1-\theta)x_2\in C$，这个式子隐性要求了$x_1, x_2$前面的系数$\theta_i$之和为1。仿射集与凸集定义的不同点在于$\theta$的取值范围
- 仿射集合定义里面的$\theta\in R$，这样对应的$y$取值是一条直线。
- 凸集里面的$\theta\in[0,1]$，对应的$y$取值是一条线段。
- 锥的定义中不要求系数和为1，而是约束的所有的系数$\theta_i\geq 0, i\in N$
- 仿射集、凸集与锥的定义中只涉及了$x_1$与$x_2$。但是一般的，对于大于两个变量$x$的形如$\theta_1 x_1+…+\theta_k x_k$这样的组合，可以形成对应的仿射组合/凸组合/锥组合；而使用了所有的$x$的组合（即当$k=n$时）被称为包（仿射包/凸包/锥包）
重要的凸集们
这里面主要讲了：超平面和半空间，Euclid球和椭球，范数球和范数锥，多面体，以及半正定锥这些例子，因为这些凸集会在书本后面内容中反复多次出现。
所以又是一堆概念：
超平面和半空间
这两个概念放在一起讲是因为它俩之间只有一个符号的区别。
超平面是所有满足条件的$x$的集合：$\{x\mid a^Tx=b \}$，其中$a\in R^n$，是一个向量（注意$a$表示一个向量，而$A$才表示一个矩阵）。所以解集$x$可以看成所有与向量$a^T$的点乘是常数$b$的向量，想象一个空间中存在一个向量$a$，它的转置与它呈$90^\circ$，而向量$x$与它的点积是一个常数，也就是说$x$与$a^T$在一个平面上。$b$约束了这个平面关于该平面零点$O$的距离。
与之相对，半空间也就是把超平面中的$=$符号改成了$\leq$或者$\geq$，这样$x$表征的就不是一个平面了，而是在由这个平面分割的上/下一半的空间。如果不等式中没有等号，则称为开半空间。
Euclid球与椭球
Euclid球在$R^n$空间中，形式定义如下：
$||.||_2$表征的是Euclid范数，也就是空间中所定义的’距离’。上式的含义就是与给定的圆心$x_c$的距离在给定常数$r$以内的所有$x$向量的集合，也就是大家所理解的球。（可以考虑证明：Euclid球是个凸集-使用凸集的性质以及范数上满足的三角不等式性质）
椭球
$\varepsilon=\{x\mid (x-x_c)^TP^{-1}(x-x_c)\leq 1\}$，其中$P=P^T\succ 0$，即矩阵$P$是对称正定的，$\succ$表示左边的每个元素都大于右边对应的元素。$P$决定了椭球从$x_c$向各个方向扩展的幅度，我感觉我矩阵论没学好，愣是看不懂$P$是怎么决定扩展幅度的，但是我努力的把这个定义背下来了，不求甚解不求甚解……
范数球与范数锥
顾名思义，就是由范数定义的球和锥。其实Euclid球就是由Euclid范数定义的球，所以是范数球的一种。范数锥是集合$C=\{(x,t)\mid ||x||\leq t\}\subseteq R^{n+1}$
多面体
多面体就是由一些超平面和一些半空间的交集，也就是它们围起来的一块，想象三个$a$向外的半空间，其交点所构成的三角形内部就是一个多面体。形式化的定义为：$\mathcal{P}=\{x\mid Ax\preceq b, Cx=d\}$
使用$S^n$表示对称的$n\times n$矩阵的集合，$S^n_+$表示对称的半正定矩阵，那么更进一步，$S^n_{++}$表示对称的正定矩阵。半正定锥会用到这些概念。
半正定锥
所谓的用到上面的概念，不如说，集合$S^n_+$就是一个凸锥，也就是半正定锥。可以看到这个概念本身就符合凸锥的定义，所以不多赘述。书中给出一个$S^2$空间中 的半正定锥的定义，我并不能看懂它为什么是这样。
值得一提的是，正定锥和半正定锥的区别在于，半正定锥能在不等式中取到等号。
上面的所有概念都是凸集，如果闲着没事，可以尝试用凸集的定义来证明它们。用翟起滨老师的话说，这样就能对这些凸集的例子手拿把下XD。
保持凸性的运算
总的来说，保持凸性的运算有以下四个：
- 交运算：两个集合是凸的，那么它们的交集也是凸的。这个性质可以扩展到无穷集合的交集上。作为一个例子：多面体实际上是多个超平面与半空间的交集所以它也是凸的——这是一种不从定义本身来证明一个集合是凸的的方法。
- 仿射函数：对于函数$f(x)=Ax+b$，其中$A\in R^{m\times n}, b\in R^m$，如果一个集合是凸的，那么对集合中每个元素$x$做仿射变换$f(x)$，最终获得的另一个集合也是凸的。也就是说，线性变换不改变集合的凸性。
两个比较典型的例子是伸缩和平移：分别是$b=0$与$A=1$时的特殊情况，可以想象对一个凸集进行伸缩和平移并不影响它的凸性。
- 透视函数：简单解释就是，首先把一个向量的每个元素都除以最后一个元素的值（当然这样操作之后最后一维元素值变为1），之后最后一维舍弃掉，得到一个新的向量，这个向量是保持原向量的凸性的。因为这个变换很像对向量进行透视，所以叫做透视函数。
- 线性分式函数：线性分式函数其实是由仿射函数与透视函数复合而成的，可以看成是对凸集的一种投射。形式化表述为：$f(x)=(Ax+b)/(c^Tx+d), \mathrm{dom}f=(x\mid c^Tx+d>0)$。
当$c=0,d>0$时，可以看出$f$就是一个仿射函数，所以仿射函数是特殊的线性分式函数。
广义不等式
正常锥
要理解广义不等式的含义，首先要对正常锥进行定义。称一个锥$K$是正常锥(proper cone)，如果它满足以下条件：
- $K$是凸(convex)的，也就是$K$是个凸锥
- $K$是闭(close)的，也就是说两端的边界要能取到
- $K$是实(solid)的，就是说内部必须非空。这里要提一下，大家可能会想，锥不都是非空的吗，哪有空的锥？——Boyd教授给出了一个反例：一条射线满足凸锥的定义，但是它根本不存在内部，更没有非空一说。
- $K$是尖(pointed)的，就是说$K$不包含直线，或者说$K$中要存在点$x=0$
广义不等式的定义
广义不等式通过上面正常锥的定义得到：
当然，如果左侧的不等式中没有等号，可以说这个广义不等式是严格的，否则就是不严格的。
怎么理解这个广义不等式呢，就是说如果两个向量$x,y$相减得到的结果$y-x\in K$，就认为$x$在正常锥$K$定义的广义不等式中$\preceq_K y$。我的理解是，由于正常锥$K$本身的定义，保证了在里面的每个向量都是相对于其中的零点（定义中是尖的那个点）$x=0$要大的，所以如果$y-x\in K$，说明了$y$与$x$相减得到的差要大于这个正常锥所定义的集合中的零点，所以也就是在$K$条件下$>0$。因此，如果$y-x\in K$成立，说明$y$在条件$K$下比$x$要大，这就是广义条件下的不等式了。
特别地，如果$K=R_+$时，广义不等式中的不等号$\preceq$就是我们常说的不等号$\leq$。按我上面所说的理解，这是因为$y-x$大于了$R_+$中的零点——也就是0，所以有了$x\leq y$（我的逻辑居然自洽了，真开心）。
广义不等式的性质
广义不等式具有的性质如下，我感觉都比较好理解，因为有我们数学空间$R_+$中的不等号来类比它：
- $\preceq_K$关于加法保序：即对$x\preceq_Ky$以及$u\preceq_Kv$，有$x+u\preceq_Ky+v$，想象$1<2, 3<4$所以有$1+2<3+4$一样。
- $\preceq_K$具有传递性，这个不多解释了
- $\preceq_K$对于非负数乘是保序的：对于$x\preceq_Ky$与$\alpha\geq0$，有$\alpha x\preceq_K\alpha y$
- $\preceq_K$是自反的，就是如果$x\preceq_Ky$并且$y\preceq_Kx$，那么$x=y$
- $\preceq_K$对于极限运算也是保序的，这点稍微难理解一点，但是我感觉没啥用，就不生搬定义了。
最小元与极小元
我们常说的空间$R_+$（其实就是第一象限）中存在着最小元$x=0$，而我们定义的正常锥的空间中也存在这样的最小元的定义，对于整个空间$K$来说，其实就是尖点$x=0$。但是因为正常锥$K$空间中的某一个集合$S$并不一定包含这个尖点，所以对于集合$S$，我们可以这样定义$S$中的最小元$x$（如果存在）：
这里其实满足了两个条件：首先$x$对所有$S$中的元素必须是可比的——不像我们的数字一定是可比的，空间中的点并不一定可比。这点很好理解，比如二维空间中的两个点$(0,1)$与$(1,0)$，它们在空间$R^2_+$上并不可比。我想起了我的导师在数据仓库里面提到的数据的skyline，感觉差不多就是这个意思。
因为$S$中的数据并不一定都可比，所以不一定有最小元的存在，但是一定有极小元的存在。一个集合$S$的极小元$x$的定义为：如果$y\in S, y\preceq_Kx$可以推得$y=x$，那么称$x$是$S$关于广义不等式$\prec_K$的极小元。换句话说，如果一个$x$比所有$S$中它可比的$y$都要小，那么它就是个极小元。所以我们可以考虑这样一种特殊情况：集合$S$中有一个元素$x$与其它任何元素都不可比（其实我并不确定$K$的定义是否允许有这样的情况存在），那么$x$一定是一个极小元（其实极小元更符合skyline的定义）。
分离与支撑超平面
好的，经过了艰难的跋涉之后，我们来到了分离与支撑超平面(sperate and support hyperplane)的定义。我不明白这个概念放在这里有什么上下文的意义，窃以为Boyd教授可能是把所有零散的概念都放到这一章了。
超平面分离定理是这样的一个定理：
假设集合$C, D$是两个不相交的凸集，即$C\cap D=\emptyset$，那么存在$a\neq 0$和$b$使得$a^Tx\leq b, x\in C$，并且$a^Tx\geq b, x\in D$。
当然按照定义，两个等号不能同时取到，不然两个集合就相交了XD。
其实上面凸集和不相交两个约束都比较重要，如果两个集合相交那肯定不能分离它们，而如果两个集合不是凸集，想象一个被分离的太极图，如果分离得不是那么远，其实是找不到一个平面把它们分割开来的。
与之相对的，支撑超平面是指：
对于凸集$C$上的一点$x_0$，如果有一个超平面$\{x\mid a^Tx=a^Tx_0\}, a\neq 0$（显然这个超平面和凸集交于点$x_0$），对于$\forall x\in C$，有$a^Tx\leq a^Tx_0$，那么就称这个超平面在点$x_0$支撑$C$。
换句话说，就是一个超平面和一个凸集仅有一个交点，另外超平面的参数$a$需要是朝着凸集$C$的反向的，准确来说是：$a^T$所在的直线就是点$x_0$在凸集上的切线，这种情况下$a$有两种方向，一种指向凸集内部，一种指向外部，根据定义需要指向凸集的外部，以保证所有的$x\in C, a^Tx\leq a^Tx_0$。
对偶锥与广义不等式
对偶锥
来到了第二章最后的部分。从上面我们知道了，广义不等式是建立在一个正常锥$K$的定义上的，而这部分Boyd教授讲述了正常锥的对偶锥，既然正常锥$K$可以推出一个广义不等式，那么它的对偶锥$K^*$想必也能推出一个广义不等式。这两个广义不等式之间应该存在着一定的关系，这个关系就是下面要讨论的。
对偶锥的形式定义是：$K^*=\{y\mid x^Ty\geq0, \forall x\in K\}$。要注意，锥一定有对偶锥，而正常锥的对偶锥也是正常锥。
怎么来理解这个对偶锥呢，可以这么来考虑：对于一个锥$K$，我们考虑它的一个元素$x\in K$，这个$x$与锥的尖点（即零点）共同确定了一条直线。现在根据定义，我们先考虑它的转置$x^T$，这个转置也确定了一个方向，和前者所指定的方向关于整个$K$定义的空间是垂直的，这一点是显然的。那么，现在我们要找一个$y$，令$x^Ty\geq 0$，就意味着$y$的方向与$x^T$的方向的夹角不会超过$180^\circ$。这就是$y$的含义了。那么前面整个说的是关于锥$K$中的一个点$x$成立，现在要求这个条件要关于整个锥$K$中的所有点都成立，就把这个$y$限制在了一个特定的范围内，这个范围也是一个锥，这个锥就是$K$的对偶锥。
不知道失不失一般性的，我们可以这样来找一个锥$K$的对偶锥：$K$的边界是两条射线，那么分别经过$K$的尖点做这两条射线的垂直的射线，射线所指的方向是与$K$中元素夹角不超过$180^\circ$的方向。这两条垂线及其$<180^\circ$的夹角及其内部构成了$K$的对偶锥。
通过以上描述我们也可以知道，锥$K$与其对偶锥的两个夹角是互补的，其相加为$180^\circ$，特别地，一个$90^\circ$的正常锥$K$的对偶锥就是它自身，这种情况称为自对偶。容易知道，$R^n_+$是自对偶的。
上面扯了一大堆对对偶锥自己的理解，下面是书中所提出的对偶锥所拥有的性质：（另外，由于Mathjax与Markdown渲染机制中对*这个符号存在冲突，所以原来书中对对偶锥的记号$K^*$，在下面统一改成$K^-$）
- $K^-$是闭凸锥
- $K_1\subseteq K_2$可以推出$K^-_2\subseteq K^-_1$，因为对偶锥互补嘛，你包了我，那我的对偶肯定包了你，大家和和气气
- 如果$K$有非空内部，那么$K^-$是尖的
- 如果$K$的闭包是尖的，那么$K^-$具有非空内部。反正这两条意思就是尖和非空应该是能互推的。
- $K^{—}$是$K$的凸包的闭包
广义不等式的对偶
既然正常锥确定了一个广义不等式，那么正常锥的对偶锥也确定了一个广义不等式，把后者称为前者的对偶，即：$\preceq_{K^-}$是广义不等式$\preceq_K$的对偶。值得注意的是，在正常锥中，有$K^{—}=K$。
对应的，$K$上的最小元也有对应的对偶性质。$x$是$S$上关于广义不等式$\preceq_K$的最小元的充要条件是（注意$S$不一定需要是凸集）：对于所有的$\lambda\succ_{K^-}0$，$x$是在$z\in S$上极小化$\lambda^Tz$的唯一最优解。又是一个难以理解的定义，不过Boyd教授阐述了几何上的解释：这意味着对于$\forall \lambda\succ_{K^-}0$，超平面$\{z\mid \lambda^T(z-x)=0\}$是在$x$处对$S$的一个支撑超平面。我仔细考虑了一下，实在是表达不出来那种似懂非懂的感觉。
接下来是极小元的对偶性质，和最小元对偶是类似的，只是$x$从极小化$\lambda^Tz$的唯一最优解变成了只要求极小化就行，也就是不需要唯一（或者不需要最优？我感觉是不需要唯一比较靠谱，当然我一点都不靠谱）
Pareto最优制造前沿
在章节的末尾，Boyd教授给出了一个例子，正巧我的数据仓库学习的skyline与这个例子含义十分接近，让我来根据我的数据仓库所学来篡改这个例子，以说明最小元与极小元的区别：
我们对外滩上的酒店进行打分，简单来说：如果一个酒店价格更低，我们认为这个酒店更好；如果这个酒店距离外滩更近，我们也认为这个酒店更好。每个酒店都是一个二维的元组$(price, dist)$，以price为$x$轴，dist为$y$轴，我们能把酒店标在一个二维平面坐标系中。
那么，最小元就是这样的一个酒店：所有酒店中没有酒店离外滩的距离比它更近，没有酒店的价格比它更低；而极小元就是满足这些条件的酒店：这些酒店至少在价格或者距离任意一维上不会比任何其它酒店要差。
从这个示例中我们可以轻易的看出，最小元是不一定存在的，但是极小元一定存在。