《最优化方法》由会员分享，可在线阅读，更多相关《最优化方法（10页珍藏版）》请在金锄头文库上搜索。
1、2012-2013（1）专业课程实践论文信赖域法董文峰，0818180123, R数学08-1班伊广旭，0818180113, R数学08-1班李 超，0818180114, R 数学 08-1 班一、算法理论信赖域方法与线搜索技术一样 , 也是优化算法中的一种保证全局收敛的重 要技术. 它们的功能都是在优化算法中求出每次迭代的位移 , 从而确定新的迭 代点.所不同的是: 线搜索技术是先产生位移方向(亦称为搜索方向), 然后确定 位移的长度(亦称为搜索步长)。而信赖域技术则是直接确定位移, 产生新的迭代 点。信赖域方法的基本思想是:首先给定一个所谓的“信赖域半径”作为位移长 度的上界，并以当前
2、迭代点为中心以此“上界”为半径确定一个称之为“信赖域” 的闭球区域。然后,通过求解这个区域内的“信赖域子问题”(目标函数的二次近 似模型) 的最优点来确定“候选位移”。若候选位移能使目标函数值有充分的下 降量, 则接受该候选位移作为新的位移,并保持或扩大信赖域半径, 继续新的迭 代。否则, 说明二次模型与目标函数的近似度不够理想,需要缩小信赖域半径， 再通过求解新的信赖域内的子问题得到新的候选位移。如此重复下去，直到满足 迭代终止条件。信赖域方法解决无约束线性规划min f(x)xeR的基本算法结构。设x是第k次迭代点，记f二f(x ), g = Vfx ), B是Hessekkkkkk阵V2
3、 f(x )的第k次近似，则第k次迭代步的信赖域子问题具有如下形式：k1min q (d) = gTd + dTB d,k k 2 ks.t. d Ak其中A是信赖域半径，|卜|是任一种向量范数，通常取2 -范数或3 -范数。k定义Afk为f在第k步的实际下降量:Af 二 f - f(x + d ),k kk k定义Aq对应的预测下降量:kAq 二 q (0)- q (d )k kk k定义他们的比值为：Afr = kk Aqk则Af 0。因此，若r 0，kk一个迭代点，需要缩小信赖半径重新求解问题。若 r 比较接近于1，说明二次模k型与目标函数在信赖与范围内有很好的相似，此时x二x + d可
4、以作为新的迭k +1 k k代点，同时下一次迭代时可以增大信赖半径，对于其他情况，信赖半径可以保持 不变。二、算法框图三、算法程序function xk,val,k=trustm(x0) n=length(x0); x=x0; dta=1; eta1=0.1; eta2=0.75; dtabar=2.0; tau1=0.5; tau2=2.0; epsilon=1e-6; k=0; Bk=Hess(x);while(k50) gk=gfun(x);if(norm(gk)epsilon)break;endd,val,lam,ik=trustq(gk,Bk,dta); deltaq=-qk(x,d
5、); deltaf=fun(x)-fun(x+d); rk=deltaf/deltaq;if(rk=eta2&norm(d)=dta) dta=min(tau2*dta,dtabar);elsedta=dta;endendif(rketa1)x=x+d;Bk=Hess(x);endk=k+1;endxk=x;val=fun(xk);function d,val,lam,k=trustq(gk,Bk,dta) n=length(gk); gamma=0.05;epsilon=1.0e-6; rho=0.6; sigma=0.2; mu0=0.05; lam0=0.05;d0=ones(n,1);
6、 u0=mu0,zeros(1,n+1); z0=mu0,lam0,d0;k=0;z=z0; mu=mu0; lam=lam0; d=d0;while (k=150) dh=dah(mu,lam,d,gk,Bk,dta); if(norm(dh)epsilon)break;endA=JacobiH(mu,lam,d,Bk,dta); b=beta(mu,lam,d,gk,Bk,dta,gamma)*u0-dh;B=inv(A); dz=B*b;dmu=dz(1); dlam=dz(2); dd=dz(3:n+2);m=0; mk=0;while (m20)dhnew=dah(mu+rhoAm*
7、dmu,lam+rhoAm*dlam,d+rhoAm*dd,gk,Bk,dta);if(norm(dhnew) k0= -1. 2j 1 j ; zj valj k =t rustm (xO)1.00001.0000val =1.7510e-025例2 用信赖域法求解:min f (x)= 10(x - X +G - X2 1 1 解：运行程序(1)编译 fun.m输入 f = 10* (x(2) - x(l)人2 + (1-X)人2 ；2) 编译 gfun.m输入 gf = 1- 20(x(2) - x(1)-2*(1-x(1),20 * (x(2) - x(1);3) 编译 Hess.m输入 He = b2,-20;-20,20；4)运行主程序输入 x0 = 0.0;L,val,kL trustm(x0 )4)显示结果：(1.0000)x =(1.0000丿val = 6.4790e - 014k = 2val2 z0= Oj 0J ; xj valj k =t rustm (xd)6.4790e-0141.00001.0Q00
