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