最优化方法课程复习考试

1、最优化方法复习提要第一章最优化问题与数学预备知识. 1模型无约束最优化问题min f (x), x =(%必,|风)丁Rn .约束最优化问题(Sxx- RSgx) _0,i =1,2, ,m;hj(x) =0,j =1,2,，1)min f (x); rs.t x w S.m i nf x();hj(x)= 0j 严11佝1山21,其中f (x)称为目标函数，X1,X2,|l(,Xn称为决策变量，S称为可行域, gi(x)_0(i =1,2JI|,m),hj(x0(j =1,2,川,1)称为约束条件. 2多元函数的梯度、Hesse矩阵及Taylor公式定义 设f : Rn R, Rn .如果n

2、维向量p , _ x Rn，有f (x 二x) - f (x) = pT x o-x ).则称f (x)在点x处可微，并称df(x)=plx为f (x)在点x处的微分. 如果f(x)在点x处对于X =(X1,X2,|l|,Xn)T的各分量的偏导数 皿,i=1,2，川,n:X都存在，则称f(x)在点X处一阶可导，并称向量屮斫(卫平川占)TCX-IGX2c xn为f (x)在点X处一阶导数或梯度.定理1设f : Rn r R, X Rn .如果f (x)在点x处可微，则f (x)在点x处梯度f (x) 存在，并且有 df (x)八 f (x)T ：x .定义设f : RnR,Q Rnd是给定的n维

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

4、定义 设f ：Rn R,O Rn .如果f (x)在点x处对于自变量x =(Xi,X2,|l| ,Xn)T的各分量的二阶偏导数 土凶(i,j =1,2,H|,n)都存在，则称函数f(x)在点x处二阶 EXjfXj可导，并称矩阵刊(刃、c x xnFf)c x2c xnI1Ff()o2-xnf2f(X)f2f(X)f (X)二;：2x1III;：2x2IIIf2f(x)III:Xn ： X2为f (x)在点x处的二阶导数矩阵或Hesse矩阵.定义 设 h : Rn Rm , x Rn，记 h(x) =(hi(x), h2(x),|l|,hm(x)T，如果hi(x) (i =1,2,IH,m)在点

5、X处对于自变量x =(捲必1|凶)丁的各分量的偏导数罗22山E2川，n)都存在，则称向量函数h(x)在点x处是-一阶可导的，并且称矩阵f eh1(x)期(X)IIIh1(x)cx1cx2CXnt?h2(x)咅 h2(X)IIIch2 (x)Wmnh(X)=CX-I+cx2CXn1+chm(X)8hm(X)+III1hm(X) CX1cx2FXn为h(x)在点x处的一阶导数矩阵或Jacobi矩阵，简记为 h(x).例2 设a Rn,x Rn,bR，求f(x)二aTx，b在任意点x处的梯度和Hesse 矩阵.n解 设a 二佝耳，|l|,an)T,x =(Xi,X2川丨,Xn)T，贝U f(x) =

6、 6 akXk - b ,7因丄3 二 ak(k =1,2,111, n)，故得 f(x)=a.*又因=o(j, j =1,2,H|,n)，贝H 例3设Q Rn n是对称矩阵，b Rn,cR，称f (x xTQx bTx c为二 次函数，求f(x)在任意点x处的梯度和Hesse矩阵.解 设 Q =(qij)n n,X=(X1,X2,川,人几13=(3山2,11|,0)丁，则1 n nnf(X1,X2,|l|,Xn)qijXiXj v bkXk c， im j mk=lf(x) =0 .f(x)CX1从而灯f (x)=:Ef (x)广n乞ch%j仝nZ q x +bTnj 八 jf R二阶可导，

7、xRn,d Rn,tR，解由多元复合函数微分法知:(t) J f (x td )Td , : (t) =dT 2f (x td)d .定理4设f ：Rn R, Rn，且f （x）在点x的某邻域内具有二阶连续偏导数，则f （x）在点x处有Taylor展式f（x =x）二 f（x） f（x）T =x lxt 2f （x k ：x）lx,（0 ： v : 1）.证明 设：（t） = f（x t：x）,t 0,1，则：（0） = f （x），=f （x .：X）.按一元函数Taylor公式（t）在t = 0处展开，有（t）二（0）（0）t 丄飞）t2,（0 二:t）.2从例 4 得知（0） = f（x

8、）T，x,:（二）=Cx）Tl 2 f （x nx）.；x .1令t -1，有 f （x：x）二 f（x） f（x）T ：xxT 2f （x x） x, （0 十：:1）.根据定理1和定理4，我们有如下两个公式f（x） =f（x）f（x）T（x-x）o（x-x），f （x） = f （壬）仅）T （x x） + （x _x）TN2 f（x）（x -2） +o（| x-刘 j . 3最优化的基本术语定义设f : Rn R为目标函数，S Rn为可行域，xS .（1）若-xS，都有f （x） f（x），则称x为f（x）在S上的全局（或整体）极小点，或者说，x是约束最优化问题minf（x）的全局（或整

9、体）最优解，并称f（x）为其最优值.(2) 若-x S, x = X，都有f(x) . f (x)，则称X为f (x)在S上的严格全局(或 整体)极小点.(3) 若茨的 6 邻域 N&x) =xe Rx-x0)使得 PN&x)Ds，都 有f(x)_f(x)，则称x为f (x)在s上的局部极小点，或者说，x是约束最优化 问题min f (x)的局部最优解.X手(4) 若 x 的：邻域 N、.(x)C. .0)使得- x N、.(x)riS,x = x，都有 f(x) f(x)， 则称x为f (x)在S上的严格局部极小点.第二章最优性条件2.1无约束最优化问题的最优性条件 定理1设f : Rn ；

