2014年2月15日 星期六

[最佳化] 牛頓法 (Generalized Newton Raphson Algorithm)

這次要介紹的是 Generalized Newton Raphson Algorithm (or so called Newton Method)

想法:透過二次函數近似 (quadratic fit) 目標函數 $J(u)$ 並以此找出最小值。


現在考慮在時間 $k$ ,我們有 $u^k \in \mathbb{R}^n$ 與對應的成本函數 $J(u^k)$;

現在如果我們讓 $u^k$ 受到一點擾動 $\Delta u := u^{k+1} - u^k$,也就是說受到擾動的成本函數可寫為
\[
J(u^k + \Delta u)
\]假設我們的目標函數 $J(u) $ 是個平滑函數(smooth function),那麼我們可以對其做泰勒展開( Taylor Expansion )。故現在透過 Taylor Expansion 對上式展開 (只展開到第二項,忽略其餘高階項:因為我們的想法是利用二次函數近似,故高階項忽略),我們得到
\[
J(u^k + \Delta u) = J(u^k) + \nabla J(u^k)^T \Delta u + \frac{1}{2} \Delta u^T \left ( \nabla^2 J(u^k)^T \right) \Delta u + H.O.T.
\]其中H.O.T為高階項 higher order term。我們將其忽略不計

現在由於我們欲求極小值(最佳化),故透過一階必要條件(FONC):
\[
\nabla J(u^k) |_{\Delta u = \Delta u^*}= 0
\] 亦即對 $\Delta u$ 求一階導數並令其為 $0$ 可得
\[
\left ( \nabla J(u^k) +  \nabla^2 J(u^k) \Delta u \right) |_{\Delta u = \Delta u^*} =0
\]整理上式可得
\[ \Rightarrow \Delta u^* =  - {\left[ {{\nabla ^2}J({u^k})} \right]^{ - 1}}\left( {\nabla J({u^k})} \right)
\] 又由擾動定義 $\Delta u := u^{k+1} - u^k$,我們可將上式進一步改寫
\[\begin{array}{l}
{u^{k + 1}} - {u^k} =  - {\left[ {{\nabla ^2}J({u^k})} \right]^{ - 1}}\left( {\nabla J({u^k})} \right)\\
 \Rightarrow {u^{k + 1}} = {u^k} - {\left[ {{\nabla ^2}J({u^k})} \right]^{ - 1}}\left( {\nabla J({u^k})} \right) \ \ \ \ (\star)
\end{array}
\]上式 $(\star)$ 的iterative structure稱為 Newton-Rapshon Algorithm

Comments:
1. 注意到 Newton Method 需要兩項資訊:一是 Gradient 另外一個則是 Hessian matrix 的 inverse :${\left[ {{\nabla ^2}J({u^k})} \right]^{ - 1}}$ ,事實上 Newton Method 擁有除了一階導數以外的 Hessian 的幫助確實對於整體演算法收斂性有所助益,但是注意到求由於Newton Method 需要求 Hessian 的反矩陣,這在大尺度 ( $n$ very large) 的問題中會變得難以求解。

另外如果 Hessian matrix 在跌代過程中損失正定性質(positive-definiteness ) =>無法求反矩陣 則此暗示目標函數可能與二次近似相距甚遠 (亦即目標函數難以用二次近似),此時用Newton Method求出的解在精度上會有問題。

2. 如果起始位置靠近最佳解 $u^*$ (事實上我們並不知道是否真的靠近,除非事先已知道最佳解在哪),則Newton Method 會優於 Steepest Descent Method。反之如果起始位置遠離最佳解,則 Steepest Descent Method會優於 Newton Method (因為Newton Method 用二次近似,故跌代緩慢,此時Steepest Descent 收斂速度會快於Newton Method)。

3. Newton Method 由於採用二次近似,故對於目標函數為二次式的情況,只需要跌代一步就收斂。(WHY!?)

考慮標準二階型態的成本函數 $J: \mathbb{R}^n \rightarrow \mathbb{R}$:
\[
J(u) = \frac{1}{2}u^T A u + b^T u + c, \ A \succ 0
\]還沒使用Newton Method之前,我們可先由一階必要條件 (First order necessary condtion, FONC): $\nabla J (u) =0$ 得知最佳解應該長甚麼樣:
\[
 {\left. {\nabla J(u)} \right|_{{u^*}}} = A{u^*} + b = 0 \Rightarrow {u^*} =  - {A^{ - 1}}b
\]且由二階充分條件(Second order sufficient condition, SOSC) $\nabla^2 J(u) \succ 0$,可得 $\nabla^2 J(u^*) = A \succ 0$,故 ${u^*} =  - {A^{ - 1}}b$ 為上述二階目標函數的最佳解。

