Gauss-Newton算法是解決非線性最優問題的常見算法之一，最近研讀開源項目代碼，又碰到了，索性深入看下。本次講解内容如下：
基本數學名詞識記
牛頓法推導、算法步驟、計算執行個體
高斯牛頓法推導(如何從牛頓法派生)、算法步驟、程式設計執行個體
高斯牛頓法優劣總結
一、基本概念定義
1.非線性方程定義及最優化方法簡述
指因變量與自變量之間的關系不是線性的關系，比如平方關系、對數關系、指數關系、三角函數關系等等。對于此類方程，求解n元實函數f在整個n維向量空間Rn上的最優值點往往很難得到精确解，經常需要求近似解問題。
求解該最優化問題的方法大多是逐次一維搜尋的疊代算法，基本思想是在一個近似點處標明一個有利于搜尋方向，沿這個方向進行一維搜尋，得到新的近似點。如此反複疊代，知道滿足預定的精度要求為止。根據搜尋方向的取法不同，這類疊代算法可分為兩類：
解析法：需要用目标函數的到函數，
梯度法：又稱最速下降法，是早期的解析法，收斂速度較慢
牛頓法：收斂速度快，但不穩定，計算也較困難。高斯牛頓法基于其改進，但目标作用不同
共轭梯度法：收斂較快，效果好
變尺度法：效率較高，常用DFP法(Davidon Fletcher Powell)
直接法：不涉及導數，隻用到函數值。有交替方向法(又稱坐标輪換法)、模式搜尋法、旋轉方向法、鮑威爾共轭方向法和單純形加速法等。
2.非線性最小二乘問題
非線性最小二乘問題來自于非線性回歸，即通過觀察自變量和因變量資料，求非線性目标函數的系數參數，使得函數模型與觀測量盡量相似。
高斯牛頓法解決非線性最小二乘問題的最基本方法，并且它隻能處理二次函數。(使用時必須将目标函數轉化為二次的)
Unlike Newton'smethod, the Gauss–Newton algorithm can only be used to minimize a sum ofsquared function values
3.基本數學表達
a.梯度gradient，由多元函數的各個偏導數組成的向量
以二進制函數為例，其梯度為：
b.黑森矩陣Hessian matrix，由多元函數的二階偏導數組成的方陣，描述函數的局部曲率，以二進制函數為例，
c.雅可比矩陣 Jacobian matrix，是多元函數一階偏導數以一定方式排列成的矩陣，展現了一個可微方程與給出點的最優線性逼近。以二進制函數為例，
如果擴充多元的話F: Rn-> Rm，則雅可比矩陣是一個m行n列的矩陣：
雅可比矩陣作用，如果P是Rn中的一點，F在P點可微分，那麼在這一點的導數由JF(P)給出，在此情況下，由F(P)描述的線性算子即接近點P的F的最優線性逼近：
d.殘差 residual，表示實際觀測值與估計值(拟合值)之間的差
二、牛頓法
牛頓法的基本思想是采用多項式函數來逼近給定的函數值，然後求出極小點的估計值，重複操作，直到達到一定精度為止。
1.考慮如下一維無限制的極小化問題：
是以，一維牛頓法的計算步驟如下：
需要注意的是，牛頓法在求極值的時候，如果初始點選取不好，則可能不收斂于極小點
2.下面給出多元無限制極值的情形：
若非線性目标函數f(x)具有二階連續偏導，在x(k)為其極小點的某一近似，在這一點取f(x)的二階泰勒展開，即：
如果f(x)是二次函數，則其黑森矩陣H為常數，式(1)是精确的(等于号)，在這種情況下，從任意一點處罰，用式(2)隻要一步可求出f(x)的極小點(假設黑森矩陣正定，所有特征值大于0)
如果f(x)不是二次函數，式(1)僅是一個近似表達式，此時，按式(2)求得的極小點，隻是f(x)的近似極小點。在這種情況下，常按照下面選取搜尋方向：
牛頓法收斂的速度很快，當f(x)的二階導數及其黑森矩陣的逆矩陣便于計算時，這一方法非常有效。【但通常黑森矩陣很不好求】
3.下面給出一個實際計算例子。
例：試用牛頓法求
的極小值
解：
【f(x)是二次函數，H矩陣為常數，隻要任意點出發，隻要一步即可求出極小點】
三、牛頓高斯法
1. gauss-newton是如何由上述派生的
有時候為了拟合資料，比如根據重投影誤差求相機位姿(R,T為方程系數)，常常将求解模型轉化為非線性最小二乘問題。高斯牛頓法正是用于解決非線性最小二乘問題，達到資料拟合、參數估計和函數估計的目的。
假設我們研究如下形式的非線性最小二乘問題：
這兩個位置間殘差（重投影誤差）：
如果有大量觀測點(多元)，我們可以通過選擇合理的T使得殘差的平方和最小求得兩個相機之間的位姿。機器視覺這塊暫時不擴充，接着說怎麼求非線性最小二乘問題。
若用牛頓法求式3，則牛頓疊代公式為：
看到這裡大家都明白高斯牛頓和牛頓法的差異了吧，就在這疊代項上。經典高斯牛頓算法疊代步長λ為1.
那回過頭來，高斯牛頓法裡為啥要舍棄黑森矩陣的二階偏導數呢？主要問題是因為牛頓法中Hessian矩陣中的二階資訊項通常難以計算或者花費的工作量很大，而利用整個H的割線近似也不可取，因為在計算梯度
時已經得到J(x)，這樣H中的一階資訊項JTJ幾乎是現成的。鑒于此，為了簡化計算，獲得有效算法，我們可用一階導數資訊逼近二階資訊項。注意這麼幹的前提是，殘差r接近于零或者接近線性函數進而
接近與零時，二階資訊項才可以忽略。通常稱為“小殘量問題”，否則高斯牛頓法不收斂。
3. 舉例
接下來的代碼裡并沒有保證算法收斂的機制，在例子2的自嗨中可以看到劣勢。關于自變量維數，代碼可以支援多元，但兩個例子都是一維的，比如例子1中隻有年份t，其實可以增加其他因素的，不必在意。
例子1，根據美國1815年至1885年資料，估計人口模型中的參數A和B。如下表所示，已知年份和人口總量，及人口模型方程，求方程中的參數。
運作結果：
A=7.0,B=0.26 (初始值，A=6,B=0.3)，100次疊代到第4次就收斂了。
若初始值A=1,B=1，則要疊代14次收斂。
下圖為根據上面得到的A、B系數，利用matlab拟合的人口模型曲線
例子2：我想要拟合如下模型，
由于缺乏觀測量，就自導自演，假設4個參數已知A=5,B=1,C=10,D=2，構造100個随機數作為x的觀測值，計算相應的函數觀測值。然後，利用這些觀測值，反推4個參數。
運作結果，得到的參數并不夠理想，50次後收斂了
下圖中，每次疊代殘差并沒有持續減少，有反複
4．優缺點分析
優點：
對于零殘量問題，即r=0，有局部二階收斂速度
對于小殘量問題，即r較小或接近線性，有快的局部收斂速度
對于線性最小二乘問題，一步達到極小點
缺點：
對于不是很嚴重的大殘量問題，有較慢的局部收斂速度
對于殘量很大的問題或r的非線性程度很大的問題，不收斂
不一定總體收斂
如果J不滿秩，則方法無定義
對于它的缺點，我們通過增加線性搜尋政策，保證目标函數每一步下降，對于幾乎所有非線性最小二乘問題，它都具有局部收斂性及總體收斂，即所謂的阻尼高斯牛頓法。
其中，ak為一維搜尋因子