《最优化方法》课程复习考试

1、最优化方法复习提要第一章最优化问题与数学预备知识§. 1模型无约束最优化问题 min f(x), x (捲必丄 x)T Rn .约束最优化问题(S x|x Rn,gi(x)0,i1,2, ,m;hj(x)0, j 1,2,l)min f (x);min f (x); 亦即s.t gi(x) 0,i 1,2丄，m,s.t x S.hj(x) 0, j 1,2,L ,l.其中f (x)称为目标函数，X1,X2丄，Xn称为决策变量，S称为可行域，gi(x) 0(i 1,2,L ,m),hj(x) 0( j 1,2,L ,l)称为约束条件.§. 2多元函数的梯度、Hesse矩阵及T

2、aylor公式定义 设f : RnR,x Rn .如果n维向量p , x Rn，有f (x x) f (x) pT x o(| x).则称f (x)在点x处可微，并称df (x)pT x为f (x)在点x处的微分.如果f(x)在点x处对于x (X1,X2,L ,Xn)T的各分量的偏导数f(x)X1,2,L , n都存在，则称f(x)在点X处一阶可导，并称向量f(X)f(X)X1X2f (X)TXn为f (x)在点X处一阶导数或梯度.定理1设f : RnR, x Rn .如果f (x)在点x处可微，则f (x)在点x处梯度f (x) 存在，并且有 df (x) f (x)T x .定义设f :

3、RnR,x Rn . d是给定的n维非零向量,.如果lim f(X e f(X)(R)0存在，则称此极限为f(x)在点x沿方向d的方向导数，记作 一空定理2设f : RndR,X Rn .如果f(x)在点X处可微，则f(x)在点X处沿任何非零方向d的方向导数存在，且晋f(X)Te，其中ed-.定义 设f(x)是Rn上的连续函数，X Rn . d是n维非零向量.如果0 , 使得 (0,)，有f (X d) ( >) f (X).则称d为f (X)在点X处的下降(上 升)方向.定理3设f : RnR,X Rn，且f (X)在点X处可微，如果 非零向量d Rn，使得f (X)Td(>)

4、0,则d是f(X)在点X处的下降(上升)方向.定义 设f：Rn R,X Rn .如果f(X)在点X处对于自变量x (xi,X2,L ,Xn)T的各分量的二阶偏导数 '刃(i,j 1,2,L ,n)都存在，则称函数f (x)在点X处二阶Xi Xj可导，并称矩阵2f(X)22f(X)L2f(x)X1X1 X2X1Xn2f(X)2f(X)2L2f(x)X2为X2X2 XnMMOM2f(X)2f(X)L2f(x)2Xn X1Xn X2xnf(X)为f (x)在点X处的二阶导数矩阵或Hesse矩阵.定义 设 h : RnRm, X Rn，记 h(x) (hi(x), h)2(x),L ,hm(x

5、)T，如果hi(x) (i 1,2,L ,m)在点X处对于自变量x (捲必,L , Xn)T的各分量的偏导数(i 1,2,L,m;j1,2,L , n)Xj都存在，则称向量函数h(x)在点X处是一阶可导的，并且称矩阵hi(X)Xih2(X)m nh( X )X1Mhm(X)Xihi(x)Lh1 (x)XXnh2(X)Lh2 (x)X2XnMOMhm(X)Lhm(X)X2xn为h(X)在点X处的一阶导数矩阵或Jacobi矩阵，简记为 h(X).例 2 设 aRn, xRn, bR，求f(X) aTX b在任意点x处的梯度和Hesse矩阵.n解 设a (ai,a2丄 a) ,x (Xi,X2,L

6、x)，贝U f(x)akXk b，k 1因一 ak(k 1,2,L ,n)，故得 f(x) a . Xk又因Xi Xj0(i, j 1,2丄，n)，则 2f(x) O .例3设Q Rn n是对称矩阵,b Rn,c R，称 f(x)1xtQx bTx2c为二解设q(qij)n n,X(X1 , X2 丄,Xn )T , b(b1,b2,L ,bn)T，贝U1 nnnf (X1,X2,LX)qijXiXjbkXkc，2 i 1j 1k 1f(x)nnjjX1j 1j 1b从而f (x)MMMMQx b.f(x)nnbnqnjxjbnqnjxjXnj 1j 1次函数，求f(x)在任意点x处的梯度和H

