多胞形

本文的閱讀等級:中級

在最佳化領域,多胞形 (polytope) 是一種應用廣泛的特殊凸集[1]。多胞形可以存在於任何有限維的幾何座標空間,多邊形是二維多胞形,多面體是三維多胞形,\mathbb{R}^n 的多胞形稱為 n 多胞形。淺白地說,多胞形的邊界都是平的。本文討論的多胞形限定為有界閉集,定義如下:若 S=\{\mathbf{x}_1,\ldots,\mathbf{x}_k\} 是屬於 \mathbb{R}^n 的有限向量集,凸包 \hbox{conv}(S) 稱為一多胞形。因為凸包是凸集,凸包定義的多胞形自然是一有界閉凸集 (見“凸組合、凸包與凸集”)。本文將介紹多胞形的幾何性質,並推導有界閉凸集的一個重要定理,它指引了一條解決線性規劃問題的捷徑。

 
我們先引介多胞形的一些特殊子集合,它們建立在多胞形與超平面的關係上 (見“超平面”)。令 K\subset\mathbb{R}^n 為一有界閉凸集。設 HK 的一個支持超平面,意思是說,H 穿越 K 的一個邊界點且 K 被半空間 H^+H^- 所包含。非空集合 F=K\cap H 稱為 K 的一個面 (face)。若 F 的「維度」等於 k,則 F 叫做 k-面。這個說法僅是為了方便界定,因為 F 並不是一個完整的子空間或仿設空間。對於 \mathbb{R}^n 的多胞形,0-面稱為頂點 (vertex),1-面稱為邊 (edge),(n-1)-面稱為小面 (facet)。下圖顯示 \mathbb{R}^3 的四面體 PH_1\cap P 是二維的面 (小面),H_2\cap P 是一維的邊,H_3\cap P 是零維的頂點。

face

小面、邊與頂點

 
想像我們在多胞形 P 之外移動一超平面 H=\{\mathbf{z}\in\mathbb{R}^n\vert\mathbf{a}^T\mathbf{z}=d\},實際的操作方式是固定法向量 \mathbf{a},改變 d。當 H 首次觸及 P 的邊界時,絕大多數的情況下,F=P\cap H 為一頂點。因為這個緣故,多胞形的應用幾乎都與頂點有關。此外,頂點還具備一種特徵性質。對於凸集 K\subset\mathbb{R}^n,我們稱 \mathbf{v}\in K 是一端點 (extreme point),若不存在兩相異點 \mathbf{x}\mathbf{y} 屬於 K 使得 \mathbf{v}=\alpha\mathbf{x}+(1-\alpha)\mathbf{y},其中 0<\alpha<1。換句話說,不位於凸集中任何線段內的點即是端點。例如,在二維平面上,三角形的三個頂點為其端點,圓形的所有邊界點為其端點,但直線與半平面不存在端點。任一多胞形的頂點都是端點嗎?是的。下圖左顯示一個二維多胞形 (即所有點的凸包)。因為任一內點或邊界點必可表示為多胞形頂點的凸組合,下圖右顯示刪除內點與邊界點 (但不包括頂點) 之後的相同多胞形。根據這項觀察,若 P=\hbox{conv}(M),其中 M=\{\mathbf{v}_1,\ldots,\mathbf{v}_k\},且對於每一 i=1,\ldots,k\mathbf{v}_i 不屬於 \hbox{conv}(M-\{\mathbf{v}_i\}),我們稱向量集 M 是多胞形 P 的最小表達 (minimal representation)。定理一說明多胞形的頂點、端點與最小表達的等價性。

minimal representation

兩個相同的多胞形與最小表達

 
定理一:令 M=\{\mathbf{v}_1,\ldots,\mathbf{v}_k\} 是多胞形 P 的最小表達。下列陳述是等價的:
(a) \mathbf{v}P 的一頂點。
(b) \mathbf{v}P 的一端點。
(c) \mathbf{v} 屬於 M

(a)\Rightarrow(b):設 \mathbf{v} 是多胞形 P 的一頂點。由頂點的定義可知存在一支持超平面 H=\{\mathbf{z}\in\mathbb{R}^n\vert\mathbf{a}^T\mathbf{z}=d\} 使得 P\cap H=\{\mathbf{v}\}P\subset H^+=\{\mathbf{z}\in\mathbb{R}^n\vert\mathbf{a}^T\mathbf{z}\ge d\} (此式總是成立,因為 \mathbf{a}^T\mathbf{z}=d 乘以 -1 不改變超平面,但置換 H^+H^-)。使用反證法。假設 \mathbf{v} 不是 P 的端點,則 P 中存在 \mathbf{x}\mathbf{y} 使得 \mathbf{v}=\alpha\mathbf{x}+(1-\alpha)\mathbf{y}0<\alpha<1。將上式改寫成

