优化设计-梯度法和共轭梯度法.pdf

《优化设计-梯度法和共轭梯度法.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、梯度法和共轭梯度法1.无约束最优化问题2.梯度法3.共轭梯度法一.无约束最优化问题无约束最优化问题minf(x)ns.t.xR其中f(x)有一阶连续偏导数。解析方法：利用函数的解析性质构造迭代公式使之收敛到最优解。二.梯度法（最速下降法）迭代公式：xk1xkdkk如何选择下降最快的方向？kf(x)函数值增加最快的方向kx函数值下降的方向kf(x)函数值下降最快的方向梯度法（最速下降法）：kk1.搜索方向：df(x),也称为最速下降方向；kkkk2.搜索步长:取最优步长,即满足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为所求极值点；否则，求最优步长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最速下降法的程序流程图锯齿现象在极小点附近，目标函数可以用二次函数近似，其等值面近似椭球面。2xx*3x1x注最速下降方向反映了目标函数的一种局部性质。它只是局部目标函数值下降最快的方向。最速下降法是线性收敛的算法。三.共轭梯度法共轭梯度法FletcherReeves共轭梯度法:1TTminf(x)xAxbxc2nn其中xR,A是对称正定矩阵，bR，c是常数。基本思想：将共轭性和最速下降方向相结合，利用已知迭代点处的梯度方向构造一组共轭方向，并沿此方向进行搜索，求出

8、函数的极小点。以下分析算法的具体步骤。(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、维搜索确定最优步长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对于正定二次函数f(x)xAxbxc，FR算法在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，FR算法中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)否则