2 賦范線性空間與凸集 課件

第2章賦范線性空間與凸集2.1賦范線性空間 2.2凸集 2.3一些重要例子 2.4保持凸性的運(yùn)算 2.5分離超平面和支撐超平面2.1賦范線性空間2.1.1賦范線性空間 2.1.2開集和閉集 2.1.3上確界和下確界 2.1.4序列收斂和完備性 2.1.5緊性 2.1.6Banach空間

2.1.1賦范線性空間線性空間(linearspace)/向量空間(vectorspace)指定義加法和標(biāo)量乘法的非空集合加法(addition)，標(biāo)量乘法，，，，滿足：(交換律)(結(jié)合律)(結(jié)合律)6．，7．對(duì)，，8．線性空間在加法和標(biāo)量乘法下是閉的(closed)。線性空間的元素稱為向量(vector)。

例2.1一些線性空間維實(shí)向量空間或維歐氏空間：所有維實(shí)向量的集合所有實(shí)數(shù)序列的集合，所有多項(xiàng)式的集合。

消費(fèi)集(例1.1)和生產(chǎn)可能性集(例1.2)本身不是線性空間。但它們都是線性空間的子集，并且都從其母空間中繼續(xù)了許多線性特征。

例2.2(總需求和總供給)個(gè)消費(fèi)者，每個(gè)消費(fèi)者購買消費(fèi)組合總需求(aggregatedemand)其中對(duì)每種商品，對(duì)它的總需求其中是消費(fèi)者對(duì)商品的需求。個(gè)廠商，每個(gè)廠商的凈產(chǎn)出向量為總供給(aggregatesuppley)均衡要求總需求等于總供給，即意味著:或者:

范數(shù)(norm)實(shí)值函數(shù)稱為范數(shù)，，滿足：非負(fù)性(positivity)：嚴(yán)格非負(fù)性(strictpositivity)：齊次性(homogeneity)：三角不等式(triangleinequality)：范數(shù)用來衡量向量的大小，符號(hào)表明范數(shù)是實(shí)數(shù)集上絕對(duì)值的推廣。

度量(metric)符合距離函數(shù)的要求即對(duì)，滿足：非負(fù)性(positivity)：嚴(yán)格非負(fù)性(strictpositivity)：對(duì)稱性(symmetry)：三角不等式(triangleinequality)：集合加上其度量稱為度量空間(metricspace)，表示為。

例2.3范數(shù)的一些例子上的絕對(duì)值歐幾里德（Euclidean）或范數(shù)Cauchy-Schwarz不等式：，。絕對(duì)值之和或范數(shù)Chebyshev范數(shù)或范數(shù)上述三個(gè)范數(shù)都屬于范數(shù)的特例，其中。范數(shù)；歐幾里德范數(shù)

例2.4生產(chǎn)計(jì)劃的“大小”的測量

賦范線性空間(normedlinearspace)定義在范數(shù)之上的線性空間本書涉及的三類賦范線性空間維實(shí)向量空間階實(shí)矩陣空間上的有界、連續(xù)的實(shí)值函數(shù)空間，處的函數(shù)值為在處的函數(shù)值為

例2.5(空間)一生的消費(fèi)路徑選擇問題一種商品，表示期時(shí)對(duì)該商品的消費(fèi)量設(shè)消費(fèi)者是長生不老的消費(fèi)者計(jì)劃消費(fèi)集，它是一個(gè)線性空間每期消費(fèi)受資源限制：。結(jié)合范數(shù)，它成為賦范線性空間。在這一范數(shù)中，任意消費(fèi)計(jì)劃的規(guī)模是任一時(shí)期最大的計(jì)劃消費(fèi)的絕對(duì)值

子空間(subspace)，稱為的子空間，，每個(gè)賦范線性空間都有兩個(gè)平凡子空間：和。

