再接續前面介紹過的 [最佳化理論] Conjugate Direction Methods (0) -Theory
這次我們要介紹 Basic Conjugate Direction Methods 對於 標準二階目標函數的應用。現在考慮下列標準 二階 具有 n 個變數的目標函數
\[
J(u) = \frac{1}{2} u^T Q u + b^T u +c
\] 其中 $Q=Q^T >0$ 且 $u \in \mathbb{R}^n$
Comments:
注意到標準二階目標函數，我們知道 其真正的最佳解為何。 (why?)
由 一階必要條件 FONC： $\bigtriangledown J(u^*) =0$ 可知
\[
\bigtriangledown J^T(u) = \frac{1}{2} \left[ {{{\left( {Qu} \right)}^T} + {u^T}Q} \right] + {b^T} = 0
\]因為 $Q^T = Q$ ，上式可改寫
\[ \bigtriangledown J(u) = Q u + {b} = 0 \Rightarrow u^* = - {Q^{ - 1}}b \]再者檢驗二階充分條件 SOSC (Hessian Condition): ($\bigtriangledown^2 J(u^*) > 0$)
$ \bigtriangledown^2 J(u) =Q $ 又因為我們說 $Q$ 為正定矩陣。故 $ \bigtriangledown^2 J(u) =Q >0 $； 亦即 $u^* = - {Q^{ - 1}}b$ 為 Strong Local minimum (在此例中， $u^* = {Q^{ - 1}}b$ 亦為 Global minimum)。
------------------
對於上述的標準二階目標函數而言，Conjugate Direction Algorithm 設計如下
============================
Basic Conjugate Direction Algorithm
給定初始值 $u^{(0)}$ 與 Q-conjugate 方向 $d^{(0)}, d^{(1)}, ..., d^{(n-1)}$；對 $k \geq 0$
$ {{g^{(k)}}} = \bigtriangledown J(u^{(k)}) = Q u^{(k)} - b$
${\alpha _k} = - \frac{{{g^{(k)T}}{d^{(k)}}}}{{{d^{(k){{T}}}}{{Q}}{d^{(k)}}}} $
${u^{(k + 1)}} = {u^{(k)}} + {\alpha _k}{d^{(k)}}$
============================
回憶之前我們曾經提過 Conjugate Direction Method對標準二階 n變數的 目標函數可以在 n 步內找到最佳解。在此我們並不證明這個重要結果。只把它紀錄如下：
=============
Theorem: Quadratic Convergence Property
考慮 $J(u) = \frac{1}{2} u^T Q u + b^T u + c$ 其中 $Q=Q^T >0$ 且 $u \in \mathbb{R}^n$ 。那麼對任意初始值 $u^{(0)}$ ，上述 Basic Conjugate Direction Algorithm 可以最多在 $n$ 步收斂到最佳解 $u^{*} = -Q^{-1} b$
=============
Proof: Omitted.
=============
至此我們知道了基本的Basic Conjugate Direction Algorithm，也知道其確實十分有效率 (至少對二階具有 $n$ 個變數的目標函數 由前述定理可知 在 $n$ 步之內收斂 )；但問題是如果我們回頭檢查 Conjugate Direction Algorithm 會發現儘管有辦法給定初始值，其 Q-conjugate direction仍然未定。下一篇將會介紹 如何 在 跌代過程中順便把 Conjugate direction 也產生出來的演算法 (此法稱作 Conjugate Gradient Method )。
ref: E. K. P. Chong, S. H. Zak, An Introduction to Optimization 2nd.
====
延伸閱讀
[最佳化理論] Conjugate Direction Methods (2) - The Conjugate Gradient Algorithm for Quadratic Objective function
這次我們要介紹 Basic Conjugate Direction Methods 對於 標準二階目標函數的應用。現在考慮下列標準 二階 具有 n 個變數的目標函數
\[
J(u) = \frac{1}{2} u^T Q u + b^T u +c
\] 其中 $Q=Q^T >0$ 且 $u \in \mathbb{R}^n$
Comments:
注意到標準二階目標函數，我們知道 其真正的最佳解為何。 (why?)
由 一階必要條件 FONC： $\bigtriangledown J(u^*) =0$ 可知
\[
\bigtriangledown J^T(u) = \frac{1}{2} \left[ {{{\left( {Qu} \right)}^T} + {u^T}Q} \right] + {b^T} = 0
\]因為 $Q^T = Q$ ，上式可改寫
\[ \bigtriangledown J(u) = Q u + {b} = 0 \Rightarrow u^* = - {Q^{ - 1}}b \]再者檢驗二階充分條件 SOSC (Hessian Condition): ($\bigtriangledown^2 J(u^*) > 0$)
$ \bigtriangledown^2 J(u) =Q $ 又因為我們說 $Q$ 為正定矩陣。故 $ \bigtriangledown^2 J(u) =Q >0 $； 亦即 $u^* = - {Q^{ - 1}}b$ 為 Strong Local minimum (在此例中， $u^* = {Q^{ - 1}}b$ 亦為 Global minimum)。
------------------
對於上述的標準二階目標函數而言，Conjugate Direction Algorithm 設計如下
============================
Basic Conjugate Direction Algorithm
給定初始值 $u^{(0)}$ 與 Q-conjugate 方向 $d^{(0)}, d^{(1)}, ..., d^{(n-1)}$；對 $k \geq 0$
$ {{g^{(k)}}} = \bigtriangledown J(u^{(k)}) = Q u^{(k)} - b$
${\alpha _k} = - \frac{{{g^{(k)T}}{d^{(k)}}}}{{{d^{(k){{T}}}}{{Q}}{d^{(k)}}}} $
${u^{(k + 1)}} = {u^{(k)}} + {\alpha _k}{d^{(k)}}$
============================
回憶之前我們曾經提過 Conjugate Direction Method對標準二階 n變數的 目標函數可以在 n 步內找到最佳解。在此我們並不證明這個重要結果。只把它紀錄如下：
=============
Theorem: Quadratic Convergence Property
考慮 $J(u) = \frac{1}{2} u^T Q u + b^T u + c$ 其中 $Q=Q^T >0$ 且 $u \in \mathbb{R}^n$ 。那麼對任意初始值 $u^{(0)}$ ，上述 Basic Conjugate Direction Algorithm 可以最多在 $n$ 步收斂到最佳解 $u^{*} = -Q^{-1} b$
=============
Proof: Omitted.
=============
至此我們知道了基本的Basic Conjugate Direction Algorithm，也知道其確實十分有效率 (至少對二階具有 $n$ 個變數的目標函數 由前述定理可知 在 $n$ 步之內收斂 )；但問題是如果我們回頭檢查 Conjugate Direction Algorithm 會發現儘管有辦法給定初始值，其 Q-conjugate direction仍然未定。下一篇將會介紹 如何 在 跌代過程中順便把 Conjugate direction 也產生出來的演算法 (此法稱作 Conjugate Gradient Method )。
ref: E. K. P. Chong, S. H. Zak, An Introduction to Optimization 2nd.
延伸閱讀
[最佳化理論] Conjugate Direction Methods (2) - The Conjugate Gradient Algorithm for Quadratic Objective function
留言
張貼留言