最优化方法在图像处理中的应用【2】

今天要讨论的内容是我们要开始学习的基础，我想将这些基本概念好好描述下，以便于将来使用啊。

本次讨论的主题是Convex Sets（凸集）

1 affine and convex sets （仿射集和凸集） 1.1 Affine set

先看看line through x1 x2: all points x = θ•x1+(1-θ)x2 (θ belongs to R)

这里x1和x2都是n维空间中的点，如果用向量表示他们的坐标，他们就是n维向量了。用公式表示出的新的点x就是通过x1和x2这两个点的直线上的点。

what is affine set? affine set is a set of point. Any points on certain given line that through two distinct points in the set belongs to the set. 

例如，整个n维空间便是一个affine set. Also, solution set of linear equations {x| Ax = b}. 为什么呢？

证明一下第二个：

如果方程组没有解，那么解集合是空集，我找不到两个向量啊？一个向量都没有啊，怎么来验证满足条件呢？好吧，我只能说规定空集是仿射集。

如果方程组只有一个解，同样不能在它的解集合中找到两个不同的向量，嘿嘿，既然没有就把唯一一个解看成两个不同的向量吧，所以显然它也就属于仿射集了。

如果方程组有无限个解，那么所有解肯定可以被一组线性无关的基础解线性表出，带一遍定义就可以证明出确实解空间是仿射集！！

这时，牛说“conversely, every affine set can be expressed as solution set of linear equations.”

1.2 Convex Set 

what is line segment?

Line segment between x1 and x2 : all points x = θ•x1+(1-θ)x2 (θ belongs to [0,1])

What is convex set?

convex set: contains line segment between any two points in the set. 

包含边界的圆饼的所有点就是一个凸集。

1.3 Convex combination and convex hull

Convex combination of x1, ..., xk: any point x of the form x = θ1•x1 + θ2•x2 + ... + θk•xk

θ1+θ2+...+θk = 1, θi >=0

在本子上画一个直角二维坐标系，两个向量x1,x2, 如果他的线性组合系数之和为非负，别且系数的和为1，那么用向量的几何方法便可以绘制出θ1•x1 + θ2•x2的结果向量会落在x1和x2组成的线段上，可以用相似三角形的性质说明这一点。

Convex hull conv S: set of convex combination of points in S. 

也就是说S的凸壳或者凸包络就是S中所有点的convex combination. 

1.4 Convex cone （凸锥）

conic （nonnegative）combination of x1 and x2: any points of the form x = θ1•x1 + θ2•x2, θ1>=0 θ2>=0. 

看上面这个图，图中那个想0的符号实际是o，说明他是原点，这个图以二维空间为例子说明了x1和x2的锥组合。 

convex cone (凸锥): set that contains all conic combinations of points in the set. 他是一个集合，集合中的任意两个点的锥组合中的点都含于这个集合，这样的集合就是凸锥，更好的理解一下，就是说满足集合中点对锥组合计算封闭的集合就是凸锥。 

小结一下前面的内容，便于记忆！

首先，过两点的线段上的点可以由两点坐标向量的线性组合表出，但是要求组合系数之和是1！  下面的几个图是三种不同情况。

上图中x1的系数大于1，那么x2的系数必然小于0，向量相加后的结果落在远离X2X1的方向上。

两个系数都大于0小于1的情况，向量相加落在两点之间。

x2的系数大于1的情况，与第一种情况类似，向量之和落在远离x1x2的方向上。

给定集合中任意两点，划一条直线，直线上所有点都属于之前的集合，那么这个集合就是一个仿射集（affine set）

如果把直线限制改为线段限制，就成了凸集（convex set）。从数学公式上理解过两点的线段，它就是上面倒数第二张图的情况。那两个系数大于等于0小于等于1，（等于号是为了限制端点也属于线段本身）。

如果我们把这种线段的方式推广，就是应用与多个n维向量，这个多个n维向量的线性组合系数之和为1，并且每个叙述都大于等于0（其实这两个条件已经限制了每个系数肯定是小于等于1的），这种组合就是一种凸组合(convex combination)，以凸组合的方式把非凸的集合扩展为凸集，那么这个生成的凸集就是原集合的凸包络（convex hull）

