最优化方法——信赖域法

2012-2013（1）专业课程实践论文

信赖域法

董文峰，03，R数学08-1班

伊广旭，03，R数学08-1班

李超，04，R数学08-1班

一、算法理论

信赖域方法与线搜索技术一样, 也是优化算法中的一种保证全局收敛的重要技术. 它们的功能都是在优化算法中求出每次迭代的位移, 从而确定新的迭代点.所不同的是: 线搜索技术是先产生位移方向(亦称为搜索方向), 然后确定位移的长度(亦称为搜索步长)。而信赖域技术则是直接确定位移, 产生新的迭代点。

信赖域方法的基本思想是:首先给定一个所谓的“信赖域半径”作为位移长度的上界，并以当前迭代点为中心以此“上界”为半径确定一个称之为“信赖域”的闭球区域。然后,通过求解这个区域内的“信赖域子问题”(目标函数的二次近似模型) 的最优点来确定“候选位移”。若候选位移能使目标函数值有充分的下降量, 则接受该候选位移作为新的位移,并保持或扩大信赖域半径, 继续新的迭代。否则, 说明二次模型与目标函数的近似度不够理想,需要缩小信赖域半径，再通过求解新的信赖域内的子问题得到新的候选位移。如此重复下去，直到满足迭代终止条件。

信赖域方法解决无约束线性规划

f(x)R

x ∈min

