第四章无约束优化方法

1、 nnRxxxxxF)(min21 如图，以二次函数为例。)(0)(kxknxTnxxxx)0()0(2)0(1)0()1(0 x00011e00102e1000neikikikiexx)()(1)(?)(0)(kknxx)(*knxx *)(*xFF 60410)(21212221xxxxxxxF00)0(x11)1(0)1(1exx)1(0 x)0()1(0 xx0010011)1(1x6010)(min121)1(1xF010215105)1(1x)1(1x2222)1(1)1(251005exx6010)(min121)1(1xF5 . 425 . 45)1(2x7 . 65 . 45

2、2210)1(2xx0413. 0)5(0)5(2xx9981. 59883. 7*)5(2xx95025. 7*)(*xFF-+x2x1 脊线脊线。 如图所示，以三维二次目标函数的无约束优化问题为例。 x1x2x3 1=0 2e2 3e3S1)(1knx)(kx)(knx)(knS)(0kx)(1kmx)(kmx)(3kS)(2kx)(1kx)(1kS)(2kS)(kS(F3)(F2)(F1)23122132113)(2)(2(FFFFFFFFF)1(0 xiieS)1()1(0 x)(kiS)(min)()()(1)()()(1kiikikikikiSxFSxF)()()(1)(kikik

3、ikiSxx)(0)(kkknxxS)(1knS)(kkkknkSxx)()()()(0)(kknxx)(*kxx *)(*xFF mmkikiFFxFxF1)()(1)()(max)()(kixF)(1kmx)(kmx)(kmS)(0)()(12kknknxxx)()(13knxFF)()(01kxFF )()(2knxFF 23122132113)(2)(2(?FFFFFFFFF)()1(kikiSS)(0)()()1(02kknknkxxxx),()(1)(1)(1)1(kkmkmkkiSSSSS)()1(0kkxx的最优解。已知初始点 ，迭代精度=0.001Tx 11 011)1(0

4、x3)()1(01xFF2112221242)(xxxxxxF34)(min21)1(0exF1=2130121111)1(0)1(1exx7)()1(1xF)1(1x722)(min22)1(1exF2=0.55 . 13105 . 01322)1(1)1(2exx5 . 7)()1(2xF5 . 02115 . 13)1(0)1(21xxS1017519)1(x9 . 7)()1 (xF886. 211017151922)(0)(kkxx4)()()1(1)1(01xFxF5 . 0)()()1(2)1(12xFxF4,max211)1(eSm25115 . 1322)1(0)1(2)1(

5、1xxxn7)()1(13nxFF231221321)(2)(2(FFFFFFF25. 1)(2(221321FFFFF32)(2231FF13FF ),(12)2(SeSi)1()2(0 xx9 . 7)()2(01xFF1019519)2(1x98. 7)()2(1xF)2(1x50972599)2(2x996. 7)()2(2xF5012254101751955972599)2(0)2(22xxS42)2(x8)()2(2xF360. 010172519422)2(0)2(xx0)3(0)3(2xx42*x8*F 此式表明，相邻的两个迭代点的梯度是彼此正交的。也即在梯度的迭代过程中，相邻

6、的搜索方向相互垂直。梯度法向极小点的逼近路径是锯齿形路线，越接近极小点，锯齿越细，前进速度越慢。 这是因为梯度 是函数的局部性质，从局部上看，在该点附近函数的下降最快，但从总体上看则走了许多弯路，因此函数值的下降并不快。 入口入口给定：给定： x(0)， k=0|g(k)| ？x*=x(k)f*=f(x(k)出口出口x(k)= x(0)计算：计算：g(k)k=k+1沿沿g(k)方向一维搜索，方向一维搜索，求最优步长求最优步长 (k)。x(k+1)= x(k)- (k) g(k)/ |g(k)|NY=0.005222125)(xxxFTx22)0(2121502)(xxxFxFxFg1004)(

7、)0()0(xFg0799.100100422)0(g)0(x)0(g)10410016250016min()(min2)0()0(gxF02003072. 0)0(003072. 0919877. 1100402003072. 022)0()0()0()1(gxx153589. 0839754. 3)()1()1(xFg8428. 3)153589. 0(839754. 322)1(g0049. 0)5(g0000038. 000241185. 0*)5(xx6106*)(*xFFxkx*xk+1- f(xk+1)Sk+1Sk21)()(kkkxfxf21)()(kkkxfxf入口k=0，计

8、算计算：- f(x0) | f(xk+1) | ？出口出口求求 (k) ，x(k+1)= x(k) + (k)S(k)计算计算： f(xk+1) x*=xk+1f(x*)=f(xk+1)YN给定：给定： x(0)， k n ？x0=xk+1NYSk+1 = - f(xk+1) + kSkK=K+1F(x) 1(x) 0(x)x0 x1x2x*xHxxxFxFxFkTTkk21)()()(xHxxgFxkTTkk21)()0(x)(kxTnkkxFxFxFxFg21)()()(niikxFg12)(kg)(*kxx )(*)(kxFF )(kxjikkxxxFxHH)(2)(i，j=1，2n1k

9、HkkkgHS1)(并沿牛顿方向作一维搜索，求出在 方向上的最优步长)(kS)(k(1)( )( )1kkkkkxxHg入入 口口出出 口口给给 定定 ,k k 0 0 xx *)(*xFF )0(xk k k k+ +1 1)()(kxF)()(kkxFg计计 算算?kg计计 算算1kH)()(1)(kkkxFHS沿沿 方方 向向 一一 维维 搜搜 索索求求 最最 优优 步步 长长)( kS)( k)()()() 1(kkkkSxx+-的最优解。初始点 ，Tx00010) 1(2) 1(4)(212221xxxxxF510349821xxg4008H4100811H)0(x在 点处390g4

10、3893941008101)0(gHS)0(S1)0(4389438900)0()0()0() 1(Sxxk003498)43,89(211xxg 01g8125. 9*)(*xFFTx4389* ： 变尺度法的基本迭代公式写为下面的形式： x(k+1) = x(k) - (k)Ak gk Ak，k=1，2，A1=A0+A0Ak+1=Ak+AkAk称为)(kxxHxxgxFxFkTTkk21)()()(xHgxFkk)()(kxxx)1( kxx)()()1(1kkkkkxxHgg)(11)()1(kkkkkggHxx)()1(kkxx)()1(kkkxxkkgg1kkkggy1kkkyH1海

11、赛矩阵与梯度间的关系式1kA1kHkkkyA1Ak+1=Ak+Ak11)()()()(,kkTkkkTkkkkkkkTkkkkkTkkkkkkkTkkkkkTkkkTkkkkkTkkkkkkkkkkkTkkkTkkkkkkkkyAyyyAyAyyAyyAyyAyAyAyAAyawqwyAqAyAyA可知，必有比较上式等号左右两端代入上式并令：假设：kkkyA11kAkkTkTkTkkkkTkTkkkkyAyAyyAyAA11kA)()1(kkkxxkkkggy1kkTkTkTkkkkTkTkkkkkTkkkTkkyAyAyyAyAyAywy得：11)()0(0 xFg0g)0(x0gkkkgA

12、S)()(min)()()()()()(kkkkkSxFSxF)(kSk)()()()1(kkkkSxx)()1(0kxFg1kg)1( kx1kg)()1(kkkxxkkkggy1kkykkTkTkTkkkkTkTkkkkyAyAyyAyAA1输出最优解（x*，F*），终止计算 用DFP尺度法求目标函数的最优解。已知初始点 ，迭代精度=0.012221)6()5(4)(xxxFTx98)0(624)6(2)5(8)()9 , 8(21)0(0 xxxFg3 .240g62400)0(gAS)0()0()0()1(Sxx)0()0(0692486249822)1()669(5)248(4)()

13、(fxF为求极小，将上式对求导，并令f()=013077. 0)0(21538. 886152. 4)1(x43076. 410784. 0)()1(1xFg56716. 41g)1(x)1(S78462. 013848. 3)0()1(0 xx56924. 110784.25010ggy0000000000001yAyAyyAyAATTTTT003801. 1031487. 0031487. 012697. 01A48248. 428017. 011)1(gAS)2(x)1(S04942)1(00014. 699998. 4*)2(xx00028. 000016. 0)()2(2xFg000

14、32. 02g00014. 699998. 4)2(x8101 . 2*)(*xFFTx65*5000. 0001250. 02A2008H2100811H12 HA, n,x)0(输入：）（计算：）（）（00)0(xFgIA0k)()()()1()()()()()()()()(minkkkkkkkkkkkSxxSxFgAS)()1()1(kkxFgk=n？)1()1()1()()1()()()()1()()1(kkkkkTkTkTTkkkkgASNMAAyAyyANyMggyxx) 1() 0(kxx入口入口出口出口*)(*)1(xFFxxk?)1(kg+-+-kkTkkTkkkTkkkTkTkkTkkkTkkkTkkTkkkyAyAyyAsyAAysssysyAyysAA11 下面讨论本章所介绍的几种优化方法的适用范围： ：牛顿法较差，因为它对目标函数要求太高，解题成功率较低。 ：坐标变换法和梯度法的计算效率较低