运筹学与最优化MATLAB编程 教学课件 作者 吴祈宗 郑志勇 第6章.ppt

《运筹学与最优化MATLAB编程 教学课件 作者 吴祈宗 郑志勇 第6章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章　无约束优化算法6.1　最优性条件6.2　最速下降法6.3　牛顿算法6.4　拟牛顿算法(变尺度法)6.5　单纯形法6.6　含参数的优化问题6.7　大规模无约束优化问题第6章　无约束优化算法图　6-16.1　最优性条件1.极小点的一阶必要条件2.极小点的二阶必要条件3.极小点的二阶充分条件6.2　最速下降法6.2.1　算法原理6.2.2　算法步骤6.2.3　程序示例6.2.1　算法原理图　6-26.2.2　算法步骤6.2.3　程序示例1.目标函数程序BanaFun.m与BanaFunWithGrad.m2.参数设置(steepdesc.m)3.函数计

2、算(steepdesc.m)1.目标函数程序BanaFun.m与BanaFunWithGrad.mfunctionf=BanaFun(x)(不含导数解析式)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;function［f，g］=BanaFunWithGrad(x)(含导数解析式)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;g=［100*(4*x(1)^3-4*x(1)*x(2))+2*x(1)-2;100*(2*x(2)-2*x(1)^2)］;2.参数设置(steepdesc.m)LargeScale，off大

3、规模计算模式关闭HessUpdate，steepdescHess阵修正方式，采用最速下降法(不需要修正)gradobj，on目标函数导数解析式，on使用，off不使用(差分导数)MaxFunEvals，250最大目标函数计算次数，250次3.函数计算(steepdesc.m)x=［-1.9，2］;初始迭代点［x，fval，exitflag，output］=fminunc(@BanaFunWithGrad，x，OPTIONS)6.3　牛顿算法6.3.1　算法原理6.3.2　算法步骤6.3.3　算法特点6.3.1　算法原理牛顿算法的基本思想是利用二次函数近似

4、目标函数，比最速下降法的一次函数更进了一步，将次二次函数的极小点作为新的迭代点。6.3.2　算法步骤给定控制误差ε＞0。步骤1:取初始点x(0)，令k=0。步骤2:计算Δ2f(x(k))。步骤3:若s＜ε，则停机，x*=x(k+1)；否则k=k+1，转步骤2。6.3.3　算法特点(1)牛顿算法是局部收敛的。(2)牛顿算法不是下降算法，当二阶Hesse阵非正定时，不能保证产生的方向是下降方向。(3)二阶Hesse阵Δ2f(xk)必须可逆，否则算法进行困难。(4)对函数要求苛刻(二阶可微，Hesse阵可拟)，运算量巨大。6.4　拟牛顿算法(变尺度法)6.4.

5、1　算法原理6.4.2　算法步骤6.4.3　算法性质6.4.4　程序示例6.4.1　算法原理拟牛顿算法对牛顿算法有两个重要的改进：一是选用对称正定矩阵可以对搜索方向保证下降性质；二是改进变尺度矩阵，通过逐步迭代修正产生，从而避开逐点计算二阶偏导数的大量计算。6.4.2　算法步骤拟牛顿算法的具体步骤如下：步骤1:给定初始点x(0)、初始矩阵H(0)(通常取单位阵)，计算g(0)，令k=0。步骤2:令p=-H*g。步骤3:由一维搜索(精确或不精确)确定步长α。6.4.3　算法性质(1)对正定二次函数，精确一维搜索有二次终结性，且对任意初始对称矩阵H(0)有H

6、(n+1)=G-1。(2)在(1)的前提下，迭代变量满足拟牛顿方程。(3)在(1)的前提下算法产生共轭的方向，当H(0)=I时，产生的梯度相互共轭。6.4.4　程序示例(1)目标函数程序BanaFun.m与BanaFunWithGrad.m(2)参数设置quasinewton.m(3)函数计算(1)目标函数程序BanaFun.m与BanaFunWithGrad.mfunctionf=BanaFun(x)(不含导数解析式)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;function［f，g］=BanaFunWithGrad(x)(含导

7、数解析式)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;g=［100*(4*x(1)^3-4*x(1)*x(2))+2*x(1)-2;100*(2*x(2)-2*x(1)^2)］;(2)参数设置quasinewton.mDFP(Davidon-Fletcher-Powell)方法:OPTIONS=optimset(LargeScale，off，HessUpdate，dfp，gradobj，on，MaxFunEvals，250，InitialHessType，identity，display，iter);6.5　单纯形法6.5.1　算法

8、原理6.5.2　函数Fminsearch6.5.1　算法原理6.5.1　算法原理