目标函数的几种极值求解方法

1、目标函数极值求解的几种方法题目：min（Xi-22+2（x2-125取初始点xt）=（1,3/，分别用最速下降法，牛顿法，共腕梯度法编程实现。一维搜索法：迭代下降算法大都具有一个共同点，这就是得到点x（k归需要按某种规则确定一个方向d），再从x（k出发，7&方向d（k在直线（或射线）上求目标函数的极小点，从而得到x（k的后继点xf）,重复以上做法，直至求得问题的解，这里所谓求目标函数在直线上的极小点，称为一维搜索。一维搜索的方法很多，归纳起来大体可以分为两类，一类是试探法：采用这类方法，需要按某种方式找试探点，通过一系列的试探点来确定极小点。另一类是函数逼近法或插值法：这类方法是用某种

2、较简单的曲线逼近本来的函数曲线，通过求逼近函数的极小点来估计目标函数的极小点。本文采用的是第一类试探法中的黄金分割法。原理书上有详细叙述，在这里介绍一下实现过程：（1）置初始区间ai,bi及精度要求L>0,计算试探点%和），计算函数值f（t邢f俨11计算公式是：X,=a1+0.382&a1）,21=a1+0.618bl-a1）。令k=1。若bkak<L则停止计算。否则，当f®）>f俨k）时，转步骤；当“般）4f仁叫，转步骤。置涿书=&，bk«=bk,人书=也，也中=烝书+0.618（bk书ak书），计算函数值f（k）,转。置ak书=ak,b

3、k由=此,收书=叫，-k+=ak+0.3820由ak+）,计算函数值“£水）转。置卜二卜+1返回步骤（2）01.最速下降法实现原理描述：在求目标函数极小值问题时，总希望从一点出发，选择一个目标函数值下降最快的方向，以利于尽快达到极小点，正是基于这样一种愿望提出的最速下降法，并且经过一系列理论推导研究可知，负梯度方向为最速下降方向。最速下降法的迭代公式是x（k*）=xC）+均d（k），其中d（k是从x（k）出发的搜索方向，这里取在点xf向最速下降方向,即dL-Vf（xk）。限是从x（k）出发沿方向d（k）进行的一维搜索步长，满足f（xf）十嬴d（k）=minf（x（k）+Kd（k）。-

4、0实现步骤如下：给定初点xQwRn,允许误差O0,置k=1。计算搜索方向d6=-fxk）。若M卜名，则停止计算；否则，从x（k加发，7&方向d（k世行的一维搜索，求,使f仅2+?%d）=minf（x2+九d（k）。0（4）x（k*Lx（k）+，*d2,置卜=卜+1返回步骤。2 .拟牛顿法基本思想是用不包括二阶导数的矩阵近似牛顿法中的Hesse矩阵的逆矩阵，因构造近似矩阵的方法不同，因而出现了不同的拟牛顿法。牛顿法迭代公式：x（k*Lx（k）+）*d（k）,d（k）是在点x（k）处的牛顿方向，d（）=-V2f（xNfvf（x）,均是从x（k柏发沿牛顿方向d（k进行搜索的最优步长。用不包括

5、二阶导数的矩阵Hk近似取代牛顿法中的Hesse矩阵的逆矩阵v2f（x）广,Hk卡需满足拟牛顿条件。实现步骤：给定初点x1）,允许误差名下0。置Hi=In（单位矩阵），计算出在xQ）处的,$度gi=Vf（xt）,置k=1o令d（k）=-Hkgk。从x（k）出发沿方向d（k）搜索，求步长鼠，使它满足f（x）+4d，）=min（x2+h2）令x（k+）=x1）+Kkd（k）。.：._0检验是否满足收敛标准，若fy（k"M2,则停止迭代，得到点X=x（k幸）,否则进行步骤。若卜二口，令xCLxfk*）,返回；否则进行步骤。令g«=fxS）,p2=x”）-x（k）,q2=gkgk，置

6、k=k+1 。返回HHPkPkTHkqkqkTHHk1k7一qkTHkqk3 .共轲梯度法若dQdC'dC）是Rn中k个方向，它们两两关于A共腕，即满足dTAd（j）=0,i*j;i,j=1,，k,称这组方向为A的k个共腕方向。共腕梯度法的基本思想是把共腕性与最速下降法相结合，利用已知点处的梯度构造一组共腕方向，并沿这组方向进行搜索，求出目标函数的极小点，根据共腕方向的基本性质这种方法具有二次终止性。实现步骤如下：给定初点x（）,允许误差40,置yC）=xf）,dC）="f（y。），k=j=1O若fy（j）bw,则停止计算；否则，作一维搜索，求%,满足fyj%d（j»

