数学建模书写格式训练1.doc

正定. 由于正定，函数Q的驻点是Q(x)的极小点.为求此极小点，令即可解得 对照基本迭代格式（1），可知从点出发沿搜索方向.并取步长 即可得Q(x)的最小点通常，把方向 叫做从点 出发的 Newton 方向.从一初始点开始，每一轮从当前迭代点出发，沿Newton 方向并取步长为1 的求解方法，称之为Newton 法.其具体步骤如下：1选取初始数据。选取初始点，给定终止误差，令k := 0.2求梯度向量。计算若 停止迭代，输出否则，进行3.3构造Newton 方向.计算取4 求下一迭代点.令转2.例5 用Newton 法求解， 选取 解：(i) （ii）编写 M 文件nwfun.m 如下：function f,df,d2f=nwfun(x);f=x(1)4+25*x(2)4+x(1)2*x(2)2;df=4*x(1)3+2*x(1)*x(2)2;100*x(2)3+2*x(1)2*x(2);d2f=2*x(1)2+2*x(2)2,4*x(1)*x(2)4*x(1)*x(2),300*x(2)2+2*x(1)2;（III）编写主程序文件example5.m 如下：clcx=2;2;f0,g1,g2=nwfun(x);while norm(g1)0.00001p=-inv(g2)*g1;x=x+p;f0,g1,g2=nwfun(x);endx, f0 如果目标函数是非二次函数，一般地说，用Newton 法通过有限轮迭代并不能保证可求得其最优解. 为了提高计算精度，我们在迭代时可以采用变步长计算上述问题，编写主程序文件example5_2 如下：clc,clearx=2;2;f0,g1,g2=nwfun(x);while norm(g1)0.00001p=-inv(g2)*g1;p=p/norm(p);t=1.0;f=nwfun(x+t*p);while ff0t=t/2;f=nwfun(x+t*p);endx=x+t*p;f0,g1,g2=nwfun(x);endx,f0 Newton 法的优点是收敛速度快；缺点是有时不好用而需采取改进措施，此外，当维数较高时，计算的工作量很大.2.3.1.3 变尺度法 变尺度法（Variable Metric Algorithm）是近20 多年来发展起来的，它不仅是求解无约束极值问题非常有效的算法，而且也已被推广用来求解约束极值问题.由于它既避免计算二阶导数矩阵及其求逆过程，又比梯度法的收敛速度快，特别是对高维问题具有显著的优越性，因而使变尺度法获得了很高的声誉.下面我们就来简要地介绍一种变尺度法DFP 法的基本原理及其计算过程。这一方法首先由Davidon 在1959 年提出，后经Fletcher 和Powell 加以改进. 我们已经知道，牛顿法的搜索方向是为了不计算二阶导数矩阵及其逆阵，我们设法构造另一个矩阵，用它来逼近二阶导数矩阵的逆阵这一类方法也称拟牛顿法（Quasi-Newton Method）. 下面研究如何构造这样的近似矩阵，并将它记为我们要求：每一步都能以现有的信息来确定下一个搜索方向；每做一次选代，目标函数值均有所下降；这些近似矩阵最后应收敛于解点处的Hesse 阵的逆阵. 当 f (x)是二次函数时，其Hesse 阵为常数阵A，任两点和处的梯度之差为 或 对于非二次函数，仿照二次函数的情形，要求其 Hesse 阵的逆阵的第k +1次近似矩阵满足关系式 (7)这就是常说的拟Newton 条件. 若令 (8)则式（7）变为 (9)现假定已知，用下式求（设 和均为对称正定阵）； (10)其中称为第k 次校正矩阵.显然，应满足拟Newton 条件（9），即要求 或 (11)由此可以设想， 的一种比较简单的形式是 （12）其中和为两个待定列向量.将式（12）中的代入（11），得这说明，应使 (13)考虑到应为对称阵，最简单的办法就是取 (14)由式（13）得 (15)若和不等于零，则有 (16)于是，得校正矩阵 (17)从而得到 (18) 上述矩阵称为尺度矩阵.通常，我们取第一个尺度矩阵为单位阵，以后的尺度矩阵按式（18）逐步形成.可以证明： （i）当xk 不是极小点且正定时，式（17）右端两项的分母不为零，从而可按式（18）产生下一个尺度矩阵； （ii）若为对称正定阵，则由式（18）产生的也是对称正定阵； （iii）由此推出DFP 法的搜索方向为下降方向. 现将 DFP 变尺度法的计算步骤总结如下. 1给定初始点及梯度允许误差 2若则x0即为近似极小点，停止迭代，否则，转向下一步. 3令（单位矩阵），在 方向进行一维搜索，确定最佳步长:如此可得下一个近似点4一般地，设已得到近似点算出若则即为所求的近似解，停止迭代；否则，计算： 并令在 方向上进行一维搜索，得,从而可得下一个近似点 5若满足精度要求，则即为所求的近似解，否则，转回4，直到求出某点满足精度要求为止.2.3.2 直接法 在无约束非线性规划方法中，遇到问题的目标函数不可导或导函数的解析式难以表示时，人们一般需要使用直接搜索方法.同时，由于这些方法一般都比较直观和易于理解，因而在实际应用中常为人们所采用.下面我们介绍Powell 方法.这个方法主要由所谓基本搜索、加速搜索和调整搜索方向三部分组成，具体步骤如下：1 选取初始数据。选取初始点n个线性无关初始方向，组成初搜索方向组.给定终止误差令k := 0.2进行基本搜索.令依次沿中的方向进行一维搜索.对应地得到辅助迭代点即否则进行4.4确定调整方向。按下式找出m .若 成立，进行5.否则，进行6.5调整搜索方向组.令 同时，令k := k +1，转2.6不调整搜索方向组。令转2.2.4 Matlab 求无约束极值问题 在 Matlab 工具箱中，用于求解无约束极值问题的函数有fminunc 和fminsearch，用法介绍如下.求函数的极小值 其中 x 可以为标量或向量.Matlab 中fminunc 的基本命令是X,FVAL=FMINUNC(FUN,X0,OPTIONS,P1,P2, .)其中的返回值X 是所求得的极小点，FVAL 是函数的极小值，其它返回值的含义参见相关的帮助.FUN 是一个M 文件，当FUN只有一个返回值时，它的返回值是函数f (x)； 当FUN有两个返回值时，它的第二个返回值是f (x)的梯度向量；当FUN有三个返回值时，它的第三个返回值是f (x)的二阶导数阵（Hessian 阵）.X0是向量x的初始值，OPTIONS 是优化参数，可以使用缺省参数.P1，P2 是可以传递给FUN 的一些参数.例6 求函数的最小值.解：编写M 文件fun2.m 如下：function f,g=fun2(x);f=100*(x(2)-x(1)2)2+(1-x(1)2;g=-400*x(1)*(x(2)-x(1)2)-2*(1-x(1);200*(x(2)-x(1)2);编写主函数文件example6.m如下：options = optimset(GradObj,on);x,y=fminunc(fun2,rand(1,2),options)即可求得函数的极小值. 在求极值时，也可以利用二阶导数，编写 M 文件fun3.m 如下：function f,df,d2f=fun3(x);f=100*(x(2)-x(1)2)2+(1-x(1)2;df=-400*x(1)*(x(2)-x(1)2)-2*(1-x(1);200*(x(2)-x(1)2);d2f=-400*x(2)+1200*x(1)2+2,-400*x(1)-400*x(1),200;编写主函数文件example62.m如下：options = optimset(GradObj,on,Hessian,on);x,y=fminunc(fun3,rand(1,2),options)即可求得函数的极小值. 求多元函数的极值也可以使用 Matlab 的fminsearch 命令，其使用格式为：X,FVAL,EXITFLAG,OUTPUTFMINSEARCH(FUN,X0,OPTIONS,P1,P2,.)例7 求函数解 编写 f (x)的M 文件fun4.m如下：function f=fun4(x);f=sin(x)+3;编写主函数文件example7.m如下：x0=2;x,y=fminsearch(fun4,x0)即求得在初值2 附近的极小点及极小值。取最小值时的x值.3 约束极值问题 带有约束条件的极值问题称为约束极值问题，也叫规划问题. 求解约束极值问题要比求解无约束极值问题困难得多.为了简化其优化工作，可采用以下方法：将约束问题化为无约束问题；将非线性规划问题化为线性规划问题，以及能将复杂问题变换为较简单问题的其它方法. 库恩塔克条件是非线性规划领域中最重要的理论成果之一，是确定某点为最优点的必要条件，但一般说它并不是充分条件（对于凸规划，它既是最优点存在的必要条件，同时也是充分条件）.3.1 二次规划 若某非线性规划的目标函数为自变量 x 的二次函数，约束条件又全是线性的，就称这种规划为二次规划.Matlab 中二次规划的数学模型可表述如下：这里H 是实对称矩阵， f ,b是列向量， A是相应维数的矩阵.Matlab 中求解二次规划的命令是X,FVAL= QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS).返回值X 是决策向量x 的值，返回值FVAL 是目标函数在x 处的值.（具体细节可以参看在Matlab 指令中运行help quadprog 后的帮助）.例 8 求解二次规划解 编写如下程序：h=4,-4;-4,8;f=-6;-3;a=1,1;4,1;b=3;9;x,value=quadprog(h,f,a,b,zeros(2,1)求得:3.2 罚函数法 利用罚函数法，可将非线性规划问题的求解，转化为求解一系列无约束极值问题，因而也称这种方法为序列无约束最小化技术，简记为 SUMT (Sequential UnconstrainedMinization Technique). 罚函数法求解非线性规划问题的思想是，利用问题中的约束函数作出适当的罚函数，由此构造出带参数的增广目标函数，把问题转化为无约束非线性规划问题。主要有两种形式，一种叫外罚函数法，另一种叫内罚函数法，下面介绍外罚函数法