的基本算法结构。设k x 是第k 次迭代点，记)f(x f k k =，)f(x g k k ?=，k B 是Hesse 阵)f(x k 2?的第k 次近似，则第k 次迭代步的信赖域子问题具有如下形式：

,2

1g (d)min T k

d B d d q k T

k += k d t s ?≤.

.

其中k

?是信赖域半径，?是任一种向量范数，通常取2-范数或∞-范数。

定义k

f ?为f 在第k 步的实际下降量：

),d f(x f Δf k k k k +=-

定义k q ?对应的预测下降量：

()().-0k k k k d q q q =?

定义他们的比值为：

k

k

k q f r ??=

一般的，我们有0>?k q 。因此，若0

二、算法框图

三、算法程序

function [xk,val,k]=trustm(x0)

n=length(x0); x=x0; dta=1;

eta1=; eta2=; dtabar=;

tau1=; tau2=; epsilon=1e-6;

k=0; Bk=Hess(x);

while(k<50)

gk=gfun(x);

if(norm(gk)

break;

end

[d,val,lam,ik]=trustq(gk,Bk,dta);

deltaq=-qk(x,d);

deltaf=fun(x)-fun(x+d);

rk=deltaf/deltaq;

if(rk<=eta1)

dta=tau1*dta;

else if (rk>=eta2&norm(d)==dta)

dta=min(tau2*dta,dtabar);

else

dta=dta;

end

end

if(rk>eta1)

x=x+d;

Bk=Hess(x);

end

k=k+1;

end

xk=x;

val=fun(xk);

function [d,val,lam,k]=trustq(gk,Bk,dta)

n=length(gk); gamma=;

epsilon=; rho=; sigma=;

mu0=; lam0=;

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)

break;

end

A=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 (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;

end

m=m+1;

end

alpha=rho^mk;

mu=mu+alpha*dmu;

lam=lam+alpha*dlam;

d=d+alpha*dd;

k=k+1;

end

val=gk'*d+*d'*Bk*d; %%%%%%%%%%%%%%%%%%%%%%%%%%

function p=phi(mu,a,b)

p=a+b-sqrt((a-b)^2+4*mu); %%%%%%%%%%%%%%%%%%%%%%%%%%

function dh=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*eye(n))*d+gk;

for(i=1:n)

dh(2+i)=mh(i);

end

dh=dh(:); %%%%%%%%%%%%%%%%%%%%%%%%%%

function bet=beta(mu,lam,d,gk,Bk,dta,gamma)

dh=dah(mu,lam,d,gk,Bk,dta);

bet=gamma*norm(dh)*min(1,norm(dh)); %%%%%%%%%%%%%%%%%%%%%%%%%%

function A=JacobiH(mu,lam,d,Bk,dta)

n=length(d);

A=zeros(n+2,n+2);

pmu=-4*mu/sqrt((lam+norm(d)^2-dta^2)^2+4*mu^2);

thetak=(lam+norm(d)^2-dta^2)/sqrt((lam+norm(d)^2-dta^2)^2+4*mu^2); A=[1, 0, zeros(1,n);

pmu, 1-thetak, -2*(1+thetak)*d';

zeros(n,1), d, Bk+lam*eye(n)];

%function f=fun(x)

%f=100*(x(1)^2-x(2))^2+(x(1)-1)^2;

%end

%function gf=gfun(x)

%gf=[400*x(1)*(x(1)^2-x(2))+2*(x(1)-1), -200*(x(1)^2-x(2))]';

%end

%function He=Hess(x)

%He=[1200*x(1)^2-400*x(2)+2, -400*x(1); -400*x(1), 200];

%end

function qd=qk(x,d)

gk=gfun(x); Bk=Hess(x);

qd=gk'*d+*d'*Bk*d;

四、算法实现

例1用信赖域法求解 ()()2

12

221)(x 1100min 2-+-=?

∈x x x f x

该问题的精确解为()()0,1,1==**x f x T

解：运行程序 （1）编译m fun .

输入1)^2-(x(1)x(1))^2-(x(1)^2*100+=f ; （2）编译m gfun .

输入[]x (2))-(x (1)^2*1),-200-(x (1)*2-x (2))-(x (1)^2*(1)*400x gf =; （3）编译m Hess .

输入[]x (1),200*x (1);-400*2,-400x (2)*400-(1)^2*1200+=x He ;

（4）运行主程序

输入;[-1.2,1]'0=x

[])trustm(x x,val,k 0=

（4）显示结果：

????

??=0000.10000.1x 25-7510.1e val = 47=k

例2用信赖域法求解:

()()()

2

12

12-1-10min

x x x x f +=

解：运行程序

（1）编译m fun .

输入x(1))^2-(1x(1))^2-(x(2)*10+=f ;

（2）编译m gfun .

输入[]x (1))-(x (2)*x (1)),20-(1*2-x (1))-0(x (2)2-=gf ; （3）编译m Hess .

输入[],2022,-20;-20=He ;

（4）运行主程序

输入;[0.0]'0=x

[])trustm(x x,val,k 0=

（4）显示结果：

???? ??=0000.10000.1x 014-4790.6e val = 2=k

最优化方法——信赖域法

信赖域法 董文峰，03，R数学08-1班伊广旭，03，R数学08-1班李超，04，R数学08-1班 一、算法理论

信赖域方法与线搜索技术一样, 也是优化算法中的一种保证全局收敛的重要技术. 它们的功能都是在优化算法中求出每次迭代的位移, 从而确定新的迭代点.所不同的是: 线搜索技术是先产生位移方向(亦称为搜索方向), 然后确定位移的长度(亦称为搜索步长)。而信赖域技术则是直接确定位移, 产生新的迭代点。 信赖域方法的基本思想是:首先给定一个所谓的“信赖域半径”作为位移长度的上界，并以当前迭代点为中心以此“上界”为半径确定一个称之为“信赖域”的闭球区域。然后,通过求解这个区域内的“信赖域子问题”(目标函数的二次近似模型) 的最优点来确定“候选位移”。若候选位移能使目标函数值有充分的下降量, 则接受该候选位移作为新的位移,并保持或扩大信赖域半径, 继续新的迭代。否则, 说明二次模型与目标函数的近似度不够理想,需要缩小信赖域半径，再通过求解新的信赖域内的子问题得到新的候选位移。如此重复下去，直到满足迭代终止条件。 信赖域方法解决无约束线性规划 f(x)R x ∈min 的基本算法结构。设k x 是第k 次迭代点，记)f(x f k k =，)f(x g k k ?=，k B 是Hesse 阵)f(x k 2?的第k 次近似，则第k 次迭代步的信赖域子问题具有如下形式： ,2 1g (d)min T k d B d d q k T k += k d t s ?≤.. 其中k ?是信赖域半径，?是任一种向量范数，通常取2-范数或∞-范数。 定义k f ?为f 在第k 步的实际下降量： ),d f(x f Δf k k k k +=- 定义k q ?对应的预测下降量： ()().-0k k k k d q q q =? 定义他们的比值为： k k k q f r ??= 一般的，我们有0>?k q 。因此，若0

信赖域法示例浅析

信赖域法示例浅析 摘要：本文介绍了非单调信赖域算法的基本知识，包括非单调信赖域算法的理论、算法框图及数值运算实例，数值结果表明该算法在求解高维非线性规划问题时比一般算法更有效。 关键词：信赖域法信赖半径Hesse阵Bk 引言 信赖域方法是求解非线性规划问题的常用方法之一，因其具有良好的可靠性和强健的收敛性备受非线性优化领域专家们的关注[1]，信赖域方法与线搜索技术一样，也是优化算法中的一种保证全局收敛的重要技术。它们的功能都是在优化算法中求出每次迭代的位移，从而确定新的迭代点。漂亮的收敛性和有效的计算性确定了信赖域算法是一类重要和实用的方法[2]。因此研究约束优化问题的信赖域算法具有重要的意义。 1、算法的基本理论 与线搜索技术相比不同的是：线搜索技术是先产生位移方向（亦称为搜索方向），然后确定位移的长度（亦称为搜索步长）。而信赖域技术则是直接确定位移，产生新的迭代点。信赖域方法的基本思想是：首先给定一个所谓的“信赖域半径”作为位移长度的上界，并以当前迭代点为中心以此“上界”为半径确定一个称之为“信赖域”的闭球区域。然后，通过求解这个区域内的“信赖域子问题”（目标函数的二次近似模型）的最优点来确定“候选位移”。若候选位移能使目标函数值有充分的下降量，则接受该候选位移作为新的位移，并保持或扩大信赖域半径，继续新的迭代。否则，说明二次模型与目标函数的近似度不够理想，需要缩小信赖域半径，再通过求解新的信赖域内的子问题得到新的候选位移。如此重复下去，直到满足迭代终止条件。 2、信赖域方法解决无约束线性规划的基本算法结构 设■是第■次迭代点，记是Hesse阵■的第■次近似，则第■次迭代步的信赖域子问题具有如下形式： 其中■是信赖域半径，■是任一种向量范数，通常取2-范数或∞-范数。定义■为■在第■步的实际下降量： 定义■对应的预测下降量： 定义他们的比值为：。一般的，我们有■。因此，若■，则■，■不能作为下一个迭代点，需要缩小信赖半径重新求解问题。若■比较接近于1，说明二次模型与目标函数在信赖与范围内有很好的相似，此时■可以作为新的迭代点，同时

信赖域方法

信赖域方法 信赖域方法在当前搜索点附近具有一个区域，其中关于局部极小化的二次模型 被"信赖"为正确的，并且步骤被选择留在该区域内. 在搜索的过程中，区域大小根据模型和实际函数计算的符合程度被修改. 非常典型地，信赖域采取的是一个满足的椭圆. 是一个对角缩放（通常采用近似 Hessian 的对角），而是信赖域半径，它在每个步骤被更新. 当基于二次模型的步骤本身位于信赖域之内的时候，那么就认为函数值在变小，因而采用这一步骤. 因此，正如线搜索方法中一样，步控制不会干涉算法在二次模型表现良好的极小值附近的收敛效果. 当基于二次模型的步骤位于信赖域之外时，则采用一个只到边界位置的步骤，以使得该步骤成为二次模型在信赖域边界处的近似极小化步骤. 一旦一个步骤被选择，该函数就在新的点被计算，而实际函数值与通过二次模型预测所得到的值互相对照. 真正计算的是实际与预测减少量的比率. 如果接近1，那么该二次模型是一个相当不错的预测器，该区域的大小可以扩大. 另一方面，如果太小，则该区域的大小就要被降低. 当低于某一阈值时，该步骤被拒绝并重新计算. 您可以使用方法选项"AcceptableStepRatio"->控制这一阈值. 通常情况下，是相当小的，以避免走向极小值的步骤也被拒绝. 然而，如果在一个点获取二次模型相当昂贵（例如，计算Hessian 需要花费相对较长的时间），一个较大值的将降低Hessian 计算的次数，但是它可能增加函数计算的次数. 要开始信赖域算法，需要确定一个初始半径. 默认情况下，Mathematica使用基于受比较宽松的相对步长限制的模型(1) 的步骤的大小. 然而，在某些情况下，这可能使您离开您原来感兴趣的区域，所以您可以使用选项指定一个初始半径 . 该选项在它的名字中包含Scaled，因为信赖域半径使用了对角缩放，所以这不是一个绝对的步长. 这里加载一个包含一些功用函数的程序包. In[1]:= 这里显示在搜索一个与Rosenbrock函数类似的函数的局部极小值的过程中，所采用的步骤和计算，用的是了利用信赖域步控制的牛顿法.

关于无约束最优化问题的信赖域解法

关于无约束最优化问题的信赖域解法 一、引言 无约束优化问题是实际工程中最常见的问题之一。这类问题虽然形式比较简单，但是对于某些大规模的或者非线性很强的问题，求解它们仍然是有相当难度的。 无约束问题的算法大致分成两类：一类在计算过程中要用到目标函数的导数，另一类则只要求目标函数值。本文中所讲述的信赖域法，与牛顿法、最速下降法、共轭梯度法一样，同属于第一类方法。 二、信赖域法的主要内容 2.1 信赖域法的基本思想 虽然信赖域法与最速下降法等同属于一大类，但是在基本思想上还是有所不同。其他几种方法的基本策略是：给定点x(k)后，定义搜索方向d(k),再从x(k)出发沿d(k)作一维搜索，信赖域法则不然，下面重点阐述一下其基本思想：首先给定一个所谓的“信赖域半径”作为位移长度的上界，并以当前迭代点为中心以此“上界”为半径确定一个称之为“信赖域”的闭球区域。然后,通过求解这个区域内的“信赖域子问题”(目标函数的二次近似模型) 的最优点来确定“候选位移”。若候选位移能使目标函数值有充分的下降量, 则接受该候选位移作为新的位移,并保持或扩大信赖域半径, 继续新的迭代。否则, 说明二次模型与目标函数的近似度不够理想,需要缩小信赖域半径，再通过求解新的信赖域内的子问题得到新的候选位移。如此重复下去，直到满足迭代终止条件。 2.2 信赖域法的数学分析

三、 运用信赖域法求解具体问题 考虑无约束问题 432 1122min () 45f x x x x x =++-+ 取初点(1)00x ?? =????，信赖域半径r 1=1，取μ=0.25，η=0.75.用信赖域法求解过 程： 1) 将初值代入目标函数求得函数值f(x (1))=5，目标函数的梯度