7、;=minf（y（j）+九d（j»,令y（j*）=y（j）+九jd（j）。0若j<n,则进行步骤，否则进行步骤“yj”2令d（j”=-fy（g）HBjd（j）,其中Bj=24-，置可+1，转。“yj令x3+）=y"），y0）=x（k+）,d，）=Wf（y，），置j=1,k=k+1,转。4.实验结果用以上三种方法通过Matlab编程得到实验数据。初始值xC)=(1,3)T。迭代精度sum(abs(x1-x).A2)<1e-4。最速卜降法拟牛顿法共腕梯度法第一次迭代结果xF)xQi)1.51516312861.51516312861.5151631286x42)0.

8、93934748540.9393474850.9393474854第二次迭代结果xf)xHn1.97300822752.01081080722.0000076259x.2)1.05389923740.98615771081.0000419788第三次迭代结果x(4)x(421.98691339342.0054101622.0000038167x(40.99836543780.98962692400.9999998271第四次迭代结果xf)xnD1.9992739761x2)1.0014531964实验结果分析：由上表格可以看到最速下降法需要四次迭代实现所要求的精度，拟牛顿法和共腕梯度法需要三次

9、。程序：%精确一维搜索法的子函数，0.618(黄金分割)法，gold.m%俞入的变量x为初始迭代点是二维的向量，d为初始迭代方向是二维的向量%俞出变量是在0,10区间上使函数取得极小值点的步长因子functionalfa=gold(x,d)a=0;b=10;tao=0.618;lanmda=a+(1-tao)*(b-a);mu=a+tao*(b-a);alfa=lanmda;%初始化f=(x(1)+alfa*d(1)-2)A2+2*(x(2)+alfa*d(2)-1)A2;%目标函数m=f;alfa=mu;n=f;while1ifm>nifabs(lanmda-b)<1e-4alf

10、a=mu;returnelsea=lanmda;lanmda=mu;m=n;mu=a+tao*(b-a);alfa=mu;n=(x(1)+alfa*d(1)-2)A2+2*(x(2)+alfa*d(2)-1)A2;endelseifabs(mu-a)<1e-4alfa=lanmda;returnelseb=mu;mu=lanmda;n=m;lanmda=a+(1-tao)*(b-a);alfa=lanmda;m=(x(1)+alfa*d(1)-2)A2+2*(x(2)+alfa*d(2)-1)A2;endendend%弟度子函数，tidu.m,输入的变量为二维的向量，返回梯度在x处的数值

11、向量functiong=tidu(x)%待求解的函数f=(x(1)-2)A2+2*(x(2)-1)A2;%求函数的梯度表达式g=2*(x(1)-2)4*(x(2)-1);x1=x(1);x2=x(2);%!速下降法极小化函数的通用子函数zuisu.m%俞入变量为初始的迭代点，输出变量为极小值点functionx0=zuisu(x)%断梯度范数是否满足计算精度1e-4的要求.是,标志变量设为1,输出结果;%5,标志变量设为0ifsum(abs(tidu(x).A2)<1e-4flag=1;x0=x;elseflag=0;end%循环求解函数的极小点whileflag=0d=-tidu(x)

12、;a=gold(x,d);x=x+a*d%判断梯度范数是否满足计算精度的要求.是,标志变量设为1,输出结果；%否，标志变量设为0,继续迭代ifsum(abs(tidu(x).A2)<1e-4flag=1;x0=x;elseflag=0;endEnd%以牛顿法极小化函数的通用子函数，gonge.m%俞入变量为初始的迭代点，输出变量为极小值点functionx0=ninewton(x)师U断梯度范数是否满足计算精度的要求.是,标志变量设为1,输出结果；%否,标志变量设为0,继续迭代ifsum(abs(tidu(x).A2)<1e-4flag=1；x0=x;elseflag=0;end%

13、初始的H矩阵为单位矩阵h0=eye(2);%循环求解函数的极小点whileflag=0%计算新的迭代方向d=-h0*tidu(x)'a=gold(x,d);x1=(x'+a*h0*d)'s=x1-x;y=tidu(x1)-tidu(x);v=s*y'%校正H矩阵h0=(eye(2)-s'*y./v)*h0*(eye(2)-y'*s./v)+s'*s./v;%判断下一次和上一次迭代点之差是否满足计算精度的要求.是，标志变量设为1,输出结果；否，标志变量设为0,继续迭代ifsum(abs(x-x1).A2)<1e-4flag=1;x0=x;elseflag=0;endx=x1end%共腕剃度法极小化函数的通用子函数，gonge.m%输入变量为初始的迭代点，输出变量为极小值点functionx0=gonge(x)师U断梯度范数是否满足计算精度的要求.是,标志变量设为1,输出结果；%否,标志变量设为0,继续迭代ifsum(abs(tidu(x).A2)<1e-4flag=1;x0=x;elseflag=0;end%第一次的迭代方法为负梯度方向d1=-tidu(x);a=gold(x,d1);x1=x+a*d1;%循环求解函数的极小点whileflag=0g1=tid