10、 R在点x处可微，若x是问题min f (x)的局部极小点，则f (x) =0 .定义 设f : S( Rn) R在x intS处可微，若f (x0，则称x为f (x)的平稳点.定理2设f : Rn R在点x处具有二阶连续偏导数，若x是问题min f (x)的局部极小点，贝U、f(x)=0，且12f(x)半正定.定理3设f ：Rn R在点x处具有二阶连续偏导数，若 f(x)=0，且 2f(x)正定，则x是问题min f (x)的严格局部极小点.注：定理2不是充分条件，定理3不是必要条件.例1 对于无约束最优化问题min，其中乂珂论兀厂R2，显然f(x) =(2冷-3x；)T,R2，令 f(x)

11、 = 0,得 f(x)的平稳点 x =(0,0)T，而且2f(x) = 0_6x2 J2f(x)=o0020易见I2f(x)为半正定矩阵.但是，在x的任意6邻域x x|，总可以取到X = (0,?)T，使f(X) fx)一 ,丨 2即X不是局部极小点.例2 对于无约束最优化问题 min f(x) = x： 2x2x； x2，其中x=(Xi,X2)t R2 ,易知 l f (x) =(4x； - 4x|,4Xi2X2 - 4x；)t，从而得平稳点 x (0,0) T，并且l2f(x) =12x12 4x；8X20 0、N2f(X) =丿1 8x22 24x.|12x2显然i ；f(x)不是正定矩

