歐氏空間凸多面體極點(diǎn)凸組合表示定理的推廣

姚志敏

(廣東培正學(xué)院計(jì)算機(jī)科學(xué)與工程系,廣東 廣州 510830)

歐氏空間凸多面體極點(diǎn)凸組合表示定理的推廣

姚志敏

(廣東培正學(xué)院計(jì)算機(jī)科學(xué)與工程系,廣東 廣州 510830)

使用切面技術(shù)、歸納法等證明了歐氏空間中凸集極點(diǎn)的存在性,進(jìn)一步證明了空間中一般有界閉凸集(不只局限于凸多面體)中任意一點(diǎn)同樣可表示為極點(diǎn)的凸組合.方法獨(dú)到.

凸集;凸組合;極點(diǎn);切平面;仿射集

1 引言

線性規(guī)劃領(lǐng)域[1-2]常有提出n維歐氏空間(后續(xù)簡(jiǎn)記為Rn)中有界凸集中任意一點(diǎn)可由此集合極點(diǎn)的凸組合表示,但其所涉及的凸集只局限于凸多面體[1,3],且一般著述中鮮有進(jìn)行證明.事實(shí)上,進(jìn)一步推廣,對(duì)于n維歐氏空間中一般有界閉凸集S,任意一點(diǎn)x∈S同樣可表示為S的極點(diǎn)的凸組合.

2 預(yù)備知識(shí)

定義 2.1[1]若集合M ?Rn包含所有通過(guò)其內(nèi)任意兩點(diǎn)的直線,即?x1,x2∈M,λ∈R有

則稱M 為一個(gè)仿射集(仿射流形).

命題 2.1[4]一個(gè)仿射集的平移也是仿射集,Rn的子空間是包含原點(diǎn)的仿射集.

定義 2.2[1]非空仿射集M 的維數(shù)是指平行于仿射集M 的子空間的維數(shù),Rn中任意集合S的維數(shù)為包含S的仿射集的最小維數(shù).

定義 2.3[5]設(shè)S?Rn,若對(duì)任意x1,x2∈S和任意數(shù)λ∈[0,1],有

則稱S為Rn中的凸集.

設(shè)

且

命題 2.2[4,6]凸集的交集還是凸集,閉凸集的交集還是閉凸集.

定義 2.4[6]設(shè)S是凸集,x0∈S,若x0不能用不同的兩點(diǎn)x1∈S,x2∈S的線性組合表示,即

則稱x0為S的一個(gè)極點(diǎn)(頂點(diǎn)).

定義 2.5[1]對(duì)于給定的非零向量PT=(p1,p2,…,pn)和實(shí)數(shù)β(這里x為列向量),集合

稱為Rn中的超平面.集合

稱為Rn中的閉半空間,即由超平面H所劃分的兩個(gè)閉半空間.

命題 2.3[1]Rn中超平面H等同n?1維仿射集,即某一n?1維子空間的平移.

3 主要結(jié)果一:n維歐氏空間中凸集極點(diǎn)的存在性

顯然,Rn中凸集不一定存在極點(diǎn).例如,給定x1,x2∈Rn,經(jīng)過(guò)兩點(diǎn)的直線

為凸集,無(wú)界且不存在極點(diǎn);經(jīng)過(guò)點(diǎn)x2的線段

為凸集,有界且存在極點(diǎn)x2;單位開球{x|∥x∥＜1,x∈Rn}為凸集,有界且不存在極點(diǎn).

對(duì)于Rn中凸集,要研究其中任意一點(diǎn)可否表示為其極點(diǎn)的凸組合,前提是此凸集必須存在極點(diǎn).

引理 3.1[7-9]設(shè)S(≠?)為Rn中的閉凸集,y?S,則存在非零向量p∈R及實(shí)數(shù)ε＞0,使得對(duì)點(diǎn)x∈S,有

引理 3.2[5,7,10]設(shè)S(≠?)為Rn中的閉凸集,y∈?S(?S為S的邊界,此處?S?S),則存在非零向量p∈Rn,使得對(duì)點(diǎn)x∈S,有pTy≥pTx,即存在經(jīng)過(guò)y點(diǎn)的S的n?1維切平面(支撐超平面)

定理 3.1設(shè)S(≠?)為Rn中有界閉凸集,則S一定存在極點(diǎn).

4 主要結(jié)果二:n維歐氏空間中凸集的極點(diǎn)凸組合表示

Rn中凸集S即使存在極點(diǎn),?x∈S也未必能由極點(diǎn)的凸組合所表示.舉例如下:

例 4.1?x1,x2∈Rn,經(jīng)過(guò)點(diǎn)x2的線段{x|x=λx1+(1?λ)x2,λ∈[0,1)}為凸集,非閉有界,(唯一)極點(diǎn)x2外任意一點(diǎn)不能由極點(diǎn)x2的凸組合表示;經(jīng)過(guò)點(diǎn)x2的射線

