Loading [MathJax]/jax/output/CommonHTML/jax.js

2/15/2014

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

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

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


現在考慮在時間 k ,我們有 ukRn 與對應的成本函數 J(uk)

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

現在由於我們欲求極小值(最佳化),故透過一階必要條件(FONC):
J(uk)|Δu=Δu=0 亦即對 Δu 求一階導數並令其為 0 可得
(J(uk)+2J(uk)Δu)|Δu=Δu=0整理上式可得
Δu=[2J(uk)]1(J(uk)) 又由擾動定義 Δu:=uk+1uk,我們可將上式進一步改寫
uk+1uk=[2J(uk)]1(J(uk))uk+1=uk[2J(uk)]1(J(uk))    ()上式 () 的iterative structure稱為 Newton-Rapshon Algorithm

Comments:
1. 注意到 Newton Method 需要兩項資訊:一是 Gradient 另外一個則是 Hessian matrix 的 inverse :[2J(uk)]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:RnR
J(u)=12uTAu+bTu+c, A0還沒使用Newton Method之前,我們可先由一階必要條件 (First order necessary condtion, FONC): J(u)=0 得知最佳解應該長甚麼樣:
J(u)|u=Au+b=0u=A1b且由二階充分條件(Second order sufficient condition, SOSC) 2J(u)0,可得 2J(u)=A0,故 u=A1b 為上述二階目標函數的最佳解。

現在我們看看用上Newton Method會發生甚麼事情:
uk+1=uk[2J(uk)]1(J(uk))考慮 k=0的時候我們有
u1=u0A1(Au0+b)u1=A1b=u 故由上述討論可知確實Newton Method 一步就收斂。


現在我們來看個實際的例子:
======================
Example
考慮如下目標函數
J(u)=(11u1u2)2+(1+10u2+u1u1u2)2 且給定初始條件 u0=[18,3]T (任意給定)

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

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

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

在使用 Newton Method之前需要兩個資訊:Gradient 與 Hessian,故我們依序計算如下:
J(u)=[Ju1Ju2]J(u)=[2(11u1u2)+2(1+10u2+u1u1u2)(1u2)2(11u1u2)+2(1+10u2+u1u1u2)(10u1)]J(u0)=[40100]
Hessian:
2J(u)=[2(u21)2+24(u1(u21)10u2+5)4(u1(u21)10u2+5)2(u110)2+2]2J(u0)=[104444130]

那麼我們用 Newton Method:
uk+1=uk[2J(uk)]1(J(uk))u1=[183][104444130]1[40100]=[19.25791.8570]同樣的我們可計算下一步 u2=[13.265,3.613]T 逐步下去可以發現(在此初始條件之下)確實越來越接近最佳解 u=[13,4]。計算細節在此不再贅述。

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



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

沒有留言:

張貼留言

[人工智慧] 本地端 DeepSeek R1 快速安裝:以 Macbook Pro M4 Chip為例

最近火熱的 DeepSeek R1 模型由於採用了 distill 技術,可以大幅降低計算成本,使得一般人有機會在自家筆電上跑性能逼近 Open AI ChatGPT o1的大語言模型。本文簡單介紹一步安裝在 Macbook Pro 的方法以及使用方法,以下測試採用 Macboo...