信赖域方法概论

非线性优化中的信赖域方法及其应用 摘要 信赖域方法是非线性优化的一类重要的数值计算方法它在近二十年来受到了非线性优化研究界非常的重视。特别是最近几年，一直是非线性优化的研究热点。目前，信赖域方法已经和传统的线收索方法并列为非线性规划的两类主要数值方法。 关键词：信赖域法非线性优化约束条件 引言 非线性最优化是20世纪50年代发展起来的，它讨论非线性决策问题的最佳选择之特性，构造寻求最佳解的计算方法，研究这些计算方法的理论性质及实际计算表现。随着电子计算机的发展和应用，非线性最优化理论和方法有了很大发展。目前，它已成为运筹学的一个重要分支，并且在自然科学，工程技术，经济管理，系统工程，特别是“优化设计”等诸多领域得到广泛的应用，成为一门十分活跃的学科。 非线性优化的传统方法几乎都是线搜索类型的方法，即每次迭代时产生一搜索方向，然后在搜索方向上进行精确的或不精确的一维搜索，以得到下一个迭代点。信赖域方法是一类很新的方法，它和线搜索法并列为目前求解非线性规划的两类主要的数值方法。信赖域方法思想新颖，算法可靠，具有很强的收敛性，它不仅能很快地解决良态问题 ,而且也能有效地求解病态(ill-conditioned)的优化问题。因而对信赖域方法的研究是近20年来非线性规划领域的一个重要的研究方向，是当今寻求如何构造新的优化计算方法的主要途径。 信赖域方法的研究起源于Powell 1970 年的工作，他提出了一个求解无约束优化问题的算法，该算法在每次迭代时强制性地要求新的迭代点与当前的迭代点之间的距离不超过某一控制量。引入控制步长是因为传统的线搜索方法常常由于步长过大而导致算法失败，特别是当问题是病态时尤为如此。控制步长实质上等价于在以当前迭代点为中心的一个邻域内对一个近似于原问题的简单模型求极值。这种技巧可理解为只在一个邻域内对近似模型信赖，所以此邻域被称为信赖域(trust region)。利用这一技巧的方法也就被称为信赖域法。信赖域的大小通过迭代逐步调节。一般来说,如果在当前迭代模型较好地逼近原问题，则信赖域可扩大，否则信赖域应缩小。后来，人们发现信赖域方法的基本技巧在一定意义下等价于十分著名的求解非线性最小二乘问题的Levenberg - 2Marquadt方法。 一、算法理论 信赖域方法与线搜索技术一样，也是优化算法中的一种保证全局收敛的重要技术。它们的功能都是在优化算法中求出每次迭代的位移，从而确定新的迭代点.所不同的是: 线搜索技术是先产生位移方向(亦称为搜索方向)，然后确定位移的长度(亦称为搜索步长)。而信赖域技术则是直接确定位移，产生新的迭代点。

