關(guān)于凸集及凸集分離定理的教學(xué)設(shè)計①

付云姍 劉蘭冬

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

關(guān)于凸集及凸集分離定理的教學(xué)設(shè)計①

付云姍 劉蘭冬

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

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

凸集；投影；凸集分離定理；教學(xué)設(shè)計

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

一、課堂導(dǎo)入

我們首先回顧一下集合的概念，廣義地講，集合是指具有某種性質(zhì)的事物的總體。今天我們來學(xué)習(xí)的凸集即是一類具有特殊結(jié)構(gòu)特點(diǎn)的集合。首先，我們來學(xué)習(xí)一下凸集的概念。

二、凸集及投影的概念

定義1設(shè)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中與點(diǎn)x∈Rn距離最近的點(diǎn)稱為x在S上的投影（projection），記為PS（x）。下面將為大家講解一下點(diǎn)到非空閉凸集的投影的存在性、唯一性以及非擴(kuò)張性等性質(zhì)。首先我們不加證明地給出存在性和唯一性結(jié)果。

定理1設(shè)SRn為非空閉凸集，則對任意點(diǎn)x∈Rn，x在S上的投影PS（x）存在且唯一，并且滿足

當(dāng)將投影PS看成從Rn到Rn的映射時，它具有非擴(kuò)張性，如下結(jié)論揭示了任意兩點(diǎn)的距離不因到閉凸集上的投影而擴(kuò)大這一事實。

定理2設(shè)SRn為非空閉凸集，則有下式成立：

利用定理1的結(jié)論以及Cauchy－Schwarz不等式即可得到本結(jié)論，故此處省略證明過程。

三、分離定理

（一）分離定理

定理3給定非空凸集SRn，與點(diǎn)xclS，則必存在S和x的分離超平面H＝｛x∈Rn｜〈a，x〉＝α｝使得

（二）凸集分離定理的應(yīng)用

Farkas引理（1902）在形式上時線性方程組及線性不等式組和線性表示式這兩者中必有一個且僅有一個成立，所以該引理也稱為擇一性引理。

引理4設(shè)l和l′是兩個非負(fù)整數(shù)，a0，ai（i＝1，…，l）和bi（i＝1，…，l′）是Rn中的向量，則線性方程組及不等式組

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

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

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

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

［3］張瑩.運(yùn)籌學(xué)基礎(chǔ)［M］.清華大學(xué)出版社，2010.

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