1、2.6、DFP變尺度法：變尺度法是Davidon由于1959年提出后又經Fletcher和Powell加以發展和完善了后的一種變尺度法，故稱DFP變尺度法1、基本思想： 變尺度法是克服了梯度法收斂慢和牛頓法計算量大的缺點而發展起來的，是求解無約束問題最有效的算法，在工程優化設計中得到了廣泛的應用。 利用牛頓法的迭代公式，然后并不是直接計算 1)()(kxH而是 用一個對稱正定矩陣 )()(kxG近似 地代替 ,)(1)(kxH)()(kxG在迭代過程中不斷改進。 最后逼近 1)()(kxH這種方法省去了海色矩陣的計算和求逆，計算量大為減少。3、迭代計算公式：令 )()()()()(KKKxfx

2、GS則迭代計算公式為： )()()()()()()()()()1(kkkkkkkkxfxGxSxx若在初始點 )0(x取 IxG)()0(（單位矩陣） 迭代計算公式為： )()()()()1(kkkkxfxx相當于梯度法)(kE為k 次迭代的修正矩陣 )()()1()()(KkkExGxG)()()()()()()()()()()()()()()()()()()()()()()()(kKTkKTkkKkTkTkkkKTkKTkkKkTkTkkkkgGgGggGgxxxgGgGggGgsssE)()1()(kkkxxx即兩迭代點信息之差,位移矢量差 )()()()1()()1()(kkkkkxf

3、xfggg梯度矢量差即兩迭 代點的目標函數一階導數信息之差。4.計算迭代步驟給定初始點 )0(x迭代精度 維數 n置 k0單位矩陣 )0(GI 計算 )0()0()(gxf計算搜索方向 )()()(kkkSgG進行一維搜索求 )(k得迭代計算點 )1()()()(kkkkxSx檢驗是否滿足迭代終止條件： )()1(kxf若滿足，則終止迭代，輸出最優解 )()(*)1(*)1(xfxfxxkk否則進行下一步：檢查迭代次數若 nk 置)0()1( xxk則轉(2) 若 nk 則轉(7) 計算 )1()()()()()()1()()()1()1()1()(kkkkkkkkkkkkGEGExxxggg

4、gxf然后 置 kk1轉(3) 程序框圖見 47p)()()(kkkSgG5、變尺度法的特點迭代第一步為梯度法:在迭代開始時,一般是 IG 0（單位矩陣）此時變尺度法的迭代公式就是梯度法的迭代公式當變尺度矩陣逼近 1)()(kxH時，變尺度法迭代公式逼近牛頓法的迭代公式。例：試用變尺度法求解下列無約束優化問題： 2221)6()5(4)(xxxf的極小點和極小值，取初始點.Tox9,8)(梯度精度 01. 0解：第一次迭代取初始點 Tox9,8)(45)()0(xF目標函數梯度函數為： 1001)6(2)5(8)()0(21IGxxxf計算 )0(x點的梯度值 624)69(2)58(8)()

5、0()0(xfg求 )0(S搜索方向 )()0()0()0(xFGS及新的迭代點 )1 (x)0()0()0()0()0()0()1()0()0()0(69248624986246241001SxxgGS用一維搜索（優化）方法求解最優步長 )0(本題的目標函數簡單，可用解析法求 但因)0(于是得： 2)0(2)0()1(6)69(5)248(4)(xf0)()0()1(dxdf130769. 006124680)0()0(9846. 4)(2154. 88615. 4)1()1(xfx計算 )1 (x點的函數梯度，檢驗迭代終止條件 56719. 4)43076. 4()10784. 1()(4

6、3076. 410784. 1)62154. 8(2)58615. 4(8)(22)1()1()1(xfxfg因此 )1(x不是極小點，則繼續迭代。 第二迭代 TTxxxggg78462. 0,13848. 356924. 1,10784.25)0()1()0()0()1()0(按DFP公式計算近似矩陣 )1(G（變尺度法） 003801. 1031487. 0031487. 012697. 056924. 110784.25100156924. 1,10784.25100156924. 1,10784.2556924. 110784.25100156924. 110784.2578462.

7、0,13848. 378462. 0,13848. 378462. 013848. 31001)0()0()0()0()0()0()0()0()0()0()0()0()1(GggGggGgxxxGGTTTT求搜索方向 )1(S即新的迭代點 )2(x48248. 428017. 043076. 410784. 1003801. 1031487. 003148. 012697. 0)()1()1()1()1()1(xfGgGS沿 )1(S方向進行一維搜索得:00014. 699998. 44942. 0)1()1()1()2()1(Sxx檢驗迭代終止條件。 00032. 0)00028. 0()0

8、0016. 0()(00028. 000016. 0)600014. 6(2)599998. 4(8)(22)2()2(xfxf滿足精度要求，迭代結束，輸出最優解： 8)2(*)2(*101 . 2)()(00014. 6,99998. 4xfxfxxT總結： 變尺度法的最初的幾步迭代與梯度法類似，函數值下降較快而在最后的幾步迭代，與牛頓法相近可較快地收斂為極小點。變尺度法能夠克服梯度法收斂慢的缺點，但卻保留了梯度法在最初幾步函數值下降快的優點。同時，變尺度法避免了計算海色矩陣及其逆陣。從而克服了牛頓法計算量大的缺點，變尺度法的收斂速度介于梯度法和牛頓法之間。說明:)(xf變尺度法所構成的搜索方向 已有文