跳到主要內容

[最佳化] 淺談線性規劃(3)- Geometric View of LP

延續前篇,由 Fundamental Theorem of LP,我們得知 Optimal Feasible Solution存在,則必存在Optimal Basic Feasible Solution。現在我們從幾何的觀點來看看這個件事情。

也就是說我們想知道 Optimal Basic Feasible Solution 在幾何中有甚麼意義?
在文中我們會介紹 Basic Feasible Solution 等價標準LP拘束集合的 極點 (Extreme Point, or Vertex)

進行幾何的觀點討論之前,我們需要一些先備概念 (凸性 Convexity)來幫助我們。

以下先給出凸集合 (Convex set)的定義:

=============================
Definition (Convex Set)
我們說一個集合 $\Theta \subset \mathbb{R}^n$ 為一個 Convex set 如果下列條件滿足:
對任意兩向量 $x, y \in \Theta$,且對任意實數 $\alpha \in (0, 1), \alpha \in \mathbb{R}^1$,其凸組合 (convex combination)
\[
\alpha x + (1- \alpha) y \in \Theta
\]=============================

如果用圖形表示的話:考慮 $x,y \in \mathbb{R}^2$,下圖說明甚麼是convex set 什麼不是convex set。


有了Convex set 的概念之後,我們回頭檢驗看看 標準型式LP問題的拘束條件:
現在定義拘束集合
\[
 \Theta := \{x: x\geq 0, Ax =b \}
\] 則第一個問題是,我們這樣的拘束集合有甚麼幾何性質? 他是不是一個 Convex set?

答案是肯定的,我們將其寫作如下 FACT:

=================================
FACT:
標準型式 LP問題的拘束條件所形成的集合
\[
 \Theta := \{x: x\geq 0, Ax =b \}
\] 為 Convex set。
=================================

Proof:
由Convex set的定義,我們給定 $x, y \in \Theta$,且給定任意實數 $\alpha \in (0, 1), \alpha \in \mathbb{R}^1$,

我們要證明線性組合
\[
\alpha x + (1- \alpha) y \in \Theta
\]也就是說任意滿足拘束條件的兩項量經過線性組合之後仍然滿足拘束條件 (落在 $\Theta$ 之中);亦即要證明

(1). $\alpha x + (1- \alpha) y \geq 0$ 且
(2).  $A (\alpha x + (1- \alpha) y) = b $

故我們首先觀察 (1):
因為 $x,y \in \Theta$ 故 $x, y \geq 0$ 又因為 $\alpha \in (0,1)$;故我們可知
\[\alpha x + (1 - \alpha )y \ge 0\]
接著觀察 (2):
因為 $x,y \in \Theta$ 故 $Ax =b, Ay =b$ 又因為 $\alpha \in (0,1)$;故我們可知
\[A\left( {\alpha x + (1 - \alpha )y} \right) = \alpha Ax + (1 - \alpha )Ay = \alpha b + (1 - \alpha )b = b\]
至此 (1)、(2) 都滿足,故我們說
\[
\alpha x + (1- \alpha) y \in \Theta
\]亦即標準型式LP的拘束條件所形成的集合 $\Theta$ 為一個Convex Set。 $\square$


Comments:
在更深入的最佳化理論 或者 凸分析理論中,上述集合被稱為 polyhedral。


在知道拘束條件所形成的集合為 Convex Set 之後,我們現在便可以引入 Exterme Point的概念:

==========================
Definition (Extreme Point)
令標準型式 LP問題的拘束條件所形成的集合
\[
 \Theta := \{x: x\geq 0, Ax =b \}
\] ,我們說一個向量 $x \in \Theta$ 為一個 Exterme Point of $\Theta$ 若下列條件成立:
不存在 任意兩向量 $x,y \in \Theta$, $x \neq y$ 使得對 $\alpha \in (0,1)$ 有 凸組合(convex combination)
\[
\alpha x + (1- \alpha) y \in \Theta
\]==========================

簡而言知,就是如果 $x^* \in \Theta$ 為極點(Exterme Point),則該點無法由其他集合中的任意兩點所構成:也就是說如果我們今天找到了集合中某兩向量 $x,y \in \Theta$ 與 $\alpha \in (0,1)$ 並用Convex combination 把 $x^*$ 寫下:
\[
x= \alpha x + (1- \alpha) y
\]則 $x$ 必須等於 $y$,亦即 $x=y$。

(上述的不存在條件,在證明的時候並不容易使用,我們多會將其用歸謬法推回,亦即說它存在,然後再得到某個矛盾。)


有了 Extreme point 的概念之後,我們現在便可以把 Basic Feasible Solution 與 Exterme Point概念作連結。下面的定理告訴我們此兩者等價。

