第三章无约束非线性规划课件

无约束非线性规划第一节最优性条件第二节一维搜索第三节最速下降法和共轭梯度法第四节牛顿法和拟牛顿法(变尺度法)第五节信赖域法无约束非线性规划第一节最优性条件第二节一维搜索第三节最引言本章讨论如下的优化模型其中是的实值连续函数，通常假定具有二阶连续偏导数。引言本章讨论如下的优化模型其中是预备知识预备知识预备知识预备知识预备知识预备知识最优性条件最优性条件最优性条件定理的逆不成立，即梯度为零的点不一定是局部解。最优性条件定理的逆不成立，即梯度为零的点不一定是局部解。最优性条件最优性条件迭代法求解无约束优化问题的常用方法是数值解法，而数值解法中最为常见的是迭代法。迭代法思想：迭代法求解无约束优化问题的常用方法是数值解法，而数值解法中最迭代法迭代法最优性条件最优性条件迭代算法迭代的终止条件在不同的最优化方法中也是不同的。理论上，根据最优性的一阶必要条件，以及算法的设计思想，可以用来终止迭代，其中是给定的精度要求。迭代算法迭代的终止条件在不同的最优化方法中也是不同的。理论上一维搜索一维搜索一维搜索——二分法

对于区间[a,b]上连续不断、且f(a)f(b)<0的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫做二分法（bisection）例2借助计算器或计算机用二分法求方程2x+3x=7的近似解(精确到0.1).一维搜索——二分法对于区间[a,b]上连续不断、且一维搜索——二分法那么我们一起来总结一下二分法的解题步骤给定精确度，用二分法求函数f(x)零点近似解的步骤如下：,给定精确度；⑴确定区间[a,b],验证⑵求区间(a,b)的中点；⑶计算f()；若f()=0，则就是函数的零点；②若，则令b=()；此时零点③若，则令a=(此时零点)；⑷判断是否达到精确度：即若|a-b|<,则得到零点近似值为a(或b);否则重复⑵~⑷一维搜索——二分法那么我们一起来总结一下二分法的解题步骤给定一维搜索——黄金分割法黄金分割法也叫0.618法，它是基于一种区间收缩的极小点搜索算法，当确定搜索区间[a,b]后，我们只知道极小点包含于搜索区间内，但是具体是哪个点，无法得知。1.算法原理黄金分割法的思想很直接，既然极小点包含于搜索区间内，那么可以不断的缩小搜索区间，就可以使搜索区间的端点逼近到极小点。一维搜索——黄金分割法黄金分割法也叫0.618法，它是基于一一维搜索——黄金分割法一维搜索——黄金分割法一维搜索——黄金分割法2.算法步骤①②③④一维搜索——黄金分割法2.算法步骤①②③④一维搜索——黄金分割法③⑤②④一维搜索——黄金分割法③⑤②④function[x,minf]=minHJ(f,a,b,eps)formatlong;ifnargin==3eps=1.0e-6;endl=a+0.382*(b-a);u=a+0.618*(b-a);k=1;tol=b-a;whiletol>eps&&k<100000fl=subs(f,findsym(f),l);fu=subs(f,findsym(f),u);iffl>fua=l;l=u;u=a+0.618*(b-a);elseb=u;u=l;l=a+0.382*(b-a);endk=k+1;tol=abs(b-a);endifk==100000disp('找不到最小值！');x=NaN;minf=NaN;return;endx=(a+b)/2;minf=subs(f,findsym(f),x);formatshort;黄金分割法源程序function[x,minf]=minHJ(f,a,一维搜索——牛顿法一维搜索——牛顿法一维搜索——牛顿法一维搜索——牛顿法一维搜索——牛顿法对于正定二次函数，牛顿法一步即可达到最优解。对于一般非二次函数，牛顿法并不能保证经过有限次迭代法求得最优解，但如果初始点充分靠近极小点，牛顿法的收敛速度一般是很快的。一维搜索——牛顿法对于正定二次函数，牛顿法一步即牛顿法程序function[x,minf]=minNewton(f,x0,eps)formatlong;ifnargin==2eps=1.0e-6;enddf=diff(f);d2f=diff(df);k=0;tol=1;whiletol>epsdfx=subs(df,findsym(df),x0);ifdiff(d2f)==0d2fx=double(d2f);elsed2fx=subs(d2f,findsym(d2f),x0);endx1=x0-dfx/d2fx;k=k+1;tol=abs(dfx);x0=x1;endx=x1;minf=subs(f,findsym(f),x);formatshort;牛顿法程序function[x,minf]=minNe最速下降法和共轭梯度法最速下降法和共轭梯度法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法源程序运行结果最速下降法源程序运行结果共轭梯度法1.算法原理

共轭梯度法是利用目标函数梯度逐步产生共轭方向作为线搜索方向的方法，每次搜索方向都是在目标函数梯度的共轭方向，搜索步长通过一维极值算法确定。共轭梯度法是介于最速下降法与牛顿法之间的一个方法。它仅需利用一阶导数的信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点。共轭梯度法不仅是解大型线性方程组最有用的方法之一，也是解大型非线性最优化问题最有效的算法之一。共轭梯度法1.算法原理共轭梯度法是介于最速下降法与牛共轭梯度法共轭梯度法最早是由Hestenes和Stiefel(1952)提出来的，用于解正定系数矩阵的线性方程组。在这个基础上，Fletcher和Reeves(1964)首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用于实际问题中。共轭梯度法共轭梯度法最早是由Hestenes和Sti共轭梯度法共轭梯度法共轭梯度法共轭梯度法共轭梯度法共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的。而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合。因此存储量小，计算方便。共轭梯度法共轭梯度法是一个典型的共轭方向法，它的每一个搜共轭梯度法共轭梯度法共轭梯度法共轭梯度法共轭梯度法共轭梯度法共轭梯度法这说明我们在每一个迭代点处产生的下降方向都是互相共轭的，这满足算法的要求。共轭梯度法这说明我们在每一个迭代点处产生的下降方向都共轭梯度法共轭梯度法共轭梯度法综合以上，我们可以得到各个迭代点处下降方向都是Q共轭的共轭梯度算法。共轭梯度法综合以上，我们可以得到各个迭代点处下降方向共轭梯度法共轭梯度法共轭梯度法共轭梯度法共轭梯度法共轭梯度法共轭梯度法共轭梯度法共轭梯度法共轭梯度法共轭梯度法共轭梯度法共轭梯度法源程序共轭梯度法源程序共轭梯度法小结共轭梯度法小结共轭梯度法小结共轭梯度法小结共轭梯度法小结共轭梯度法小结共轭梯度法小结共轭梯度法小结牛顿法牛顿法牛顿法牛顿法牛顿法牛顿法牛顿法源程序运行结果牛顿法源程序运行结果拟牛顿法(变尺度法)牛顿法成功的关键是利用了Hesse矩阵提供的曲率信息，但计算Hesse矩阵工作量大，并且有的目标函数的Hesse矩阵很难计算，甚至不好求出，这就导致了一个想法:能否仅利用目标函数值和一阶导数的信息，构造出目标函数的曲率近似，使方法具有类似牛顿法的收敛速度快的优点。拟牛顿法就是这样的一类算法。由于它不需要二阶导数，拟牛顿法往往比牛顿法更有效。拟牛顿条件和牛顿法的推导一样，考虑目标函数在当前点处的二次模型。拟牛顿法(变尺度法)牛顿法成功的关键是利用了He拟牛顿法(变尺度法)拟牛顿法(变尺度法)拟牛顿法(变尺度法)拟牛顿法(变尺度法)拟牛顿法(变尺度法)拟牛顿法(变尺度法)拟牛顿法(变尺度法)拟牛顿法(变尺度法)拟牛顿法(变尺度法)拟牛顿算法拟牛顿法(变尺度法)拟牛顿算法拟牛顿法(变尺度法)拟牛顿法(变尺度法)拟牛顿法(变尺度法)DFP校正是第一个拟牛顿校正，是1959年由Davidon提出的，后来由Fletcher和Powell(1963)解释和发展的.BFGS校正是目前最流行的也是最有效的拟牛顿校正，它是由Broyden,Fletcher,Goldfarb和Schanno在1970年各自独立提出的拟牛顿法。拟牛顿法(变尺度法)DFP校正是第一个拟牛顿校正，是1959拟牛顿法(变尺度法)拟牛顿法(变尺度法)拟牛顿法(变尺