那既然直线和线段的线性组合系数大家都了解了，我在推广一步，就是那两个向量的系数我要求只大于等于0就可以了，这样一来，夹在ox1 和 ox2这两条射线（注意这两条射线的端点只有原点o）之间的所有线段都被包含了进来，这个组合就是锥组合（conic combination），一个集合中的点对锥组合运算满足封闭性，那这个集合就是凸锥（convex cone）

 

我们继续！

1.5 Hyperplanes and halfspace

所谓超平面和半空间是也！

hyperplane ：set of the form {x|a'x=b} (a!=0)

其中a、b是给定的两个常数列向量，也就是满足a'x=b的所有x组成的点集就是超平面（hyperplane）。

那这里a向量跟hyperplane有神马关系呢？我们任意取两点x1,x2，他们是超平面上的两个点，得到一个新的向量，新向量坐标可以是（x1-x2），那么，我们用它左乘a'，显然结果是零，所以我们可以认为a就是超平面的法向量。在三维空间中，一个平面可以由法向量和平面上一点决定，那我们就像联想这个b到底是个神吗东西，我们可以通过平面的点法式来看看，假设平面上有一点k（k1,k2,...,kn）,x(x1,x2,..,xn)是平面上任意一点，那么x-k这个向量跟法向量a的点积就是0，根据这个可以最终写出一个新的式子：a'x = a'k ，其实k又何尝不是可以任意取得呢？暂且不考虑k的任意性，假设它是固定的常熟向量，想想吧，我没想出来，这个b到底限制了什么！！！！！！

还有个问题，超平面上的任意两点之间的连线上的点还属于这个超平面么？这两个点的仿射组合（没看见他的定义，我根据凸组合的限制自己定义的）就是两点连线上点的集合，写成数学式子：x=θ•x1+(1-θ)•x2 。那么a'x=θ•(a'x1-a'x2)+a'x2 = 0 + b = b,所以a'x=b，所以两点连线上的所有点都在这个超平面上！！！

 

halfspace ：set of form {x|a'x<=b}

 

我想知道我的点会落在a'x=b这个超平面的哪一边，怎么办呢？？？？呵呵，不是我们可以用点法式来表示超平面么？对呀，我们写出来(x1-k1)a1+...+(xn-kn)an<=0的话，x-k这个向量肯定与a向量是钝角，那么我们固定k在超平面上，那么x点的位置就晓得了！看看下面的图

1.6 Euclidean balls and ellipsoids

就是欧几里得球和椭球。

Euclidean ball with center xc and radius r. :

B(xc,r) = {x| ||x-xc||2 <= r} = {xc+r u | ||u||2<=1}. 2范数就是Euclidean space distance。 其实u可以组成一个单位Euclidean ball。

Elipsoid : set of form {x|(x-xc)'Inv(P)(x-xc)<=1}, 其中P是一个n阶正定矩阵（正定矩阵的性质啊:(，symmetric positive definite）。

Other representation : {xc + Au| ||u||2<=1}, with A nonsingular.

 

1.7 norm balls and norm cones

the definition of norm in mathematic 。

norm ball with center xc and ridius r: {x | ||x-xc||<=r}

norm cone with vertex xv and last dimension t(>=0). {(x,t) | ||(x-xv)||<=t}, 不知道为什么牛把他定义为xv=0。我该怎么用呢？？？？走着瞧吧！！！唉！！

看下面的图就是xv=0的时候。

这个不好看，要是把那些竖线去掉换成，由无穷个从小到大的圆饼组成的东西就容易看出这个锥了！

其中Euclidean norm cone is called as second-order cone. ~~~

norm balls and norm cones are convex!! It is easy to image! So I do not intend to prove it. 

 

1.8 polyhedra

Solution set of finitely many linear inequalities and equalities.

Ax .<= b , Cx .= b, where A is mxn real matrix, C is pxn real matrix ! .<= is componentwise inequality. 

.表示安分量怎样怎样！！！！！

看下下面这个图！

其实polyhydron就是一个hyperplane 和有限个halfspace的intersection.

1.9 Positive semidefinite cone

下面是一些记号啦：

 

下面呢就是一个例子，说明半正定锥：

 

好吧，这样就可以了吧大概，后面会更多呀。