本文的閱讀等級:初級
幾何座標空間 的一個向量 表示該向量端點的座標。點與座標向量具有一對一的對應關係,因為這個緣故,我們經常以座標向量代表點。本文介紹一種別於子空間與仿射空間 (子空間的平移) 的向量集。我們稱一個向量集 是凸集 (convex set),若給定任兩點 和 ,點 屬於 。淺白地說,在凸集中,任兩個點皆可「看見」彼此,連接這兩點的直線段不含集合以外的點。見圖一的例子。比較特別的是, 所包含的子空間與仿射空間都是凸集。
下面是凸集的基本定理,它說明純量乘法、向量加法和交集運算保留凸性 (convexity)。
定理一:對於 裏的凸集,下列性質成立:
- 若 是一個凸集且 是實數,則 是一個凸集。
- 若 和 是凸集,則 是一個凸集。
- 若 與 是凸集,則 是一個凸集。
使用定義即可證明。這裡僅提供 (3) 的證明,(1) 和 (2) 留給讀者自行完成。設 且 ,可知 屬於 與 。因為 和 是凸集, 同時屬於 與 ,也就有 ,證明 是一個凸集。圖二顯示這三個凸集性質。
考慮幾何座標空間 中 個點 。我們定義 的凸組合 (convex combination) 為
,
其中 且每一 。凸組合是在線性組合的基礎下,加入係數和等於 ,並限定係數不為負值。以 的兩個線性獨立向量 和 為例,所有的線性組合 構成一個穿越原點且包含 和 的平面。如果限制 ,則稱為仿射組合;所有的仿射組合構成穿越 和 的直線 (見“仿射組合與仿射空間”)。再加入 和 ,即為凸組合;所有的凸組合構成連接 和 的直線段。對於一個向量集 ,凸包 (convex hull) 是指 所含向量的所有凸組合形成的集合,記作 。明顯地,單一點 的凸包為向量本身。圖三顯示 平面上兩點、三點和四點產生的凸包。
凸包 是一個凸集嗎?是的。凸包 由向量集 構成,可知 。定理二說明:若 ,則 是一個凸集。因為 的凸包為其自身,故可推論 是一個凸集。
定理二:若 中任何點的凸組合都屬於 ,即 ,則 是一個凸集;相反陳述亦成立。
我們用數學歸納法來證明。令 表示從 選取的點數。當 ,顯然該點是一個凸集。當 ,兩點連成的直線段為一個凸集。假設當 時,命題成立。考慮 ,其中 且所有 。分開兩個情況討論。若 ,則 屬於 ,這時 ,命題成立。若 ,令 。因此 ,就有
。
因為 且每一 ,由歸納假設可知 屬於 ,且 是 和 的凸組合,這時 ,命題成立。
給定一個向量集 ,凸包 有甚麼直觀意義呢?從幾何面來看,凸包 是包含 的「最小」凸集 (見定理三)。圖四描繪平面上的向量集 與對應的凸包 。
定理三:對於任意向量集 ,凸包 等於包含 的所有凸集的交集。
令 表示包含 的所有凸集的交集。定理一 (3) 指出 是一個凸集。因為 是一個凸集且 ,可知 。另一方面, 包含 推得 。因為 是一個凸集,定理二說明 ,故 。合併以上結果即證明 。
若 屬於凸包 ,那麼 可以寫成 中某些點的凸組合。但需要多少個點才足夠呢?定理四告訴我們:如果 ,最多只要 個點便可寫出凸包 中任一點的凸組合表達式。以 平面為例,對於任一 ,只要找到向量集 中三個點使得 位於此三點構成的三角形內即可;或找到兩個點使得 位於這兩點連成的直線段上;甚至,如果 ,則該點即為自身的凸組合。
定理四:若 是一個非空向量集,則任一屬於 的向量必可表示成 中 個點的凸組合,。
給定 ,我們要證明下列表達式存在[1]:,其中 ,,,,且 。若 ,則 必是仿射相依 (見“仿射獨立”,定理三),也就是說,存在不全為零的數組 使得
且 。考慮
。
因為第一式乘以 不造成影響且 不全為零,故存在 使得 。置換指標 和 ,如此可使 且當 時,。將第二式減去第一式通乘 的結果,消去 項,如下:
令 ,,且 。使用 和 的性質,
,
而且每一 。理由如下:若 ,則 。若 ,則 。所以,
是 的一個凸組合。重複此程序至到 停止,因為這時仿射相依未必成立。
參考來源:
[1] 證明修改自 David C. Lay, Linear Algebra and its Applications, 4th ed., 2012, pp 457-458.
終于能上老師的博客了。最近會大陸,想不到一會去就上不了老師這個網站了。好不容易花錢買了個vpn終于正常上網了。
兩年前我老婆去人大講學半載。臨行前,我說:在大陸妳就沒法上我的網站了。她笑回:在台灣我也不會上去。
哈哈,只要脖子长,不怕墙~
写得非常好,拜读了!
博客非常不错,是个复习线代的好地方:)
老师您好!您这篇文章写得真是太好啦!文笔好可爱~