為凸集,無(wú)界閉集,(唯一)極點(diǎn)x2外任意一點(diǎn)也不能由極點(diǎn)x2的凸組合表示.

例 4.2R2中,半圓{(x,y)|x2+y2≤1,x＞0,x,y∈R}為凸集,非閉有界,其中任意一點(diǎn)能由極點(diǎn)的凸組合表示;集合

為凸集,無(wú)界閉集,其中任意一點(diǎn)也能由極點(diǎn)的凸組合表示;集合

為凸集,非閉無(wú)界,極點(diǎn)(0,0)外任意一點(diǎn)卻不能由極點(diǎn)的凸組合表示.

例 4.3R3中集合{(x,y,z)|y2+z2≤x,y＞0,x,y,z∈R}為凸集,非閉無(wú)界,其中任意一點(diǎn)能由極點(diǎn)的凸組合表示.

然而,對(duì)于Rn中的有界閉凸集,情況則不一樣了.

定理 4.1設(shè)S為Rn中有界閉凸集,?x∈S總可以找到S的有限個(gè)極點(diǎn)x1,x2,…,xm,使得

其中

且

證明由定理3.1知Rn中有界閉凸集存在極點(diǎn).數(shù)學(xué)歸納法:

注 1Rn中,由于凸多面體屬于有界閉凸集中的一種特殊形式,所以線性規(guī)劃領(lǐng)域[1,4]凸多面體中任意一點(diǎn)可由該多面體極點(diǎn)的凸組合表示,這一重要定理就成了定理4.1的一個(gè)直接推論.

5 結(jié)語(yǔ)

定理3.1中要直接證明S存在極點(diǎn)是非常困難的,所以先使用切面技術(shù)得到S的低維子集S′,再證明S′的極點(diǎn)同時(shí)是S的極點(diǎn),最后結(jié)合歸納假設(shè)完成其證明.方法獨(dú)到.

定理4.1的證明同樣使用了”S′的極點(diǎn)同時(shí)是S的極點(diǎn)”這一重要結(jié)果.

定理3.1、4.1中結(jié)論有望作更進(jìn)一步的推廣,研究其在Banach、一般度量等空間中的成立性.

參考文獻(xiàn)

[1]Dimitris Bertsimas,John N.Tsitsiklis.Introduction to Linear Optimization[M].Nashua:Athena Scienti fi c, 1997.

[2]譚澤光.多面體有限基定理的一個(gè)證明[J].清華大學(xué)學(xué)報(bào):自然科學(xué)版,1988,28(3):83-90.

[3]魏權(quán)齡,汪俊,閆洪.無(wú)界凸面體由“和形式”向“交形式”的轉(zhuǎn)化[J].系統(tǒng)工程理論與實(shí)踐,2004,24(3):87-90.

[4]Leonid Nison Vaserstein,Christopher Cattelier Byrne.Introduction to Linear Programming[M].Bergen: Pearson Education,Inc.,2003.

[5]Borwein J M,Lewis A S.Convex Analysis and Nonlinear Optimization[M].2nd ed.Berlin:Springer,2006.

[6]張干宗.線性規(guī)劃[M].武漢:武漢大學(xué)出版社,2004.

[7]柯爾莫戈洛夫A H,佛明C B.函數(shù)論與泛函分析初步[M].段虞榮,鄭洪深,郭思旭,譯.北京:高等教育出版社,2006.

[8]陳利國(guó),羅成.關(guān)于局部凸空間的中點(diǎn)局部一致凸性[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2011,27(6):749-755.

[9]Ha¨?m Brezis.Analyse Fonctionnelle-Th é orieet Applications[M].Berlin:Springer,2009.

[10]陳喬.嚴(yán)格r-預(yù)不變凸函數(shù)[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2013,29(6):621-626.

[11]張恭慶,林源渠.泛函分析講義:上冊(cè)[M].北京:北京大學(xué)出版社,2008.

Generalization of the representation theorem of the convex combinations of convex polyhedron extreme points in Euclidean space

Yao Zhimin
(Department of Computer Science and Engineering,Guangdong Peizheng College, Guangzhou 510830,China)

By the techniques such as tangent plane,mathematical induction,we obtain the existence of extreme points of convex set in n-dimensional Euclidean space.We further prove,by a unique method,any point in a bounded closed convex set(not limited to convex polyhedron)can be expressed as a convex combination of the extreme points.

convex set,convex combination,extreme point,tangent plane,tangent plane

O174.13

A

1008-5513(2017)01-0019-07

10.3969/j.issn.1008-5513.2017.01.003

2016-11-06.

國(guó)家自然科學(xué)基金(11461002);廣西高校科學(xué)技術(shù)研究項(xiàng)目基金(LX2014194).

姚志敏(1975-),碩士,講師,研究方向：應(yīng)用數(shù)學(xué)及理論.

2010 MSC:52A20