\displaystyle  \mathbf{x}=\frac{1}{\alpha}\mathbf{v}-\left(\frac{1}{\alpha}-1\right)\mathbf{y}

就有 \mathbf{a}^T\mathbf{x}=(1/\alpha)\mathbf{a}^T\mathbf{v}-(1/\alpha-1)\mathbf{a}^T\mathbf{y}。然而,\mathbf{a}^T\mathbf{v}=d\mathbf{a}^T\mathbf{y}\ge d,所以

\displaystyle  \mathbf{a}^T\mathbf{x}\le\frac{d}{\alpha}-\left(\frac{1}{\alpha}-1\right)d=d

另一方面,\mathbf{x}\in P 推知 \mathbf{a}^T\mathbf{x}\ge d。合併以上結果,\mathbf{a}^T\mathbf{x}=d,可知 \mathbf{x}\in P\cap H。但這與 P\cap H=\{\mathbf{v}\} 矛盾,即證得所求。

(b)\Rightarrow(c):因為 P 的任一端點不位於多胞形中任何線段內的點,故必為最小表達 M 的一員。

(c)\Rightarrow(a):設 \mathbf{v}\in M,並令 Q=\hbox{conv}(M-\{\mathbf{v}\})。最小表達的定義說明 \mathbf{v}\notin Q。因為 Q 是一有界閉凸集,我們可以找到一分離超平面 H 穿越 \mathbf{v} 使得 Q 被半空間 \tilde{H}^+ 所包含 (見“超平面”,定理一),如下圖所示。明顯地,P\subset H^+,得知 HP 於點 \mathbf{v} 的一支持超平面。因為 \mathbf{v}P 中唯一一個與 H 相交的點,P\cap H=\{\mathbf{v}\},證明 \mathbf{v}P 的一頂點。

Extreme point

多胞形、頂點與半空間

 
定理一表明多胞形可由其端點的凸包建構而成。那麼一般的有界凸集是否也等於其端點的凸包?這個猜測確實為真。正式證明之前,我們需要下列引理。

引理一:令 K\subset\mathbb{R}^n 為一有界閉凸集,HK 的一支持超平面,且 F=K\cap H。面 F 的每一端點是 K 的一個端點。

假設 \mathbf{v}\in F 不是 K 的一端點,我們要證明 \mathbf{v} 也不是 F 的端點。據此,\mathbf{v}=\alpha\mathbf{x}+(1-\alpha)\mathbf{y},其中 \mathbf{x}\mathbf{y} 是屬於 K 的兩相異點,0<\alpha<1。令 H=\{\mathbf{z}\in\mathbb{R}^n\vert\mathbf{a}^T\mathbf{z}=d\} 使得 K\subset H^+。因此,\mathbf{a}^T\mathbf{x}\ge d\mathbf{a}^T\mathbf{y}\ge d。但 \mathbf{v}\in H,可得

d=\mathbf{a}^T\mathbf{v}=\alpha\mathbf{a}^T\mathbf{x}+(1-\alpha)\mathbf{a}^T\mathbf{y}

合併以上結果,推知 \mathbf{a}^T\mathbf{x}=d\mathbf{a}^T\mathbf{y}=d。這意味 \mathbf{x},\mathbf{y}\in H,即 \mathbf{x},\mathbf{y}\in F,因此證明 \mathbf{v} 不是 F 的端點。

 
定理二:任一有界閉凸集 K\subset\mathbb{R}^n 等於 K 的所有端點的凸包。

針對 \mathbb{R}^n,我們採用數學歸納法來證明。若 n=1,命題顯然成立。假設命題於 n-1 時成立。令 K\subset \mathbb{R}^n 為一有界閉凸集,且 P 是由 K 的端點構成的凸包。我們的目標是證明 K=P。使用反證法,假設 \mathbf{p}\in K\mathbf{p}\notin P。利用分離超平面定理,存在一超平面 H 穿越 \mathbf{p} 且半空間 \tilde{H}^+ 包含 P,也就是說,存在非零向量 \mathbf{a},使得 \mathbf{a}^T\mathbf{p}<\inf_{\mathbf{x}\in P}\mathbf{a}^T\mathbf{x}。令 d_0=\inf_{\mathbf{x}\in K}\mathbf{a}^T\mathbf{x}。根據極值定理,連續函數 \mathbf{a}^T\mathbf{x} 在任意有界閉集必有極小值,故存在 \mathbf{x}_0\in K 滿足 \mathbf{a}^T\mathbf{x}_0=d_0。因此,H=\{\mathbf{x}\in\mathbb{R}^n\vert\mathbf{a}^T\mathbf{x}=d_0\}K 的一支持超平面 (穿越 \mathbf{x}_0),且 HP 不交集,因為 d_0\le \mathbf{a}^T\mathbf{p}<\inf_{\mathbf{x}\in P}\mathbf{a}^T\mathbf{x}。接下來的工作是演繹出與假設 P 是由 K 的端點構成的凸包相矛盾的結論。令 F=K\cap H。因為 \mathbf{x}_0\in F,可知 F\subset H 是一非空子集合。超平面 H 的維數等於 (n-1),由歸納假設可知有界閉凸集 F 包含端點,引理一表明這些端點都是 K 的端點。換言之,我們找到 K 的端點,但不屬於 P (因為 HP 不交集),這與假設矛盾,故得證。

 
定理三是定理二的一個重要應用,我們可稱之為線性規劃的一塊磐石 (見“線性規劃 (一):標準型問題”)。

