[最佳化理論] Conjugate Direction Methods (1) - Basic Algorithm for Quadratic Objective function

再接續前面介紹過的 [最佳化理論] 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