2011年4月28日 星期四

[衍生商品] 希臘值與動態避險 (0) - Delta and Delta Neutral

這次要介紹的是財務中的 希臘值 Greek Letters:
\[ \Delta, \Gamma, \Theta, \rho, \nu
\],上述的這些希臘字母被用作財務中衍生商品的 避險 (Hedging) 的指標。

那麼問題是這些希臘字母到底如何跟避險扯上關係呢? 這必須要回歸 Black-Scholes Formula:
\[\left\{ \begin{array}{l}
C = S{e^{ - qT}}N \left( {{d_1}} \right) - K{e^{ - rT}}N \left( {{d_2}} \right)\\
P = K{e^{ - r(T)}}N \left( { - {d_2}} \right) - S{e^{ - qT}}N \left( { - {d_1}} \right)
\end{array} \right.\]
其中 $C$ 為 Call option 價格,$P$ 為 Put Option 價格, $N(\cdot)$ 為 Standard Normal Cumulative distribution function (CDF),且\[\left\{ \begin{array}{l}
{d_1} = \frac{{\ln (S/K) + (r - q + \frac{1}{2}{\sigma ^2})(T)}}{{\sigma \sqrt T }}\\
{d_2} = {d_1} - \sigma \sqrt T
\end{array} \right.\]

觀察上述 Black-Scholes Formula,我們知道 選擇權價格 $C, P$ 可表為一個多變數的函數
\[
f(S,K,T,r,q,\sigma)
\]其中 $S$ 為現時股價,$K$ 為執行價格, $T$ 為到期時間, $r$ 為連續複利的無風險年利率, $q$ 為連續複利的年股息,$\sigma$ 為 波動度。


想法:對於 B-S formula 所求得的 $f(S,K,T,r,q,\sigma)$ 對特定參數的變動,我們用一個特定希臘字母來表示他,這些變動用來測量不同的風險:

這邊先介紹 $\Delta$
\[
\Delta := \frac{\partial f}{ \partial S}
\]亦即表示為選擇權價格對股價的變化率。(由於其為一階導數,故為斜率)

回憶先前介紹過,
對於 Long Call Position: $0 \leq \Delta \leq 1$ (Short call 則對左式同取負號)
對於 Long Put Position : $-1 \leq \Delta \leq 0$ (Short put 則對左式同取負號)

上述結果可繪製如下圖:




Comment: 
1. 如果 $\Delta =0$,則表示股票些微變化 不影響 選擇權價格。且此狀態稱為 Delta Neutral
2. $\Delta$ 在 Black-Scholes Call opton formula 中等價為 $e^{-qT}N(d_1)$;亦即
\[
\Delta := \frac{{\partial f}}{{\partial S}} = e^{-qT}N\left( {{d_1}} \right)
\] 其中 $N(\cdot)$ 為 Cumulative normal distribution。
3. 關於 Put Option 與 Call Option 的 $\Delta$ 值之間存在一固定關係,我們將此關係寫成下面的 Claim :

Claim:
對於 Call option 與 Put Option 的 $\Delta$ 有如下關係:
\[
\Delta_c - \Delta_p = e^{-qT}
\]Proof
上述關係可以很簡潔的利用 Put-Call Parity 來證明,現在回憶 Put-Call Parity 如下:
\[
C-P = Se^{-qT} - Ke^{-rT}
\]對上式兩邊取對 $S$ 偏導數 $\frac{{\partial }}{{\partial {\rm{S}}}}$:
\[\begin{array}{l}
C - P = S{e^{ - qT}} - K{e^{ - rT}}\\
 \Rightarrow \underbrace {\frac{{\partial C}}{{\partial S}}}_{{\Delta _c}} - \underbrace {\frac{{\partial P}}{{\partial S}}}_{{\Delta _p}} = {e^{ - qT}}\\
 \Rightarrow {\Delta _c} - {\Delta _p} = {e^{ - qT}}
\end{array}\] $\square$


投資組合 的 Delta 與 Superposition (Delta of Portfolio)
現在考慮 $\Pi $ 為投資組合的價值,則對單一資產 (價格為 $S$) 的 選擇權或其他衍生商品所組成的投資組合之 $\Delta$ 定義為
\[
\frac{\partial \Pi}{\partial S}
\] 投資組合的 $\Delta$ 值可由投資組合中,可先分別計算各自單一的 Options 的 $\Delta$ 值在做線性組合:亦即若考慮投資組合由數量為 $w_i$ 的選擇權所組合而成 $(1 \leq i \leq n)$ 且對應地 $i$ 個 Option 的 $\Delta$ 值為 $\Delta_i$,則此投資組合的總 $\Delta$ 值為
\[
\Delta = \displaystyle \sum_{i=1}^{n} w_i \Delta_i \ \ \ \ (*)
\]

現在我們看個例子:

Example
考慮某金融機構持有下列三種某標的資產股票:
  1. Long 100,000 call options ,執行價格為 $K=55$,到期時間 $T=3$ 個月,$\Delta=0.533$
  2. Short 200,000 Call options﹑,執行價格為 $K=56$,到期時間 $T=5$ 個月,$\Delta=0.468$
  3. Short 50,000 Call options﹑,執行價格為 $K=56$,到期時間 $T=2$ 個月,$\Delta=-0.508$

則此金融機構的總 $\Delta$ 可由 $(*)$ 計算而得
\[
\Delta = 100,000 \times 0.533 - 200,000 \times 0.468 - 50,000 \times (-0.508) = -14,900
\]亦即,如果要達到使此投資組合為 Delta Neutral,則必須 購入 $14,900$ 股 股票。

ref: John C. Hull, Options, Futures and Other Derivatives 7th.

2011年4月22日 星期五

[線性規劃] Minimax Problem in LP format

考慮如下 minimax (non-cooperative game)問題:

\[\begin{array}{l}
\mathop {\min }\limits_x \mathop {\max }\limits_{i = 1,...,N} c_i^Tx\\
s.t.\\
Ax \le b
\end{array}
\]注意到上式 $\displaystyle \mathop {\max }\limits_{i = 1,...,N} c_i^Tx$ 為 凸函數 (Convex function) WHY?。故可求解最佳解(min)時 其Local minimum = global minimum。

現在問題是上述的 minimax 問題該如何將其改寫成LP問題呢?

方法如下:

首先引入一個新的變數 $z$ 並考慮如下 新的 LP問題:
\[\begin{array}{l}
\mathop {\min }\limits_{x,z} z\\
s.t.\\
\left\{ \begin{array}{l}
Ax \le b\\
c_i^Tx \le z,\begin{array}{*{20}{c}}
{}
\end{array}\forall i = 1,...,N
\end{array} \right.
\end{array}
\] 則現在此LP問題求解 等價 求解原本的minimax問題。亦即兩者間最佳解相同。

Proof:omitted


那麼如果現在問題變成 min min problem (cooperative game)
\[\begin{array}{l}
\mathop {\min }\limits_x \mathop {\min }\limits_{i = 1,...,N} c_i^Tx\\
s.t.\\
Ax \le b
\end{array}
\]該如何處理呢?

注意到上述的引入新變數 $z$ 的方法在此會失敗。因為此時 $\displaystyle \mathop {\min }\limits_x \mathop {\min }\limits_{i = 1,...,N} c_i^Tx$ 不再是 凸函數 (convex function),(亦即convexity 無法保證)。求解最佳解(min)的會有問題 (如果其為 凹函數 (concave function),則最佳解(minimum)不一定存在!)。

一般而言處理mini min problem的問題是將原本問題改寫成求解 $N$ 組 LP問題:
\[\begin{array}{*{20}{l}}
{\mathop {\min }\limits_{i = 1,...,N} \mathop {\min }\limits_x c_i^Tx}\\
{s.t.}\\
{Ax \le b}
\end{array}
\]亦即左右minimum 對調。(Proof: omitted)

2011年4月20日 星期三

[講義] PID / PI-D / I-PD 控制的差別

此講義主要介紹PID控制器的修正型態 (standard PID, I-PD, PI-D),
內容涵蓋所需的基礎PID控制介紹與參數設定法,接著透過一個簡單的模擬例子,來說明三種控制架構的的差異。

講義如附檔
Modifications of PID control schemes
Edited by 謝宗翰, 2011

ref: Katsuhiko Ogata, Modern Control Engineering, Fourth Edition, Prentice Hall, 2002. Chapter 10

2011年4月13日 星期三

[最佳化] 淺談線性規劃(5)- The LP Tableau

延續前篇,我們現在知道如何從一個 Basic Feasible Solution 移動到 另一個 Basic Feasible Solution ,但問題是我們該如何得知應該選哪一個 Basic Feasible Solution 作為我們下一部移動的目標呢?? 亦即 我們該選誰使得我們可以逐步降低Cost Value。

這次介紹一個極為精簡的方法,就是透過matrix row operation 建立 LP Tableau,方法如下:

現在考慮標準型式LP問題:

令 $x \in \mathbb{R}^n$,
\[\begin{array}{l}
\min {c^T}x\\
s.t.\\
\left\{ \begin{array}{l}
Ax = b,\\
x \ge 0
\end{array} \right.
\end{array}\]其中 $A = [a_1, a_2, ..., a_m] \in \mathbb{R}^{m \times n}$ 矩陣且 $n>m$, $rank(A) = m$,$A$ 沒有全為零的column$;b \geq 0$,

接著透過Row operation,把拘束 $Ax =b$ 改寫成如下:
\[\left\{ \begin{array}{l}
{x_1}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array} + {y_{1,m + 1}}{x_{m + 1}} + {y_{1,m + 2}}{x_{m + 2}} +  \cdots  + {y_{1,n}}{x_n} = {y_{1,0}}\\
\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}{x_2}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array} + {y_{2,m + 1}}{x_{m + 1}} + {y_{2,m + 2}}{x_{m + 2}} +  \cdots  + {y_{2,n}}{x_n} = {y_{2,0}}\\
\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array} \ddots \\
\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}{x_m} + {y_{m,m + 1}}{x_{m + 1}} + {y_{m,m + 2}}{x_{m + 2}} +  \cdots  + {y_{m,n}}{x_n} = {y_{m,0}}
\end{array} \right.
\]透過上式,我們我們可建立如下 LP Tableau:
\[\left[ {\begin{array}{*{20}{c}}
1&0& \cdots &0&{{y_{1,m + 1}}}&{{y_{1,m + 2}}}& \cdots &{{y_{1,n}}}&{{y_{1,0}}}\\
0&1& \cdots &0&{{y_{2,m + 1}}}&{{y_{2,m + 2}}}& \cdots &{{y_{2,n}}}&{{y_{2,0}}}\\
 \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0&0& \cdots &1&{{y_{m,m + 2}}}&{{y_{m,m + 2}}}& \cdots &{{y_{m,n}}}&{{y_{m,0}}}
\end{array}} \right]\]觀察上式,我們可以發現有 一組 Feasible Basic Solution:
\[\begin{array}{*{20}{l}}
{{x_1} = {y_{1,0}}}\\
{{x_2} = {y_{2,0}}}\\
 \vdots \\
\begin{array}{l}
{x_m} = {y_{m,0}}\\
{x_{m + 1}} = 0\\
 \vdots \\
{x_n} = 0
\end{array}
\end{array}\]
那麼由之前文章可知,我們可以從這組 Feasible Basic Soluiton開始,逐步移動到下一個Basic Feasible Solution,但現在問題變成我們應該移動到哪一個才可以在移動過程中使 Cost 也逐步降低呢?

