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

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

2、、Hesse矩阵及Taylor公式定义 设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 (x,x2,L ,xn)T的各分量的偏导数f(x)1,2,L ,n精品资料都存在，则称f (x)在点x处一阶可导，并称向量f(x)(f(x)fl,L*2f(x)Txn为f (x)在点x处一阶导数或梯度.定理1设f：Rn R,x Rn .如果f(x)在点x处可微，则f(x)在点又处梯度f (又) 存在，并且有df (x) f &)T x

3、 .定义设f：RnR,x Rn. d是给定的n维非零向量，e标如果lim 四一e f (x) ( R)0存在，则称此极限为f(x)在点x沿方向d的方向导数，记作定理2设f ：RnR,xRn .如果f (x)在点X处可微，则f (x)在点X处沿任何非零方向d的方向导数存在，且 3)f(x)Te,其中e 2.dId定义 设f(x)是Rn上的连续函数，x Rn. d是n维非零向量.如果 0,使得 (0,),有f(x d)(>) f(x) .则称d为f(x)在点云处的下降(上升)方向.定理3设f：Rn R,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的各分量的二阶偏导数2 f(x)X xj(i,j 1,2,L ,n)都存在,则称函数f(x)在点x处二阶可导，并称矩阵2 f (x) f G)2 f (x)L2fG)2 £ /一2f (x)x2 xix2x2 xnM MOM222 一一2 f (x)2 f (x) ,2 f (x)L2xn xixn x2xn为f (x)在点x处的二阶导数矩阵或Hesse矩阵.定义 设 h：RnRm,x Rn,记 h(x) (hi(x), h2(x),L ,h

5、m(x)T ,如果hi(x)(i i,2,L ,m)在点x处对于自变量x (x1,x2,L ,xn)T的各分量的偏导数 f (x),2f 2Lxixi x2xi xnx)(i 1,2,L,m;j 1,2,L ,n) xj都存在，则称向量函数h(x)在点又处是一阶可导的，并且称矩阵一 一(又)Lhi (X)XiX2Xnh2(X)h2(X)Lh2(X)m nh(X)XiX2XnMMOMhm(X)hm(X)Lhm(X)XiX2Xn为h(X)在点x处的一阶导数矩阵或Jacobi矩阵，简记为h(x).例2设a Rn, x Rn,b R,求f(X) aTX b在任意点x处的梯度和Hesse 矩阵. n解

6、设a (ai,a2,L ,an) ,x (x1,X2,L ,Xn),则 f(x)akXk b,k i因一f ak(k i,2,L,n),故得 f(x) a . Xk又因 _1(x_ 0(i, j i,2,L,n),则 2f (x) O .Xi XjIt t例3设Q R 是对称矩阵，b Rn,c R,称f(x) xTQx bTx c为二 次函数，求f(x)在任意点x处的梯度和Hesse矩阵.解设Q(qij)n n，X (X，X2，L ,Xn)T,b（h'L总）二则1n nnf (Xi,X2,L,Xn) -qijXXjbkXkc ?2 i i j ik innf (x).qijXjhqij

7、XjuXij ij ib从而f (X)MMMM Qx b.f(x)n卜nbnqnjxjbnqnjxjXnj ij i再对 fx)qjXj bi (i 1,2,L ,n)求偏导得到 fx) qj(i,j 1,2,L,n),于Xij iX Xj是qi2 Lqinq22 Lq2n八Q .MOM02 Lqnn2f(x)q21qn1例 4 设(t) f(x td),其中 f：RnR二阶可导，X Rn,d Rn,t R,试求(t),(t).解由多元复合函数微分法知(t) f(X td)Td, (t) dT 2f(X td)d .定理4设f：RnR,X Rn ,且f(X)在点X的某邻域内具有二阶连续偏导数，

