付云姍 劉蘭冬

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

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

付云姍 劉蘭冬

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

本文考慮凸集及分離定理的教學(xué)設(shè)計(jì)，本文內(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è)計(jì)

凸集是凸分析的基礎(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中的一個(gè)非空集合，如果對于任意x（1），x（2）∈S及任意實(shí)數(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的映射時(shí)，它具有非擴(kuò)張性，如下結(jié)論揭示了任意兩點(diǎn)的距離不因到閉凸集上的投影而擴(kuò)大這一事實(shí)。

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

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

三、分離定理

（一）分離定理

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

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

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

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

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

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

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

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

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

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