[最佳化理論] Conjugate Direction Methods (2) - The Conjugate Gradient Algorithm for Quadratic Objective function

OK，現在接續前面兩篇

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

這次要來解決如何找到 Conjugate Direction的辦法。幫助我們找到 Conjugate Direction 的方法稱作 共軛梯度演算法 (Conjugate Gradient algorithm) 。

此演算法 藉由 梯度的幫助，使得在任意跌代步驟中，Conjugate Direction 可以由 前一個跌代步的方向 與 現在的 梯度做線性組合來計算出來。且用此法所產生的 Direction 可以保證是 每個方向都是互為 Q-conjugate。故名為 Conjugate Gradient Algorithm；最後我們會給出一個以 二階具有 $n=3$ 個變數的目標函數 作為例子來展示這套方法。

===============

如前所述，考慮標準二階目標函數
$$J(u) = \frac{1}{2} u^T Q u - u^T b, \ u \in \mathbb{R}^n$$
其中 $Q = Q^T >0$。

現在我們來看看Conjugate Gradient Algorithm 是如何找到 Conjugate Direction：

對 初始跌代步：$k=0$。
給定任意初始值 $x^{(0)}$ ，且設定 初始方向為最陡坡度(steepest descent)方向，亦即

$d^{(0)} = - \bigtriangledown J(u^{(0)})$

因此 $u^{(1)} = u^{(0)} + \alpha_0 d^{(0)}$

其中 $\alpha_0$ 一般而言是由line search (一般而言使用MATLAB fminsearch 指令較為簡便)得到，亦即 $\alpha_0 = \arg \min J(x^{(0)} + \alpha d^{(0)})$
不過如果是 考慮 二階目標函數中，則我們可以求得精確的 $\alpha_k$ 如下式
$$\alpha_0 = \arg \min J(x^{(0)} + \alpha d^{(0)}) =  - \frac{{\bigtriangledown^T J({u^{(k)}}){d^{(k)}}}}{{{d^{(k)T}}Q{d^{(k)}}}}$$ 在算出 $u^{(1)}$ 之後，接著我們移動到下一個跌代步。
因為我們要找到 $d^{(1)}$ 且 此方向與 $d^{(0)}$ 互為Q-conjugate。所以如前所述我們選擇
$$d^{(1)} = \text {linear combination of } \bigtriangledown J(u^{(1)}) \ \& \ d^{(0)}$$ 亦即，對 $k+1$ 跌代步的時候 我們選
$$d^{(k+1)} = - \bigtriangledown J(u^{(k+1)}) + \beta_k \cdot d^{(k)} \ \ \ ,k=0,1,2,...$$

其中 $\beta_k = - \frac{{\bigtriangledown^T J({u^{(k+1)}}){d^{(k)}}}}{{{d^{(k)T}}Q{d^{(k)}}}}$

=========================
我們將 Conjugate Gradient Algorithm (for Quadratic Objective Function) 總結如下8個步驟：

1. 在 $k=0$ 時候給定初始值 $u^{(0)}$
2. 計算初始梯度 $\bigtriangledown J(u^{(0)})$ ，且設令其為初始方向 $d^{(0)} = - \bigtriangledown J(u^{(0)})$ ：注意，如果 $\bigtriangledown J(u^{(0)}) = 0$ 則跌代停止
3. 決定 $\alpha_k = - \frac{{\bigtriangledown^T J({u^{(k)}}){d^{(k)}}}}{{{d^{(k)T}}Q{d^{(k)}}}}$
4. 計算 $u^{(k+1)} = u^{(k)} + \alpha_k d^{(k)}$
5. 計算下一個跌代的梯度：  $\bigtriangledown J(u^{(k+1)})$；如果 $\bigtriangledown J(u^{(0)}) = 0$ 則跌代停止
6. 計算 $\beta_k = - \frac{{\bigtriangledown^T J({u^{(k+1)}}){d^{(k)}}}}{{{d^{(k)T}}Q{d^{(k)}}}}$
7. 計算下一個Conjugate 方向 $d^{(k+1)} = - \bigtriangledown J(u^{(k+1)}) + \beta_k \cdot d^{(k)}$
8. 令 $k=k+1$ 並重覆到step 3

下面我們將給個例子來驗證上述的方法。

=================