7、esse矩阵.再对_L凶XinqijXj bi (i 1,2,L ,n)求偏导得到i2f(x)X Xjqij (i, j 1,2丄，n)，于qii2 q21 f (x)' 7 Mqi2q22Mqniqn2LLOLqinq2nQ .Mqnn(t) f(x td)，其中 f ：RnR二阶可导,x Rn, dRn, t R ,试求(t),解由多元复合函数微分法知(t)f (x td )Td ,(t) dT 2 f (x td )d .定理4设f ：Rn R,x Rn，且f (x)在点x的某邻域内具有二阶连续偏导数,则f (x)在点x处有Taylor展式f(xT1T 2x) f(x)f (x)

8、T X ? XT 2f (xx)x,(01).证明设(t)f(x t x),t 0,1，则(0)f(x),(1)f (Xx).按一兀函数Taylor公式(t)在t 0处展开，有1 2(t)(0)(0)t -( )t2,(02t).从例 4 得知 (0)f (x)T x, ( ) ( x)T 2 f (x x) x .i令 t i，有 f(x x) f(x) f (x)T xxT 2 f (x x) x, (0 i).根据定理i和定理4,我们有如下两个公式f(x) f(x) f(x)T(x x) o(x x),f(x) f (x)f (x)T (x x) £(x x)T 2f(x)(x

9、 x) o(x x|j .§. 3最优化的基本术语定义设f : RnR为目标函数，S Rn为可行域，x S .(1) 若x S，都有f (x) f(x)，则称x为f(x)在S上的全局(或整体)极小点，或者说，x是约束最优化问题minf(x)的全局(或整体)最优解，并称f(x)x S为其最优值.(2) 若x S,x x，都有f(x) f(x)，则称x为f(x)在S上的严格全局(或 整体)极小点.(3) 若 x 的 邻域 N (x) x Rn x x (0)使得 x N (x) I S，都有f (x) f (x)，则称x为f (x)在S上的局部极小点，或者说，x是约束最优化 问题min

10、f (x)的局部最优解.x S(4) 若 x 的 邻域 N(x)(0)使得 x N (x)I S,x x，都有 f(x) f(x)，则称x为f (x)在S上的严格局部极小点.第二章最优性条件§2.1无约束最优化问题的最优性条件定理1设f : Rn R在点x处可微，若x是问题min f (x)的局部极小点，则f(x)0 .定义 设f : S( Rn) R在x intS处可微，若 f(x)0，则称x为f (x)的平稳点.定理2设f : RnR在点x处具有二阶连续偏导数，若x是问题min f (x)的局部极小点，贝U f(x)0，且2f(x)半正定.定理3设f ：RnR在点x处具有二阶连续

11、偏导数，若f(x)0，且2f(x)正定，则x是问题min f (x)的严格局部极小点.注：定理2不是充分条件，定理3不是必要条件.例1 对于无约束最优化问题min f(x) x； x2，其中x (人兀)丁 R2，显然f(x) (2x3x；)t, x R2，令 f(x) 0,得 f(x)的平稳点 x (0,0)T，而且f(x)0 6x22f(x)易见2f(x)为半正定矩阵.但是，在x的任意邻域，总可以取到% (0, )T，使 f (X) f (x)，2即x不是局部极小点.对于无约束最优化问题min f(x) Xi4 2x1x24X2，其中 X (X1,X2)T R2，易知f (x) (4x； 4

12、x!x|,4x12X2 4x；)t，从而得平稳点 x(0,0) T，并且显然2f(x)12x； 4xf8为冷8x22 24x.|12x22f(x)2f(x)不是正定矩阵.但是,2f (x) (X1x；)2在x处取最小值，即x为严格局部极小点.例3 求解下面无约束最优化问题min f (x)13x11 33x22X2xi，其中x/、T2(Xi,X2)R，解因为f(x)X：1x| 2x22f(x)2为002x2所以令f(x)20,有 X12X21 0,0.2x2解此方程组得到f(x)的平稳点x(1)(3),x()从而2f(x)2f(x(2)2f(x(3)2f(x(4)由于2f(x)和2 f (x(

13、4)是不定的，因此x(1)和x(4)不是极值点.2f(x)是负定的，故X不是极值点，实际上它是极大点.2 f ( X(2)是正定的，从而x(2)是严格局部极小点.定理4设f：RnR是凸函数，且f(x)在点x Rn处可微，若f(X) 0,则x为min f (x)的全局极小点.推论5设f : RnR是凸函数，且f (x)在点x Rn处可微.则x为 min f (x)的全局极小点的充分必要条件是 f(x) 0 .例4 试证正定二次函数f (x) -xTQx bTx c有唯一的严格全局极小点2x Q 1b，其中Q为n阶正定矩阵.证明 因为Q为正定矩阵，且 f(x) Qx b, x Rn，所以得f (x

14、)的唯一平稳 点x Q 1b .又由于f(x)是严格凸函数，因此由定理 4知，x是f (x)的严格全 局极小点.§2.2等式约束最优化问题的最优性条件定理1设f ：RnR在点x处可微，hj：Rn R(j 1,2丄，1)在点x处具有一阶连续偏导数，向量组h1(x), h2(x),L , h(x)线性无关.若x是问题min f (x);s.t hj (x)0, j 1,2,L ,l的局部极小点，贝UVj R, j 1,2丄，1，使得lf (x)Vj hj(x) 0 .j 1称 L(x,v) f (x) vTh(x)为 Lagrange函数，其中 h(x) (h(x), h2(x),L ,

15、hl(x)T .称 v (V1,V2,L ,vJT 为 Lagrange乘子向量.L 、l易见 L(x,v) x ，这里 xL(x,v) f (x)vj hj(x), vL(x, v) h(x).vLj 1定理2设f : Rn R和hj :RnR(j 1,2,L ,l)在点x Rn处具有二阶连续偏导数，若7 R1，使得 xL(x,v)0，并且，z Rn,z 0，只要ZT hj(X) 0, j 1,2,L ,1，便有 zT XxL(x,v)z 0,则 x 是问题的严格局部极小点.min f (x);s.t hj (x)0, j1,2,L ,l例1试用最优性条件求解min f (x)s.t h(x

16、)2X1%x22X2；8 0.解 Lagrange函数为 L(x, v)X；X；v( X-I x28)，则 L(x,v)2为 vx22x2 vx1,(X1X28)从而得L（x, v）的平稳点（、8,、8, 2）t 和 （ ,8, . 8,2）t，对应有x (、.8,、.8)T,v2和 x ( 、,8,、8)T,v 2.由于XxL(x,v)2 22 2 , h(X)X2因此M (x) ( Z1, z；)T | (z1,z；)h(x) 0（乙，乙2）打乙乂2 Z；X10(Z1,Z2)T|Z1z；.并且z M (x),z0，有 zt XxL(x,v)z 2z124ziZ22z； 8Z12利用定理2,

17、所得的两个可行点x c、8,、8）T和x（、8,8）都是冋题的严格局部极小点.§2.3不等式约束最优化问题的最优性条件定义设 S Rn,x cis,d Rn,d 0，若 0，使得，x d S, (0,),则称d为集合S在点x处的可行方向.这里 cIS x|x Rn,SI N (x)0.令 D d |d 0,0,使 X d S,(0, )，Fo d| f(X)Td 0.定理1设SRn是非空集合，f : S R, x S, f(x)在点x处可微.若x是问题min f(x)的局部极小点，贝U F01 D .x S对于min f(x)；()s.t gi (x)0,i1,2,L ,m,其中 f

18、 : Rn R, gi : RnR(i 1,2,L ,m).令l(x)i |gi(x)0, i 1,2丄，m，其中x是上述问题(1)的可行点.定理2 设x是问题(1)的可行点，f(x)和gi(x) (i I (x)在点x处可微， gi(x)(i I(x)在点x处连续，如果x是问题(1)的局部极小点，贝U F0I G0，其中 G° d | gi (x)Td 0, i I (x).定理3设x是问题(1)的可行点，f(x)和gi(x) (i I(x)在点x处可微， gi(x)(i I (x)在点x处连续，若x是问题(1)的局部极小点，则存在不全为0的非负数U0,Ui (i I (x)，使u

19、0 f (x) ui gi (x)0 .( x 称为 Fritz John 点)i I (x)如果gi(x) (i I (x)在点x处也可微，则存在不全为0的非负数U0, U1,L ,Um，使m(x 称为 Fritz John 点)U0 f(x)Ui gi(x) 0,i 1Ui gi (x)0, i 1,2,L ,m.min f(x)x1;例 1 设 s.t g1(x)(1g2(x) X2xj3 x0.0,试判断x(1,0)T 是否为 Fritz John 点.解因为- 1 f(x) 0 ,gi(x)01,g2(x)0，且 I(x) 1,2，1所以为使Fritz John 条件1 U0U10

20、0 U2成立，只有u00才行.取01 10定理4 设x是问题(1)的可行点，f(x)和gi(x) (i l(X)在点x处可微， gi(x)(i l(x)在点x处连续，并且 gi(x)(i l(x)线性无关.若x是问题(1) 的局部极小点，则存在Ui 0(iI(x)，使得f (x) u gi (x) 0 .( x 称为 K-T 点)i I (x)如果gi(x)(iI(x)在点x处也可微，则存在Ui 0(i1,2,L ,m)，使得m(x称为K-T点)X2；2 0,的 K-T 点.f(x)Ui gi(x) 0,i 1Ui gi (x)0, i 1,2,L , m.2minf (x) (x1 1)例2

21、求最优化问题s.t g1(x)% x2g2 (x) X2 0解因为f(x)2(x； 1) , g1(x)1 ,11 g2（x）0，所以K-T条件为12(X1 1) U10,1U|u20,u1 ( x1x22) 0,u2x20,u10,u20.若U20，则U11，这与U10矛盾.故U20，从而X2 0 ；若x 20,则U12，这与U1 0矛盾.故U10，从而 U21, x11 ;由于U10,U20,且x （1,0）T为问题的可行点，因此x是K-T点.定理5设在问题（1）中，f（x）和g'xM 1,2,L ,m）是凸函数，x是可行点，并且f（x）和gi（x）（il（x）在点x处可微.若x是

22、问题（1） 的 K-T点，则x是问题（1）的全局极小点.§2.4 一般约束最优化问题的最优性条件考虑等式和不等式约束最优化问题min f(x);s.t gi (x)0,i1,2,L ,m,(1)hj(x)0, j 1,2,L ,l,其中 f:Rn R, gi : RnR(i 12L,m), hj：RnR(j 1,2,L ,l).并把问题(1)的可行域记为 S . x S, I (x) Ai |gi(x)0, i 1,2,L , m.定理1设x为问题(1)的可行点,f (x)和gi(x) (i I (x)在点x处可微,hj(x)(j 1,2,L ,l)在点x处具有一阶连续偏导数，gi(

23、x)(i 1(幻)在点x处连续,并且向量组 A(x), h2(x),L , h (x)线性无关.若x是问题(1)的局部极小点，则 Fol Go I Ho这里 F。d| f(x)Td 0 , G。d| gi(x)Td 0, i I(x),H。d| hj (x)Td 0, j 1,2,L ,l.定理2 设x为问题(1)的可行点，f(x)和gi(x) (i l(x)在点x处可微,hj(x)(j 1,2,L ,l)在点x处具有一阶连续偏导数，gi(x)(i l(x)在点x处连续.若x为问题(1)的局部极小点，则存在不全为0 的数 uo,Ui (i I (x)和Vj (j 1,2,L ,l)，且 U0,

24、Ui 0(il(x)，使lU0 f (x)Ui gi(x)Vj hj(x) 0.i I (x)j 1(x 称为 Fritz John 点)若gi (x) (i I(x)在点x处也可微，则存在不全为0 的数 U0,Ui (i 1,2,L , m)和Vj (j 1,2,L ,l)，且 U0,Ui 0(i1,2,L ,m)，使mlU0 f(x)Ui gi(x) Vj hj(x) 0,i 1j 1(x 称为 Fritz John 点)Ui gi (x)0, i 1,2,L ,m.min f (x)2X12冷；例1设s.t gMx)3X1X20,试判y 断 x(1,0/ 是,否为 Fritz John

25、点.g2(x)X20,h(x)(X11)2 X20.解I(x)2，且2f(x)0,g2 (x)0 01 , h(x) 1，且丨(刃1,2，因此为使Fritz Joh n条件2 u0u0l2v00成立，只有Ug 0才行.所以0 02 11 0取U00,U21, v1，即知x是Fritz John点.定理3设X为问题(1)的可行点，f(x)和gi(x) (i l(X)在点x处可微,hj(x)(j 1,2,L ,1)在点X处具有一阶连续偏导数，gi(x)(i I(X)在点X处连续,且向量组gi(x) (i l(x),hj(x)(j 1,2, L ,l)线性无关若x是问题(1)的局部极小点，则存在数u

26、i 0 (il(x)和 Vj (j 1,2丄，1)，使f (x)Uigi(x)vj hj(x)i l(x)j 1如果gi(x) (i I (x)在点x处也可微vj (j 1,2,L ,l)，使mf(x)Uii 1lgi(x)vj hj(x)j 1Ui gi(x) 0, i1,2,L , m.0 .( x称为K-T点)则存在数Ui 0(i1,2,L ,m)和0,( x称为K-T点)令 g(x) ©(x),g2(x) L , gm(x)T , h(x) (hdx),h2(x )丄，h(x)T，u (U1,U2,L ,um)T ,v (V1,V2丄，vJT，称u与v为广义Lagrange乘

27、子向量或K-T乘子向量.f(x)g(x)Tuh(x)Tv 0,uTg(x) 0,u 0.令 L(x,u,v) f (x) uTg(x) vTh(x)为广义 Lagrange函数.称 L(x,u,v)为广义Lagrange函数.贝U K-T条件为xL(X,u,v) 0, uTg(x) 0, u 0.定理4 设在问题(1 )中，f(x)和gMx)(i 1,2,L ,m)是凸函数， hj(x)(j 1,2丄,l)是线性函数，x是可行点，并且f (x)和gi(x) (i I (x)在点x处可微.若x是冋题(1)的K-T点，则x是冋题(1)的全局极小点.2 2min f (x)(xi3)(x?1);例2

28、 求解最优化问题s.t g(x)x设u 0，则有X20,h(x) 2x1 X2 3 0.解广义Lagrange函数为2 2 2L(x,u,v) f(x)ug(x) vh(x)(x13) (x2 1)u( x1 x2)v(2x1x23).因为 L(x,u,v)2(x13) 2ux12v， L(x,u,v)2(x21) uv .X1X2所以K-T条件及约束条件为2(x1 3) 2ux1 2v 0,v 0,0,0,2(x2 1) u u( xf X2) x； x20,2 x2 3 u 0.下面分两种情况讨论.(1) 设u 0，则有2v 0,v 0,30.(7,1/不是可行点，因而不是 K-T点.5

29、52以3)2(X21)2x1 x2 由此可解得X17,X2，v8，但X5552(X13)2u%2v 0,2(X21)u v0,2X1X20,2%X23 0.由此可得 Xi 2xi 3 0 ,解得Xi 1或Xi 3。从而X2 1或x2 9 .于是u 1 或u 11 (这与u 0矛盾).v 1或v 27 .由此可知X (1,1是问题的K-T 点，但X ( 3,9)t不是问题的K-T点.易见，f (x)是R2上的凸函数，g(x)是R2上的凹函数，h(x)是线性函数， 因此由定理4知，X (1,1/是问题的全局最优解.定理5设X为问题(1)的可行点，f(x), g(x)(i I(x)和hj(x)(j

30、1,2丄，1)在 点X处具有二阶连续偏导数，并且存在乘子向量u (U1,U2,L ,Um)T 0和 v (V1,V2, L ,Vm)T 0 使 K-T 条件成立，即丄(x,u,v)0,uTg(x)0.若对于任何满足zT gi(x)0, iI (x)且 ui0,zT gi(x)0, iI (X)且 ui0,zT hj(X)0, j1,2,L ,l的向量z 0，都有zT2xxL(x, u,v)z0，则x是冋题(1)的严格局部极小点min f (x)ng.Ji 1 Xi例3 求解最优化问题s.t gi(x)N 0,i 1,2,L , n,h(x)naiXib 0,i 1其中常数 ai 0, G 0,

31、 i 1,2,L ,n；b 0 .解该问题的广义Lagrange函数为n nnCiL(x,u,v)uixi v(a/ b).i 1 Xi i 1i 1因为L(x,u,v) c2 Ui X；2Xia；v, i1,2,L , n .所以问题的K-T条件及约束条件为c；2Uix；UiXi0,x；0, ina；Xi 1u；0, iaiv0, i 1,2,L ,n,1,2,L ,n,1,2,L , n,b 0,1,2,L , n.由第1式、第3式知x 0（i 1,2丄，n）,从而由第二式解得u；0, i 1,2,L , n 于是再由第1式知v0，且 aiVXi2 Ci0, i 1,2,L , n ,于是

32、x;所以xGav即得X；b 0，解得vn1,2,L ,n，从而a；i 1n(.aiC )2i 1bbnJ a； c；i 1纟,i 1,2,L ,n .ai（Xi,X2丄，凡）T是问题的K-T点.：L（x,U,v）是一个 n又由于L（x,u,v）在点（XT,UT,V）T处关于x的Hesse矩阵阶对角矩阵，其对角线上第i个元素为餐 0, i 1,2,L ,n,x；因此；L（x,U,v）是正定矩阵.根据定理5, x为问题的严格局部极小点.第三章常用优化算法介绍§3.1一维搜索给定Xk,dk Rn，令（）f区dk),0.定乂 如果求得步长 k，使得f(Xkkdk) min f (Xkdj或(

33、Q min ( )()则称这样的一维搜索为最优一维搜索或精确一维搜索.k叫做最优步长.定理1对于问题."，设f : SR是可微函数，xk 1是从xk出发沿方向dk作s.t x S最优一维搜索得到的，则有f (Xk 1)Tdk 0 .定义 如果选取 k，使目标函数f沿方向dk取得适当的可接受的下降量，即使得下降量f(xQ f (Xk 1) 0是我们可接受的，则称这样的一维搜索为可接受一维搜索或非精确一 维搜索.定义设:R R, 一 0,，并且(一)min ( ) 如果对于a,b0,有-a,b，那么称a,b是问题mip ()的搜索区间.定义 设:R R,a,b R，若存在a,b，使得()

34、在a/上严格单调减少，在一,b上严格单调增加，则称a,b是()的单谷区间， ()是a,b上的单谷函数或单峰函数.定理2设:RR,a,b为()的单谷区间，1, 2a,b，且12，那么(1) 若(1)(2)Ha, 2是()的单谷区间；(2) 若(1)(2)，则1,b是()的单谷区间.算法3-1 (进退法)Step1选取初始数据。给定初始点o,初始步长ho0 ,加倍系数1 (一般取2 ),计算0( °)，置k 0 .Step2 试探令 k 1 k hk，计算 k 1( k 1).Step3 比较目标函数值.若k 1 k，转Step4，否则，转 Step5.Step4 加步探索令 hk 1h

35、k,k, k : k 1, k ： k 1,k : k 1，转 Step2.代令 a min , k 1, b max , k 1.输出搜索区间a,b.§3.2 0.618 法与 Fibonacci 法考虑min (t),t R .假定(t)的一个搜索区间知已确定，并设(t)在山上为单谷函数.算法 3-2 (0.618 法)(4 印)，1 a1(daj ,求出1印(1Step1选取初始数据确定初始搜索区间a1,bi和允许误差0,0.618 .(J,( 1)，并置 k 1 .Step3 检查 kk?是，停止计算，输出tk ;否则，转 Step4.2Step4 比较函数值.若(Q( k)

36、，转 Step5;若(Q( k)，转 Step6Step5 向左搜索令 ak1:ak,bk1k, k 1k, ( k 1)(k).并计算 k 1ak 1 (1)(bk 1 ak 1), ( k 1)，转 Step7.Step6 向右搜索令 ak 1k,bk1: bk, k 1k, ( k 1 )(k).并计算 k 1 ak 1(bk 1 比 1), ( k 1)，转 Step7.Step2 计算最初两个试探点：Step7 置 k : k 1，转 Step3.定义 Fibonacci数是指满足下述条件的数列Fk ：F0F1 1,)用数学归纳法可以证明，Fibo nacci数可由下式表示:Fn15

37、n 0,1,2,L(3.2. 2)算法 3-3 ( Fibonacci 法)Step1选取初始数据.给定初始搜索区间a1,bi和允许误差0，辨别系数求搜索次数n，使nStep2计算最初两个试探点：1 a1(b1), 1 a1Fn 1 (b1aj，求函数F nFn值（1）和（1），并置k1.Step3 检查(k)(k)?是，转Step4 ;否，转 Step5.Step4 向左搜索.令ak 1ak? bk 1k? k 1k?( k 1)(k).并计算aFn k 2并计算k 1ak 1(bk 1ak 1)和(k 1)，转 Step6.Fn kStep5 向右搜索.令ak 1k? bk 1 bk, k

38、 1k,( k 1 )(k).并计算aFn k 1并计算k 1ak 1(bk 1ak 1)和(k 1)，转 Step6.Fn kStep6 置 k : k 1,若kn 1，转 Step3 ；若 k n 1，转Step7.Step7 令 nn 1?nn1，计算（n）和（n）。若(n)（n），则令an an 1,bnn ；否则，令ann, bn bn 1，停止计算，极小点含于区间an ,bn.§3.3 Newton 法考虑 min (t),t R.假定（t）具有三阶连续导数.算法 3-4 (Newton 法)Step1给定初始点to，允许误差0，置k 0 .Step2检查（tk）?是，输

39、出tk，停止计算；否，转Step3.Step3计算点 tk 1tk ，置 k： k 1，转 Step2.(tk)§3.4最速下降法考虑无约束最优化问题min f(x)，(341)其中f : Rn R具有一阶连续偏导数.算法3-5 (最速下降法)Stepl选取初始数据选取初始点X。，给定允许误差0，令k 0 .Step2检查是否满足终止准则计算f(Xk)，若| f(Xk)，迭代终止，Xk为问题(341 )的近似最优解；否则，转 Step3.Step3进行一维搜索取dkf (Xk)，求k和Xk i，使得f (Xkkdk) min f (XkdQ ,Xk 1 Xkkdk令 k : k 1，

40、返回 Step2.特别地，考虑1 ttmin f (x) x Qx b x c,()其中x Rn,Q Rn n为正定矩阵，b Rn , c R .设第k次迭代点为Xk，从点Xk出发沿f (Xk)作一维搜索，得Xk 1Xkk f (Xk),其中k为最优步长.根据定理，有f (Xk 1)T f (Xk) 0 而 f (x) Qx b, x Rn ,所以 f(Xk1)f (Xk)kQ f (Xk)，从而(f (Xk)kQ f (Xk )T f (Xk) 0,而 Q 正定，即f(Xk)TQ f(xQ 0，故由上式解出(343)f(Xk)T f(Xk)f (Xk)TQ f (Xk)于是这是最速下降法用于

41、问题(Xk 1Xkf(Xk)T f(Xk)f (Xk)TQ f (Xk)的迭代公式.f (Xk)(344)例1 用最速下降法求解问题(345)min f (x) 4x12 x22,其中x（Xi,X2）T 取初始点x（0）（1,lf，允许误差0.1.问题（345）中的f是正定二次函数，且f在点x (Xi,X2)T 处的梯度f (x)（8为，2血）丁 .第一次迭代:令搜索方向d（0）f(x(0)( 8, 2)t，d(0),64一4 217,从点x（0）出发沿d（0）作一维搜索，由（）式和（344）式有(0) 520 °.130769，x (1,1)t 0.130769( 8, 2)T (

42、 0.046152,0.738462) T .第二次迭代:f(x)(0.369216, 1.476924)T，、2.18305 1.522375,从点X出发沿d作一维搜索，按（）式得x(2)(0.101537,0.147682) T .第三次迭代:令 d(2)f (x )(0.812296, 0.295364)T，d.0.747056 0.864329,按（）式求得x(0.009747,0.107217) T .第四次迭代:f (x(3)(0.077976, 0.214434)t，d0.052062 0.228171,按(344)式求得(0.019126,0.027816)第五次迭代:f (x

43、)(0.153008, 0.055632)t ,d0.026506 0.162807按()式求得x(5)0.001835,0.020195)此时， f(x ).0.001847，已满足精度要求，故得问题(345)的近似最优解0.001835,0.020195)实际上问题(345)的最优解为X (0,0)1§3.5 Newton 法算法 3-6 (Newt on 法)Step1选取初始数据选取初始点X。，给定允许误差0，令k 0 .，迭代终止，Xk为问题Step2检查是否满足终止准则计算f(Xk)，若| f(Xk)(341 )的近似最优解；否则，转Step3.Step32 1 2 1构

44、造 Newton 方向计算f(xj，取 dkf(xjf (xQ .Step4求下一个迭代点.令 xk 1xk dk , k: k 1，返回Step2.例2用Newton法求解冋题(),仍取初始点x()(1,1)，允许误差0.1.解f(x(0)(8,2)T ,2 f (x(0)0 2，故2f(X(0)1 10 102，d(0) 2f(X(0)1 f(X(0)x(1)x(0) d(0)(1”(1,1$(0,0)T .由于| f(X)0 0.1,迭代结束，得X(1)为问题(345)的最优解.算法3-7 (阻尼Newton法)Stepl选取初始数据选取初始点X。，给定允许误差0，令k 0 .Step2

45、检查是否满足终止准则计算f(Xk)，若| f(Xk)，迭代终止，Xk为问题(341 )的近似最优解；否则，转Step3.2 1 2 1Step3 构造 Newton 方向.计算f(xj，取 dk f(xjf (Xk).Step4进行一维搜索求 k和Xk 1，使得f (Xkkdk)min f (XkdQ ,xk 1xkkdk1，返回 Step2.用阻尼Newt on法求解下面问题:)2 2 2min f (x) (1 x1)2(x2 为),其中x(X1,X2)T .取初始点X(0)(0,0)T，允许误差0.1.第一次迭代:f(x)2(1 x1) 8(x2 x14(X2 xj)X12f(x)16为

46、28(x2 x12)8为(0) f (X )2,0)T,f(x(0)2f(x(0)：,2f(x(0)11/2 001/4是，Newton 方向 d (0)2f (X(0) 1 f (X(0)(1,0)T ,从 X(0)出发沿 d(0)作一维搜索,即求 minf(x(0)d(0)min(1024)2 的最优解，得到(0)1A2 .令x(1)x(0)(0)d(0)(1/2,0)t .f(x )(0,1)T,f(x)1第二次迭代:f (x(D)84482 (1) 1 1 1，f(x)4 1d2f(x)1f (x)(1/4,1/2)丁 从X出发沿d作一维搜索，即求minf(xd)min 丄8(20 1

47、28)2 (2)4的最优解，得到2 令x(2) x(1)(1,1)T f(x)(0,1)T,f（x）此时，f （X）(0,0)T,f(x(2)0,得问题（）的最优解为x(2)(1,1T,这是惟一的最优解.§3.6共轭梯度法定义设Q Rnn为正定矩阵若Rn中的向量组do,di,L ,dm 1满足diTQdj0, i,j0,1丄，m 1,i j ,则称d0,d1,L ,dm 1是Q共轭的.算法3-8 （共轭方向法）给定一个正定矩阵Q Rn nStep1选取初始数据.选取初始点X0，给定允许误差f（X0），求出d0，使0.f(X0)Td°0,Step2选取初始搜索方向.计算Ste

48、p3检查是否满足终止准则.若II f(xk)，迭代终止；否则，转Step4进行一维搜索.求k和Xk1，使得f (Xkkdk)min f (xkdk),Xk 1Xkkdk .令k 0.Step4.Tep5选取搜索方向.求dk 1使dTQdj 0, j 0,1,L,k,令 k： k 1，返回 Step3.如果用共轭方向法求解正定二次函数的无约束最优化问题bTxc,1 t min f (x) x Qx2其中Q Rn n为正定矩阵，b Rn,cR (此时算法中的正定矩阵应与二次函数的正定矩阵一致)，那么容易推出迭代公式为对于问题(3.4.1 )的求解,Xk 1Xkf (Xk)T dk dkTQdk(362)我们还有如下一些方法.Fletcher-Reeves ( FR)公式:2f(Xk1)；2 ；f(Xk)2Dixon-Myers ( DM )公式:f(Xk1)Tf (Xk 1)；dkT f(Xk)Polak-Ribiere