关于凸集及凸集分离定理的教学设计①

付云姗 刘兰冬

（中国矿业大学（北京）理学院 北京 100083）

关于凸集及凸集分离定理的教学设计①

付云姗 刘兰冬

（中国矿业大学（北京）理学院 北京 100083）

本文考虑凸集及分离定理的教学设计，本文内容为本科生课程《运筹学》教学过程中，凸集及其性质的深入研究，由凸集及其性质的讲授拓展引出凸分析相关内容，本文将教学内容拓展到分离定理的研究。利用启发式和总结式相结合的方法，展开了对分离定理的教学研究，使学生对凸集及分离定理的概念和性质立体的、深刻的理解，从而有效地提高教学质量。

凸集；投影；凸集分离定理；教学设计

凸集是凸分析的基础概念之一，而分离定理是凸分析的基础理论内容，因此是教学中的重点也是难点。本文针对性的对凸集及拓展知识分离定理进行了教学研究。从同学们熟悉的集合例子谈起，给出凸集的定义，引入投影的概念，逐步推导出凸集分离定理的内容。

一、课堂导入

我们首先回顾一下集合的概念，广义地讲，集合是指具有某种性质的事物的总体。今天我们来学习的凸集即是一类具有特殊结构特点的集合。首先，我们来学习一下凸集的概念。

二、凸集及投影的概念

定义1设S是Rn中的一个非空集合，如果对于任意x（1），x（2）∈S及任意实数λ∈［0，1］，有λx（1）＋（1－λ）x（2）∈S，则称S为凸集，否则称它为非凸集，我们称λx（1）＋（1－λ）x（2）为x（1）和x（2）的凸组合。

非空闭凸集SRn中与点x∈Rn距离最近的点称为x在S上的投影（projection），记为PS（x）。下面将为大家讲解一下点到非空闭凸集的投影的存在性、唯一性以及非扩张性等性质。首先我们不加证明地给出存在性和唯一性结果。

定理1设SRn为非空闭凸集，则对任意点x∈Rn，x在S上的投影PS（x）存在且唯一，并且满足

当将投影PS看成从Rn到Rn的映射时，它具有非扩张性，如下结论揭示了任意两点的距离不因到闭凸集上的投影而扩大这一事实。

定理2设SRn为非空闭凸集，则有下式成立：

利用定理1的结论以及Cauchy－Schwarz不等式即可得到本结论，故此处省略证明过程。

三、分离定理

（一）分离定理

定理3给定非空凸集SRn，与点xclS，则必存在S和x的分离超平面H＝｛x∈Rn｜〈a，x〉＝α｝使得

（二）凸集分离定理的应用

Farkas引理（1902）在形式上时线性方程组及线性不等式组和线性表示式这两者中必有一个且仅有一个成立，所以该引理也称为择一性引理。

引理4设l和l′是两个非负整数，a0，ai（i＝1，…，l）和bi（i＝1，…，l′）是Rn中的向量，则线性方程组及不等式组

无解当且仅当存在实数λi（i＝1，…，l）和非负实数μi（i＝1，…，l′），使得

引理4即是著名的Farkas引理，在它的充分性证明时利用了凸集分离定理的结论。可由Farkas引理推出约束优化问题的必要性条件，即著名的Karush-Kuhn-Tucker定理。

［1］袁亚湘.非线性优化计算方法［M］.科学出版社，2008.

［2］刁在筠，刘桂真，宿洁，马建华.运筹学［M］.高等教育出版社，2007.

［3］张莹.运筹学基础［M］.清华大学出版社，2010.

本文受中国矿业大学（北京）教学改革项目：“运筹学”课程建设（项目编号：k130701）资助。