定理三:令 K\subset \mathbb{R}^n 為一非空有界閉凸集。若 f 是一定義於 K 的線性泛函,則存在 K 的一端點 \mathbf{v} 使得

\displaystyle  f(\mathbf{v})=\min_{\mathbf{x}\in K}f(\mathbf{x})

線性泛函是值域為實數的線性函數,表示為 f(\mathbf{x})=\mathbf{c}^T\mathbf{x},詳見“線性泛函與對偶空間”。證明於下。假設 f\mathbf{x}'\in K 有極小值 m=f(\mathbf{x}')。根據定理二,\mathbf{x}' 可表示為 K 的端點的凸組合,也就是說,存在端點 \mathbf{v}_1,\ldots,\mathbf{v}_k 與非負純量 d_1,\ldots,d_k 使得

\mathbf{x}'=d_1\mathbf{v}_1+\cdots+d_k\mathbf{v}_k

d_1+\cdots+d_k=1。假如 f(\mathbf{v}_i)>mi=1,\ldots,k,則

\begin{aligned}  m&=f(\mathbf{x}')=f(d_1\mathbf{v}_1+\cdots+d_k\mathbf{v}_k)=d_1f(\mathbf{v}_1)+\cdots+d_kf(\mathbf{v}_k)\\  &>d_1m+\cdots+d_km=(d_1+\cdots+d_k)m=m.  \end{aligned}

矛盾發生,故證明存在至少一端點 \mathbf{v}_j 使得 f(\mathbf{v}_j)=m

 
在實際應用場合,多胞形經常由多個閉半空間的交集所描述,如下:

\displaystyle  P=\bigcap_{j=1,\ldots,k}H_j^-

其中 H_j^-=\{\mathbf{x}\in\mathbb{R}^n\vert\mathbf{a}_j^T\mathbf{x}\le d_j\}。因為閉半空間是凸集,凸集的交集仍為凸集,可知若閉半空間交集為有界閉集,則該集合是一多胞形。見下圖,考慮 \mathbf{v}_1=\begin{bmatrix}  2\\  0  \end{bmatrix}\mathbf{v}_2=\begin{bmatrix}  3\\  2  \end{bmatrix}\mathbf{v}_3=\begin{bmatrix}  0\\  1  \end{bmatrix}。多胞形 (三角形) P 等於其端點 \mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3 的凸包,即 P=\hbox{conv}(\{\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3\})。因為兩點連成一直線,P 被三個半平面所包含。直線 2x_1-x_2=4 穿越 \mathbf{v}_1\mathbf{v}_2,故 P 位於半平面 2x_1-x_2\le 4。直線 -x_1+3x_2=3 穿越 \mathbf{v}_2\mathbf{v}_3,故 P 位於半平面 -x_1+3x_2\le 3。直線 x_1+2x_2=2 穿越 \mathbf{v}_1\mathbf{v}_3,故 P 位於半平面 x_1+2x_2\ge 2,即 -x_1-2x_2\le -2。所以,三角形 P 是下列線性不等式的解集合:

\begin{aligned}  2x_1-x_2&\le 4\\  -x_1+3x_2&\le 3\\  -x_1-2x_2&\le -2  \end{aligned}

考慮定義於 P 的任意線性泛函,譬如,f(\mathbf{x})=x_1-2x_2。根據定理三,三角形 P 的一個端點 (頂點) \mathbf{v} 使得 f(\mathbf{v})=\min_{\mathbf{x}\in P}f(\mathbf{x})。代入數值計算,f(\mathbf{v}_1)=2f(\mathbf{v}_2)=-1f(\mathbf{v}_3)=-2。所以,當 \mathbf{x}=\mathbf{v}_3=(0,1)^Tf 有最小值 -2

Intersection of half spaces

半平面交集構成的多胞形

 
註解:
[1] 多胞形沒有統一的定義,本文所稱的多胞形隱含凸性,即凸多胞形 (convex polytope)。

Advertisements
本篇發表於 線性代數專欄, 仿射幾何 並標籤為 , , , 。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s