仿射集:对于一个集合,如果集合内的任意两点构成的直线仍在集合C内,则称集合C为仿射集。仿射集就是包含该集合内任意两点的线性组合,即包含了所有经过该集合集中任意两点的直线的集合。 比如:一维情况下可以类似理解为直线,但仿射集是一个更广意义的直线。 仿射包:对于任意一个集合,集合间所有点的仿射组合称为集合C的仿射包,仿射包是包含某些点构成的集合C的最小仿射集。如果任意仿射集S包含集合C,则集合C的仿射包是集合S的子集。我们一般将仿射包记为: 凸集 :实数域R上(或复数C上)的向量空间中,如果集合S中任两点的连线上的点都在S内,则称集合S为凸集,如下图所示: 另外,和仿射组合类似,我们定义凸集组合: 注意的是,仿射组合和凸集组合的区别在于θ的取值,也就是满足仿射组合定义的前提下,要求。 凸包:对应的凸包(convex hull)则可记为: 从定义上来看,凸包肯定是凸集,它是包含集合C的最小凸集。从下图我们可以看出,左边第一个图中的15个点的凸包为阴影包括的多边形,第二个图中肾型集合的凸包为直线封闭下的集合。 凸集和仿射集的联系和区别:从定义我们可以看出,仿射集和凸集间的区别就在于凸集是线段在集合中。仿射集要求的是集合中经过任意两点的直线上的任意点都在集合中。 注意:有人说凸集是仿射集的子集,但其实谁也不是谁的子集。确切的讲,包含所有仿射集的集合是包含所有凸集的集合的子集,因为一个仿射集是一个凸集。凸集定义比仿射集的定义更加苛刻,但是条件更加的苛刻不等于就是子集,不等于他们就是一类。比如,如果我们要区分固态和气态,常温常压下二氧化碳就是气态,如果限定他的温度、压力,条件更加苛刻,让其变成固态的干冰,我们还能说二氧化碳就是气态吗?我们能说固态是气态的子集吗?不能,因为“类别(集合)是根据某些固定条件去定义的”,而不是靠“苛刻程度”去识别的,所以我们有明确一下两个基础逻辑。 凸锥:锥体(cone)的定义为如果集合C中的任意点,其中,则集合C称为锥。如果集合既是凸集又是锥体,我们就称该集合为凸锥(convex cone)。凸锥的数学表达为: 凸锥中各点的线性组合我们称之为凸锥组合(conic combination),某集合C的各点的凸锥组合构成集合C的锥包(conic hull),记为 锥包:与仿射包和凸包类似,锥包也是包含集合C的最小凸锥集合。以下是两个锥包的实例,阴影部分表示集合构成的锥包,当然,顶点位置不同,所表示出的锥包也各不相同: 上图中第一个图中的15个点的锥包为阴影部分的集合,对应的第二个图中肾型集合的凸锥集合。 综合举例:
2、超平面和半空间 半空间:数学表达式为,,Emmm...又理解不了,简单理解,如下图,上面说了,超平面就是一个空间的一个界线,也就是说,超平面可以将空间分为两个半空间,举个二维例子: 凸集分离定理:所谓两个凸集分离,直观地看是指两个凸集合没有交叉和重合的部分,因此可以用一张超平面将两者隔在两边,如下图所示:
不改变凸集性质的运算对于凸集而言很重要,因为凸集的优良性质会使得优化求解过程更为简单,同时,我们也可以根据具体问题构建凸函数解决对应问题。不改变凸集的运算主要有以下几种: 透视函数:透视函数的直观理解如下:为一个不透光隔板,只有在原点有一个小孔,光透过小孔投射至的隔板上,如果上面的光点所构成的集合是凸的,那么投射至下方的光点构成的集合也是凸的。更加直观的想象我们通过一个针孔照相机去拍摄一个凸的对象,那么生成的图像也是凸的,如下图所示: 数学描述如下:
凸函数:就是一个定义域在某个向量空间的凸子集C上的实值函数。 凸优化问题:”凸优化“ 是指一种比较特殊的优化,是指求取最小值的目标函数为凸函数的一类优化问题。其中,目标函数为凸函数且定义域为凸集的优化问题称为无约束凸优化问题。而目标函数和不等式约束函数均为凸函数,等式约束函数为仿射函数,并且定义域为凸集的优化问题为约束优化问题在优化问题中,凸优化问题由于具有优良的性质(局部最优解即是全局解),受到广泛研究。对于一个含约束的优化问题: 将上面的约束条件的形式更加明确一点,一个凸优化问题可以写成:以上便是凸优化问题的一般形式。常见的线性规划、二次规划、二次约束二次规划等优化问题都是凸优化问题。
说了凸优化问题之后,我们再从无约束的优化,等式约束优化和不等式约束优化全面了解优化的类型的求解: 图中的等高线表示 的值。此时 在局部极小值点 处的梯度必然为0,比较容易理解。这个梯度为零的条件是局部极小值点的必要条件。这样,优化问题的求解变成了对该必要条件解方程组。这个是很简单的一种优化,直接。带等式约束的优化问题: s.t. 表示条件 与无约束的问题不同。我们所要求的极小值点被限制在曲线 上,我们将 称为可行域, 解只能在这个可行域里取。如下图所示,曲线 (黑色实曲线)经过无约束极小值点(黑点)附近。那么满足约束的极小值点应该与黑点尽可能近。我们将f(x) 的等高线不断放大,直到与曲线 相切,切点即为所求。相切是关键,也是极小值点的条件。 因此带等式约束的优化问题转化为了无约束的优化问题,只需要对拉格朗日条件解方程组即可。这里λ就是拉格朗日乘子,有多少个等式约束就有多少个拉格朗日乘子。 带不等式约束的优化问题: 当只有一个不等式时, 如我们把问题2里的等式约束 改为 ,如下图所示,可行域变成了阴影部分,最小值点还是切点,情况和问题2完全一样,只需要把不等号当做等号去求解即可。 当两个不等式起作用时,那么问题就来了 如下图,当 f(x)的等高线慢慢扩大时,等高线与可行域(阴影部分)第一次相遇的点是个顶点,2个不等式同时起作用了。满足约束的最小值点从原来的黑点位置(切点)移动到了红点位置,现在跟哪条约束函数曲线都不相切。那怎么才能找到这个黑点并求解?这时候就需要用到kkt条件了。这里的“条件”是指:某一个点它如果是最小值点的话,就必须满足这个条件(在含不等式约束的优化问题里)。这是个必要条件,前面说的也全部是必要条件。 其中,μ叫KKT乘子,有多少个不等式约束就有多少个KKT乘子。加上问题3中的约束部分,就是完整版的KKT条件。(注意:对于有等式的情况,你把其中一个不等式约束换成等式,可行域变成了半条曲线,最小值点还是那个红点,和下面这种情况是一样的。) 说完KKT条件是什么,然后说说KKT条件是怎么来的?: 注意:以上所有都是局部极小值点的必要条件。据此求得的解不一定是局部极小值点(更别提全局了),原因是上图中我所画的等高线也许根本就不闭合,也就是说我们一直想要靠近的等高线中间的黑点压根就是个鞍点或者近似鞍点。所以,很多时候,我们都是求其对偶问题来使得上面的条件变成充要条件,而一般问题也变成凸优化问题,具体下面讲解。 -结束- |
|