==========================
Theorem: (Basic feasible solution is Extreme Point)
對標準形式LP問題,定義其拘束條件所形成的集合
\[
 \Theta := \{x: x\geq 0, Ax =b \}
\] 其中 $A \in \mathbb{R}^{m \times n}, m<n$。則 $x$ 為 $\Theta$ 中的 Extreme Point 若且唯若 (if and only if)
$x$ 為 Basic feasible solution of 標準型式LP問題。
==========================
Proof:
先證 $\Leftarrow$
假設 $x$ 為 Basic feasible solution,欲證明 $x$ 為 Extreme point。

我們用歸謬法 (Proof by contradiction)幫忙。
假設  $x$ 為 Basic feasible solution,但 $x$ 不為 Extreme point

則由不是 Extreme point 的定義,我們可以將 $x$ 用拘束集合 $\Theta$ 中任意不同兩點 $v^0, v^1$ 與一個常數 $\lambda \in (0,1)$ 以凸組合(convex combination)表示,亦即
\[
x = (1- \lambda) v^0 + \lambda v^1
\] 又因為 $v^0, v^1 \in \Theta$,故 $v^0, v^1$ 必滿足拘束條件,亦即 $v^0, v^1 \geq 0$ 且
\[
 A v^0 =b, A v^1 =b\\
\Rightarrow A (v^0 - v^1) =0
\]上述向量 $v^0 - v^1$ 的非零部分 必定對應到 $A$ 矩陣中 線性獨立的column  $[a^1, a^2, ... a^m]$ 為,故 $v^0 - v^1 =0 \Rightarrow v^0 = v^1$ 亦即此與一開始假設的不同兩點 相矛盾。故 $x$ 為 Extreme point。

---
現在我們接著證明 $\Rightarrow$

假設 $x$ 為 $\Theta$ 中的 Extreme Point,我們要證明 $x$ 為 Basic Feasible Solution:

注意到 $x \in \Theta$,故其必滿足拘束條件,故 $x$ 為 Feasible。故我們只須證明 $x$ 為Basic Solution。

再度使用歸謬法(Proof by contradiction)幫助我們
假設 $x$ 為 $\Theta$ 中的 Extreme Point,但 $x$ 不為 Basic Solution:

現在令 $x_1, x_2, ..., x_p$ 為 $x$ 非零的部分,由於其為Feasible solution,滿足拘束條件,我們可以寫下:
\[
Ax = b \Rightarrow a^1 x_1 + a^2 x_2 + ... + a^p x_p =b \ \ \ \ (*)
\] 由 非 Basic Solution 定義 ( $x$ 對應到 $A$ 矩陣線性相依的columns $a^1, a^2, ..., a^p$),故 存在一組非零的純量 $y_1, y_2, ... y_p$ 使得
\[
\displaystyle \sum_{i=1}^{p} y_i a^i = y_1 a^1 + y_2 a^2 + ... + y_p a^p =0
\]現在我們把上式乘上 $\varepsilon >0$
\[
\varepsilon y_1 a^1 + \varepsilon y_2 a^2 + ... + \varepsilon y_p a^p =0
\]
,且將其分別 加/減 到 $(*)$式,
\[\begin{array}{l}
\left( {{x_1} + \varepsilon {y_1}} \right){a^1} + \left( {{x_2} + \varepsilon {y_2}} \right){a^2} + ... + \left( {{x^p} + \varepsilon {y_p}} \right){a^p} = b\\
\left( {{x_1} - \varepsilon {y_1}} \right){a^1} + \left( {{x_2} - \varepsilon {y_2}} \right){a^2} + ... + \left( {{x_p} - \varepsilon {y_p}} \right){a^p} = b
\end{array}
\]我們可以選適當的 $\varepsilon $ (EX: 類似前幾篇文章所定義 $\varepsilon := \min \{ x_i/ y_i: i=1,..,p, y_i >0 \})$ 使得上式每一項都非負 $x_i + \varepsilon y_i \geq0, x_i - \varepsilon \geq 0$,則我們有下列向量:
\[\begin{array}{l}
{z_1}: = {\left[ {\begin{array}{*{20}{c}}
{{x_1} + \varepsilon {y_1}}&{{x_2} + \varepsilon {y_2}}&{...}&{{x_p} + \varepsilon {y_p}}&{0,...,0}
\end{array}} \right]^T}\\
{z_2}: = {\left[ {\begin{array}{*{20}{c}}
{{x_1} - \varepsilon {y_1}}&{{x_2} - \varepsilon {y_2}}&{...}&{{x_p} - \varepsilon {y_p}}&{0,...,0}
\end{array}} \right]^T}
\end{array}
\]上述兩向量都都落在 拘束集合中,且我們觀察 $x = \frac{1}{2} z_1 + \frac{1}{2} z_2$。又由於我們的假設可知 $x$ 為 Extreme point (無法被其他在拘束集合中的任意兩點用凸組合表示),故 $z_1 = z_2$;亦即 $y_i =0, \forall i$,此與我們之前提及的 非 Basic Solution 定義推得的線性相依
\[
\displaystyle \sum_{i=1}^{p} y_i a^i = y_1 a^1 + y_2 a^2 + ... + y_p a^p =0
\]矛盾。
亦即 $x$ 為 Basic Feasible Solution。 $\square$


