资源描述：
《最优化方法——信赖域法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2012-2013（1）专业课程实践论文信赖域法董文峰，0818180123，R数学08-1班伊广旭，0818180113，R数学08-1班李超，0818180114，R数学08-1班一、算法理论信赖域方法与线搜索技术一样,也是优化算法中的一种保证全局收敛的重要技术.它们的功能都是在优化算法中求出每次迭代的位移,从而确定新的迭代点.所不同的是:线搜索技术是先产生位移方向(亦称为搜索方向),然后确定位移的长度(亦称为搜索步长)。而信赖域技术则是直接确定位移,产生新的迭代点。信赖域方法的基本思想是:首先给定一个所谓的“信赖域半径”作为位移长度的上界，并以当前迭代点为中心以此“上界”
2、为半径确定一个称之为“信赖域”的闭球区域。然后,通过求解这个区域内的“信赖域子问题”(目标函数的二次近似模型)的最优点来确定“候选位移”。若候选位移能使目标函数值有充分的下降量,则接受该候选位移作为新的位移,并保持或扩大信赖域半径,继续新的迭代。否则,说明二次模型与目标函数的近似度不够理想,需要缩小信赖域半径，再通过求解新的信赖域内的子问题得到新的候选位移。如此重复下去，直到满足迭代终止条件。信赖域方法解决无约束线性规划的基本算法结构。设是第次迭代点，记，，是Hesse阵的第次近似，则第次迭代步的信赖域子问题具有如下形式：其中是信赖域半径，是任一种向量范数，通常取-范数或-范数
3、。定义为在第步的实际下降量：定义对应的预测下降量：定义他们的比值为：一般的，我们有。因此，若，则，不能作为下一个迭代点，需要缩小信赖半径重新求解问题。若比较接近于，说明二次模型与目标函数在信赖与范围内有很好的相似，此时可以作为新的迭代点，同时下一次迭代时可以增大信赖半径，对于其他情况，信赖半径可以保持不变。二、算法框图三、算法程序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(
4、x);while(k<50)gk=gfun(x);if(norm(gk)=eta2&norm(d)==dta)dta=min(tau2*dta,dtabar);elsedta=dta;endendif(rk>eta1)x=x+d;Bk=Hess(x);endk=k+1;endxk=x;val=fun
5、(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);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)6、,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(m<20)dhnew=dah(mu+rho^m*dmu,lam+rho^m*dlam,d+rho^m*dd,gk,Bk,dta);if(norm(dhnew)<=(1-sigma*(1-gamma*mu0)*rho^m)*dh)mk=m;break;endm=m+1;endalpha=rho^mk;mu=mu+alpha*dmu;lam=lam+alpha
7、*dlam;d=d+alpha*dd;k=k+1;endval=gk'*d+0.5*d'*Bk*d;%%%%%%%%%%%%%%%%%%%%%%%%%%functionp=phi(mu,a,b)p=a+b-sqrt((a-b)^2+4*mu);%%%%%%%%%%%%%%%%%%%%%%%%%%functiondh=dah(mu,lam,d,gk,Bk,dta)n=length(d);dh(1)=mu;dh(2)=phi(mu,lam,dta^2-norm(d)^2);mh=(Bk+lam*