現在觀察我們的Cost function:
\[
\begin{array}{l}
J = {c^T}x = {c_1}{x_1} + {c_2}{x_2} + ...+{c_m}{x_m} + {c_{m + 1}}x_{m+1} + ... + {c_n}x_n \ \ \ \ (*)
\end{array}
\]將 $J$ 用 $x_{m+1}, x_{m+2}, ..., x_{n}$ 表示:亦即
由LP Tableau,可知
\[\begin{array}{l}
\left\{ \begin{array}{l}
{x_1} + {y_{1,m + 1}}{x_{m + 1}} + {y_{1,m + 2}}{x_{m + 2}} +  \cdots  + {y_{1,n}}{x_n} = {y_{1,0}}\\
{x_2} + {y_{2,m + 1}}{x_{m + 1}} + {y_{2,m + 2}}{x_{m + 2}} +  \cdots  + {y_{2,n}}{x_n} = {y_{2,0}}\\
 \vdots \\
{x_m} + {y_{m,m + 1}}{x_{m + 1}} + {y_{m,m + 2}}{x_{m + 2}} +  \cdots  + {y_{m,n}}{x_n} = {y_{m,0}}
\end{array} \right.\\
 \Rightarrow \left\{ \begin{array}{l}
{x_1} = {y_{1,0}} - \left( {{y_{1,m + 1}}{x_{m + 1}} + {y_{1,m + 2}}{x_{m + 2}} +  \cdots  + {y_{1,n}}{x_n}} \right)\\
{x_2} = {y_{2,0}} - \left( {{y_{2,m + 1}}{x_{m + 1}} + {y_{2,m + 2}}{x_{m + 2}} +  \cdots  + {y_{2,n}}{x_n}} \right)\\
 \vdots \\
{x_m} = {y_{m,0}} - \left( {{y_{m,m + 1}}{x_{m + 1}} + {y_{m,m + 2}}{x_{m + 2}} +  \cdots  + {y_{m,n}}{x_n}} \right)
\end{array} \right.
\end{array}
\]將上式代入 Cost function $(*)$可得
\[
\begin{array}{l}
 \Rightarrow J = \underbrace {\left( {{c_1}{y_{1,0}} + {c_2}{y_{2,0}} +  \cdots  + {c_m}{y_{m,0}}} \right)}_{: = {J_0}}\\
\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array} + \left[ {{c_{m + 1}} - \sum\limits_{i = 1}^m {{c_i}{y_{i,m + 1}}} } \right]{x_{m + 1}} +  \cdots  + \left[ {{c_n} - \sum\limits_{i = 1}^m {{c_i}{y_{i,n}}} } \right]{x_n}
\end{array}
\]將上式進一步整理
\[\begin{array}{l}
 \Rightarrow J = \underbrace {\left( {{c_1}{y_{1,0}} + {c_2}{y_{2,0}} +  \cdots  + {c_m}{y_{m,0}}} \right)}_{: = {J_0}}\\
\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array} + \underbrace {\left[ {{c_{m + 1}} - \sum\limits_{i = 1}^m {{c_i}{y_{i,m + 1}}} } \right]}_{: = {r_{m + 1}}}{x_{m + 1}} +  \cdots  + \underbrace {\left[ {{c_n} - \sum\limits_{i = 1}^m {{c_i}{y_{i,n}}} } \right]}_{: = {r_n}}{x_n}\\
 \Rightarrow J = {J_0} + {r_{m + 1}}{x_{m + 1}} + {r_{m + 2}}{x_{m + 2}} +  \cdots  + {r_n}{x_n}\\
 \Rightarrow J = {J_0} + \sum\limits_{j = m + 1}^n {{r_j}{x_j}}
\end{array}
\]
Comment:
1. 上式的 $r_j$ 稱作 Relative cost coefficient;$ J_0$ 為 current cost value
2. 如果 $r_j <0$ 則我們可以讓 $J$ 降低。 反之如果 $r_j >0$,則 $J$ 變大 (makes things worse)。
3. 如果所有的 $r_j \geq 0$ (都非負),則Cost 無法再繼續降低,我們說此即為最佳解。

