目标函数极值求解的几种方法目标函数极值求解的几种方法题目：，取初始点，分别用最速下降2 22 1122minxx Tx3 , 11法，你牛顿法，共轭梯度法编程实现。一维搜索法：迭代下降算法大都具有一个共同点，这就是得到点后需要按某种规则确 kx定一个方向，再从出发，沿方向在直线（或射线）上求目标函数的 kd kx kd极小点，从而得到的后继点，重复以上做法，直至求得问题的解，这 kx1kx里所谓求目标函数在直线上的极小点，称为一维搜索。一维搜索的方法很多，归纳起来大体可以分为两类，一类是试探法：采用这类方法，需要按某种方式找试探点，通过一系列的试探点来确定极小点。另一类是函数逼近法或插值法：这类方法是用某种较简单的曲线逼近本来的函数曲线，通过求逼近函数的极小点来估计目标函数的极小点。本文采用的是第一类试探法中的黄金分割法。原理书上有详细叙述，在这里介绍一下实现过程： 置初始区间及精度要求 L0,计算试探点和，计算函数值11,ba11和，计算公式是：，。令 1f 1f1111382. 0aba1111618. 0abak=1。 若则停止计算。否则，当时,转步骤;当Labkk Kf kf Kf时,转步骤 。 kf 置,计算函数值kka1kkbb1kk11111618. 0kkkkaba,转。1kf 置,计算函数kkaa1kkb1kk11111382. 0kkkkaba值,转。1kf 置 k=k+1 返回步骤 。1. 最速下降法实现原理描述：在求目标函数极小值问题时,总希望从一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点,正是基于这样一种愿望提出的最速下降法,并且经过一系列理论推导研究可知,负梯度方向为最速下降方向。最速下降法的迭代公式是，其中是从出发的搜索 k kkkdxx1 kd kx方向，这里取在点处最速下降方向，即。是从出发沿方 kx kkxfdk kx向进行的一维搜索步长，满足。 kd kkk kkdxfdxf 0min实现步骤如下： 给定初点 ，允许误差，置 k=1。 nRx10 计算搜索方向。 kkxfd 若，则停止计算；否则，从出发，沿方向进行的一维 kd kx kd搜索，求，使。k kkk kkdxfdxf 0min ，置 k=k+1 返回步骤 。 k kkkdxx12. 拟牛顿法 基本思想是用不包括二阶导数的矩阵近似牛顿法中的 Hesse 矩阵的逆矩阵，因构造近似矩阵的方法不同，因而出现了不同的拟牛顿法。牛顿法迭代公式：，是在点处的牛顿方向， k kkkdxx1 kd kx，是从出发沿牛顿方向进行搜索的最优步长。 kkkxfxfd12 k kx kd用不包括二阶导数的矩阵近似取代牛顿法中的 Hesse 矩阵的逆矩阵kH，需满足拟牛顿条件。 12kxf1kH实现步骤： 给定初点 ，允许误差。 1x0 置（单位矩阵） ，计算出在处的梯度，置 k=1。nIH 1 1x 1 1xfg 令。 kkkgHd 从出发沿方向搜索，求步长，使它满足 kx kdk，令。 kkk kkdxfdxf 0min k kkkdxx1 检验是否满足收敛标准，若，则停止迭代，得到点1kyf，否则进行步骤。1 kxx 若 k=n，令，返回；否则进行步骤。 11kxx令，1 1 k kxfg kkkxxp1 kkkggq1，置 k=k+1 。返回。 k kTkkTkk k kTkTkkkkqHqHqqH qpppHH13. 共轭梯度法若是中 k 个方向，它们两两关于 A 共轭，即满足 kddd,21LnR，称这组方向为 A 的 k 个共轭方向。共轭梯度法 kjijiAddjTi, 1,;, 0L的基本思想是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点，根据共轭方向的基本性质这种方法具有二次终止性。实现步骤如下： 给定初点 ，允许误差，置 1x0，k=j=1。 11xy 11yfd 若，则停止计算；否则，作一维搜索，求，满足 jyfj，令。 jjj jjdyfdyf 0min j jjjdyy1 若，则进行步骤，否则进行步骤nj 令，其中，置 j=j+1，转 j jjjdyfd11 221jjjyfyf 。 令，置 j=1，k=k+1，转 11nkyx 11kxy 11yfd。4. 实验结果用以上三种方法通过 Matlab 编程得到实验数据。初始值 。迭 Tx3 , 11代精度 sum(abs(x1-x).2)nif abs(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;endelseif abs(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 处的数值向量function g=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%输入变量为初始的迭代点，输出变量为极小值点function x0=zuisu(x)%判断梯度范数是否满足计算精度 1e-4 的要求.是,标志变量设为 1，输出结果; %否,标志变量设为 0if sum(abs(tidu(x).2)1e-4flag=1; x0=x;else flag=0;end%循环求解函数的极小点while flag=0d=-tidu(x); a=gold(x,d); x=x+a*d%判断梯度范数是否满足计算精度的要求.是,标志变量设为 1，输出结果;%否,标志变量设为 0，继续迭代if sum(abs(tidu(x).2)1e-4flag=1; x0=x;else flag=0;endEnd%拟牛顿法极小化函数的通用子函数，gonge.m%输入变量为初始的迭代点，输出变量为极小值点function x0=ninewton(x)%判断梯度范数是否满足计算精度的要求.是,标志变量设为 1，输出结果;%否,标志变量设为 0，继续迭代if sum(abs(tidu(x).2)1e-4flag=1； x0=x;else flag=0;end%初始的 H 矩阵为单位矩阵h0=eye(2);%循环求解函数的极小点while flag=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，继续迭代if sum(abs(x-x1).2)1e-4flag=1; x0=x;else flag=0;endx=x1end %共轭剃度法极小化函数的通用子函数，gonge.m%输入变量为初始的迭代点，输出变量为极小值点function x0=gonge(x)%判断梯度范数是否满足计算精度的要求.是,标志变量设为 1，输出结果;%否,标志变量设为 0，继续迭代if sum(abs(tidu(x).2)1e-4flag=1; x0=x;else flag=0;end%第一次的迭代方法为负梯度方向d1=-tidu(x);a=gold(x,d1);x1=x+a*d1;%循环求解函数的极小点while flag=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，继续迭代if sum(abs(x1-x).2)1e-4 flag=1; x0=x1;else flag=0;endend