[最佳化] 淺談 Steepest Descent Method (1) - Optimal step size

延續上篇文章 [最佳化] 淺談 Steepest Descent Method (0) -Why Steepest !?，這次我們要介紹 Steepest Descent Method with Optimal Step size

修訂後的Steepest Descent Algorithm 需要甚麼呢?

1. 初始條件 $u^0$
2. 最大跌代步長上限(Maximum fixed step size): $H$
3. Steepest Descent with Optimal Step size的跌代架構(iterative scheme) \[u^{k+1} = u^k - h_k \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||} \ \ \ \ (*)\]
4. 演算法停止判別機制(stopping criterion) : EX: \[ ||\nabla J(u^k)|| < \varepsilon\]

那麼問題變成 $h_k$ 該怎麼求?

首先我們考慮第 $k$次 跌代，手上有 $u^k$，則我們可以定義

\[
\tilde J(h) := J(u^k - h \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||})
\]接著我們做 Line search 找出一個最佳的 $h \in [0,H] $ ( 亦即 $\min \tilde J(h)$) 把此 $h$ 稱做 $h_k $，也就是說

\[
\tilde J(h_k) = \displaystyle \min_{h \in [0, H]} \tilde J(h)
\]做Line search之後得到的 $h_k$ 再把他放回 $(*)$ 即可!!

\[
u^{k+1} = u^k - h_k \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||} \ \ \ \ (*)
\]上式即稱為 Steepest Descent with Optimal Step size (此Optimal step 由Line search 對 $ \min J(u^k - h \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||})$ 求得)

對於Steepest Descent Algorithm而言，我們有 現在的跌代步的梯度 與下一個跌代步的梯度互為垂直；亦即
\[
\left ( \nabla J(u^k) \right )^T \cdot \nabla J(u^{k+1}) =0
\]現在如果我們考慮更一般的情況，

===============================
Theorem: (Optimal Descent Condition)
考慮 $v \in \mathbb{R}^n$ 為某一個方向 (不必是梯度)，且假設 $h_k$ 把 $\tilde J(u^k + h \cdot v)$最小化，且我們的跌代式為
\[
u^{k+1} = u^k + h_k \cdot v
\]則我們有 $v^T \cdot \nabla J(u^{k+1}) =0$，我們稱此條件為 Optimal Descent Conditon。
===============================

Proof:
我們欲證  $v^T \cdot \nabla J(u^{k+1}) =0$，