12、阵.但是,f(x)=(x； X；)2在x处取最小值，即x为严格局部极小点.例3 求解下面无约束最优化问题min f (x) =1 Xi33+ 1x| -X； - Xi，3其中 x =(为,x；)T R2，解因为、f (x)=Lf(x)/2x1002x； _2x； 1 = 0二 0.所以令 f(x)=0,有；_，2 _2x2解此方程组得到f(x)的平稳点,x(2)=(3),x()=宀x(1)从而、2f(x(1)20、2f(x(2) =2由于 2f(x)和 2f(x)是不定的，因此x(1)和x(4)不是极值点. 2f(x)是负定的，故X不是极值点，实际上它是极大点.2f(x)是正定的，从而X是 严

13、格局部极小点. 定理4设f ：R“r R是凸函数，且f(x)在点Rn处可微，若l 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 bT x c有唯一的严格全局极小点2x - -Qb，其中Q为n阶正定矩阵.证明 因为Q为正定矩阵，且f(x)二Qxb,-xRn，所以得f (x)的唯一平稳 点x-Qb .又由于f(x)是严格凸函数，因此由定理 4知，x是f (x)的严格全 局极小点.2.2等式约束最优化问题的最优性

14、条件定理1设f ：Rn R在点x处可微，hj：Rn R(j -1,2|,l)在点x处具有一阶 连续偏导数，向量组 hi(x),h2(x),|l(j h(x)线性无关.若x是问题min f (x);s.t hj(x) =0, j =1,2,川,1的局部极小点，贝Uj R, j =1,2,川,1，使得l、f (x) _、 V, hj(x) = 0 .j 二称 L(x,v) = f (x) -vTh(x)为 Lagrange函数，其中 h(x) =(h(x), h2(x),|l| ,hl(x)T .称v =(vV2,|I|,V|)T 为 Lagrange乘子向量.l易见 L(x,v)=这里、xL(x

15、,v) = f (x) v/ hj(x),、vL(x, v)二-h(x).j定理2设f : Rn R和hj :Rn R(j -1,2jH,l)在点xRn处具有二阶连续偏 导数，若 v R1，使得 丄(7：v) 0并且，zRn,z = 0，只要zThj(X)=O, j =1,2,川,1，便有 z XxL(x,v)z .0,则 x 是问题min f (x);s.t hj(x)=0, j =1,2，川,1的严格局部极小点.例1试用最优性条件求解min f (x) = x： x；;s.t h(x)二 x2 _8 = 0.2片 _vx2解 Lagrange函数为 L(x,v) =x；+x；vx?-8)，

16、则#L(x,v)= 2x2v%，L(xix2 8)J从而得L（x, v）的平稳点G,8, ,8,2）t和（r& -.、8,2）T，对应有x = (、, 8,、, 8)T ,v =2和 x = (-、, 8, -i 8)T, v = 2 .2由于 xxL(x,v)2-v 广2-2、；Vh(x)=X2 2 R, S, f(x)在点x处可微.若x是问题min f (x)的局部极小点，则X睜对于min f (x);s.t g (x) _0,i =1,2，川，m,(1)其中 f : Rn R, gi : Rn R(i =1,2,1 山 m).令l(x)二i |gi(x0, i =12|H，m，其中x是上

17、述问题(1)的可行点.定理2 设x是问题(1)的可行点，f(x)和gi(x)(L I(x)在点x处可微,gi(x) (k I (x)在点x处连续，如果x是问题(1)的局部极小点，贝U FoClGof ,其中 Go 二d|ig(x)Td 0, r I (x).定理3设x是问题(1)的可行点，f(x)和gi(x)(r I(x)在点x处可微,gi(x) (n I (x)在点x处连续，若x是问题(1)的局部极小点，则存在不全为0的非负数u0,ui (L I(x)，使U(A f (乂)-uj gi (x 0 .i)(x 称为 Fritz John 点)如果gi(x)(i T(x)在点x处也可微，则存在不

18、全为0的非负数口0,5,川8，使u?f(x uigi(x)=O,i =1Mgi(x)=0, i =1,2，川,m.(x 称为 Fritz John 点)min f(x) = -x1;例 1 设 *s.t g,x) =(1 xj3 X2 g2(x) =X2 =0.-0,试判断x = (1,0)T是否为Fritz John点.解因为f (x)=所以为使Fritz John条件u0-10r0-10-1且 l(x)=1,2,二0成立，只有u0 = 0才行.取u0 =0, u1 =u0 即可，因此 x 是 Fritz John 点.定理4 设x是问题(1)的可行点，f(x)和gi(x)(i I(X)在点

19、x处可微,gi(x) (K I (x)在点x处连续，并且gi(x) (r I (x)线性无关.若x是问题(1)的局部极小点，则存在ui _0(L I(x)，使得、f (x) - uA g (x) = 0 .( x 称为 K-T 点)i)如果gi(x)(i T(x)在点x处也可微，则存在Ui _0(i =1,2,|(,m)，使得f(x)m Uiig(x) =0,(x称为K-T点)=i生yg/x) =0, i =1,2,川，m.- 2min f (x)=(捲一1) +x2;例2 求最优化问题s.t gx)=-为-X2+2兰0,的K-T点.g2(x)7 王 0因为 f(x)= f 罕 1),J2(X

20、)=仁所以K-T条件为2% -1) + u1 =0,1 +比 _u2 =0,5(-为X22) =0,u2x2 = 0,5 _ 0,u2 - 0.若u2 =0，则5 = T，这与u1 -0矛盾.故u2 0，从而X2 = 0 ;若-为2=0，则s = -2，这与5 一 0矛盾.故5=0，从而u2 = 1,为=1 ;由于5一0,氏-0,且x -(1,0)T为问题的可行点，因此x是K-T点.定理5设在问题(1)中，f(x)和7(x)(i =1,2,|(,m)是凸函数，x是可行点,并且f(x)和gi(x)(i1仮)在点x处可微.若x是问题(1) 的 K-T点，则x是问题(1)的全局极小点.2.4 一般约

21、束最优化问题的最优性条件续.若x为问题（1）的局部极小点，则存在不全为0 的数 U0, Ui (L I (x)和考虑等式和不等式约束最优化问题min f(x);Ijs.t gj (x) ZO,i =1,2,川，m,(1)hj(x) =0, j =1,2,|,l,其中 f:Rn R, gi : Rn R(i =1,2J|,m), hj：Rn R(j =1,2J|,l) 并把问题(1)的可行域记为 S -X S, I (X) |_i lgi(x) = 0, i = 1,2,m.定理1设x为问题(1)的可行点，f (x)和gi(x) (r I (x)在点x处可微, hj（x） （j = 1,2川,在

22、点x处具有一阶连续偏导数,gi（x）（L- I（x）在点x处连续,并且向量组（方），小2（乂），川八h（x）线性无关.若x是问题（1）的局部极小点, 贝 U F0 riGjlH：;这里 F。二d|f（x）Td : 0 , G。二d|gi（x）Td 0, i l（x）,H。二d|hj（x）Td =0, j =1,2,川,1.定理2 设x为问题（1）的可行点，f（x）和gi（x）（i I&）在点x处可微，gi（x）（i T（x）在点 x 处连hj（x） （j = 1,2川丨在点x处具有一阶连续偏导数,(x 称为 Fritz John 点)0 的数 U0, Ui (i =1,2川,m)和(x 称为

23、Fritz John 点)Vj (j =1,2,|)l,l)，且 U0,Ui 0(il(x)，使lf (x) Uji gi(x)Vji hj(x)二 0 .i 召(x)jT若gi(x) (i I (x)在点x处也可微，则存在不全为Vj (j =1,2jH, l)，且 u,Ui 0(i =1,2,|l(,m)，使mlU0f(x)- Uigi(x)- Vjhj(x)=0,i#j#Ugi(x)=0, i =1,2|,m.2 2min f(x)=为 +屜；3例 1 设严 gl(x) =X1 -X2 -0, 试判断 X=(1,O)T 是否为 Fritz John 点. g2(x) =X2 亠0,2h(x

24、) = -( 1) +x2 = 0.l(x)二(2 2,且 Vf (x) = 0 , Vg2(x)=0J丿且 1(小1,2,因此为使Fritz John条件u0 2 -u2 J0=(0 i成立，只有u0=0才行.所以 1丿J丿J丿1丿取比=0,匕=1, v - -1，即知 x 是 Fritz John 点.定理3设x为问题(1)的可行点，f(x)和gj(x)(i l(x)在点x处可微, hj(x) (j =1,2川,在点x处具有一阶连续偏导数，gi(x)(i T(x)在点x处连续, 且向量组 9(x)(i l(x), lhj(x)(j =1,2,111,1)线性无关.若x是问题(1)的局 部极

25、小点，则存在数ui -0(r I (x)和Vj (j =1,2,|)|,l)，使(x称为K-T点)l、f 仅)一為 u, gi 仅)一嘉 Vj、hj(x)二 0 .i)j 二如果gi( x) (f ( x在9点x处也可微，则存在数5 一0 (i =1,2,|( ,m)和Vj (j =1,2川 1,1)，使Iml(x称为K-T点) f(x)-、u gi(x)Vj hj(x)=0,57j#Ujgi(x)=0, i =1,2,|l|,m.令 g(x) (x), g2(x), |l|, gm(x)T , h(x) phx), h2(x),|)l, hi(x)T，U =(U1, U2, |l(,Um)T

26、 , V =(V1,V2,川,V|)T，称u与v为广义Lagrange乘子向量或K-T乘子向量.帝f (2) _g(x)TU _h(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条件为PxL(X,u,v) =0, uTg(X) =0, u兰0.定理4 设在问题(1 )中，f(x)和一 gdx)(i =12M，m)是凸函数， hj(x)(j =1,2,川，1)是线性函数，X是可行点，并且f(x)和gdx)(i I(刃)在点X处 可微.若x是问题

27、(1)的K-T点，则x是问题(1)的全局极小点.- 2 2min f (x)=(为 一3)十化 一1);例2求解最优化问题 s.t g(x) - -x； X2 _0,h(x) =2x1 + X2 3 启 0.解广义Lagrange函数为2 2 2r L(x,u,v)$X2L(x,u,v) = f (x)-ug(x) -vh(x)=(捲-3)(x2-1) 一u(-论x2)-v(2xjx2-3).因为L(x,u,v)= 2(x3) 2ux2v， cx1所以K-T条件及约束条件为2(% - 3) + 2u% - 2v = 0,2(X2 1) u v = 0,2u(-X1X2) =0,2-x-! +x

28、2 兰0, 2片 +x2 _3 =0,u 一0.F面分两种情况讨论.(1) 设u =0，贝U有2(为-3)-2v =0, 2(X2 -1)-v =0, 2x0矛盾).v = -1或v=27 .由此可知x =(1,1)r是问题的K-T 点，但x=(-3,9)T不是问题的K-T点.易见，f (x)是R2上的凸函数，g(x)是R2上的凹函数，h(x)是线性函数， 因此由定理4知，乂=(1,付是问题的全局最优解.定理5设x为问题(1)的可行点,f(x), g(x)(il(x)和hj(x)(j =1,2,川，1)在点x处具有二阶连续偏导数，并且存在乘子向量U =(U1,U2,|l|,Um)T 一0和 v

29、 =(v1,V2jl|,Vm)T -0 使 K-T 条件成立，即 xL(x,U,V) =0,UTg(x)=0.若对于任何满足”zTNgi(x)A0,诈 I (乂)且 4 =0,zT、gi(x) =0, r I (x)且 Ui 0,zPhj(x)=0, j=1,2|(,l的向量z=0，都有zTi：L(x,U,v)z0,则x是问题(1)的严格局部极小点.nmin f (x) 冬例3求解最优化问题 s.t gKx) = xi 一 0, i =1,2,1 , n,nh(x)=送 a* -b =0,I其中常数 3i 0, Ci 0, i “211(,n；b 0 .解该问题的广义Lagrange函数为nn

30、nL(x,u,v) 八 cun -v(、qx -b).i = xii =1i =1因为：L(x,u v )CXic2Xi-u aiv, i所以问题的K-T条件及约束条件为2 ui a v = 0, i = h211, n, XiUiXi =0, i =12ill，n,人 一0, i =12,n,n区 aj x -b = 0,i M 30, i =1,2|,n.Ui = 0, i = 1,2,| 1(, n .于由第1式、第3式知x 0(i =12川,n)，从而由第二式解得是再由第 1 式知 v ：0，且 QvXi2 y =0, i =1,2,|)l,n ,nn,aiCf)2即得 Xj = /

31、, i =1,2,川，n ,从而q b = 0，解得 v = 一2 -aivz Y -aivb、罰&=12川小i A所以X =(X1,X2,|l|,Xn)T是问题的K-T点.又由于L(X,u,v)在点(XT,UT,v)T处关于X的Hesse矩阵 XxL(X,U,v)是一个n 阶对角矩阵，其对角线上第i个元素为2c令 0, i =1,2,111, n ,Xi因此 2xL(x,u,v)是正定矩阵.根据定理5, X为问题的严格局部极小点.第三章常用优化算法介绍3.1一维搜索给定 Xk,dk Rn，令()=f(XkdQ, - 0 .定乂如果求得步长/.k，使得f(Xkkdk)二min f(Xkdk)或

32、(Q 二mip ()(3.1.1) 0 0则称这样的一维搜索为最优一维搜索或精确一维搜索. k叫做最优步长.定理1对于问题min f(X)；，设f sR是可微函数，xkd是从xk出发沿方向dk作s.t xS最优一维搜索得到的，则有f(Xki)Td0 .定义 如果选取 “，使目标函数f沿方向dk取得适当的可接受的下降量，即使得下降量f (xQ - f (Xk .J 0是我们可接受的，则称这样的一维搜索为可接受一维搜索或非精确一 维搜索.定义 设:RR,0,：，并且()= mi n() 如果对于a,b 0,：有 .- _0:尸a,b，那么称a,b是问题min : ()的搜索区间.定义 设:R R,

33、a,b R，若存在-a,b，使得 (、)在aj上严格单调减 少，在：,b上严格单调增加，则称a,b是()的单谷区间，是a,b上的单谷函数 或单峰函数.定理2 设:R)R,a,b为;:()的单谷区间，1, 2 a,b，且：匕，那么(1) 若：(1 ：(2)Ha, 2是()的单谷区间；(2) 若(J _(2)，则db是：()的单谷区间.算法3-1 (进退法)Step1选取初始数据。给定初始点0,初始步长h0 0 ,加倍系数 1 (一般取-2 ), 计算= ：(0)，置 k =0 .Step2 试探令k k hk，计算 11= ( k -1).Step3 比较目标函数值.若 1 1 ： 1，转Ste

34、p4，否则，转 Step5.Step4 加步探索.令 hk1 =hk, =k, k：=k1,，k：= k1,k:=k 1，转 Step2.Step5反向搜索.若k =0，转换搜索方向，hk -hk - - k i，转Step2;否则，停止迭代令 a =min，, k 1, b =max , k 1.输出搜索区间a,b.3.2 0.618 法与 Fibonacci 法考虑min （t）,r R .假定（t）的一个搜索区间知已确定，并设:（t）在山上为单谷函数.算法 3-2 （0.618 法）Step1选取初始数据确定初始搜索区间a1,bi和允许误差；0 =0.618 .Step2 计算最初两个试

35、探点：、=印（1 - .）（0 -印），叫二aj （0 - aj ,求出（J,（叫），并置 k=1.Step3检查 k 0，置k = 0.Step2检查 （tk） c E?是，输出tk，停止计算；否，转 Step3.Step3cP7tk)计算点 tk+=tk 卑k)，置 k：=k+1，转 Step2.(tk )3.4最速下降法考虑无约束最优化问题(341)m i nf x(,)其中f : Rn R具有一阶连续偏导数.算法3-5 (最速下降法)Stepl选取初始数据选取初始点X。，给定允许误差； 0，令k =0 .Step2检查是否满足终止准则计算f(Xk)，若|f(Xk)：；,迭代终止，Xk为

36、问题(341 )的近似最优解；否则，转Step3.Step3进行一维搜索取dk -八f (Xk)，求 k和Xk .1，使得f (Xk=mip f (兀dQ ,-0Xk i=Xk kdk.令 k :二 k 1，返回 Step2.特别地，考虑1m i nf x( =) xtQx bTx c,(3.4.2)其中Rn,QRn n为正定矩阵，bRn,cR .设第k次迭代点为Xk，从点Xk出发沿-f (Xk)作一维搜索，得Xk 1=Xk - f (Xk),其中K为最优步长根据定理3.1.1，有可f(xdTXf)x0= 而0 fX)gb刘R n , 所以 f(Xk 1)Jf(Xk) - kQ f(Xk)，从

37、而 C f (Xk) - 2、f(Xk)b f (Xk) =0，而 Q 正 定，即f (Xk)TQ f (Xk) 0，故由上式解出:可(Xk)Pf(Xk)(343)(344)(345)kt-、f (Xk) Q f (Xk)于是X _x _ (Xk八 f(xk)“(X)k1 k (Xk)Qf(Xk) f(k)这是最速下降法用于问题(3.4.2)的迭代公式.例1 用最速下降法求解问题min f (x)二 4x12 x22 ,其中X=（Xi,X2）T 取初始点X（0） =（1,1亍，允许误差；=0.1.解 问题（345）中的f是正定二次函数，且0、,b =f 在点 x =(X1,X2)T处的梯度 f

38、 (x) =(8x1,2x2)T 第一次迭代:令搜索方向 d(x ) =(-8,-2)丁 ,d(0)= ,64 =217；,从点x（0）出发沿d（0）作一维搜索，由（3.4.3）式和（344）式有备 .130769，x=(1,1)T 0.130769(七-2)(-0.046152,0.738462) T .第二次迭代:令 d -(x)=(0.369216, -1.476924)t ,=2.18305=1.522375；,从点X出发沿d作一维搜索，按（3.4.4）式得x=(0.101537,0.147682) T .第三次迭代:令 d(x)=(-0.812296, -0.295364)T ,d

39、一0.747056 二 0.864329；,按（3.4.4）式求得x=(-0.009747,0.107217) T .第四次迭代:令 d -f (x(3) =(0.077976, -0.214434)丁 ,d 二 0.052062 = 0.228171按(344)式求得= (0.019126,0.027816)第五次迭代:令 d-if (x )=(-0.153008, -0.055632)丁 ,d= 0.026506 = 0.162807；,按(3.4.4)式求得x(5)= (-0.001835,0.020195)1此时，f (x)=、0.001847 ：；,已满足精度要求，故得问题(3.4.5)的近似最优解-(-0.001835,0.020195)实际上问题(3.4.5)的最优解为x =(0,0)13.5 Newton 法算法 3-6 (Newt on 法)Step1选取初始数据选取初始点X。，给定允许误差； 0 ,令k = 0 .Step2检查