關于凸集及凸集分離定理的教學設計①

付云姍 劉蘭冬

（中國礦業(yè)大學（北京）理學院 北京 100083）

關于凸集及凸集分離定理的教學設計①

付云姍 劉蘭冬

（中國礦業(yè)大學（北京）理學院 北京 100083）

本文考慮凸集及分離定理的教學設計，本文內容為本科生課程《運籌學》教學過程中，凸集及其性質的深入研究，由凸集及其性質的講授拓展引出凸分析相關內容，本文將教學內容拓展到分離定理的研究。利用啟發(fā)式和總結式相結合的方法，展開了對分離定理的教學研究，使學生對凸集及分離定理的概念和性質立體的、深刻的理解，從而有效地提高教學質量。

凸集；投影；凸集分離定理；教學設計

凸集是凸分析的基礎概念之一，而分離定理是凸分析的基礎理論內容，因此是教學中的重點也是難點。本文針對性的對凸集及拓展知識分離定理進行了教學研究。從同學們熟悉的集合例子談起，給出凸集的定義，引入投影的概念，逐步推導出凸集分離定理的內容。

一、課堂導入

我們首先回顧一下集合的概念，廣義地講，集合是指具有某種性質的事物的總體。今天我們來學習的凸集即是一類具有特殊結構特點的集合。首先，我們來學習一下凸集的概念。

二、凸集及投影的概念

定義1設S是Rn中的一個非空集合，如果對于任意x（1），x（2）∈S及任意實數(shù)λ∈［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′是兩個非負整數(shù)，a0，ai（i＝1，…，l）和bi（i＝1，…，l′）是Rn中的向量，則線性方程組及不等式組

無解當且僅當存在實數(shù)λi（i＝1，…，l）和非負實數(shù)μi（i＝1，…，l′），使得

引理4即是著名的Farkas引理，在它的充分性證明時利用了凸集分離定理的結論。可由Farkas引理推出約束優(yōu)化問題的必要性條件，即著名的Karush-Kuhn-Tucker定理。

［1］袁亞湘.非線性優(yōu)化計算方法［M］.科學出版社，2008.

［2］刁在筠，劉桂真，宿潔，馬建華.運籌學［M］.高等教育出版社，2007.

［3］張瑩.運籌學基礎［M］.清華大學出版社，2010.

本文受中國礦業(yè)大學（北京）教學改革項目：“運籌學”課程建設（項目編號：k130701）資助。