Gauss-Newton Method 高斯牛頓法（最佳化簡介）

上一篇文章提到牛頓法中要計算 Hessian matrix 的時間與空間的複雜度太大，而高斯牛頓法的精神就是去近似 Hessian matrix 進而降低梯度。高斯牛頓法的前提是這個最佳化問題必須為 least square problem，也就是以下式子： $$x^* = arg\ \underset{x}{min}\ F(x), \\ F(x) = \frac{1}{2} \sum_{i=1}^{m}(f_i(x))^2 = \frac{1}{2}\parallel f(x) \parallel ^2 = \frac{1}{2}f(x)^Tf(x)$$ 以上的問題當然可以用上一篇文章談的梯度下降法或牛頓法來解，但是如果用高斯牛頓法的話會更有效率。

簡介高斯牛頓法

高斯牛頓法的概念是去近似 $f(x)$，如果用泰勒展開式展開 $f(x)$ 可得： $$f(x + \Delta x) \approx f(x) + J(x)\Delta x$$ 注意在這邊 $x$ 與 $\Delta x$ 都是 n 維的向量，而 J(x) 是 m by n 的 Jacobian matrix： $$J(x) = \begin{bmatrix} \frac{\partial f_1(x)}{\partial x_1} & ... & \frac{\partial f_1(x)}{\partial x_n}\\ \vdots & \ddots & \vdots \\ \frac{\partial f_m(x)}{\partial x_1} & ... & \frac{\partial f_m(x)}{\partial x_n} \end{bmatrix}$$ 回到我們要求解的問題，也就是想找 $\Delta x$ 使得 $F(x + \Delta x)$ 最小，也就是： $$\Delta x^* = arg\ \underset{\Delta x}{min}\ F(x + \Delta x) \\ = arg\ \underset{\Delta x}{min}\ \frac{1}{2}\parallel f(x + \Delta x) \parallel ^2 \\ \approx arg\ \underset{\Delta x}{min}\ \frac{1}{2}\parallel f(x) + J(x)\Delta x \parallel ^2 \\ = arg\ \underset{\Delta x}{min}\ \frac{1}{2}( f(x) + J(x)\Delta x)^T( f(x) + J(x)\Delta x) \\ = arg\ \underset{\Delta x}{min}\ \frac{1}{2}(\parallel f(x) \parallel_2^2 + 2\Delta x^T J(x)^T f(x) + \Delta x^TJ(x)^T J(x)\Delta x )$$ 取對於 $\Delta x$ 的導數並設為零求極值： $$J(x)^T f(x) + J(x)^T J(x) \Delta x = 0$$ 可以求得 $\Delta x$： $$\Delta x = - (J(x)^T J(x))^{-1}J(x)^T f(x)$$ 因此我們就可以利用以下式子一直更新 x： $$x_{k+1} = x_k + \Delta x = x_k - (J(x_k)^T J(x_k))^{-1}J(x_k)^T f(x_k)$$ 跟前一篇文章中牛頓法的式子對照可以看出高斯牛頓法的精神便是拿 $J(x)^T J(x)$ 來近似 Hessian matrix 。

高斯牛頓法的優缺點

實務上來說高斯牛頓法的演算法很簡單，但是由於 $J(x)^T J(x)$ 為半正定矩陣，所以可能出現 ill-condition 的情況，所以高斯牛頓法可能不會收斂。此外當如果求出的 $\Delta x$ 太大時，我們所用的泰勒展開近似式子便不夠準確，也可能會導致不收斂的結果，因此有非線性最佳化領域中有許多方法都是透過改進高斯牛頓法達到最佳化的效果。

參考資料

[1] Methods For Non-Linear Least Squares Problems, Madsen et al. 2004