想法:透過二次函數近似 (quadratic fit) 目標函數 J(u) 並以此找出最小值。
現在考慮在時間 k ,我們有 uk∈Rn 與對應的成本函數 J(uk);
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+1−uk,我們可將上式進一步改寫
uk+1−uk=−[∇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:Rn→R:
J(u)=12uTAu+bTu+c, A≻0還沒使用Newton Method之前,我們可先由一階必要條件 (First order necessary condtion, FONC): ∇J(u)=0 得知最佳解應該長甚麼樣:
∇J(u)|u∗=Au∗+b=0⇒u∗=−A−1b且由二階充分條件(Second order sufficient condition, SOSC) ∇2J(u)≻0,可得 ∇2J(u∗)=A≻0,故 u∗=−A−1b 為上述二階目標函數的最佳解。
現在我們看看用上Newton Method會發生甚麼事情:
uk+1=uk−[∇2J(uk)]−1(∇J(uk))考慮 k=0的時候我們有
u1=u0−A−1(Au0+b)⇒u1=A−1b=u∗ 故由上述討論可知確實Newton Method 一步就收斂。 ◻
現在我們來看個實際的例子:
======================
Example
考慮如下目標函數
J(u)=(11−u1−u2)2+(1+10u2+u1−u1u2)2 且給定初始條件 u0=[18,3]T (任意給定)
1. 試用FONC與SOSC求解最佳解 u∗
2. 試用Newton Method 求 u1 與 u2。
3. 試比較此兩種方法之解
Solution:
讀者可事先計算上述目標函數之最佳解(滿足FONC與SOSC)為 u∗=[13,4]T。
現在我們看看Newton Method有甚麼效果?
在使用 Newton Method之前需要兩個資訊:Gradient 與 Hessian,故我們依序計算如下:
∇J(u)=[∂J∂u1∂J∂u2]⇒∇J(u)=[−2(11−u1−u2)+2(1+10u2+u1−u1u2)(1−u2)−2(11−u1−u2)+2(1+10u2+u1−u1u2)(10−u1)]⇒∇J(u0)=[40100]
Hessian:
∇2J(u)=[2(u2−1)2+24(u1(u2−1)−10u2+5)4(u1(u2−1)−10u2+5)2(u1−10)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.
∇J(u)|u∗=Au∗+b=0⇒u∗=−A−1b且由二階充分條件(Second order sufficient condition, SOSC) ∇2J(u)≻0,可得 ∇2J(u∗)=A≻0,故 u∗=−A−1b 為上述二階目標函數的最佳解。
現在我們看看用上Newton Method會發生甚麼事情:
uk+1=uk−[∇2J(uk)]−1(∇J(uk))考慮 k=0的時候我們有
u1=u0−A−1(Au0+b)⇒u1=A−1b=u∗ 故由上述討論可知確實Newton Method 一步就收斂。 ◻
現在我們來看個實際的例子:
======================
Example
考慮如下目標函數
J(u)=(11−u1−u2)2+(1+10u2+u1−u1u2)2 且給定初始條件 u0=[18,3]T (任意給定)
1. 試用FONC與SOSC求解最佳解 u∗
2. 試用Newton Method 求 u1 與 u2。
3. 試比較此兩種方法之解
Solution:
讀者可事先計算上述目標函數之最佳解(滿足FONC與SOSC)為 u∗=[13,4]T。
現在我們看看Newton Method有甚麼效果?
在使用 Newton Method之前需要兩個資訊:Gradient 與 Hessian,故我們依序計算如下:
∇J(u)=[∂J∂u1∂J∂u2]⇒∇J(u)=[−2(11−u1−u2)+2(1+10u2+u1−u1u2)(1−u2)−2(11−u1−u2)+2(1+10u2+u1−u1u2)(10−u1)]⇒∇J(u0)=[40100]
Hessian:
∇2J(u)=[2(u2−1)2+24(u1(u2−1)−10u2+5)4(u1(u2−1)−10u2+5)2(u1−10)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.
沒有留言:
張貼留言