歐氏空間凸多面體極點凸組合表示定理的推廣

姚志敏

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

歐氏空間凸多面體極點凸組合表示定理的推廣

姚志敏

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

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

凸集;凸組合;極點;切平面;仿射集

1 引言

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

2 預(yù)備知識

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

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

命題 2.1[4]一個仿射集的平移也是仿射集,Rn的子空間是包含原點的仿射集.

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

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

則稱S為Rn中的凸集.

設(shè)

且

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

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

則稱x0為S的一個極點(頂點).

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

稱為Rn中的超平面.集合

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

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

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

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

為凸集,無界且不存在極點;經(jīng)過點x2的線段

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

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

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

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

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

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

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

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

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

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

為凸集,無界閉集,其中任意一點也能由極點的凸組合表示;集合

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

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

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

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

其中

且

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

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

5 結(jié)語

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

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

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

參考文獻

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

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

[3]魏權(quán)齡,汪俊,閆洪.無界凸面體由“和形式”向“交形式”的轉(zhuǎn)化[J].系統(tǒng)工程理論與實踐,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ā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]陳喬.嚴格r-預(yù)不變凸函數(shù)[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2013,29(6):621-626.

[11]張恭慶,林源渠.泛函分析講義:上冊[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.

國家自然科學(xué)基金(11461002);廣西高?？茖W(xué)技術(shù)研究項目基金(LX2014194).

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

2010 MSC:52A20