例2.6的子空間原點(diǎn)所有經(jīng)過原點(diǎn)的直線所有經(jīng)過原點(diǎn)的平面本身例2.7次數(shù)小于的多項(xiàng)式設(shè)表示所有次數(shù)小于的多項(xiàng)式，由于加法和標(biāo)量乘法不會(huì)提高多項(xiàng)式的次數(shù)，因此，集合是所有多項(xiàng)式的集合的子空間。

非空集合，跨度：設(shè)是子空間的子集，如果中沒有真子集具有跨度這一性質(zhì)，則稱是子空間的基(base)。基的元素是線性無關(guān)的除外，子空間通常有很多不同的基。若有一個(gè)由有限個(gè)元素組成的基，則所有基都有相同數(shù)目的非零元素，這一數(shù)目稱為子空間的維(dimension)。若子空間沒有有限基，則它是無限維的。

例2.8的標(biāo)準(zhǔn)基單位向量的集合稱為的標(biāo)準(zhǔn)基。每一向量都有唯一表達(dá)式：

是具有許多可能的基的維空間任意個(gè)線性無關(guān)的維向量的跨度形成的維子空間。

2.1.2開集、閉集和緊集開球(openball)例2.9中的單位球單位球(unitball)歐幾里德或范數(shù)：圓形范數(shù)：正方形范數(shù)，單位球是菱形的是的鄰域包含的開球，稱為的內(nèi)點(diǎn)(interiorpoint)內(nèi)部(interior)中所有內(nèi)點(diǎn)的集合是開的(open)是閉的(closed)是開的。

例2.10開球是開集圖2.4開球是開集

中的開集和閉集具有如下事實(shí)：任意個(gè)開集的并是開集，有限個(gè)開集的交是開集。任意個(gè)閉集的交是閉集，有限個(gè)閉集的并是閉集。

邊界點(diǎn)(boundarypoint)是的邊界點(diǎn)的每個(gè)鄰域既包含中的點(diǎn)也包含中的點(diǎn)邊界(boundary)是所有邊界點(diǎn)的集合圖2.5中的內(nèi)點(diǎn)和邊界點(diǎn)

閉包(closure)開閉。

例2.10(閉球)閉球是閉集。例2.11(單位球面)單位球的邊界是，稱為單位球面(unitsphere)。中單位球面是，它是集合的邊界。

例2.13效率生產(chǎn)生產(chǎn)計(jì)劃是有效率的(efficient)不存在可行計(jì)劃，-有效率的生產(chǎn)計(jì)劃的集合Eff的每個(gè)內(nèi)點(diǎn)都是非效率的通常是的真子集

2.1.5上確界和下確界，是的上界(upperbound)，的上界的集合(此時(shí)稱無上界)整個(gè)(僅當(dāng)時(shí))閉的無界區(qū)間上確界(supremumin)集合的最小上界；向上無界，則取，而當(dāng)時(shí)，稱取得(或達(dá)到)上確界。，是的下界(upperbound)，。下確界(infimum)集合的最大下界；向上無界，則取，而當(dāng)，稱取得(或達(dá)到)上確界。

2.1.4序列收斂和完備性中的序列(sequence)或或，，。稱為的極限點(diǎn)(limitpoint)或極限(limit)

序列收斂極限惟一圖2.6序列收斂

柯西序列(Cauchysequence)極限點(diǎn)的候選點(diǎn)不易得時(shí)，一般采用柯西準(zhǔn)則。為柯西序列，，。每個(gè)收斂的序列都是柯西序列。

有界(bounded)直徑有限，即?？挛餍蛄杏薪?，這意味著，每個(gè)收斂序列都有界。

在一些度量空間中，柯西序列不會(huì)收斂于空間中的元素。為此，我們有：定義2.4(完備度量空間)如果集合中的每個(gè)柯西序列都收斂于中的一個(gè)元素，則稱度量空間()是完備的(complete)?；臼聦?shí)具有度量的實(shí)數(shù)集是一個(gè)完備的度量空間。