故由  $h_k$ 把 $\tilde J(u^k + h \cdot v)$最小化 的假設，我們已知一階必要條件成立，故可利用一階必要條件FONC
\[\frac{{\partial \tilde J({u^k} + h \cdot v)}}{{\partial h}} = 0
\]為了方便起見，現在令 $z: = {u^k} + h \cdot v$，則上式可推得
\[\begin{array}{l}
\frac{{d\tilde J(z)}}{{dh}} = \frac{{\partial \tilde J(z)}}{{\partial {z_1}}}\frac{{\partial {z_1}}}{{\partial h}} + \frac{{\partial \tilde J(z)}}{{\partial {z_2}}}\frac{{\partial {z_2}}}{{\partial h}}... + \frac{{\partial \tilde J(z)}}{{\partial {z_n}}}\frac{{\partial {z_n}}}{{\partial h}} = 0\\
 \Rightarrow \frac{{d\tilde J(z)}}{{dh}} = \frac{{\partial \tilde J(z)}}{{\partial {z_1}}}{v_1} + \frac{{\partial \tilde J(z)}}{{\partial {z_2}}}{v_2}... + \frac{{\partial \tilde J(z)}}{{\partial {z_n}}}{v_n} = 0\\
 \Rightarrow \frac{{d\tilde J(z)}}{{dh}} = \left[ {\begin{array}{*{20}{c}}
{{v_1}}&{{v_2}}& \cdots &{{v_n}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{\frac{{\partial \tilde J(z)}}{{\partial {z_1}}}}\\
{\frac{{\partial \tilde J(z)}}{{\partial {z_2}}}}\\
 \vdots \\
{\frac{{\partial \tilde J(z)}}{{\partial {z_n}}}}
\end{array}} \right] = 0\\
 \Rightarrow \frac{{d\tilde J(z)}}{{dh}} = {v^T}\nabla \tilde J(z) = {v^T}\nabla \tilde J({u^k} + h \cdot v) = {v^T}\nabla \tilde J({u^{k + 1}}) = 0
\end{array}
\]最後一個等式成立是由於 $h$ 最小化 $\tilde J(u^k + h \cdot v)$，故稱此$h=h_k$，又由跌代式的假設 $u^{k+1} = u^k + h_k \cdot v$。 $\square$


那麼現在我們來看看如果目標函數是標準二次的情況

考慮如下標準二次函數
\[
J(u) = u^T A u + b^T u + c, \ A=A^T, \ A \succ 0
\]注意到上述二次函數可以直接用 一階必要條件FONC ( $\nabla J(u^k) =0$) 與 二階充分條件SOSC ($\nabla^2 J(u^k) \succ 0$) 直接求解，可得最佳解為 $u^* = \frac{1}{2} A^{-1}b$

那麼如果我們現在採用 Steepest Descent Algorithm with Optimal Step size $h_k$ ，我們想要知道選怎樣的 $h_k$ 可以得到同樣的最佳解呢?

故首先給定初始條件 $u^0$, 且給定足夠大的步長上限 $H$，

接著我們寫下 Line Search需要的式子
\[
\tilde J (h) := J(u^k  - h \cdot \nabla J(u^k)) \ \ \ \ (*)
\] ，目標是要找出 $h =?$

首先觀察 $(*)$，我們可以先計算上式的梯度部分，由 FONC 可知梯度為
\[
\nabla J(u^k) = 2 A u^k + b
\]故將其代入 $(*)$ 可得
\[
\tilde J(h): = J\left( {{u^k} - h\left( {2A{u^k} + b} \right)} \right)
\]又因為
\[
J(u) = u^T A u + b^T u + c
\]故可推得
\[\begin{array}{l}
 \Rightarrow \tilde J(h) = {\left( {{u^k} - h\left( {2A{u^k} + b} \right)} \right)^T}A\left( {{u^k} - h\left( {2A{u^k} + b} \right)} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} + {b^T}\left( {{u^k} - h\left( {2A{u^k} + b} \right)} \right) + c
\end{array}
\]由於 $h$ 為最小化 $\tilde J(h)$ 故由FONC對 $h$ 可知 $\frac{d \tilde J(h)}{dh} =0$ 亦即
\[\begin{array}{l}
 \Rightarrow \frac{{d\tilde J(h)}}{{dh}} = 0\\
 \Rightarrow  - {u^k}^TA\left( {2A{u^k} + b} \right) - {\left( {2A{u^k} + b} \right)^T}A{u^k}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} + 2h{\left( {2A{u^k} + b} \right)^T}A\left( {2A{u^k} + b} \right) - {b^T}\left( {2A{u^k} + b} \right) = 0\\
 \Rightarrow {h_k}: = h = \frac{1}{2}\frac{{{{\left( {2A{u^k} + b} \right)}^T}\left( {2A{u^k} + b} \right)}}{{{{\left( {2A{u^k} + b} \right)}^T}A\left( {2A{u^k} + b} \right)}}
\end{array}
\]
Comments:
1. 注意到上式中分母為 ${{{\left( {2A{u^k} + b} \right)}^T}A\left( {2A{u^k} + b} \right)}$ 為 $1 \times 1$ 此時分母不再是矩陣或者向量，故可以直接執行除法。且由於我們的假設 $A$ 矩陣為正定矩陣，亦即 $x^T A x >0, \forall x \neq 0$，仔細觀察上式分母，若令 $x:={\left( {2A{u^k} + b} \right)}$，我們確實得到
\[
{{{\left( {2A{u^k} + b} \right)}^T}A\left( {2A{u^k} + b} \right)} = x^T A x >0
\]