[最佳化] 淺談 Steepest Descent Method (0) -Why Steepest !?

這次要介紹的是最陡坡度法(Steepest Descent Method)，又稱 Gradient descent method：

想法：透過負梯度 (negative gradient) 作為最陡坡度，逐步找到 (局部)最小值 (最佳解 $u^*$)

這個演算法需要甚麼呢?

1. 初始條件 $u^0$
2. 固定的跌代步長(fixed step size): $h$
3. Steepest Descent 的跌代架構(iterative scheme) $$u^{k+1} = u^k - h \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||}$$
4. 演算法停止判別機制(stopping criterion) : EX: 給定誤差 $\varepsilon>0$，檢驗 $$||\nabla J(u^k)|| < \varepsilon$$

那麼現在我們來解決一個問題：

為什麼此法被稱作 "最陡" 坡度? 
也就是說 為什麼Iterative scheme 中的方向 $\nabla J(u^k)$ 被稱做是最陡(Steepest)方向??

考慮目標函數 $J: \mathbb{R}^n \rightarrow \mathbb{R}$，其在某點 $u^0 \in \mathbb{R}$ 與方向$v$ 的方向導數(Directional derivative at point $u^0$ in direction $v$)定義如下：

$${\left. {\frac{{\partial J\left( u \right)}}{{\partial v}}} \right|_{u = {u^0}}}: = {\left[ {\nabla J({u^0})} \right]^T} \cdot \frac{v}{{\left\| v \right\|}}$$ 由Cauchy-Schwarz inequality $\left| {{x^T}y} \right| \le \left\| x \right\|\left\| y \right\|$，可推得上式如下：
$$\left| {{{\left[ {\nabla J({u^0})} \right]}^T} \cdot \frac{v}{{\left\| v \right\|}}} \right| \le \left\| {\nabla J({u^0})} \right\|\frac{{\left\| v \right\|}}{{\left\| v \right\|}}$$ 現在如果我們把方向 $v$ 選成梯度方向，亦即

$$v = \nabla J(u^0)$$ 則可發現上述不等式變成
$$\begin{array}{l}  \Rightarrow \left| {{{\left[ {\nabla J({u^0})} \right]}^T} \cdot \frac{{\nabla J({u^0})}}{{\left\| {\nabla J({u^0})} \right\|}}} \right| \le \left\| {\nabla J({u^0})} \right\|\\  \Rightarrow \frac{{{{\left\| {\nabla J({u^0})} \right\|}^2}}}{{\left\| {\nabla J({u^0})} \right\|}} \le \left\| {\nabla J({u^0})} \right\|\\  \Rightarrow \left\| {\nabla J({u^0})} \right\| = \left\| {\nabla J({u^0})} \right\| \end{array}$$ 故可知當我們選 $v = \nabla J(u^0)$ Cauchy-Schwarz inequality 的 "等" 式成立，故 $\nabla J(u^0)$ 為使方向導數最大的值! 亦即 最陡方向(Steepest)!

至於為什麼我們說Steepest Descent (最陡坡度下降)，是因為注意到Steepest Descent 演算法中跌代式子

$$u^{k+1} = u^k - h \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||}$$ 的方向為負，亦即 $- \nabla J(u^k)$ !!，故我們是朝著最陡的方向往下逐步得到最佳解(最小值) $u^*$

現在我們給個例子：

Example
考慮如下目標函數
$$J(u) = {\left( {11 - {u_1} - {u_2}} \right)^2} + {\left( {1 + 10{u_2} + {u_1} - {u_1}{u_2}} \right)^2}$$  1. 試證上述目標函數最佳解為 $[13, 4]^T$
2. 繪製其 $0 \le u_1 \le 20$ 與 $0 \le u_2 \le 15$ 的範圍
3. 給定初始值 $u^0 = [8, 12]^T$使用上述 Steepest Descent algorithm 與不同的固定步長 $h=0.01, 1.0$看看發生甚麼事情

Solution:
1. 透過一階必要條件(FONC) 與 二階充分條件(SOSC)即可求得最佳解 $u^* = [13, 4]^T$。在此不贅述。

2. 透過MATLAB contour 指令可以繪製目標函數的等高線圖如下

3. 考慮$u^0 = [8, 12]^T$ ，並考慮 $h=0.01$的情況，透過MATLAB實現上述Steepest Descent Algorithm並限制停止判別為跌代步驟不超過兩千步 $k_{max} := 2,000$。
在約 $k=1000$ 步之後，可收斂到 $u = [13.01, 3.993]$。如下圖所示： (點圖放大)；

若現在考慮 $h=1.0$ 則Steepest Descent 展示了Zig-Zag的現象，最終落在 $u=[12.6, 3.601] to [13.31, 4.08]$之間，且跌代步如下圖所示 (點圖放大)

注意到上述例子中，對於較大的固定步e.g., $h=1.0$ ，Steepest Descent 表現出來回震盪的情況，對於較小的固定步 e.g., $h=0.01$，Steepest Descent 收斂緩慢 (超過一千步才收斂)。

Summary: 
Steepest Descent Algorithm 雖然想法很直覺，但事實上本質有兩個重大的缺點：
1. 注意到Steepest Descent的跌代式子中除了要計算梯度之後，仍需要給定固定步長 $h$，如果固定步長 $h$ 太大!，則會演算法產生衝過頭的情形。也就是說假設 $h=100$ (100步長單位) 當我可能今天只需要1步就到達最佳解，但Steepest Descent Method卻被迫每次都要走步長單位為 $100$ ，則永遠只能在最佳解附近震盪永遠到不了最佳解，

2. 如果固定步長 $h$ 太小，則雖然在某種程度上解決了震盪問題，但此時收斂速度會變得異常緩慢。

如何解決上述的問題!??
我們需要徹底地拔除固定步長的限制，此法稱做 Steepest Descent with Optimal Step Algorithm。
亦即我們將原本的Steepest Descent Algorithm的跌代式中的固定步長 $h$改成動態步長 $h_k$
$$u^{k+1} = u^k - h_k \frac{\nabla J(u^k)}{|| \nabla J(u^k)||}$$ 至於此 $h_k$該怎麼選? 有興趣的讀者可以參考下篇
[最佳化] 淺談 Steepest Descent Method (1) - Optimal step size