Example:
考慮下列二階 目標函數
$$J({u_1},{u_2},{u_3}) = \frac{3}{2}u_1^2 + 2u_2^2 + \frac{3}{2}u_3^2 + u_1u_3 + 2u_2u_3 - 3{u_1} - {u_3}$$ 令初始值為 $u^{(0) } = [0, \ 0, \ 0]^T$ 求使用 Conjugate Gradient Method 找出最佳解。

Solution

首先觀察二階 目標函數，我們可以將其改寫成矩陣型式如下

$J(u) = \frac{1}{2} u^T Q u - u^T b$

$\Rightarrow J(u)= \frac{1}{2}\left[ {\begin{array}{*{20}{c}}{{u_1}}&{{u_2}}&{{u_3}}\end{array}} \right]\left[ {\begin{array}{*{20}{c}}3&0&1\\0&4&2\\1&2&3\end{array}} \right]\left[ {\begin{array}{*{20}{c}}{{u_1}}\\{{u_2}}\\{{u_3}}\end{array}} \right] - \left[ {\begin{array}{*{20}{c}}{{u_1}}&{{u_2}}&{{u_3}}\end{array}} \right]\left[ {\begin{array}{*{20}{c}}3\\0\\1\end{array}} \right]$

接著我們計算梯度：

$\bigtriangledown J(u) = Q u - b = \left[ {\begin{array}{*{20}{c}}{3{u_1} + {u_3} - 3}\\{4{u_2} + 2{u_3}}\\{{u_1} + 2{u_2} + 3{u_3} - 1}\end{array}} \right]$

在使用 Conjugate Gradient Method之前我們可以先看看其最佳解落在哪裡：
由一階必要條件  $\bigtriangledown J(u^*)=0$ 與二階充分條件 $\bigtriangledown^2 J(u^*) >0$ 可知最佳解為

 $u^* = Q^{-1}b = [1, 0, 0]^T$

現在我們開始用 Conjugate Gradient Method 來看看會
現在由步驟2可知初始梯度為

$\bigtriangledown J(u^{(0)}) = Q u^{(0)} - b = \left[ {\begin{array}{*{20}{c}}{ - 3}\\{0}\\{ - 1}\end{array}} \right]$

故 初始Conjugate direction

$d^{(0)} = -\bigtriangledown J(u^{(0)}) =\left[ {\begin{array}{*{20}{c}}{  3}\\{0}\\{  1}\end{array}} \right]$

接著由步驟3 我們可以計算 初始 $\alpha_k$

 $\alpha_0 = - \frac{{\bigtriangledown^T J({u^{(0)}}){d^{(0)}}}}{{{d^{(0)T}}Q{d^{(0)}}}} = \frac{10}{36} = 0.2778$

接著由步驟4 ： $u^{(k+1)} = u^{(k)} + \alpha_k d^{(k)}$ 可以算出

$u^{(1)} = u^{(0)} + \alpha_0 d^{(0)} = [0.8333,\ 0, \ 0.2778]^T$

接著由步驟5：計算下一個跌代的梯度：  $\bigtriangledown J(u^{(k+1)})$

$\bigtriangledown J(u^{(1)}) = Q u^{(1)} - b =  [-0.2222,\ 0.5566, \ 0.6667]^T$

接著由步驟6：計算  $\beta_k$

$\beta_0 = - \frac{{\bigtriangledown^T J({u^{(1)}}){d^{(0)}}}}{{{d^{(0)T}}Q{d^{(0)}}}} = 0.08025$

再者由步驟7 ：計算下一個Conjugate 方向 $d^{(k+1)}$

 $d^{(1)} = - \bigtriangledown J(u^{(1)}) + \beta_0 \cdot d^{(0)} = [0.4630, -0.5556, -0.5864]^T$

再來回到步驟3 重複前述步驟

最後會得到 $u^{(3)} = u^{(2)} + \alpha_2 d^{(2)} = [1, \ 0, \ 0]^T$ 且 $\bigtriangledown J(u^{(3)}) = 0$

上述表示在第三步的時候收斂到最佳解。此結果確實說明了 Conjugate Direction Method 保證對二階 具有 n變數的 目標函數 能夠在 n次跌代之內收斂。此例 n=3 故在第3次跌代的時候即收斂到最佳解。

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

---

延伸閱讀

[最佳化理論] Conjugate Direction Methods (0) -Theory

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