数学优化与凸集4（斯坦福凸优化笔记4）

1 分离与支撑超平面

（图片来自斯坦福Boyd Convex Optimization）
假设C和D是两个不相交的凸集，那么一定存在a≠0的超平面aTx=b将凸集分隔开，使C中点满足aTx≤b,而D中点满足aTx≥b。注意，逆定理能被超平面分离说明不相交是不成立的。
严格分离：如果存在a≠0的超平面aTx=b将凸集分隔开，使C中点满足aTx<b,而D中点满足aTx>b，我们称超平面将凸集严格分离。对于不相交的凸集来说，不一定能被严格分离，但是通常是可以构造出严格分离的。

（图片来自斯坦福Boyd Convex Optimization）
设C⊆Rn而x0是其边界bdC上一点，若a≠0，并且对于任意x∈C满足aTx≤aTx0，那么称超平面{x∣aTx=aTx0}为集合C在x0点处的支撑超平面。（有点像切线的感觉）对于任意非空的凸集边界上任意一点一定存在支撑超平面。

2 对偶锥

令K是一个锥，集合K∗={y∣xTy≥0,∀x∈K}，称为K的对偶锥。K∗是一个锥，而且总是凸的，即使K不是凸锥。

（图片来自斯坦福Boyd Convex Optimization）
我们从几何角度来看看对偶锥。对偶锥的几何意义如下：
对于左图，如果认为y是内法向量，那么y一侧的半平面包含K,所以y在对偶锥K∗里。
对于右图，如果认为z是内法向量，那么z一侧的半平面不包含K,所以z不在在对偶锥K∗里。

所以，我们很容易得到，对偶锥的范围实际就是上图阴影所示的范围。（很像初中几何的，这个锥的两条边和K的两条边相互垂直，所以夹角和K互补）
下面举几个常见对偶锥的例子：
K=Rn+,K∗=Rn+
K=Sn+,K∗=Sn+
这种情况我们称为锥自对偶。
范数锥的对偶：
K={(x,t)∣∥x∥2≤t}
K∗={(x,t)∣∥x∥2≤t}

K={(x,t)∣∥x∥1≤t}
K∗={(x,t)∣∥x∥∞≤t}
关于锥的对偶还有一个重要的性质：
如果K是一个正常锥，那么K∗也是一个正常锥。进一步有K∗∗=K

最小元的对偶性质
我们首先考虑最小元的性质。x是S上关于广义不等式⪯K的最小元的充要条件是，对于所有λ≻K∗0，x是在z∈S上极小化λTz的唯一最优解。在几何上看，这意味着对于任意λ≻K∗0，超平面
{z∣λT(z−x)=0}是在x处对S的一个严格支撑超平面（即这个超平面与S只相交于S）。

（图片来自斯坦福Boyd Convex Optimization）
点x是集合S中关于R2+的最小元。这个等价解释如下：
R2+的对偶锥还是R2+。由上面定义，对于任意λ≻R2+0，超平面{z∣λT(z−x)=0}严格支撑。（超平面目前就是直线，λ是超平面的法线）
设

由平面几何知识，超平面的法向量是(A,B)，因为A>0,B>0所以法线指向第一象限。

因为法线在第一象限，所以超平面所在区域可以理解为在上图弧线的对测的优角所在的区域。

举个例子就是这样。
因此，这个区域内的超平面很明显都是S的支撑超平面。（还都只在x点与S相交）
因此，用几何解释了x是R2+上的最小元。

我们讨论极小元的类似性质。注意，此时充分条件和必要条件不完全一致，我们要分别讨论。

如果λ≻K∗0并且x在z∈S上极小化λTz,那么x是极小的；
从几何上来看与最小元的定理是很相似的，只是这次支撑超平面可能不止一个了，如下图所示：（找最小或者极小λTx（λ>0）只需要做以λ为法向量的直线，从左下方向右上方移动找相切的切点）

（图片来自斯坦福Boyd Convex Optimization）
上图左下边界暗色区域均是极小元，因为都可以类似x1,x2一样找到也个切点。
这个命题的逆命题只有在S在凸的时候才成立（其实逆定理和原定理的逆命题有一点区别，过一会我们讨论这个问题）。如果S不是凸集，那么可能S上的极小元x对于任何λ都不是z∈S上极小化λTz的解。下图展示了这种情况。
（图片来自斯坦福Boyd Convex Optimization）
由于S不是凸的，左侧突出的部分才是极小化λTz的解。然而，x依然是极小元。（因为x的左下侧阴影与S不相交）

（图片来自斯坦福Boyd Convex Optimization）
另外注意的是，即使S是凸的，成立的逆定理是：
假设S是凸集，可以说对于任意的极小元x，存在非零的λ⪰K∗0使得x在z∈S上极小化λTz。
正命题的≻变成了非零⪰。为什么呢？看上图左边这个例子。
点x1∈S1是极小的，但对于任何λ≻0，它都没有在S1上极小化λTz 。（因为极小化λTz成立的向量是λ=[1,0]T，这个向量λ=[1,0]T不满足λ≻0）
正命题我们也不能将≻变成⪰，同样是不成立的。右图是这种情况的反例：
点x2∈S2不是极小的，但对于λ=[0,1]T⪰0，它确实极小化了λTz。
(未完，待续)