ref: E. K. P. Chong, S. H. Zak, An Introduction to Optimization 2nd, Chapter 15.

==============
延伸閱讀

[最佳化] 淺談線性規劃(4)- How to move from one Basic Feasible solution to another- An Example

留言

這個網誌中的熱門文章

[數學分析] 什麼是若且唯若 "if and only if"

數學上的 if and only if  ( 此文不討論邏輯學中的 if and only if,只討論數學上的 if and only if。) 中文翻譯叫做  若且唯若 (or 當且僅當) , 記得當初剛接觸這個詞彙的時候,我是完全不明白到底是甚麼意思,查了翻譯也是愛莫能助,畢竟有翻跟沒翻一樣,都是有看沒有懂。 在數學上如果看到 if and only if  這類的句子,其實是表示一種 雙條件句 ,通常可以直接將其視為" 定義(Definition)" 待之,今天要分享的是這樣的一個句子如何用比較直觀的方法去看他 假設我們現在有 兩個邏輯陳述句 A 與  B. 注意到,在此我們不必考慮這兩個陳述句到底是什麼,想表達什麼,或者到底是否為真(true),這些都不重要。只要知道是兩個陳述即可。 現在,考慮新的陳述:  "A if and only if B" 好了,現在主角登場,我們可以怎麼看待這個句子呢? 事實上我們可以很直覺的把這句子拆成兩部分看待,也就是 "( A if B ) and ( A only if B )" 那麼先針對第一個部分  A if B  來看, 其實這句就是說  if B then A, 更直白一點就是 "if B is true, then A is also true".  在數學上等價可以寫為 "B implies A" .  或者更常用一個箭頭符號來表示 "B $\Rightarrow$  A"  現在針對第二個部分  A only if B 此句意指  "If B is not true, then A is also not true". 所以如果已知 A is true,  那麼按照上句不難推得 B is also true 也就是說  A only if B  等價為 "If A is true then B is also true". 同樣,也可以寫作   "A implies B"   或者用箭頭表示  "A   $\Rightarrow$     B".

[數學分析] 淺談各種基本範數 (Norm)

這次要介紹的是數學上一個重要的概念: Norm: 一般翻譯成 範數 (在英語中 norm 有規範的意思,比如我們說normalization就是把某種東西/物品/事件 做 正規化,也就是加上規範使其正常化),不過個人認為其實翻譯成 範數 也是看不懂的...這邊建議把 Norm 想成長度就好 (事實上norm是長度的抽象推廣), 也許讀者會認為好端端的長度不用,為何又要發明一個 norm 來自討苦吃?? 既抽象又艱澀。 事實上想法是這樣的: 比如說現在想要比較兩個數字 $3$ , $5$ 之間的大小,則我們可以馬上知道 $ 3 < 5 $;同樣的,如果再考慮小數與無理數如 $1.8753$ 與 $\pi$,我們仍然可以比較大小 $1.8753 < \pi = 3.1415...$ 故可以發現我們有辦法對 "純量" 做明確的比大小,WHY? 因為前述例子中 $3$, $5$, $1.8753$ or $\pi$ 其各自的大小有辦法被 "measure "! 但是如果是現在考慮的是一組數字 我們如何去measure 其大小呢?? 比如說 \[x:=[1, -2, 0.1, 0 ]^T \]上式的大小該是多少? 是 $1$? $-2$? $0.1$??? 再者如果更過分一點,我們考慮一個矩陣 \[A = \left[ {\begin{array}{*{20}{c}} 1&2\\ 3&4 \end{array}} \right] \],想要知道這個矩陣的大小又該怎麼辦?? 是 $1$ ? $2$ 還是 $4$ ?..其實現階段我們說不清楚。 也正是如此,可以發現我們確實需要新的 "長度" 的定義來幫助我們如何去 measure 矩陣/向量/甚至是函數的大小。 故此,我們首先定義甚麼是Norm,(也就是把 "長度" or "大小" 的本質抽離出來) ================== Definition: Norm 考慮 $V$ 為一個向量空間(Vector space),則我們說  Norm 為一個函數 $||\cdot|| : V \rightarrow \mathbb{R}$ 且滿足下列性質