8、则f (x)在点X处有Taylor展式尸一尸一尸.T1丁2尸f (xx) f (x)f (x)X -X f (xx) X, (01).证明 设(t) f(x t x),t 0,1,则(0)f(x), (1) f(X X).按一元函数Taylor公式(t)在t 0处展开，有12(t)(0)(0)t - ()t2,(0 t) .2从例 4 得知 (0)f (x)T x, ( ) ( x)T 2 f (x x) x .T 1 T 2令 t 1,有 f(x x) f (x)f (x) X - x f(x x) X, (01).根据定理1和定理4,我们有如下两个公式f(x)f(x)f(x)T(xx)o(

9、|xX|),f(x)f(x)f (x)T(xx)；(xX)T2f(x)(x x) o(x x|2).§1 . 3最优化的基本术语定义设f：RnR为目标函数，SRn为可行域，X S.(1)若x S,都有f(x) f(X),则称又为f(x)在S上的全局(或整体)极小点，或者说，X是约束最优化问题min f(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为

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

11、：RnR在点x处具有二阶连续偏导数，若f () 0,且2f(©正定，则x是问题min f (x)的严格局部极小点.注：定理2不是充分条件，定理3不是必要条件.例1对于无约束最优化问题min f(x) xi2 x3 ,其中x (Xi,X2)t R2,显然f(x) (2X1, 3x2)T, x R2,令 f (x) 0,得 f(x)的平稳点 x (0,0)T ,而且2f(x)6x22f(X)易见2 f(X)为半正定矩阵.但是，在X的任意邻域，总可以取到(",使" f(X)'即X不是局部极小点.对于无约束最优化问题min f(x) Xi4 2x2x24X2 ，其

12、中 x (X1,X2)T R2,易知f (x) (4x3 4X1X2,4X2X2 4x3)T ,从而得平稳点 x(0,0) T ,并且显然2 f(X)12x12 4x28x1x28x1x22 一 24x1 12x22 f (X)2 f (X)不是正定矩阵.但是,-2f (x) (X1X2)2在X处取最小值,即又为严格局部极小点.例3求解下面无约束最优化问题min f (x)3X11 33X22X2其中xT 2(X1,X2)R ,解因为f(x)X12 1X2 2x22 f (x)2%002x2所以令f(x)2一 X1 0 ,有1 2X22x20,0.解此方程组得到f(x)的平稳点(1)X,X,X

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

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

15、(x)为 Lagrange 函数,其中 h(x) (h1(x),h2(x),L ,hl(x)T .称 v (v1,v2,L ,vJT 为 Lagrange 乘子向量.xL 、el易见 L(x,v),这里 xL(x,v) f (x)vj hj(x), vL(x, v) h(x).vLj 1定理2设f:Rn R和hj:Rn R(j 1,2,L,l)在点x Rn处具有二阶连续偏导数，若 v Rl ,使得xL(X,v)0 ,并且，z Rn,z 0 ,只要zT hj(x) 0, j 1,2,L,l,便有 zT 2xL(x,v)z 0,则又是问题min f (x);st hj (x) 0, j 1,2,L

16、,l的严格局部极小点.22例1试用最优性条件求解min f (x)x1x2;s.t h(x)x1x2 8 0.2x1 vx2 解 Lagrange 函数为 L(x,v) x； xf v(x1x2 8),贝U L(x,v)2x2 vx1,(XiX2 8)从而得L（x,v）的平稳点（褥褥2）丁和（而 78,2），对应有x(78,78)T,v 2和 X (® 78)T,v 2.由于XXL(X,v)h(x)X2Xi因此M(x) (Z1,Z2)T |(Zi,Z2)h(x) 0( Z1, Z2)T | Z1X2Z2X102z2 8z20 .(Z1,Z2)T|Z1Z2.并且 z M (x), z

17、0,有 zT XxL(x, v)z 2z2 4z1Z2利用定理2,所得的两个可行点x（我，而）T和x （限 78）T都是问题的严格局部极小点.§2.3不等式约束最优化问题的最优性条件定义 设 SRn,x clS,d Rn,d 0,若 0,使得，x d S, （0,）,则称d为集合S在点X处的可行方向.这里 clS 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)的局部极小点，则F0 I D .x S对于minf

18、(x);(1)s.t gi(x) 0,i 1,2,L ,m,其中 f : RnR, gi : RnR(i 1,2,L ,m).令I(x) i|gi(x) 0, i 1,2,L ,m,其中x是上述问题(1)的可行点.定理2 设x是问题(1)的可行点，f(x)和g/x)(i I(x)在点x处可微，gi(x)(i I(x)在点x处连续，如果x是问题(1)的局部极小点，则FoI Go ,其中 Go d | gi (x)Td 0, i I (x).定理3设x是问题(1)的可行点，f(x)和g/x)(i I (x)在点x处可微，gi(x)(i I(x)在点x处连续，若x是问题(1)的局部极小点，则存在不全

19、为0的非负数U0,Ui (i I (x),使u0 f (x)ui gi(x) 0 .(x 称为 Fritz John 点)i I (x)如果gi(x)(i I (幻)在点x处也可微，则存在不全为0的非负数Uo,Ui,L ,Um,使m(x 称为 Fritz John 点)Uo f (x)Ui gi(x) 0,i 1Uigi(x) 0, i 1,2,L ,m.min f(x)x1;0,试判断x (1,0)T是否为Fritz John 点.设 s.t g1(x) (1 x1)3 x2 g2(x) x20.1斛因为 f(x) 0 , g1(x)0g2(x),且 I (x) 1,2,1所以为使Fritz

20、 John条件u0UiU20成立，只有u0 0才行.取0U00, U1U20即可，因此x是Fritz John 点.定理4 设X是问题(1)的可行点，f(x)和gi(x)(iI(x)在点x处可微,gi(x)(iI(x)在点X处连续,并且 gi(x) (i I (x)线性无关.若I是问题(1)的局部极小点，则存在Ui0(i I(X),使得f(x) Ui gi(x) 0 .i I (x)(x称为K-T点)如果gi(x) (i I(x)在点x处也可微,则存在Ui 0(i 1,2,L ,m),使得mf(x)Ui gi(x) 0,i 1Uigi(x) 0, i 1,2,L ,m.(x称为K-T点)min

21、 f (x) (x1例2 求最优化问题s.t g1(x)x1g2(x) Xz1)2X20X2；20,的K-T点.解因为2(X1 1)f(X)1, g1(X)g2(X)0 ,所以K-T条件为12(X11 U11) U1U20,0,U1( X1 X2 2) 0, u2x20,u10,u2 0.则U11 ,这与U10矛盾.故U2 0 ,从而X2 0 ;0 ,则U12 ,这与U1 0矛盾.故U10 ,从而 U2 1, X11 ;由于U1 0,U2 0,且x (1,0)T为问题的可行点，因此X是K-T点.定理5设在问题(1)中，f(x)和gi (x)(i 1,2,L ,m)是凸函数，X是可行点,并且f(

22、x)和gi(x)(i I(X)在点x处可微.若x是问题(1)的K-T点，则X是问题(1)的全局极小点.§2.4一般约束最优化问题的最优性条件考虑等式和不等式约束最优化问题min f (x);s.t gi(x) 0,i 1,2,L ,m,(Dhj(x) 0, j 1,2,L ,l,其中 f:Rn R, gi：RnR(i 1,2,L ,m), hj : Rn R(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)和g/x)(i I (x)在点x处可微， hj (x) (j 1,

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

24、1,2,L ,l),且 Uo,Ui 0(iI(x),使lu0 f (x) ui gi(x) vj hj (x) 0 .( x 称为 Fritz Johni I(x)j 1点)若gi(x)(i I (kA在点x处也可微,则存在不全为0的数Uo,Ui (i 1,2,L ,m)和Vj (j 1,2,L ,l),且见山 0(i 1,2,L ,m),使 ml(x 称为 Fritz JohnUo f(x) Ui gi(x)Vj hj(x) 0,i 1j 1Uigi(x) 0, i 1,2,L ,m.点)22min f (x)x1x2;s.t gi(x) Xi3X20,g2(x)X2 0,h(x)(x1 1

25、)2 x2试判断x (1,0)T是否为Fritz John0.百八、120斛3 2,且 f 0，g2(x)10 L，、h1 '且1 1,2,200因此为使Fritz John条件u0u2v0 02 11成立，只有u0 0才行.所以取 Uo 0, U2 1, v 1 ,即知 x 是 Fritz John 点.定理3设x为问题(1)的可行点，f(x)和gi(x)(i I(x)在点x处可微，hj(x)(j 1,2,L ,l)在点x处具有一阶连续偏导数，gi(x)(i I(x)在点x处连续,且向量组gi(x)(i I(x), hj(x)(j 1,2,L ,l)线性无关.若x是问题(1)的局部极

26、小点，则存在数Ui 0(iI(x)和 Vj (j 1,2,L ,l),使lf(x)Ui gi(x)Vj hj(x) 0 .i I(x)j 1(I称为K-T点)如果gi(x) (i Ia)在点x处也可微，则存在数U 0(i 1,2,L ,m)和Vj (j 1,2,L ,l),使mlf (x)Ui gi(x)Vj hj(x)i 1j 1Uigi(x) 0, i 1,2,L ,m,0,(又称为K-T点)令 g(x) (g1(x), g2(x),L , gm(x)T , h(x)T (%(x), h2(x),L ,hl(x),U (Ui,U2,L ,Um)T , V (Vi,V2,L m)t ,称u与

27、v为广义Lagrange乘子向量或K-T乘子向量. 一T T _f(x) g(x) u h(x) v 0,Tu g(x) 0,u 0.令 L(x,u,v) f (x) uTg(x) vTh(x)为广义 Lagrange 函数.称 L(x,u,v)为广义Lagrange函数.则K-T条件为xL(X,u,v) 0, uTg(X) 0, u 0.定理4 设在问题(1)中，f(x)和gi(x)(i 1,2,L,m)是凸函数，hj(x)(j 1,2,L ,l)是线性函数,X是可行点,并且f(x)和gi(x)(i 1(幻)在点X处可微.若x是问题(1)的K-T点，则x是问题(1)的全局极小点. 一一 22

28、min f (x)(k3)(x21);例2 求解最优化问题st g(x)x2x20,h(x) 2xi x2 3 0.解广义Lagrange函数为 八、2/、22L(x,u,v) f(x)ug(x) vh(x)(Xi3) (x2 1)u( x x2)v(2x1x23).因为 L(x,u,v)2(x13) 2ux12v, L(x,u,V)2(x21) uv .Xix2所以K-T条件及约束条件为2(Xi3)2uXi2v0,2(x21)u v0,2u( Xi X2) 0, X12x20,2x1 x2 3 0, u 0.下面分两种情况讨论.(1)设u 0,则有2(x1 3) 2v 0, 2(X2 1)

29、v 0, 2x1 x2 3 0.由此可解得X1 7,X2 1,v8,但x (7,1)T不是可行点，因而不是 K-T点.5555 5(2)设u 0,则有2(Xi 3) 2uxi 2v 0,2(x2 1) u v 0,x12 x2 0,2x1 x2 3 0.由此可得x2 243 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是问题的全局最优解.

30、定理 5 设 x 为问题(1)的可行点，f(x), gi(x)(i I(x)和 hj(x)(j 1,2,L ,l)在点x处具有二阶连续偏导数，并且存在乘子向量u (Ui,U2,L ,um)T 0和 v (Vi,V2,L ,vm)T 0 使 K-T 条件成立，即xL(x,u,v) 0,uTg(x) 0.若对于任何满足zT gi(x) 0, iI(x)且 ui 0,zT gi(x) 0, iI(x)且 ui 0,Tzhj(x) 0, j 1,2,L ,l的向量 z 0 ,都有 zT 2xL(x, u,v)z0,则x是问题1)的严格局部极小点.例3求解最优化问题ncmin f (x) 一；i 1 X

31、st gi(x) x 0, i 1,2,L ,n,nh(x)aixi b 0,i 1其中常数 ai0, Ci 0, i 1,2,L ,n;b 0.解该问题白勺广义Lagrange函数为L(x,u,v)i 1 xi口为i 1nv(aix b) i 1因为L（x，u，v）3 Ui aiV,i 1,2,L,n.XiXi所以问题的K-T条件及约束条件为c一 .一. Ui aiV 0, i 1,2,L ,n, XiUiXi 0, i 1,2,L ,n,Xi 0, i 1,2,L ,n,naiX b 0,i 1Ui 0, i 1,2,L ,n.0, i 1,2,L ,n .于由第1式、第3式知x 0(i

32、1,2,L ,n),从而由第二式解得Ui是再由第 1 式知 v 0,且 aiVXi2 Ci 0, i 1,2,L,n,即得Xini 1b2所以X (X1,X2,L ,元),是问题的K-T点.又由于L(x,u,v)在点(XT,UT,V)T处关于x的Hesse矩阵XxL(X,U,V)是一个n 阶对角矩阵，其对角线上第i个元素为2G出 0, i 1,2,L ,n,Xi因此xxL(X,U,V)是正定矩阵.根据定理5, X为问题的严格局部极小点.第三章常用优化算法介绍§3.1一维搜索给定 Xk&Rn,令（）f（Xk dk）,0.定义如果求得步长k,使得f（Xkkdk） min f（Xk

33、d。或（k） min （ ）（3.1.1 ）则称这样的一维搜索为最优一维搜索或精确一维搜索.k叫做最优步长.定理1对于问题 min f（X）'，设f :SR是可微函数，Xk i是从Xk出发沿方向d/乍s.t x S最优一维搜索得到的，则有f（Xki）Tdk 0 .定义 如果选取 使目标函数f沿方向dk取得适当的可接受的下降量，即使得下降量f （Xk） f （Xk 1）。是我们可接受的，则称这样的一维搜索为可接受一维搜索或非精确一 维搜索.定义设：R R, 一 0,并且 ） min （ ） .如果对于a,b 0,有 一a,b,那么称a,b是问题min （）的搜索区间.定义 设：R R,a

34、,b R,若存在a,b,使得（）在a,上严格单调减 少，在二3上严格单调增加，则称a,b是（）的单谷区间， （）是a,b上的单谷函数 或单峰函数.定理2设：R,但,均为（）的单谷区间，1, 2 a,b,且12,那么（1）若（1）（ 2）,则a, 2是（）的单谷区间；若（1）（ 2）,则1,b是（）的单谷区间.算法3-1 （进退法）Step1选取初始数据。给定初始点0，初始步长h00 ,加倍系数1（一般取2）,计算0（。），置k 0.Step2 试探令 k 1 k hk,计算 k 1（ k 1）.Step3 比较目标函数值.若k 1k ,转Step4 ,否则，转Step5 .SteP4 加步探索

35、.令 hk 1hk, k, k: k 1, k: k 1,k : k 1 ,转 Step2 .Step5 反向搜索.若k 0,转换搜索方向，hk：hk,k i ,转Step2 ;否则，停止迭代.令 a mink 1, b max , k 1.输出搜索区间a,b.§3.2 0.618 法与Fibonacci 法考虑min (t),t R.假定(t)的一个搜索区间切心已确定,并设在Mb,上为单谷函数.算法 3-2 (0.618 法)Step1 选取初始数据.确定初始搜索区间a1,b1和允许误差0,0.618 .Step2 计算最初两个试探点：1 a1 (1)(bi” 1ai(bia1),

36、求出(i), ( i),并置 k 1 .Step3检查是，停止计算，输出否则，转Step4 .Step4比较函数值.若k)( k),转 Step5 ;若(k)(k)，Step6 .Step5向左搜索.令akak,bk1(k).并计算k1ak 1 (1)(bk 1(k 1)，转 Step7 .Step6向右搜索.令ak 11 :bk, k 1 k, (k).并计算k 1ak 1(bk 1ak 1), ( k1),转 Step7 .Step7定义Fibonacci数是指满足下述条件的数列Fk :F0F1Fk1Fk1,Fk 1,k 1,2,L .(3.2.1 )用数学归纳法可以证明,Fibonacc

37、i数可由下式表示:Fn1_ 15521.5 n12,n 0,1.2,L .(3.2. 2)算法 3-3 (Fibonacci法)Step1 选取初始数据.给定初始搜索区间a1,b和允许误差 0,辨别系数0,求搜索次数n ,使FnStep2 计算最初两个试探点:i ai -F12(bi a) i ai -Fn-1 (bi 研)，求函数 FnFn值(i)和(i),并置k 1.Step3 检查(订 (J ?是，转 Step4;否，转 Step5 .Step4向左搜索。令 烝涿笛 k, k i k, ( k i)( k).并计算 k i ak i Fn k 2 也 i ak i)和(k i),转 St

38、ep6 . FnkStep5 向右搜索令 akik,bki： bk, k, ( ki)( k).并计算 k iak i Fn k i (bk i ak i)和(k i)，转 Step6 -Fn kStep6 置 k： k i,若 k n i,转 Step3 ；若 k n i,转 Step7.Step7 令 n ni, n ni ，计算(n)和(n)。若(n)( n),则令an ： an i,bnn ；否则，令Hn n,4 ： Hi,停止计算，极小点含于区间an,bn .§3.3 Newton 法考虑min (t),t R.假定 (t)具有三阶连续导数.算法 3-4 (Newton 法

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

40、一维搜索取dkf(xk),求k和Xki,使得f(Xkkdk)min f(Xkdk),xk 1Xkkdk-令 k : k 1,返回 Step2 .特别地，考虑1 T Tmin f (x) - x Qx b x c,2(3.4.2 )其中x Rn,Q Rnn为正定矩阵，b Rn , c R .设第k次迭代点为Xk,从点Xk出发沿f(Xk)作一维搜索，得Xk 1Xkk f (Xk),其中k为最优步长.根据定理3.1.1 ,有 f (Xk 1)T f (Xk) 0 .而f (x) Qx b, x Rn,所以f(Xk1)f(Xk)kQf(Xk),从而(f (Xk)kQf(Xk)Tf(Xk)0,而 Q正定

41、，即f(Xk)TQ f(x。 0,故由上式解出f(Xk)T f(Xk)k _ t _f (Xk) Q f (Xk)(3.4.3 )于是Xk 1Xkf(Xk)f(Xk)T f(Xk)f(Xk)TQ f(Xk)(3.4.4 )这是最速下降法用于问题（3.4.2）的迭代公式.用最速下降法求解问题其中xT（%»2）.取初始点(0) x2min f(x) 4x1（1,1：T ,允许误差2 x2 ，(3.4.5 )0.1.问题（3.4.5 ）中的f是正定二次函数，且00,b ,c 020f在点x （x1,x2）T处的梯度f(x)(8x,2x2)T .第一次迭代:令搜索方向df(x(0)( 8,

42、2)T ,d(0),67 2.V从点x出发沿d作一维搜索，由（3.4.3 ）式和（3.4.4 ）式有深。.130769,x (1,1)T 0.130769( 8, 2)T ( 0.046152,0.738462) T .第二次迭代:f(x)(0.369216, 1.476924)T ,、 2.18305 1.522375从点x（1）出发沿d作一维搜索，按（3.4.4 ）式得x(2)(0.101537,0.147682) T .第三次迭代:f (x )(0.812296, 0.295364)T ,0.747056 0.864329按（3.4.4 ）式求得x(0.009747,0.107217)

43、T .第四次迭代:令 d f(x)(0.077976, 0.214434)T, |d(3)|J0.052062 0.228171,按(3.4.4 )式求得x(0.019126,0.027816) T .第五次迭代：令 d(4)f(x(4) ( 0.153008, 0.055632)T ,|d(4) | J0.026506 0.162807,按(3.4.4 )式求得x(0.001835,0.020195) T .此时，| f(x(5)| J0.001847,已满足精度要求，故得问题(3.4.5 )的近似最优解x(5)( 0.001835,0.020195) T .实际上问题(3.4.5 )的最优

44、解为x (0,0) T .§3.5 Newton 法算法 3-6 ( Newton 法)Step1选取初始数据.选取初始点x0,给定允许误差0,令k 0.Step2检查是否满足终止准则.计算f(xk),若| f(xk)|，迭代终止，xk为问题(3.4.1 )的近似最优解；否则，转 Step3 .Step3 构造 Newton 方向.计算2 f (xj1,取 dk 2 f (xj 1 f(xj .Step4 求下一个迭代点.令 xk 1 xk dk , k : k 1 ,返回Step2 .例2 用Newton法求解问题(3.4.5 ),仍取初始点x(0) (1,1)T,允许误差 0.1

45、.解 f (x(0) (8,2)T ,2 f (x(0)8 0，故由于2f(x(0) 1(1)(0). (0)x x df(x(1)01/8001/2,d(0) 2f(x(0)1 f(x(0)1 ,1(1,4(1,40.1,迭代结束,算法3-7 (阻尼Newton法)Stepl选取初始数据.选取初始点Step2题(3.4.1 )Step3Step4其中x(0,0) T.得x为问题(3.4.5 )的最优解.X0 ,给定允许误差检查是否满足终止准则.计算f (xk),若的近似最优解；否则，转 Step3 .构造Newton方向.计算2 f (xk) 1 ,取dk进行一维搜索.求k和xk 1,使得f

46、 (xkkdk)min f (xkdk)xk 1xkkdk-0,令 k 0.f (xk)|,迭代终止，xk为问2f(xk)1 f(xk).1 ,返回 Step2 .用阻尼Newton法求解下面问题:-2_2 2min f (x) (1 x1)2(x2 x1 ),(x1,x2)T .取初始点x(0)(0,0)T ,允许误差第一次迭代:f(x)2 f (x)f(x(0)2 f (x(0)(3.5.1 )0.1.是，Newton 方向 d(0)22(1 x1) 8(x2 x14(x2 x；)22、16K8(x2 x1 )8x1)X2 8x142,0)T,f(x(0),2f(x(0) 11/2001/

47、42 f (x(0) 1f (x(0) (1,0)T ,从 x(0)出发沿 d 作一维搜索,(0)(0)24(0)1即求mipf(xd(0)min(1 )22 4的最优解，得到 万.令xx(0)d(0)(1/2,0)T.f(x(1) (0, 1)T,| f(x(1) 1第二次迭代：2 f (x(1),2f(x(1) 1d(1)2 f (x)1 f(x)(1/4,1/2)T.从x(1)出发沿d作一维搜索，即求1min f (x(1)d)min 8(2)2 (2)400 128的最优解，得到2 .令§1.1 d(1,1)f(x(1) (0, 1)T,| f(x(1) 1此时，f(x)(0

48、,0)T,| f(x)| 0 ，得问题(3.5.1 )的最优解为x(1,1,这是惟一的最优解.§3.6 共腕梯度法定义 设Q Rnn为正定矩阵.若 Rn中的向量组d0,d1,L ,dm1满足djQdj0, i, j 0,1,L ,m 1,i j ,则称d0,d1,L ,dm 1是Q共轲的.算法3-8 (共轲方向法)给定一个正定矩阵Q Rn n.Step1 选取初始数据.选取初始点x0,给定允许误差 0.Step2 选取初始搜索方向.计算f(x0),求出d0,使 "x。)。0,令k 0.Step3检查是否满足终止准则.若| f (xk)|，迭代终止；否则，转 Step4.St

49、ep4 进行一维搜索.求k和Xk 1,使得f (Xkkdk) min f(Xkdk),xk 1xkkdk-Tep5选取搜索方向.求dk i使dk 1TQdj0, j 0,1,L,k,令 k : k 1,返回 Step3 .如果用共轲方向法求解正定二次函数的无约束最优化问题1 T _min f (x) x Qx2bTx c,(3.6.1 )其中Q Rnn为正定矩阵，b Rn,cR (此时算法中的正定矩阵应与二次函数的正定矩阵一致)，那么容易推出迭代公式为对于问题(3.4.1 )的求解,Fletcher-Reeves(FR)公式:Dixon-Myers ( DM 公式：kXk 1x f (Xk)T

50、 dk dx dkTQdkdk-我们还有如下一些方法.f(Xk)2 'f(Xk1)T f(Xk1).djf(Xk)(3.6.2 )Polak-Ribiere-Polyak (PRP公式:f(Xk1)T f(Xk1)f(Xk)f(Xk)T f(Xk)算法3-9 (FR共轲梯度法)Step1选取初始数据.选取初始点X0 ,给定允许误差0.Step2 检查是否满足终止71则.计算f(x0),若| f (x0)|，迭代终止，Xo为(3.4.1 )的近似最优解；否则，转 Step3.Step3 构造初始搜索方向.计算d0 f(x0), k 0 .Step4 进行一维搜索.求k和xk 1 ,使得f(Xkkdk)min f(Xkdk),xk 1 xkkdk-令 k : k 1,返回 Step2 .Tep5检查是否满足终止准则.计算f(xk1),若| f(xk1)，迭代终止，Xki为(3.4.1 )的近似最优解；否则，转 Step6.xn ,返回 Step3 ;否则，转 Step7.(1“2II f (