優(yōu)化設計-梯度法和共軛梯度法.pdf

《優(yōu)化設計-梯度法和共軛梯度法.pdf》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。

1、梯度法和共軛梯度法1.無約束最優(yōu)化問題2.梯度法3.共軛梯度法一.無約束最優(yōu)化問題無約束最優(yōu)化問題minf(x)ns.t.x?R其中f(x)有一階連續(xù)偏導數(shù)。解析方法：利用函數(shù)的解析性質構造迭代公式使之收斂到最優(yōu)解。二.梯度法（最速下降法）迭代公式：xk?1?xk??dkk如何選擇下降最快的方向？k?f(x)函數(shù)值增加最快的方向kx函數(shù)值下降的方向k??f(x)函數(shù)值下降最快的方向梯度法（最速下降法）：kk1.搜索方向：d???f(x),也稱為最速下降方向；kkkk2.搜索步長:?取最優(yōu)步長,即滿足f(x??d)?minf(x??d)。kk?梯度法算法步驟：1n1.給定初始點x?

2、R,允許誤差??0,令k?1。kk2.計算搜索方向d???f(x);kk3.若

3、

4、d

5、

6、??,則停止計算，x為所求極值點；否則，求最優(yōu)步長?kkkkk使得f(x??kd)?minf(x??d)。?k?1kk4.令x?x??kd,令k:?k?1,轉2。221T例.用最速下降法求解:minf(x)?x?3x,設初始點為x?(2,1),122求迭代一次后的迭代點x。T解：??f(x)?(2x1,6x2),11T?d???f(x)?(?4,?6).11T?x??d?(2?4?,1?6?).1122令?(?)?f(x??d)?(2?4?)?3(1?6?)，求解min?(?)?13令??(?

7、)??8(2?4?)?36(1?6?)?0??1?6221136?8T?x?x??1d?(,)3131最速下降法的程序流程圖鋸齒現(xiàn)象在極小點附近，目標函數(shù)可以用二次函數(shù)近似，其等值面近似橢球面。2x?x*3x1x注最速下降方向反映了目標函數(shù)的一種局部性質。它只是局部目標函數(shù)值下降最快的方向。最速下降法是線性收斂的算法。三.共軛梯度法共軛梯度法Fletcher?Reeves共軛梯度法:1TTminf(x)?xAx?bx?c2nn其中x?R,A是對稱正定矩陣，b?R，c是常數(shù)?；舅枷耄簩⒐曹椥院妥钏傧陆捣较蛳嘟Y合，利用已知迭代點處的梯度方向構造一組共軛方向，并沿此方向進行搜索，求出

8、函數(shù)的極小點。以下分析算法的具體步驟。(1)(1)(1)(1)任取初始點x，第一個搜索方向取為d???f(x)；(k?1)(k?1)(k?1)(2)設已求得點x，若?f(x)?0，令gk?1??f(x)，(k?1)則下一個搜索方向d按如下方式確定:(k?1)(k)令d??gk?1??kd(1)如何確定?k？(k?1)(k)要求d和d關于A共軛。T(k)則在（1）式兩邊同時左乘dA，得TTT(k)(k?1)(k)(k)(k)0?dAd??dAgk?1??kdAdT(k)dAgk?1解得?k?(2)T(k)(k)dAd(3)搜索步長的確定:(k)(k)已知迭代點x和搜索方向d,利用一

9、維搜索確定最優(yōu)步長?k，(k)(k)即求解minf(x??d)。?(k)(k)記?(?)?f(x??d),(k)(k)T(k)令??(?)??f(x??d)d?0，(k)(k)T(k)即有[A(x??d)?b]d?0，(k)(k)令gk??f(x)?Ax?b，則有(k)T(k)[gk??Ad]d?0，T(k)gkd解得?k??(3)T(k)(k)dAd1TT定理3對于正定二次函數(shù)f(x)?xAx?bx?c，F(xiàn)R算法在m?n次2一維搜索后即終止，并且對所有的（i1?i?m），下列關系成立T(i)(j)(1)dAd?0,j?1,2,?,i?1;T(2)gigj?0,j?1,2,?,i

10、?1;T(i)T(3)gid??gigi。注(1)(2)(m)（1）由定理3可知搜索方向d,d,?,d是A共軛的。(2)算法中第一個搜索方向必須取負梯度方向，否則構造的搜索方向不能保證共軛性。T(i)T2(3)由定理3的（3）可知，gid??gigi??

11、

12、gi

13、

14、?0,(i)(i)所以d是迭代點x處的下降方向。(4)由定理3，F(xiàn)R算法中?i的計算公式可以簡化。Td(i)AgT(i)??i?1gi?1AdiT?Td(i)Ad(i)(i)(i)dAdT(i?1)(i)gi?1A[(x?x)/?i]?T(i)(i?1)(i)dA[(x?x)/?i](i)(i)?gi??f(x)?Ax

15、?b.T2gi?1(gi?1?gi)?

16、

17、gi?1

18、

19、??i?TT(i)?d(i)gd(gi?1?gi)i2

20、

21、gi?1

22、

23、?(4)2

24、

25、gi

26、

27、FR算法步驟：(1)1.任取初始點x，精度要求?，令k?1。(1)(1)2.令g1??f(x),若

28、

29、g1

30、

31、??,停止，x為所求極小點；(1)(2)(1)(1)否則，令d??g1,利用公式（3）計算?1，令x?x??1d。(k?1)(k?1)3.令gk?1??f(x),若

32、

33、gk?1

34、

35、??,停止，x為所求極小點；(k?1)(k)否則