現在我們看看用上Newton Method會發生甚麼事情:
\[{u^{k + 1}} = {u^k} - {\left[ {{\nabla ^2}J({u^k})} \right]^{ - 1}}\left( {\nabla J({u^k})} \right) \]考慮 $k=0$的時候我們有
\[\begin{array}{l}
 {u^1} = {u^0} - {A^{ - 1}}\left( {A{u^0} + b} \right)\\
 \Rightarrow {u^1} = {A^{ - 1}}b = {u^*}
\end{array}
\] 故由上述討論可知確實Newton Method 一步就收斂。 $\square$


現在我們來看個實際的例子:
======================
Example
考慮如下目標函數
\[J(u) = {\left( {11 - {u_1} - {u_2}} \right)^2} + {\left( {1 + 10{u_2} + {u_1} - {u_1}{u_2}} \right)^2}
\] 且給定初始條件 $u^0 = [18, 3]^T$ (任意給定)

1. 試用FONC與SOSC求解最佳解 $u^*$
2. 試用Newton Method 求 $u^1$ 與 $u^2$。
3. 試比較此兩種方法之解

Solution:
讀者可事先計算上述目標函數之最佳解(滿足FONC與SOSC)為 $u^* = [13, 4]^T$。

現在我們看看Newton Method有甚麼效果?

在使用 Newton Method之前需要兩個資訊:Gradient 與 Hessian,故我們依序計算如下:
\[\begin{array}{l}
\nabla J(u) = \left[ {\begin{array}{*{20}{c}}
{\frac{{\partial J}}{{\partial {u_1}}}}\\
{\frac{{\partial J}}{{\partial {u_2}}}}
\end{array}} \right]\\
 \Rightarrow \nabla J(u) = \left[ {\begin{array}{*{20}{c}}
{ - 2\left( {11 - {u_1} - {u_2}} \right) + 2\left( {1 + 10{u_2} + {u_1} - {u_1}{u_2}} \right)\left( {1 - {u_2}} \right)}\\
{ - 2\left( {11 - {u_1} - {u_2}} \right) + 2\left( {1 + 10{u_2} + {u_1} - {u_1}{u_2}} \right)\left( {10 - {u_1}} \right)}
\end{array}} \right]\\
 \Rightarrow \nabla J({u^0}) = \left[ {\begin{array}{*{20}{c}}
{40}\\
{100}
\end{array}} \right]
\end{array}
\]
Hessian:
\[\begin{array}{l}
{\nabla ^2}J(u) = \left[ {\begin{array}{*{20}{c}}
{2{{\left( {{u_2} - 1} \right)}^2} + 2}&{4\left( {{u_1}\left( {{u_2} - 1} \right) - 10{u_2} + 5} \right)}\\
{4\left( {{u_1}\left( {{u_2} - 1} \right) - 10{u_2} + 5} \right)}&{2{{\left( {{u_1} - 10} \right)}^2} + 2}
\end{array}} \right]\\
 \Rightarrow {\nabla ^2}J({u^0}) = \left[ {\begin{array}{*{20}{c}}
{10}&{44}\\
{44}&{130}
\end{array}} \right]
\end{array}\]

那麼我們用 Newton Method:
\[\begin{array}{l}
{u^{k + 1}} = {u^k} - {\left[ {{\nabla ^2}J({u^k})} \right]^{ - 1}}\left( {\nabla J({u^k})} \right)\\
 \Rightarrow {u^1} = \left[ {\begin{array}{*{20}{c}}
{18}\\
3
\end{array}} \right] - {\left[ {\begin{array}{*{20}{c}}
{10}&{44}\\
{44}&{130}
\end{array}} \right]^{ - 1}}\left[ {\begin{array}{*{20}{c}}
{40}\\
{100}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{19.2579}\\
{1.8570}
\end{array}} \right]
\end{array}\]同樣的我們可計算下一步 $u^2 = [13.265, 3.613]^T$ 逐步下去可以發現(在此初始條件之下)確實越來越接近最佳解 $u^*=[13, 4]$。計算細節在此不再贅述。

但是注意到,如果更改初始條件為其他值(比如說如果選很接近 $u^0 = [7, -2]^T$ 或者 $u^0 =[10, 1]^T$),則很可能得不到上述的最佳解!! 此時需要重新給定初始值再度測試。 $\square$



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

2014年2月12日 星期三

[衍生商品] 期貨的基差風險 (Basis Risk)