最优化方法——信赖域法

2012-2013（1）专业课程实践论文 信赖域法 董文峰，03，R数学08-1班 伊广旭，03，R数学08-1班 李超，04，R数学08-1班

一、算法理论 信赖域方法与线搜索技术一样, 也是优化算法中的一种保证全局收敛的重要技术. 它们的功能都是在优化算法中求出每次迭代的位移, 从而确定新的迭代点.所不同的是: 线搜索技术是先产生位移方向(亦称为搜索方向), 然后确定位移的长度(亦称为搜索步长)。而信赖域技术则是直接确定位移, 产生新的迭代点。 信赖域方法的基本思想是:首先给定一个所谓的“信赖域半径”作为位移长度的上界，并以当前迭代点为中心以此“上界”为半径确定一个称之为“信赖域”的闭球区域。然后,通过求解这个区域内的“信赖域子问题”(目标函数的二次近似模型) 的最优点来确定“候选位移”。若候选位移能使目标函数值有充分的下降量, 则接受该候选位移作为新的位移,并保持或扩大信赖域半径, 继续新的迭代。否则, 说明二次模型与目标函数的近似度不够理想,需要缩小信赖域半径，再通过求解新的信赖域内的子问题得到新的候选位移。如此重复下去，直到满足迭代终止条件。 信赖域方法解决无约束线性规划

f(x)R x ∈min 的基本算法结构。设k x 是第k 次迭代点，记)f(x f k k =，)f(x g k k ?=，k B 是Hesse 阵)f(x k 2?的第k 次近似，则第k 次迭代步的信赖域子问题具有如下形式： ,2 1g (d)min T k d B d d q k T k += k d t s ?≤. . 其中k ?是信赖域半径，?是任一种向量范数，通常取2-范数或∞-范数。 定义k f ?为f 在第k 步的实际下降量： ),d f(x f Δf k k k k +=- 定义k q ?对应的预测下降量： ()().-0k k k k d q q q =? 定义他们的比值为： k k k q f r ??= 一般的，我们有0>?k q 。因此，若0