逐次線性化

計算方法

目標函式及約束條件在某一個可行點附近線性化後得出的解點，則在這一點附近將函式或者約束條件進行線性化。

當解點超出可行域範圍時，增加一個限制步長的約束條件，計算中每次疊代所用的步長可以先取用前次疊代的數值，若解點超出可行域則減少這一數值重新求解該線性規劃問題，直到滿足收斂要求並得出極值點。

步長限值的取值對算法的成功與否有很大影響，由於一般都採用較小的步長，所以又稱小步長梯度法。實踐證明這種方法在目標函式為凸函式且可行域為凸集的情況下是收斂的，然而其確切的收斂性能尚未得到充分證明。另外這種方法所需要的疊代次數通常比較多，計算工作量也比較大，且花費的時間也比較多。

假設有

在數值逼近學科中，拉格朗日插值能夠得到n次插值多項式，然而，每當有新的節點增加，原來的計算出的數據均不能利用，需要重新計算，為了克服這個缺點，提出了逐次線性化插值法，由於插值多項式的存在唯一，利用逐次線性插值求出的插值多項式和拉格朗日插值多項式相同。

通過這些點做逐次線性插值，其大體思想如下：

圖2.逐次線性化插值思路