將以上討論寫成如下定理:

=======================
Theorem
一個 Basic Feasible Solution 為最佳解 若且唯若 (if and only if ) 其對應的 Relative Cost Coefficient $r_j \geq 0, \ \forall j$
=======================

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

2011年4月10日 星期日

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

延續前篇,我們現在手上有了 LP問題的基本定理:

=================================
Theorem (Fundamental Theorem of LP):
考慮標準型式的線性規劃 (Standard LP)問題

令 $x \in \mathbb{R}^n$,
\[\begin{array}{l}
\min {c^T}x\\
s.t.\\
\left\{ \begin{array}{l}
Ax = b,\\
x \ge 0
\end{array} \right.
\end{array}\]其中 $A$ 為 $m \times n$ 矩陣且 $n>m$, $rank(A) = m$,$A$ 沒有全為零的column$;b \geq 0$,
1. 若其存在一個 Feasible Solution,則必存在一個 Basic + Feasible 的解
2. 若其存在一個optimal + feasible solution,則必定存在一個optimal basic + feasible solution 。
=================================

現在我們來看看線性規劃的一些例子:

Example:
考慮如下 LP 問題:
\[\begin{array}{l}
\max \left( {3{u_1} + 5{u_2}} \right)\\
s.t.\\
\left\{ \begin{array}{l}
{u_1} + 5{u_2} \le 40\\
2{u_1} + {u_2} \le 20\\
{u_1} + {u_2} \le 12
\end{array} \right.\\
{u_i} \ge 0,i = 1,2
\end{array}
\]首先將其改寫成標準型式LP問題: (引入 slack variable $y_3, y_4, y_5 \geq 0$)
\[\begin{array}{l}
\min \left( { - 3{u_1} - 5{u_2}} \right)\\
s.t.\\
\left\{ \begin{array}{l}
{u_1} + 5{u_2} + {y_3} = 40\\
2{u_1} + {u_2} + \begin{array}{*{20}{c}}
{}
\end{array}{y_4} = 20\\
{u_1} + {u_2} + \begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}{y_5} = 12
\end{array} \right.\\
{u_i} \ge 0,i = 1,2,3,4,5
\end{array}\]定義 $x := [x_1 \ x_2 \ x_3 \ x_4 \ x_5 ]^T = [u_1 \ u_2 \ y_1 \ y_2 \ y_3 ]^T $ 我們得到標準型LP問題如下
\[\begin{array}{l}
\min \left( { - 3{x_1} - 5{x_2}} \right)\\
s.t.\\
\left\{ \begin{array}{l}
{x_1} + 5{x_2} + {x_3} = 40\\
2{x_1} + {x_2} + \begin{array}{*{20}{c}}
{}
\end{array}{x_4} = 20\\
{x_1} + {x_2} + \begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}{x_5} = 12
\end{array} \right.\\
{x_i} \ge 0,i = 1,2,3,4,5
\end{array}\]
注意到我們可以把拘束條件改寫為
\[\begin{array}{l}
{x_1}\left[ {\begin{array}{*{20}{c}}
1\\
2\\
1
\end{array}} \right] + {x_2}\left[ {\begin{array}{*{20}{c}}
5\\
1\\
1
\end{array}} \right] + {x_3}\left[ {\begin{array}{*{20}{c}}
1\\
0\\
0
\end{array}} \right] + {x_4}\left[ {\begin{array}{*{20}{c}}
0\\
1\\
0
\end{array}} \right] + {x_5}\left[ {\begin{array}{*{20}{c}}
0\\
0\\
1
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{40}\\
{20}\\
{12}
\end{array}} \right]\\
{x_i} \ge 0,i = 1,2,3,4,5
\end{array}
\]且 $x= [0, 0, 40, 20, 12]^T$ 為一個 feasible solution 且 為一個 Extreme point (由之前文章的定理可知Exterme Point $\Leftrightarrow$ Basic Feasible Solution)。但是如果我們選此 $x$則我們的cost :$-3 x_1 - 5 x_2 = -3 \cdot 0 + -5 \cdot 0 =0$。亦即此cost並不是minimum,故我們需要在其他 Extreme Point 中尋找最佳解。

想法: 從一個 Extreme Point 移動到另一個 Exterme Point 使得我們的cost 可以逐步降低。

故由 $x= [0, 0, 40, 20, 12]^T$ 開始,我們有
\[{0\underbrace {\left[ {\begin{array}{*{20}{c}}
1\\
2\\
1
\end{array}} \right]}_{{a_1}} + 0\underbrace {\left[ {\begin{array}{*{20}{c}}
5\\
1\\
1
\end{array}} \right]}_{{a_2}} + 40\underbrace {\left[ {\begin{array}{*{20}{c}}
1\\
0\\
0
\end{array}} \right]}_{{a_3}} + 20\underbrace {\left[ {\begin{array}{*{20}{c}}
0\\
1\\
0
\end{array}} \right]}_{{a_4}} + 12\underbrace {\left[ {\begin{array}{*{20}{c}}
0\\
0\\
1
\end{array}} \right]}_{{a_5}} = \left[ {\begin{array}{*{20}{c}}
{40}\\
{20}\\
{12}
\end{array}} \right]} \\
\Rightarrow 0 a_1 + 0 a_2 + 40 a_3 +20 a_4 + 12 a_5 = b
\]現在為了要選取下一個鄰近的 Extreme Point,我們選 $a_1$ column 做為新的基底。然後我們需要把現有的舊的基底 $a_3, a_4, a_5$ 中剔除一個。那麼該怎麼做呢? 方法如下:

首先把 $a_1$ 用舊基底線性組合來表示:
\[
a_1 = 1 a_3 + 2 a_4 + 1 a_5
\]對上式兩邊同乘 $\varepsilon_1 >0$,我們可得
\[{{\varepsilon _1}{a_1} = {\varepsilon _1}{a_3} + 2{\varepsilon _1}{a_4} + {\varepsilon _1}{a_5}}
\]現在把上式加到 $(*)$ 並整理如下:
\[\begin{array}{l}
\left( {{\varepsilon _1}{a_1} - {\varepsilon _1}{a_3} - 2{\varepsilon _1}{a_4} - 1{\varepsilon _1}{a_5}} \right) + \left( {0{a_1} + 0{a_2} + 40{a_3} + 20{a_4} + 12{a_5}} \right) = 0 + b\\
 \Rightarrow \left( {{\varepsilon _1} + 0} \right){a_1} + 0{a_2} + \left( {40 - {\varepsilon _1}} \right){a_3} + \left( {20 - 2{\varepsilon _1}} \right){a_4} + \left( {12 - 1{\varepsilon _1}} \right){a_5} = b
\end{array}
\] 那麼現在我們想要選 $\varepsilon_1$ 使得 上式的係數都非負,且同時舊的基底 $a_3, a_4, a_5$ 其中一個的係數變成零 (這樣我們就可以把舊的基底其中一個換成新基底 $a_1$)。觀察上式可以發現選舊的基底 $a_3, a_4, a_5$ 對應的係數中最小的, 亦即我們要選 $\varepsilon_1 = 10$ (替換 $a_4$ 基底)。故得到
\[
 \Rightarrow 10{a_1} + 0{a_2} + 30{a_3} + 0{a_4} + 2{a_5} = b
\]其對應的 Basic Feasible Solution (Extreme Point) 為
\[
[10, 0, 30, 0, 2]^T
\]且此時我們的Cost: $-3 x_1 - 5 x_2 = -30$,亦即從原本的 $0$ 降低到 $-30$。

接著我們重複上述步驟在移動到下一個鄰近的Extreme Point,希望可以再降低我們的Cost 。這次我們選 $a_2$ 做為新的基底,故我們讓 $a_2$ 用現有的基底 $a_1, a_3, a_5$表示:
\[
a_2 = 1/2 a_1 + 9/2 a_3 + 1/2 a_5 \ \ \ \ (**)
\]接著對上式兩邊同乘 $\varepsilon_2 >0$,我們可得
\[{{\varepsilon _2}{a_2} = \frac{1}{2}{\varepsilon _2}{a_1} + \frac{9}{2}{\varepsilon _2}{a_3} + \frac{1}{2}{\varepsilon _2}{a_5}}
\]把上式 與 $(**)$ 相加
\[ \Rightarrow \left( {10 - \frac{1}{2}{\varepsilon _2}} \right){a_1} + {\varepsilon _2}{a_2} + \left( {30 - \frac{9}{2}{\varepsilon _2}} \right){a_3} + 0{a_4} + \left( {2 - \frac{1}{2}{\varepsilon _2}} \right){a_5} = b
\]同之前步驟,我們需要把 現有基底 $a_1, a_3, a_5$ 中踢出一個,故應選 $\varepsilon_2$ 使得 上式的係數都非負,且同時舊的基底 $a_1, a_3, a_5$ 其中一個的係數變成零;觀察上式發現應選 $\varepsilon_2 = 4$,我們得到
\[ \Rightarrow 8{a_1} + 4{a_2} + 12{a_3} + 0{a_4} + 0{a_5} = b
\]此時對應的解為
\[
[8, 4, 12, 0, 0]^T
\]且對應的 Cost: $ -3 x_1 -5 x_2 = -44$亦即又比剛剛的 $-30$ 更小。現在我們再重複上述例子,這次我們選 $a_4$做為新的替換基底並將其用舊的基底表示為
\[
a_4 = a_1 - a_2 +4 a_3
\]接著對上式兩邊同乘 $\varepsilon_3 >0$,並將其與原有的基底相加可得
\[
(8-\varepsilon_3) a_1 + (4 + \varepsilon_3) a_2 +(12 - 4 \varepsilon_3) a_3 + \varepsilon_3 a_4 = b
\]觀察上式,我們應選 $\varepsilon_3 = 3$,故得到
\[
5 a_1 + 7 a_2 +0 a_3 + 3 a_4 = b
\]故對應的解為
\[
[5, 7, 0, 3, 0]^T
\]此時對應的 Cost 為 $ -3 x_1 -5 x_2 = -50$且此即為對此 標準LP問題的最佳解,故我們的最佳解對原本問題即為 $x^* = [x_1, x_2]= [u_1, u_2] = [5, 7]$。 $\square$

上述的方法:從一個Extreme point 到另一個 Extreme Point的方法,亦會在之後的 Simplex Method 中再做詳細的介紹。

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

==============
延伸閱讀
[最佳化] 淺談線性規劃(0)- Standard form of Linear Programming

[最佳化] 淺談線性規劃(1)- Feasible solution and Basic solution

[最佳化] 淺談線性規劃(2)- Optimality Theorem

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

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

2011年4月9日 星期六

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

2011年4月7日 星期四

[數學分析] 逐點收斂與均勻收斂(1)- sequence of functions

這次要介紹的是數學分析中關於函數收斂性 的 兩個非常重要的觀念: Pointwise convergence (逐點收斂) Uniform convergence (均勻收斂) 。

不過在談函數的收斂之前,我們需要先知道到底是誰要收斂? 在此我們所指的函數的收斂為考慮 函數 sequence  (也就是 函數 所形成的數列) 的收斂 。以下我們稱 $\{f_k \}_{k=1}^{\infty}$ 為一個 函數 sequence,其中 $f_k$ 為該數列中第 $k$ 個元素函數。

有了上述定義,我們便可以引入 這樣的函數到底如何收斂,首先我們介紹 函數 sequence 逐點收斂 的概念:
======================
Definition (Pointwise Convergence)
我們說一個 函數的 sequence $\{ f_k(t)\}_{k=1}^\infty $ 逐點收斂(converges pointwise) 到 某函數 $f(t)$ 若下列條件成立:
對任意 $ t \in [t_0, t_1]$
\[
 \mathop {\lim }\limits_{k \to \infty } {f_k}(t) = f(t)
\]======================

Comment:
1. 上述定義清楚的說明甚麼是逐點收斂。注意到第一個條件是 對任意 $t \in [t_0, t_1]$;也就是說 如果我們固定 $t$在某個閉區間範圍 $[t_0, t_1]$,在該時刻 $t$,我們的函數sequence $f_k(t) \rightarrow f(t)$ 對每一點時刻都成立。故稱為逐點收斂。

2. $f_k(t) \rightarrow f(t)  \Leftrightarrow \mathop {\lim }\limits_{k \to \infty } {f_k}(t)$ 在數學分析內容中,通常會更精確陳述為:
給定 $t \in [t_0,t_1]$, 對任意 $\varepsilon >0$ 存在一個夠大的 $N>0$ 使得 當 $n \ge N \Rightarrow |f_k(t) - f(t)| < \varepsilon$


下面給個例子說明Pointwise Convergence的概念:

Example (Pointwise Convergence)
考慮 $t \in [0, 1]$且我們的函數sequence
\[
{f_k}\left( t \right): = \left[ {\begin{array}{*{20}{c}}
{{e^{ - tk}}\cos kt + 2}\\
{{e^{ - 2tk}}\cos kt + t}
\end{array}} \right]
\]
則我們現在固定任意 $t \in [0,1]$ ,並檢驗當 $k \rightarrow \infty$ 的時候會發生甚麼事情?
\[ \Rightarrow \mathop {\lim }\limits_{k \to \infty } {f_k}\left( t \right) = \mathop {\lim }\limits_{k \to \infty } \left[ {\begin{array}{*{20}{c}}
{{e^{ - tk}}\cos kt + 2}\\
{{e^{ - 2tk}}\cos kt + t}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
2\\
t
\end{array}} \right]
\]上式告訴我們對每一個固定的 $t \in [0,1]$ 我們都有
\[{f_k}(t) \to \left[ {\begin{array}{*{20}{c}}
2\\
t
\end{array}} \right]
\]亦即 ${f_k}(t)$ 逐點收斂到 $\left[ {\begin{array}{*{20}{c}}
2\\
t
\end{array}} \right]$

注意到,儘管convergence pointwise 看起來似乎是很強的收斂條件,但其實我們很難從此種收斂中得出一些我們感興趣的性質 (比如說 此函數sequence原本為連續函數,那麼其對應的極限函數 $f$ 是否仍為連續? 或者原函數squence 可微(積)分,那麼對應的極限函數 $f$ 是否也可微(積)分?) 事實上並無法被保證。

比如說考慮下圖 (點圖放大)


若以式子描述則為 \[{f_k}\left( t \right) = \left\{ {\begin{array}{*{20}{l}} {0,\begin{array}{*{20}{c}} {} \end{array}t \le 0}\\ {kt,\begin{array}{*{20}{c}} {} \end{array}0 < t < \frac{1}{k}}\\ {1,\begin{array}{*{20}{c}} {} \end{array}t \ge \frac{1}{k}} \end{array}} \right.\begin{array}{*{20}{c}} {} \end{array} \to \begin{array}{*{20}{c}} {} \end{array}\mathop {\lim }\limits_{k \to \infty } {f_k}\left( t \right) = f\left( t \right) = \left\{ {\begin{array}{*{20}{l}} {0,\begin{array}{*{20}{c}} {} \end{array}t \le 0}\\ {1,\begin{array}{*{20}{c}} {} \end{array}t > 0} \end{array}} \right.\] 左圖 $f_k$ 為連續函數。 但現在如果我們固定任意 $t$,並且讓 $k \rightarrow \infty$,我們得到的 $f$ 為一個step function,故連續性再逐點收斂中並沒有被保證。


故我們需要一個比逐點收斂更強的收斂。稱作均勻收斂 (Uniform convergence)

======================
Definition: (Uniform Convergence)
我們說一個 函數的 sequence $\{ f_k\}_{k=1}^\infty $ 均勻收斂(converges uniformly) 到 某函數 $f$ 若下列條件成立:
\[
||f_k - f || \rightarrow 0 \ \text{as $k \rightarrow \infty$} \\
\text{or}\\
 \ \mathop {\lim }\limits_{k \to \infty } \left\| {{f_k} - f} \right\| = 0
\]======================

Comments
1. 上述定義不再要求 $t$,亦即與 $t$ 無關 (Uniform means total lack of restriction on $t$)。

2. $ ||f || := \displaystyle \sup_{t \in [t_0, t_1]} |f(t)|$;亦即我們的函數的norm是取sup norm of function (or so-called uniform norm, or infinity norm)

現在我們看個例子:

Example :
考慮 $f_n: \mathbb{R} \to \mathbb{R}$,且
$$f_n(x):=\frac{x^2+nx}{n}
$$ 1. 試求當 $n \to \infty$ 其極限為何?
2. 試判斷是否均勻收斂至其極限?

Solution
1. \[\mathop {\lim }\limits_{n \to \infty } {f_n}(x) = \mathop {\lim }\limits_{n \to \infty } \frac{{{x^2} + nx}}{n} = x\]
2. 檢驗其是否均勻收斂至 $x$ 我們可檢驗其 supnorm 是否收斂到 $0$
\[\left\| {{f_n} - f} \right\| = \mathop {\sup }\limits_{x \in {\rm{R}}} \left| {\frac{{{x^2} + nx}}{n} - x} \right| = \mathop {\sup }\limits_{x \in {\rm{R}}} \left| {\frac{{{x^2}}}{n}} \right|\]注意到若取 $x := \sqrt{n} \in \mathbb{R}$ 其 supnorm $=1$ 故不收斂到 $0$;因此 此例 $f_n(x)$ 並無均勻收斂到 $x$。$\square$


接著我們看個重要的結果,也就是均勻收斂保證 逐點收斂。

==================
FACT: $f_k$ converges uniformly to $f$ $\Rightarrow$ $f_k$ converges pointwise to $f$ 
==================
Proof:
固定 $t \in [t_0, t_1]$,我們要證明 $f_k \rightarrow f$ pointwise,亦即要證明
\[
\lim_{k \rightarrow \infty}|f_k(t) - f(t) | =0
\]故我們觀察
\[
|f_k(t) - f(t) | \le \displaystyle \sup_{t \in [t_0, t_1]}|f_k(t) - f(t) | = ||f_k - f ||
\] 又因為 $f_k \rightarrow f$ uniformly,故我們知道
\[
 ||f_k - f || \rightarrow 0
\] 亦即 Uniformly convergence $\Rightarrow$ Pointwise Convergence $\square$。


均勻收斂 保證 連續性。
==================
FACT: 令 $\{f_k\}: X \to \mathbb{R}$ 為 連續函數 sequence;若 $f_n \to f$ 均勻收斂,則 $f$ 為連續函數 (連續性被保持)
==================
(Proof is omitted.)
回頭再檢驗一下我們剛剛的圖

其並非均勻收斂 (WHY??) 由均勻收斂定義,我們計算其sup norm看看發生甚麼事:
\[
\left\| {{f_k} - f} \right\| = \sup_t \left| {{f_k}\left( t \right) - f\left( t \right)} \right| = 1 \ne 0
\]
WHY supnorm = 1?? 由定義我們是找 "兩者間差異" 取 sup,也就是找 $f_k - f$的差異最大的時候,那麼兩者間最大差異為1 不為0,亦即不均勻收斂。(失去連續性)


==================
FACT: 若 $\{ f_k \}_{k=1}^\infty$ converges uniformly to $f$ 若且唯若 $\{ f_k \}_{k=1}^\infty$  為 Cauchy sequence。亦即;對所有的 $\varepsilon > 0$, 存在一個 $K \in \mathbb{N}$ 使得 對所有的 $j,k \geq K$,我們有 \[ ||f_j - f_k|| < \varepsilon \]==================


接著我們看一個 Uniform Convergence 的結果:如果我們確認某函數 sequence  $\{ f_k \}$ 均勻收斂到 某極限函數 $f$,則 對其取積分再取極限 等價 取極限再取積分。(亦即 積分與極限次序可以互換)!!

==================
Theorem
令 $\{ f_k \}_{k=1}^\infty$ 為在有界 分段連續函數空間 $\cal{B}([t_0, t_1], \mathbb{R}^n)$ 的 sequence,且均勻收斂到 $f$。則
\[
\displaystyle \lim_{k \rightarrow \infty} \int_{t_0}^{t_1} f_k(t) dt = \int_{t_0}^{t_1} f(t) dt
\]==================

Proof
首先計算下列兩積分的差
\[\begin{array}{l}
\left\| {\int_{{t_0}}^{{t_1}} {{f_k}} (t)dt - \int_{{t_0}}^{{t_1}} f (t)dt} \right\| = \left\| {\int_{{t_0}}^{{t_1}} {{f_k}} (t) - f(t)dt} \right\|\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}&{}&{}&{}&{}
\end{array} \le \int_{{t_0}}^{{t_1}} {\left\| {{f_k}(t) - f(t)} \right\|} dt\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}&{}&{}&{}&{}
\end{array} \le \int_{{t_0}}^{{t_1}} {\sup \left\| {{f_k}(t) - f(t)} \right\|} dt = \int_{{t_0}}^{{t_1}} {\left\| {{f_k} - f} \right\|} dt\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}&{}&{}&{}&{}
\end{array} = \left\| {{f_k} - f} \right\|\int_{{t_0}}^{{t_1}} 1 dt = \underbrace {\left\| {{f_k} - f} \right\|}_{ \to 0}\left( {{t_1} - {t_0}} \right)
\end{array}
\]故
\[
\displaystyle \lim_{k \rightarrow \infty} \int_{t_0}^{t_1} f_k(t) dt = \int_{t_0}^{t_1} f(t) dt. \ \ \ \ \square
\]

延伸閱讀
[數學分析] 逐點收斂與均勻收斂(2) - Series version
[數學分析] 逐點收斂與均勻收斂(3) - Differentiation property

[線性系統] 淺談 Normed Vector Space

==================
Definition: Vector Space
一個 向量空間 (Vector Space) 是由兩個運算元 $+, \cdot$ (向量加法 與 純量乘法) 以及一個 $0$ 元素 所定義,我們可記做
\[
(+, \cdot, 0)
\] ==================
一般而言 Vector Space 可視為 抽象化的  Euclidean space (有限維度 );但 Vector Space 亦可為 無窮維度。



以下我們給出 三個線性系統理論中常用的 Vector Space 作為例子:
---
Examples: 
1. $\mathbb{R}^n, n=1,2,3,...$ 是一個向量空間
2. 連續函數 $f(t)$ 在區間 $[t_0, t_1]$ 所形成的集合亦為一個向量空間 (此稱為 continuous function space,記做 $\cal{C}( [t_0, t_1], \mathbb{R})$.
3. 有界 分段連續函數 $f(t)$ 在區間 $[t_0, t_1]$ 所形成的集合亦為一個向量空間 (此稱為 bounded piecewise continuous function space,記做 $\cal{B}( [t_0, t_1], \mathbb{R})$.
---

Comments:
讀者可以自行檢驗上述兩個例子確實形成向量空間,比如說
令 $f$ 為連續函數,亦即 $ f \in \cal{C}( [t_0, t_1], \mathbb{R})$,我們檢驗其兩個運算元與 0 元素 如下

1. 連續函數 $f_1$ + 連續函數 $f_2$ 仍為連續函數 亦即 $f_1 + f_2 \in \cal{C}( [t_0, t_1], \mathbb{R})$
2. 純量 $\alpha$ $\cdot$ 連續函數 $f$ 仍為連續函數 亦即 $\alpha f \in \cal{C}( [t_0, t_1], \mathbb{R})$
3. $0$ 為連續函數,亦即 $0 \in \cal{C}( [t_0, t_1], \mathbb{R})$。

向量空間的子空間
==================
Definition: Subspace
令 $M$ 為向量空間 $X$ 的非空子集,我們稱 $M$ 為 $X$ 的子空間(Subspace) 若下列條件成立:給定向量 $x,y \in M$ 且 $\alpha, \beta \in \mathbb{R}$,則
$$
\alpha x + \beta y \in M
$$==================


向量空間可以相加嗎?
==================
Definition: Addition of Two Sets
令 $S$ 與 $T$ 分別為 向量空間 $X$ 的子集合,現在定義 $S+T$ 為所有向量具有 $s+t$ 的形式,其中 $s \in S$ 且 $t \in T$,亦即
\[
S+T:=\{s+t: s\in S, t \in T\}
\]==================


==================
Proposition: 令 $S$ 與 $T$ 為向量空間 $X$ 的子空間,則 $S+T$ 仍為 $X$ 的子空間
==================
Proof: omitted. 



現在如果我們 在 Vector Space 中引入廣義的長度 (稱為 Norm) 的概念,則這種 Vector Space 稱為 Normed Vector Space。 此目的在於一但我們有了長度,我們便可以在 Vector space 上定義什麼叫做連續性。以下我們給出 Norm 的定義。

===================
Definition: (Norm)
令 $X$ 為一 Vector Space,我們說一個映射(mapping) $||\cdot|| : X \rightarrow \mathbb{R}$ 為一個 Norm,如果下列四個條件成立:
1. $||\mathbf{x} || \ge 0, \ \forall \mathbf{x} \in X$
2. $||\mathbf{x}|| = 0$ 若且為若 $\mathbf{x} =\mathbf{0}$
3. $||\lambda \mathbf{x}|| = |\lambda| ||\mathbf{x}||, \ \forall \lambda \in \mathbb{R}, \mathbf{x} \in X$
4. $||\mathbf{x} + \mathbf{y}|| \le ||\mathbf{x}|| + ||\mathbf{y}||, \ \forall \mathbf{x},\mathbf{y} \in X$
===================
Comment:
Norm: $||\cdot||$ 本質上亦為一連續函數。



有了 Norm 的概念之後我們便可以將其引入 到 Vector Space 中:
================
Definition: Normed Vector Space
一個 Normed Space 記做 $(V,||\cdot||)$ 其中 $V$ 為 Vector Space , $||\cdot||$ 為 norm 滿足上述定義。
================

Comment: 任何 Normed Vector Space 必為 Metric Space (反之則非!!)


底下我們看幾個經典的 Normed Vector Space:


R^n Space ($\mathbb{R}^n$)
現在我們如果考慮 Vector Space  $X = \mathbb{R}^n$,則 $\mathbf{x} \in \mathbb{R}^n$ 可以記做
\[
\mathbf{x} = [x_1 \ x_2 \ ... \ x_n]^T
\]
一般在 $\mathbb{R}^n$ 空間常見的 Norm 有三種,但最主要最常見的稱為 $l^2$-norm,定義如下:
\[
||\mathbf{x}||_2 := \sqrt{\mathbf{x}^T}{\mathbf{x}} = \sqrt{\sum_i^n x_i^2}
\] 另外兩個分別為 $l^1$-norm 與 $l^\infty$-nrom。
\[
||\mathbf{x}||_1 := \sum_{i=1}^n |x_i| \\
||\mathbf{x}||_\infty := \max_i |x_i|
\]

Comments:
一般而言,在線性系統理論中,Norm 的概念主要用在討論 連續性,收斂性(Convergence) 與 系統穩定度 (Stability) 相關議題。關於收斂性有興趣的讀者請參考:
[數學分析] 逐點收斂與均勻收斂 (Pointwise Convergence & Uniform convergence)



連續函數所形成的函數空間: $\cal{C}([t_0, t_1], \mathbb{R})$
現在我們再看看如果我們取 Vector Space $X = \cal{C}([t_0, t_1], \mathbb{R})$ ($X$ 現在為 Continuous Function Space),若 $ f(t) \in  \cal{C}({[t_0, t_1], \mathbb{R}})$ (亦即 $f(t)$ 在 區間 $[t_0, t_1]$ 上為連續實數函數。),則我們亦可定義 Norm 如下:
\[
||f|| := \max_{t \in [t_0, t_1]} |f(t)|
\]另外常見的 Norm on function space  $ \cal{C}([t_0, t_1], \mathbb{R})$ 還有 $L^2$-norm:
\[
||f||_{L^2} := \sqrt{\int_{t_0}^{t_1} |f(t)|^2 dt}
\]
以下我們簡單驗證 $||f||$ 確實滿足我們前述的 norm的條件:
Proof: 注意到 $||f|| := \max_{t \in [t_0, t_1]} |f(t)| \ge 0$ 且 $||f|| = 0$ 若且唯若 $f = 0$,接著我們驗證性質 3: 觀察
\[\begin{array}{l}
||\lambda f|| = \mathop {\max }\limits_{t \in [{t_0},{t_1}]} |\lambda f(t)|\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = \mathop {\max }\limits_{t \in [{t_0},{t_1}]} \left| \lambda  \right||f(t)| = \left| \lambda  \right|\mathop {\max }\limits_{t \in [{t_0},{t_1}]} |f(t)| = \left| \lambda  \right|\left\| f \right\|
\end{array}\]
最後我們驗證性質 4: (三角不等式)給定 $f,g \in C([t_0,t_1])$
\[\begin{array}{l}
||f + g|| = \mathop {\max }\limits_{t \in [{t_0},{t_1}]} |f(t) + g\left( t \right)|\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} \le \mathop {\max }\limits_{t \in [{t_0},{t_1}]} \left( {|f(t)| + |g\left( t \right)|} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} \le \mathop {\max }\limits_{t \in [{t_0},{t_1}]} |f(t)| + \mathop {\max }\limits_{t \in [{t_0},{t_1}]} |g\left( t \right)|\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = ||f|| + ||g||
\end{array}\]至此我們證明了上述的 norm 確實符合四個性質。$\square$


Bounded continuous function Space: $\cal{B}([t_0, t_1], \mathbb{R})$
如果我們現在對上述 Continuous function space  $\cal{C}([t_0, t_1], \mathbb{R})$ 做進一步拓展:考慮函數為 分段連續(piecewise continuous) 且 有界 (bounded),亦即所有分段連續函數必須有界所組成的 function space 我們稱之為 $\cal{B}([t_0, t_1], \mathbb{R})$,注意到
\[
\cal{C}([t_0, t_1], \mathbb{R}) \supset \cal{B}([t_0, t_1], \mathbb{R})
\]
則此有界分段連續函數組成的 space 在區間 $t \in [t_0, t_1]$ 亦為 一個 Vector Space。我們檢驗如下:

1. 有界 分段連續函數 $f_1$ + 有界 分段連續函數 $f_2$ 仍為有界 分段連續函數 亦即 $f_1 + f_2 \in \cal{B}([t_0, t_1], \mathbb{R})$
2. 純量 $\alpha$ $\cdot$ 有界 分段連續函數 $f$ 仍為有界連續函數 亦即 $\alpha f \in \cal{B}([t_0, t_1], \mathbb{R})$
3. $0$ 為有界 分段連續函數,亦即 $0 \in \cal{B}[(t_0, t_1), \mathbb{R}]$。

知道 $\cal{B}([t_0, t_1], \mathbb{R})$ 之後,現在我們可以在其上定義 norm。
\[
||f|| := \sup_{t \in [t_0, t_1]} |f(t)|
\]
現在如果我們有許多個 $f(t)$ ,我們可將其收集起來寫成 向量的形式如下:

N-dimensional function vectors:
考慮 $f_i(t) \in \cal{B}([t_0, t_1], \mathbb{R}), \ \forall i = 1,...,n$,則我們可定義
\[{\bf{f}}(t): = \left[ {\begin{array}{*{20}{c}}
{{f_1}(t)}\\
{{f_2}(t)}\\
 \vdots \\
{{f_n}(t)}
\end{array}} \right]
\]亦即上述函數向量 $\mathbf{f}(t) \in \cal{B}([t_0, t_1], \mathbb{R}^n)$,且 $\cal{B}([t_0, t_1], \mathbb{R}^n)$ 仍為一個 Vector Space。故我們仍可在其上定義 Norm 如下:
\[
||\mathbf{f}|| := \sup_{t \in [t_0, t_1]} ||\mathbf{f}(t)||
\]


2011年4月2日 星期六

[最佳化] 淺談線性規劃(2)- Optimality Theorem & Fundamental Theorem of LP

延續上篇,我們知道了標準型式的Linear Programming 問題若存在feasible solution,則必定存在一個 basic + feasible solution,但我們完全沒有提及到底如何最佳化(在此我們以最小化為主;亦即目標是要盡可能降低cost function的值),

也就是在從一個feasible solution移動到下一個basic + feasible solution之後,cost function的值是如何被降低的。這次要介紹的是 Optimality Theorem

=========================
Theorem: Optimality Theorem
對具有標準形式的Linear Programming問題,若其存在一個optimal + feasible solution $x^*$,則必定存在一個optimal basic + feasible solution $\tilde x^*$。
=========================

Proof:
考慮下列兩種情況:
1. $x^*$  為 Basic solution
2. $x^*$  不為 Basic solution

對情況1而言 (trivially true):
假設 $x^*$ 為Basic solution,則由假設我們又知道 $x^*$ 為 optimal + feasible solution;故在此情況下 $x^*$ 為 optimal basic + feasible solution 。

對情況2而言
假設 $x^*$  不為Basic solution,則由Basic Solution 定義可知
-----
一個向量 $x \in \mathbb{R}^n$ 稱作對 $Ax=b$ 的 Basic Solution ,若 $x$中 nonzero components 對應到$A$矩陣的線性獨立 Columns。
-----

故若  $x^*$  不為Basic solution,則表示  $x^*$  中的nonzero components 對應到$A$矩陣 Columns為線性相關 ;故我們進一步改寫此結果:

令   $x_1^*, x_2^*, ..., x_m^*$ 為  $x^*$中 nonzero components;其對應到 $A$ 矩陣Columns:
$a^1, a^2, ..., a^m$ 為線性相關;故由線性相關定義可知必定存在一組 非零純量 $y_i$ 使得
\[
\sum_{i=1}^{m} y_i a^i =0
\]

現在我們定義 $\eta^\varepsilon$ 如下
\[
{\eta _i^\varepsilon  }: = \left\{ \begin{array}{l}
x_i^*  - \varepsilon {y_i}, \ \ i \le m\\
0, \ \ \ \ i > m
\end{array} \right.
\] 則
\[\begin{array}{l}
A{\eta ^\varepsilon } = \left[ {\begin{array}{*{20}{c}}
{{a^1}}&{{a^2}}& \cdots &{{a^m}}&{{a^{m + 1}}}& \cdots &{{a^n}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{x_1^* - \varepsilon {y_1}}\\
{x_2^* - \varepsilon {y_2}}\\
 \vdots \\
{x_m^* - \varepsilon {y_m}}\\
0\\
 \vdots \\
0
\end{array}} \right]\\
 \Rightarrow A{\eta ^\varepsilon } = {a^1}\left( {x_1^* - \varepsilon {y_1}} \right) +  \cdots  + {a^m}\left( {x_m^* - \varepsilon {y_m}} \right)\\
 \Rightarrow A{\eta ^\varepsilon } = \left( {{a^1}x_1^* +  \cdots  + {a^m}x_m^*} \right) - \left( {\varepsilon {a^1}{y_1} +  \cdots  + \varepsilon {a^m}{y_m}} \right)\\
 \Rightarrow A{\eta ^\varepsilon } = \left( {{a^1}x_1^* +  \cdots  + {a^m}x_m^*} \right) - \underbrace {\varepsilon \sum\limits_{i = 1}^m {{a^i}{y_i}} }_{ = 0}\\
 \Rightarrow A{\eta ^\varepsilon } = \underbrace {\left[ {\begin{array}{*{20}{c}}
{{a^1}}&{{a^2}}& \cdots &{{a^m}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{x_1^*}\\
{x_2^*}\\
 \vdots \\
{x_m^*}
\end{array}} \right]}_{ = b}
\end{array}\]亦即,
\[
A \eta^{\varepsilon} = b
\]因此,如果 $|\varepsilon|$ 足夠小的時候,$\eta^\varepsilon$ 為 feasible solution;故我們說 $|\varepsilon| < \delta$;現在我們回頭檢查 對於Cost function $J = c^T x$ 有甚麼影響 :
\[
c^T \eta^\varepsilon = c^T (x^* - \varepsilon y)= c^T x^* - \varepsilon \cdot c^T y \ \ \ \ (*)
\] 且對 $i>m$的時候, $y_i =0$

觀察上式 $(*)$:可知如果我們有 $ \varepsilon \cdot c^T y >0 $ 則 Cost 就可以被我們降低。故定義 $\varepsilon := \delta \cdot \text{sign}(c^T y)$;則對此$\varepsilon$而言,
\[\begin{array}{l}
{c^T}{\eta ^\varepsilon } = {c^T}{x^*} - \varepsilon  \cdot {c^T}y\;\\
 \Rightarrow {c^T}{\eta ^\varepsilon } = {c^T}{x^*} - \delta \cdot \text{sign}\left( {{c^T}y\;} \right) \cdot {c^T}y\;\\
 \Rightarrow {c^T}{\eta ^\varepsilon } = {c^T}{x^*} - \delta \left| {{c^T}y\;} \right| \le {c^T}{x^*}
\end{array}
\]故我們得到 $\eta^\varepsilon$ 為對於 $|\varepsilon| \leq \delta$最佳解。故Optimality 被保證;亦即
我們現在找到 標準型式的Linear Programming 問題的 feasible solution $\eta^\varepsilon$,接著我們保證了此解的Optimality。
接著我們回憶前一篇得到的結果
----
標準型式的Linear Programming 問題若存在feasible solution,則必定存在一個 basic + feasible solution,
----
故我們得到
對具有標準形式的Linear Programming問題,若其存在一個optimal + feasible solution $x^*$,則必定存在一個optimal basic + feasible solution $\tilde x^*$。 至此證明完畢。 $\square$

============
Comments

一般而言,前篇的定理與Optimality Theorem合稱為 Fundamental Theorem of LP

我們將其寫在下方
=================================
Theorem (Fundamental Theorem of LP):
考慮標準型式的線性規劃 (Standard LP)問題

令 $x \in \mathbb{R}^n$,
\[\begin{array}{l}
\min {c^T}x\\
s.t.\\
\left\{ \begin{array}{l}
Ax = b,\\
x \ge 0
\end{array} \right.
\end{array}\]其中 $A$ 為 $m \times n$ 矩陣且 $n>m$, $rank(A) = m$,$A$ 沒有全為零的column$;b \geq 0$,
1. 若其存在一個 Feasible Solution,則必存在一個 Basic + Feasible 的解
2. 若其存在一個optimal + feasible solution,則必定存在一個optimal basic + feasible solution 。
=================================

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


==============
延伸閱讀
[最佳化] 淺談線性規劃(0)- Standard form of Linear Programming

[最佳化] 淺談線性規劃(1)- Feasible solution and Basic solution

[最佳化] 淺談線性規劃(2)- Optimality Theorem

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

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