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

目标函数极值求解的几种方法题目：2221122minxx，取初始点Tx3,11，分别用最速下降法，牛顿法，共轭梯度法编程实现。一维搜索法：迭代下降算法大都具有一个共同点，这就是得到点kx后需要按某种规则确定一个方向kd，再从kx出发，沿方向kd在直线（或射线）上求目标函数的极小点，从而得到kx的后继点1kx，重复以上做法，直至求得问题的解，这里所谓求目标函数在直线上的极小点，称为一维搜索。一维搜索的方法很多，归纳起来大体可以分为两类，一类是试探法：采用这类方法，需要按某种方式找试探点，通过一系列的试探点来确定极小点。另一类是函数逼近法或插值法：这类方法是用某种较简单的曲线逼近本来的函数曲线，通过求逼近函数的极小点来估计目标函数的极小点。本文采用的是第一类试探法中的黄金分割法。原理书上有详细叙述，在这里介绍一下实现过程：⑴置初始区间[11,ba]及精度要求L0,计算试探点1和1，计算函数值1f和1f，计算公式是：1111382.0aba，1111618.0aba。令k=1。⑵若Labkk则停止计算。否则，当Kfkf时,转步骤⑶;当Kfkf时,转步骤⑷。⑶置kka1,kkbb1,kk1,1111618.0kkkkaba,计算函数值1kf,转⑸。⑷置kkaa1,kkb1,kk1,1111382.0kkkkaba,计算函数值1kf,转⑸。⑸置k=k+1返回步骤⑵。1.最速下降法实现原理描述：在求目标函数极小值问题时,总希望从一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点,正是基于这样一种愿望提出的最速下降法,并且经过一系列理论推导研究可知,负梯度方向为最速下降方向。最速下降法的迭代公式是kkkkdxx1，其中kd是从kx出发的搜索方向，这里取在点kx处最速下降方向，即kkxfd。k是从kx出发沿方向kd进行的一维搜索步长，满足kkkkkdxfdxf0min。实现步骤如下：⑴给定初点nRx1，允许误差0，置k=1。⑵计算搜索方向kkxfd。⑶若kd，则停止计算；否则，从kx出发，沿方向kd进行的一维搜索，求k，使kkkkkdxfdxf0min。⑷kkkkdxx1，置k=k+1返回步骤⑵。2.拟牛顿法基本思想是用不包括二阶导数的矩阵近似牛顿法中的Hesse矩阵的逆矩阵，因构造近似矩阵的方法不同，因而出现了不同的拟牛顿法。牛顿法迭代公式：kkkkdxx1，kd是在点kx处的牛顿方向，kkkxfxfd12，k是从kx出发沿牛顿方向kd进行搜索的最优步长。用不包括二阶导数的矩阵kH近似取代牛顿法中的Hesse矩阵的逆矩阵12kxf，1kH需满足拟牛顿条件。实现步骤：⑴给定初点1x，允许误差0。⑵置nIH1（单位矩阵），计算出在1x处的梯度11xfg，置k=1。⑶令kkkgHd。⑷从kx出发沿方向kd搜索，求步长k，使它满足kkkkkdxfdxf0min，令kkkkdxx1。⑸检验是否满足收敛标准，若1kyf，则停止迭代，得到点1kxx，否则进行步骤⑹。⑹若k=n，令11kxx，返回⑵；否则进行步骤⑺。⑺令11kkxfg，kkkxxp1，kkkggq1，kkTkkTkkkkTkTkkkkqHqHqqHqpppHH1，置k=k+1。返回⑶。3.共轭梯度法若kddd,,,21是nR中k个方向，它们两两关于A共轭，即满足kjijiAddjTi,,1,;,0，称这组方向为A的k个共轭方向。共轭梯度法的基本思想是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点，根据共轭方向的基本性质这种方法具有二次终止性。实现步骤如下：⑴给定初点1x，允许误差0，置11xy，11yfd，k=j=1。⑵若jyf，则停止计算；否则，作一维搜索，求j，满足jjjjjdyfdyf0min，令jjjjdyy1。⑶若nj，则进行步骤⑷，否则进行步骤⑸⑷令jjjjdyfd11，其中221jjjyfyf，置j=j+1，转⑵。⑸令11nkyx，11kxy，11yfd，置j=1，k=k+1，转⑵。4.实验结果用以上三种方法通过Matlab编程得到实验数据。初始值Tx3,11。迭代精度sum(abs(x1-x).^2)1e-4。最速下降法拟牛顿法共轭梯度法第一次迭代结果2x12x1.51516312861.51516312861.515163128622x0.93934748540.9393474850.9393474854第二次迭代结果3x13x1.97300822752.01081080722.000007625923x1.05389923740.98615771081.0000419788第三次迭代结果4x14x1.98691339342.0054101622.000003816724x0.99836543780.98962692400.9999998271第四次迭代结果5x15x1.999273976125x1.0014531964实验结果分析：由上表格可以看到最速下降法需要四次迭代实现所要求的精度，拟牛顿法和共轭梯度法需要三次。程序：%精确一维搜索法的子函数,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)^2+2*(x(2)+alfa*d(2)-1)^2;%目标函数m=f;alfa=mu;n=f;while1ifmnifabs(lanmda-b)1e-4alfa=mu;returnelsea=lanmda;lanmda=mu;m=n;mu=a+tao*(b-a);alfa=mu;n=((x(1)+alfa*d(1))-2)^2+2*(x(2)+alfa*d(2)-1)^2;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)^2+2*(x(2)+alfa*d(2)-1)^2;endendend%梯度子函数，tidu.m,输入的变量为二维的向量，返回梯度在x处的数值向量functiong=tidu(x)%待求解的函数f=(x(1)-2)^2+2*(x(2)-1)^2;%求函数的梯度表达式g=[2*(x(1)-2)4*(x(2)-1)];x1=x(1);x2=x(2);%最速下降法极小化函数的通用子函数zuisu.m%输入变量为初始的迭代点，输出变量为极小值点functionx0=zuisu(x)%判断梯度范数是否满足计算精度1e-4的要求.是,标志变量设为1，输出结果;%否,标志变量设为0ifsum(abs(tidu(x)).^2)1e-4flag=1;x0=x;elseflag=0;end%循环求解函数的极小点whileflag==0d=-tidu(x);a=gold(x,d);x=x+a*d%判断梯度范数是否满足计算精度的要求.是,标志变量设为1，输出结果;%否,标志变量设为0，继续迭代ifsum(abs(tidu(x)).^2)1e-4flag=1;x0=x;elseflag=0;endEnd%拟牛顿法极小化函数的通用子函数，gonge.m%输入变量为初始的迭代点，输出变量为极小值点functionx0=ninewton(x)%判断梯度范数是否满足计算精度的要求.是,标志变量设为1，输出结果;%否,标志变量设为0，继续迭代ifsum(abs(tidu(x)).^2)1e-4flag=1；x0=x;elseflag=0;end%初始的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).^2)1e-4flag=1;x0=x;elseflag=0;endx=x1end%共轭剃度法极小化函数的通用子函数，gonge.m%输入变量为初始的迭代点，输出变量为极小值点functionx0=gonge(x)%判断梯度范数是否满足计算精度的要求.是,标志变量设为1，输出结果;%否,标志变量设为0，继续迭代ifsum(abs(tidu(x)).^2)1e-4flag=1;x0=x;elseflag=0;end%第一次的迭代方法为负梯度方向d1=-tidu(x);a=gold(x,d1);x1=x+a*d1;%循环求解函数的极小点whileflag==0g1=tidu(x);g2=tidu(x1);%利用FR公式求解系数batabata=(g2*g2')/(g1*g1');d2=-g2+bata*d1;a=gold(x1,d2);x=x1;x1=x+a*d2%判断下一次和上一次迭代点之差是否满足计算精度的要求.是,标志变量设为1，输出结果;否,标志变量设为0，继续迭代ifsum(abs(x1-x).^2)1e-4flag=1;x0=x1;elseflag=0;endend