子序列(subsequence)給定序列，設(shè)有一個(gè)嚴(yán)格遞增函數(shù)，它將每個(gè)正整數(shù)分配給一個(gè)正整數(shù)，則序列稱為的子序列(subsequence)。緊度量空間度量空間是緊的(compact)中的每個(gè)序列都有收斂子序列緊集閉而有界

2.1.4Banach空間Banach空間完備的賦范線性空間是典型的有限維賦范線性空間定理2.2有限維賦范線性空間的性質(zhì)：它是完備的；定義于其上的所有范數(shù)都是等價(jià)的；子集是緊集，當(dāng)且僅當(dāng)它是閉而有界的。

2.2凸集2.2.1仿射集2.2.2凸集2.2.3凸錐

2.2.1仿射集，，，形為的點(diǎn)形成經(jīng)過和的直線。對(duì)應(yīng)于對(duì)應(yīng)于對(duì)應(yīng)于和之間的線段。

是基點(diǎn)(對(duì)應(yīng)于)和用縮放的方向(由指向)之和。給出了點(diǎn)所在的從到的部分路徑。圖2.7直線和線段

是仿射的(affine)，，形為的點(diǎn)稱為點(diǎn)的仿射組合(affinecombination)，其中。仿射集包含它的點(diǎn)的每一種仿射組合，即如果是仿射集，，，則也在中

仿射集可表示為子空間加上偏移量(offset)：，是仿射集是的子空間。

例2.13線性方程組的解集線性方程組的解集是仿射集，其中矩陣，向量。證明：設(shè)，即，，則對(duì)，有這意味著仿射組合也在中。與仿射集相聯(lián)系的子空間是的零空間，即。反命題也成立：每個(gè)仿射集都可表示為線性方程組的解集。

仿射包(affinehull)中的點(diǎn)的所有仿射組合的集合仿射包是包含的最小仿射集：如果為任意滿足的仿射集，則。

2.2.2凸集集合是凸的(convex)，，每個(gè)仿射集都是凸的凸集非凸集非凸集圖2.8中的凸集與非凸集

形為的點(diǎn)稱為點(diǎn)的凸組合(convexcombination)，其中，注意，仿射組合沒有這一非負(fù)性要求集合是凸的它包含其元素的所有凸組合。凸組合可以視為點(diǎn)的混合或加權(quán)平均(mixtureorweightedaverage)，其中是的權(quán)重。

例2.14(消費(fèi)集)消費(fèi)集指所有可行消費(fèi)組合的集合(例1.1)。如果和是兩種消費(fèi)組合，它們加權(quán)平均是另一消費(fèi)組合。消費(fèi)集是的凸子集。

(投入要求集)投入要求集為，和是生產(chǎn)的兩種不同方式。問題：能否將兩種生產(chǎn)過程聯(lián)合起來，并且仍生產(chǎn)，？為凸集，則答案為是。生產(chǎn)者理論一般假設(shè)是凸集，此時(shí)，稱技術(shù)是凸的。

的凸包(convexhull)凸包是包含的最小凸集 (a) (b)圖2.9中的凸包 2.2.3凸錐集合為錐(cone)，，有。是凸錐(convexcone)既是錐又是凸集，即，，圖2.10凸錐形為的點(diǎn)稱為點(diǎn)的錐組合(coniccombination)，其中集合是凸錐包含其元素的所有錐組合。

例2.16(凸技術(shù))技術(shù)的典型假設(shè)是：(1)加法：;(2)規(guī)模報(bào)酬不變：對(duì)加法要求生產(chǎn)過程是獨(dú)立的。同時(shí)，通常的假定意味著生產(chǎn)可能性集是一個(gè)凸錐。對(duì)技術(shù)來說，凸性的要求比較嚴(yán)格。