一般而言,在期貨(Futures)的世界裡面,其無法達到完全避險(Perfect Hedging)的主要原因 (也就是基差風險)有兩個:

  1. 標的資產不匹配 (Underlying Asset Mismatch)
  2. 到期時間不匹配 (Expiration Date Mismatch)

WHY!?

下圖是期貨價格 與 標的資產 即期價格(spot price)的變動情形,也就是 基差風險 隨時間的變化。可以發現在到期時刻 $t_2$ 的時候兩者合一 (也就是到期的時候才 "匹配" ,之前都 "不匹配" )。



Comments: 
標的資產不匹配:一般而言,投資人(個體OR公司)希望避險的 標的資產(Underlying asset) 不一定找的到與其完全匹配的期貨。比如說某航空公司 要避險的標的資產是飛機的航空煤油(Jet Fuel)。但是可能期貨市場只有石油提供選擇。

到期時間不匹配:另外就是很可能到期時間跟實際上真正賣出/買入的時間有所差異 (因為期貨是標準化契約,到期時間只有固定的月份。但我們買入賣出的月份可能不落在期貨契約上),又或者更有可能發生的是,投資人在進入某個期貨合約的時候,可能仍不確定要在何時執行資產買入或賣出。此時便會發生到期時間的不匹配。

所以上述的兩種不匹配導致所謂的基差Basis Risk

-----------------------------------------------------
現在我們進入正題,如果把前述討論用數學表示亦可看出所謂基差風險;現在我們先定義一些變數如下:

$S_{t_2}:$ 標的資產在 時刻 $t_2$ 的價格
$S_{t_2}^*$ 期貨合約中替代的標的資產 在時刻 $t_2$ 的價格

$F_{t_2}$ 標的資產在時刻 $t_2$ 的期貨價格
$F_{t_2}^*$ 替代的標的資產 在時刻 $t_2$ 的期貨價格 
$F_{t_1}^*$ 替代的標的資產在時刻 $t_1$ 的期貨價格


現在考慮一間公司在時刻 $t=t_1$ 時使用 Short contract 並且在時刻 $t=t_2$ closed its position (注意:當我們說 closed some position 我們指的是進入一個相反的position;在此例中因為原本是使用Short contract,所以要close的話就是要進入一個 Long contract)。
則他會得到的收益為

$S_{t_2} + F_{t_1}^* - F_{t_2}^*$

上式可進一步改寫為

$\Rightarrow (S_{t_2} - S_{t_2}^*) + (S_{t_2}^* - F_{t_2}^*) + F_{t_1}^*  $

上述的前兩項 即為基差 (Basis Risk)
 $(S_{t_2} - S_{t_2}^*)$ : 表示 標的資產不匹配
$ (S_{t_2}^* - F_{t_2}^* )$ : 表示 到期時間不匹配

那麼身為投資者該做的事情便是盡可能讓上述兩種基差來源減小到最低。這便是所謂的最佳避險策略 (這邊的最佳:指的是 最小變異避險策略) 的方法。之後我們會再討論如何透過數學來幫助我們辦到最佳避險。

延伸閱讀
[衍生商品] 遠期合約 與 期貨 的異同

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

2014年2月1日 星期六

[分享] 解決 Office 2011 for mac 無法正常使用 MathType 的問題

大家好,這次主要要介紹Microsoft Office 2011 for mac 在安裝MathType無法正常開啓的問題。此文僅簡單翻譯MathType官網的解決步驟:


1. 首先,要先移除所有的 OLE registration database 檔案,總共有兩處。方法如下

先打開 Macintosh HD/Users/Your Home folder/ 此時應該可以看到一個房屋的圖示


接著進入房屋後,點選左上選單的 前往 (Go) ->前往檔案夾 -> 輸入 Library



找到下列的資料夾
Application Support/Microsoft/Office/Preferences/Office 2011/.
並于資料夾中搜尋此檔案: OLE Registration Database 
如果有此檔案請刪除


接著再到另一個資料夾:
Macintosh HD/Users/Home folder/Library/Preferences/Microsoft/Office 2011/.
並于資料夾中搜尋此檔案: OLE Registration Database 
如果有此檔案請刪除

兩個檔案都長下面這樣



2. 接著,為了讓上述OLE Registration Database恢復。請開啓Office Word 並開啟一個新的空白文件。接著再將之關閉(無需儲存),則OLE檔即可被產生

3. 最後,至http://www.dessci.com/en/dl 下載最新版MathType
重新安裝MathType (無需先移除原先已安裝的MathType)

至此,word 應可正常使用MathType.