[最佳化] 淺談線性規劃(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