集合的錐包(conichull)錐包是包含的最小凸錐圖2-8錐包2.3一些重要例子2.3.1超平面與半空間 2.3.2歐幾里德球、賦范球和賦范錐 2.3.3多面體

凸集的一些簡單的例子空集、任意單點(diǎn)集以及整個(gè)空間是的仿射子集，從而是的凸子集。任意直線都是仿射集，如果它經(jīng)過，那么它是子空間，因而凸錐。線段是凸集，但不是仿射集，除非它縮減為一點(diǎn)。形為的射線是凸集，但不是仿射集。如果基點(diǎn)，則它是凸錐。任意子空間都是仿射集和凸錐(因而是凸集)。2.3.1超平面與半空間超平面(hyperplane)，，，。線性方程組的解集，從而是仿射集。法向量(normalvector)為的超平面，常數(shù)決定著超平面和原點(diǎn)之間的偏移：其中是超平面上的任意點(diǎn)：

超平面由偏移加上與法向量正交的所有向量組成圖2.12中的超平面

例2.18競爭性廠商的凈收入函數(shù)是包含常數(shù)利潤為的生產(chǎn)計(jì)劃的超平面，有時(shí)稱為等利潤線(isoprofitlines)(閉)半空間(halfspace)其中半空間是凸集，但不是仿射集。圖2.14中的半空間

半空間的另一表示：，解釋：半空間由加上與(外向法)向量的夾角成鈍角或直角的任意向量組成圖2.15由決定的半空間半空間的邊界為超平面開半空間(openhalfspace)為半空間的內(nèi)部

2.3.2歐幾里德球、賦范球和賦范錐歐幾里德球(Euclideanball)，簡稱球：其中，是中心，標(biāo)量為半徑。歐幾里德球的另一表達(dá)式歐幾里德球是凸集賦范球(normball)是凸集

2.3.3多面體多面體(polyhedron)多面體是有限個(gè)半空間和超平面的交集仿射集(如子空間、超平面、直線等)、射線、線段和半空間都是多面體。多面體是凸集圖2.13多面體

多面體的簡單表達(dá)其中，

2.4保持凸性的運(yùn)算2.4.1交2.4.2仿射函數(shù)

2.4.1交兩個(gè)凸集之交是凸集任意凸集之交是凸集子空間、仿射集和凸錐在任意個(gè)交下也是閉的。如：多面體是半空間和超平面(它們都是凸集)之交，因而是凸集。

2.4.2仿射函數(shù)函數(shù)是仿射的(affine)，其中集合是凸的，是仿射的是凸的。是仿射的是凸的。

例子縮放(scaling)和移動(dòng)(translation)集合是凸的，，集合和是凸的其中，

兩個(gè)集合的和和是凸的是凸的和是凸的笛卡爾乘積(Cartesianproduct)是凸的集合在函數(shù)下的像是

例2.20(多面體)多面體P可表示為和原點(diǎn)的笛卡爾乘積在仿射函數(shù)下的逆像

2.5分離超平面和支撐超平面2.5.1分離超平面定理2.5.2支撐超平面

2.5.1分離超平面定理分離超平面定理(separatinghyperplanetheorem)凸集，，，；，超平面稱為和的分離超平面(separatinghyperplane)。圖2.17分離超平面一種特殊情形時(shí)的證明設(shè)集合和的(歐幾里德)距離為正數(shù)，且達(dá)到最小距離： 定義：我們將證明仿射函數(shù)在在非正，而在上非負(fù)，即超平面分離和。這一超平面與和之間的線段垂直，并且經(jīng)過其中心，如圖2.18。圖2.18分離超平面的構(gòu)造先證明在上非負(fù)，關(guān)于在上非正的證明相似。假設(shè)存在點(diǎn)，滿足：(2.4)則可表示為：式(2.4)意味著。于是，，因此對(duì)一些很小的，我們有也即，點(diǎn)比更靠近。由于是凸集并且包含和，因此，。但這是不可能的，因?yàn)楸患僭O(shè)