《第三章无约束非线性规划课件.ppt》由会员分享，可在线阅读，更多相关《第三章无约束非线性规划课件.ppt（83页珍藏版）》请在三一办公上搜索。
1、无约束非线性规划,第一节 最优性条件,第二节 一维搜索,第三节 最速下降法和共轭梯度法,第四节 牛顿法和拟牛顿法(变尺度法),第五节 信赖域法,引言,本章讨论如下的优化模型,其中 是 的实值连续函数，通常假定具有二阶连续偏导数。,预备知识,预备知识,预备知识,最优性条件,最优性条件,定理的逆不成立，即梯度为零的点不一定是局部解。,最优性条件,迭代法,求解无约束优化问题的常用方法是数值解法，而数值解法中最为常见的是迭代法。,迭代法思想：,迭代法,最优性条件,迭代算法,迭代的终止条件在不同的最优化方法中也是不同的。理论上，根据最优性的一阶必要条件，以及算法的设计思想，可以用,来终止迭代，其中,是给
2、定的精度要求。,一维搜索,一维搜索二分法,对于区间a,b上连续不断、且f(a)f(b)0的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫做二分法（bisection）,例2 借助计算器或计算机用二分法求方程2x+3x=7 的近似解(精确到0.1).,一维搜索二分法,那么我们一起来总结一下二分法的解题步骤,求区间(a,b)的中点；,计算f()；,一维搜索黄金分割法,黄金分割法也叫0.618法，它是基于一种区间收缩的极小点搜索算法，当确定搜索区间a,b后，我们只知道极小点包含于搜索区间内，但是具体是哪个点，无法得知。,1
3、.算法原理,黄金分割法的思想很直接，既然极小点包含于搜索区间内，那么可以不断的缩小搜索区间，就可以使搜索区间的端点逼近到极小点。,一维搜索黄金分割法,一维搜索黄金分割法,2.算法步骤,一维搜索黄金分割法,function x,minf=minHJ(f,a,b,eps)format long;if nargin=3 eps=1.0e-6;end l=a+0.382*(b-a);u=a+0.618*(b-a);k=1;tol=b-a;while toleps,end k=k+1;tol=abs(b-a);endif k=100000 disp(找不到最小值！);x=NaN;minf=NaN;ret
4、urn;endx=(a+b)/2;minf=subs(f,findsym(f),x);format short;,黄金分割法源程序,一维搜索牛顿法,一维搜索牛顿法,一维搜索牛顿法,对于正定二次函数，牛顿法一步即可达到最优解。对于一般非二次函数，牛顿法并不能保证经过有限次迭代法求得最优解，但如果初始点充分靠近极小点，牛顿法的收敛速度一般是很快的。,牛顿法程序,function x,minf=minNewton(f,x0,eps)format long;if nargin=2 eps=1.0e-6;enddf=diff(f);d2f=diff(df);k=0;tol=1;while toleps
5、dfx=subs(df,findsym(df),x0);if diff(d2f)=0 d2fx=double(d2f);else d2fx=subs(d2f,findsym(d2f),x0);end x1=x0-dfx/d2fx;k=k+1;tol=abs(dfx);x0=x1;endx=x1;minf=subs(f,findsym(f),x);format short;,最速下降法和共轭梯度法,最速下降法,最速下降法,最速下降法,最速下降法,最速下降法,最速下降法,最速下降法,最速下降法源程序,运行结果,共轭梯度法,1.算法原理 共轭梯度法是利用目标函数梯度逐步产生共轭方向作为线搜索方向的方
6、法，每次搜索方向都是在目标函数梯度的共轭方向，搜索步长通过一维极值算法确定。,共轭梯度法是介于最速下降法与牛顿法之间的一个方法。它仅需利用一阶导数的信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点。共轭梯度法不仅是解大型线性方程组最有用的方法之一，也是解大型非线性最优化问题最有效的算法之一。,共轭梯度法,共轭梯度法最早是由Hestenes和Stiefel(1952)提出来的，用于解正定系数矩阵的线性方程组。在这个基础上，Fletcher和Reeves(1964)首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度
7、和二次终止性等优点，现在共轭梯度法已经广泛地应用于实际问题中。,共轭梯度法,共轭梯度法,共轭梯度法,共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的。而这些搜索方向 仅仅是负梯度方向 与上一次迭代的搜索方向 的组合。因此存储量小，计算方便。,共轭梯度法,共轭梯度法,共轭梯度法,共轭梯度法,这说明我们在每一个迭代点处产生的下降方向都是互相共轭的，这满足算法的要求。,共轭梯度法,共轭梯度法,综合以上，我们可以得到各个迭代点处下降方向都是Q共轭的共轭梯度算法。,共轭梯度法,共轭梯度法,共轭梯度法,共轭梯度法,共轭梯度法,共轭梯度法,共轭梯度法源程序,共轭梯度法小结,共轭梯度法小结,共
8、轭梯度法小结,共轭梯度法小结,牛顿法,牛顿法,牛顿法,牛顿法源程序,运行结果,拟牛顿法(变尺度法),牛顿法成功的关键是利用了Hesse矩阵提供的曲率信息，但计算Hesse矩阵工作量大，并且有的目标函数的Hesse矩阵很难计算，甚至不好求出，这就导致了一个想法:能否仅利用目标函数值和一阶导数的信息，构造出目标函数的曲率近似，使方法具有类似牛顿法的收敛速度快的优点。拟牛顿法就是这样的一类算法。由于它不需要二阶导数，拟牛顿法往往比牛顿法更有效。,拟牛顿条件,和牛顿法的推导一样，考虑目标函数 在当前点 处的二次模型。,拟牛顿法(变尺度法),拟牛顿法(变尺度法),拟牛顿法(变尺度法),拟牛顿法(变尺度法
9、),拟牛顿法(变尺度法),拟牛顿算法,拟牛顿法(变尺度法),拟牛顿法(变尺度法),DFP校正是第一个拟牛顿校正，是1959年由Davidon提出的，后来由Fletcher和Powell(1963)解释和发展的.BFGS校正是目前最流行的也是最有效的拟牛顿校正，它是由Broyden,Fletcher,Goldfarb和Schanno在1970年各自独立提出的拟牛顿法。,拟牛顿法(变尺度法),拟牛顿法(变尺度法),拟牛顿法(变尺度法),拟牛顿法(变尺度法),拟牛顿法源程序,信赖域算法,信赖域算法,信赖域算法,信赖域算法,信赖域算法,信赖域算法,信赖域算法,信赖域算法源程序,信赖域算法运行结果,本章完,谢谢大家！,
