关于凸集分离定理.doc

关于凸分析的若干补缺1如同数学分析是以建立在实数域上的连续函数为研究对象的数学理论一样，凸分析是关于具有凸性的集合和函数的数学分析的理论，所以，它的主要对象是凸集和凸函数。另一方面，凸函数在很多情况下是非光滑的，而非光滑优化问题的分析与求解理论，是以凸分析中较深入部分为理论基础的，这一部分称为非光滑分析。此处给大家补充凸分析的基础内容。如果有同学还想继续加深自己的学习，可以参考：1胡毓达等 凸分析与非光滑分析，上海科学技术出版社，20002黄红选等 数学规划，清华大学出版社，2006外文的版本不少，你可以以“convex analysis”为主题词去查找。比如，由Alexander Rubinov写的Abstract Convexity and Global Optimization就是一本很好的书，但需要时间去认真研度。2几个重要的凸集合（1）凸包（convex hell） 凸包常用的定义有2个，一是：集合的凸包是中所有包含的凸集的交集。另一个可以由此定义推出的一个定理：定理2。1（凸包表示定理）设，则中有限个元素（点）的一切凸组合所构成的集合是凸集，并且此凸集就是的凸包，即 凸包的运算性质可用下列定理来表示。定理2。2 设，那么1），进一步若是凸集，则；2）；3）若是凸集，则。关于此两定理的证明可以参看上述文献1。（2）凸锥由定义，可以证明：集合 是一个凸锥。我们称为由所生成的凸锥。3凸集的分离定理 凸集的分离定理是应用凸集到最优化理论中的重要结果，这个结果在最优化理论中有重要的位置。由于时间问题，我们在课堂上没有细讲。这里宜补上。 所谓两个凸集分离，直观地看是指两个凸集合没有交叉和重合的部分，因此可以用一张超平面将两者隔在两边。这样理解当然是对的，但数学上需要准确的定量描述，否则在以后的演绎证明过程中，不容易推导了。定义 设为两个非空集合，如果存在非零向量及，使得 则称超平面分离了集合和。仔细看，如果两个被分离的集合在一点上“相切”，还是可以用一张超平面象一把薄刀，将它们劈开来。为了证明凸集的分离定理，先给出闭凸集合的一个性质。我们不妨把一个闭凸集想象为一个三维的充满了气体的汽球（不一定标准球形的其它形状，但必须是凸的），那么，在汽球外一点，到汽球各点（包括内部）的距离是不一样的，但直觉告诉我们，肯定在汽球上有一点，它到的距离是所有距离中最小的。这是凸集的特有性质。如果不是凸集，就不会这样了，比如一个平面上对称心形的图形（它不是凸的）外一点，至少可以找到2点，使其到外面那一点的距离最小。引理3。1 设为非空闭凸集，则存在唯一的，使得该点与的距离最小，即有 0根据范数的等价性，这里的范数可以是任一种范数。证明：先证明其存在性。考虑单位超球 取足够大的正数，使 ，（我们之所以要“制造”出这样一个集合，是为了有一个有界闭集！想想看，为什么？）因为 为闭集，而是一个有界闭集，所以，是一个非空的有界闭集。我们知道，范数是一个连续函数，一个连续函数在有界闭集上总可以在其上的某一点取得它的最大值，在另一点上取得其最小值。（对这个结论不太理解的话，你可以用一元函数在闭区间上画一条连续函数的图线就明白，不过，必须是闭区间！）设这个最小值在处达到，即是到的最小距离点。记此距离值为。再证唯一性。假设还存在另一点，使 （*）记。因为 ，两边取范数，则有 但是为凸集，是与的凸组合，所以。而由于r 是y到S的最小距离，故 （*）根据平行四边形定律（两对角线长的平方和=一组邻边平方和的两倍）（这里要把看为平行四边形的一组邻边，那么一条对角线长为，另一条为） 把（*）（*）代入，有，故有 ， 唯一性得证。 在此基础上，可给出凸集分离定理。这个定理说，对于凸集外的一点y，存在一个向量p，存在一个以此向量为法向量的超平面 ，能够分离点y与凸集。定理3。2 （凸集分离定理）设为非空闭凸集，则存在非零向量及，使得 （3。1）证明：因为为非空集合，是外的一点，故由引理3。1知，存在一点，使得 设，那么，因为凸集，故有，使 因此， 上式两边的可消去，得 在上式中，令，得 记 ，有 若记，则有 另一方面，由于所以 这正是我们要证明的结果。4凸集分离定理的一个应用例子 这里介绍Farkas引理，这个定理在我们即将学习的最优性条件中是重要的基础。定理4。1（Farkas引理）设，则下列两组关系式有且仅有一组有解： （1） ； （2） 。证明： 要证明两组关系式只有一个有解，也就是一个有解时，另一个必无解；反过来，一个无解时，另一个则必有解。所以先设（2）有解，我们来证明，此时，（1）则无解。所谓无解，是（1）中的关系式是不能成立的。因为（2）有解，即存在一个向量，使得 。此时， 记此式为（*）。在看（1），假设有，使（1）中的地一个关系式成立 。我们来看（1）中的第2个式子会如何？ 把（*）代入 ，有 （*）上述最后一个不等式的成立是因为和的缘故。显然，（*）的结果与（1）中的第2个关系矛盾，也就是（2）有解时，（1）必无解。这样，第一层的证明就完成了。接下来需要做第2层的工作。（为什么非要做？请思考！）另一方面，再设（2）无解，我们来证明，在这种情况下，（1）必有解。记集合 ，则为非空闭凸集。（因为是若干闭半空间的交），且。由凸集分离定理知，存在，使因（为什么？），故有上式知，从而。于是 但因，向量的分量可任意大，因此，。这样，我们就找到了， 使，从而（1）有解。 综合上面两个方面的论述，Farkas引理得到了证明。 请大家仔细体会证明过程中用的逻辑关系和技巧，能从中体会到“数学的美”吗？实际上，我们以后在最优化领域中所建立的许多方法，都是建立在这些逻辑思维构成的钢筋组成的地基之上的，没有它们，最优化的大厦立刻回倾倒。所以，我们不要把它们视为无用枯燥的数学游戏。利用Farkas引理，我们还可以证明有价值的Gordan定理和择一性定理。这里我们只证明Gordan定理。Gordan定理在证明最优性条件中著名的Kuhn-Tucker条件，是极为关键的基础。 定理4。2 （Gordan定理）设，则下列两组关系式有且仅有一组有解： （1） ； （2） 证明：如果（1）有解，即存在，使得，则对任意的，有，即 。这表明（2）无解。另一方面