第三章无约束非线性规划PPT讲稿.ppt

《第三章无约束非线性规划PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第三章无约束非线性规划PPT讲稿.ppt（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章无约束非线性规划第1页，共84页，编辑于2022年，星期二无约束非线性规划无约束非线性规划第一节 最优性条件第二节 一维搜索第三节 最速下降法和共轭梯度法第四节 牛顿法和拟牛顿法(变尺度法)第五节 信赖域法第2页，共84页，编辑于2022年，星期二引言本章讨论如下的优化模型其中其中 是是 的实值连续函数，通常假定具有二阶连续偏的实值连续函数，通常假定具有二阶连续偏导数。导数。第3页，共84页，编辑于2022年，星期二预备知识第4页，共84页，编辑于2022年，星期二预备知识第5页，共84页，编辑于2022年，星期二预备知识第6页，共84页，编辑于2022年，星期二最优性条件第7页，共84

2、页，编辑于2022年，星期二最优性条件定理的逆不成立，即梯度为零的点不一定是局部解。第8页，共84页，编辑于2022年，星期二最优性条件第9页，共84页，编辑于2022年，星期二迭代法求解无约束优化问题的常用方法是数值解法，而数值解法中最为常见的是迭代法。迭代法思想：第10页，共84页，编辑于2022年，星期二迭代法第11页，共84页，编辑于2022年，星期二最优性条件第12页，共84页，编辑于2022年，星期二迭代算法迭代的终止条件在不同的最优化方法中也是不同的。理论上，迭代的终止条件在不同的最优化方法中也是不同的。理论上，根据最优性的一阶必要条件，以及算法的设计思想，可以用根据最优性的一阶

3、必要条件，以及算法的设计思想，可以用来终止迭代，其中来终止迭代，其中是给定的精度要求。是给定的精度要求。第13页，共84页，编辑于2022年，星期二一维搜索第14页，共84页，编辑于2022年，星期二一维搜索二分法 对于区间a,b上连续不断、且f(a)f(b)0的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫做二分法（bisectionbisection）例2 借助计算器或计算机用二分法求方程2x+3x=7 的近似解(精确到0.1).第15页，共84页，编辑于2022年，星期二一维搜索二分法那么我们一起来总结一下二分

4、法的解题步骤那么我们一起来总结一下二分法的解题步骤给定精确度，用二分法求函数f(x)零点近似解的步骤如下：,给定精确度 ；确定区间a,b,验证求区间(a,b)的中点 ；计算f()；若f()=0，则就是函数的零点；若，则令b=()；此时零点若，则令a=(此时零点)；判断是否达到精确度：即若|a-b|eps&k fu a=l;l=u;u=a+0.618*(b-a);else b=u;u=l;l=a+0.382*(b-a);end k=k+1;tol=abs(b-a);endif k=100000 disp(找不到最小值！);x=NaN;minf=NaN;return;endx=(a+b)/2;mi

5、nf=subs(f,findsym(f),x);format short;黄金分割法源程序黄金分割法源程序第21页，共84页，编辑于2022年，星期二一维搜索牛顿法第22页，共84页，编辑于2022年，星期二一维搜索牛顿法第23页，共84页，编辑于2022年，星期二一维搜索牛顿法 对于正定二次函数，牛顿法一步即可达到最优解。对于对于正定二次函数，牛顿法一步即可达到最优解。对于一般非二次函数，牛顿法并不能保证经过有限次迭代法求得一般非二次函数，牛顿法并不能保证经过有限次迭代法求得最优解，但如果初始点充分靠近极小点，牛顿法的收敛速度最优解，但如果初始点充分靠近极小点，牛顿法的收敛速度一般是很快的。

6、一般是很快的。第24页，共84页，编辑于2022年，星期二牛顿法程序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 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=x

7、1;minf=subs(f,findsym(f),x);format short;第25页，共84页，编辑于2022年，星期二最速下降法和共轭梯度法第26页，共84页，编辑于2022年，星期二最速下降法第27页，共84页，编辑于2022年，星期二最速下降法第28页，共84页，编辑于2022年，星期二最速下降法第29页，共84页，编辑于2022年，星期二最速下降法第30页，共84页，编辑于2022年，星期二最速下降法第31页，共84页，编辑于2022年，星期二最速下降法第32页，共84页，编辑于2022年，星期二最速下降法第33页，共84页，编辑于2022年，星期二最速下降法源程序运行结果运行结

8、果第34页，共84页，编辑于2022年，星期二共轭梯度法1.1.算法原理算法原理 共轭梯度法是利用目标函数梯度逐步产生共轭方向作为线搜索方向的方法，每次搜索方向都是在目标函数梯度的共轭方向，搜索步长通过一维极值算法确定。共轭梯度法是介于最速下降法与牛顿法之间的一个方法。它仅需共轭梯度法是介于最速下降法与牛顿法之间的一个方法。它仅需利用一阶导数的信息，但克服了最速下降法收敛慢的缺点，又避免了利用一阶导数的信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算牛顿法需要存储和计算HesseHesse矩阵并求逆的缺点。共轭梯度法不仅是矩阵并求逆的缺点。共轭梯度法不仅是解大型线性方程组最有

9、用的方法之一，也是解大型非线性最优化问题解大型线性方程组最有用的方法之一，也是解大型非线性最优化问题最有效的算法之一。最有效的算法之一。第35页，共84页，编辑于2022年，星期二共轭梯度法 共轭梯度法最早是由共轭梯度法最早是由HestenesHestenes和和Stiefel(1952)Stiefel(1952)提出提出来的，用于解正定系数矩阵的线性方程组。在这个基来的，用于解正定系数矩阵的线性方程组。在这个基础上，础上，FletcherFletcher和和Reeves(1964)Reeves(1964)首先提出了解非线性首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩最优化

10、问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用于实际问题中。现在共轭梯度法已经广泛地应用于实际问题中。第36页，共84页，编辑于2022年，星期二共轭梯度法第37页，共84页，编辑于2022年，星期二共轭梯度法第38页，共84页，编辑于2022年，星期二共轭梯度法 共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的。而这些搜索方向 仅仅是负梯度方向 与上一次迭代的搜索方向 的组合。因此存储量小，计算方便。第39页，共84页，编辑于2022年，星期二共轭梯度法第40页，

11、共84页，编辑于2022年，星期二共轭梯度法第41页，共84页，编辑于2022年，星期二共轭梯度法第42页，共84页，编辑于2022年，星期二共轭梯度法 这说明我们在每一个迭代点处产生的下降方向都是互这说明我们在每一个迭代点处产生的下降方向都是互相共轭的，这满足算法的要求。相共轭的，这满足算法的要求。第43页，共84页，编辑于2022年，星期二共轭梯度法第44页，共84页，编辑于2022年，星期二共轭梯度法 综合以上，我们可以得到各个迭代点处下降方向都综合以上，我们可以得到各个迭代点处下降方向都是是Q Q共轭的共轭梯度算法。共轭的共轭梯度算法。第45页，共84页，编辑于2022年，星期二共轭梯

12、度法第46页，共84页，编辑于2022年，星期二共轭梯度法第47页，共84页，编辑于2022年，星期二共轭梯度法第48页，共84页，编辑于2022年，星期二共轭梯度法第49页，共84页，编辑于2022年，星期二共轭梯度法第50页，共84页，编辑于2022年，星期二共轭梯度法第51页，共84页，编辑于2022年，星期二共轭梯度法源程序第52页，共84页，编辑于2022年，星期二共轭梯度法小结第53页，共84页，编辑于2022年，星期二共轭梯度法小结第54页，共84页，编辑于2022年，星期二共轭梯度法小结第55页，共84页，编辑于2022年，星期二共轭梯度法小结第56页，共84页，编辑于2022

13、年，星期二牛顿法第57页，共84页，编辑于2022年，星期二牛顿法第58页，共84页，编辑于2022年，星期二牛顿法第59页，共84页，编辑于2022年，星期二牛顿法源程序运行结果运行结果第60页，共84页，编辑于2022年，星期二拟牛顿法(变尺度法)牛顿法成功的关键是利用了牛顿法成功的关键是利用了HesseHesse矩阵提供的曲矩阵提供的曲率信息，但计算率信息，但计算HesseHesse矩阵工作量大，并且有的目标矩阵工作量大，并且有的目标函数的函数的HesseHesse矩阵很难计算，甚至不好求出，这就导矩阵很难计算，甚至不好求出，这就导致了一个想法致了一个想法:能否仅利用目标函数值和一阶导数

14、的能否仅利用目标函数值和一阶导数的信息，构造出目标函数的曲率近似，使方法具有类信息，构造出目标函数的曲率近似，使方法具有类似牛顿法的收敛速度快的优点。拟牛顿法就是这样似牛顿法的收敛速度快的优点。拟牛顿法就是这样的一类算法。由于它不需要二阶导数，拟牛顿法往的一类算法。由于它不需要二阶导数，拟牛顿法往往比牛顿法更有效。往比牛顿法更有效。拟牛顿条件拟牛顿条件 和牛顿法的推导一样，考虑目标函数 在当前点 处的二次模型。第61页，共84页，编辑于2022年，星期二拟牛顿法(变尺度法)第62页，共84页，编辑于2022年，星期二拟牛顿法(变尺度法)第63页，共84页，编辑于2022年，星期二拟牛顿法(变尺

15、度法)第64页，共84页，编辑于2022年，星期二拟牛顿法(变尺度法)第65页，共84页，编辑于2022年，星期二拟牛顿法(变尺度法)拟牛顿算法拟牛顿算法第66页，共84页，编辑于2022年，星期二拟牛顿法(变尺度法)第67页，共84页，编辑于2022年，星期二拟牛顿法(变尺度法)DFPDFP校正是第一个拟牛顿校正，是校正是第一个拟牛顿校正，是19591959年由年由DavidonDavidon提出提出的，后来由的，后来由FletcherFletcher和和Powell(1963)Powell(1963)解释和发展的解释和发展的.BFGS.BFGS校正是目前最流行的也是最有效的拟牛顿校正，它是

16、由校正是目前最流行的也是最有效的拟牛顿校正，它是由Broyden,Fletcher,GoldfarbBroyden,Fletcher,Goldfarb和和SchannoSchanno在在19701970年各自独年各自独立提出的拟牛顿法。立提出的拟牛顿法。第68页，共84页，编辑于2022年，星期二拟牛顿法(变尺度法)第69页，共84页，编辑于2022年，星期二拟牛顿法(变尺度法)第70页，共84页，编辑于2022年，星期二拟牛顿法(变尺度法)第71页，共84页，编辑于2022年，星期二拟牛顿法(变尺度法)第72页，共84页，编辑于2022年，星期二拟牛顿法源程序第73页，共84页，编辑于202

17、2年，星期二信赖域算法第74页，共84页，编辑于2022年，星期二信赖域算法第75页，共84页，编辑于2022年，星期二信赖域算法第76页，共84页，编辑于2022年，星期二信赖域算法第77页，共84页，编辑于2022年，星期二信赖域算法第78页，共84页，编辑于2022年，星期二信赖域算法第79页，共84页，编辑于2022年，星期二信赖域算法第80页，共84页，编辑于2022年，星期二信赖域算法源程序第81页，共84页，编辑于2022年，星期二信赖域算法运行结果第82页，共84页，编辑于2022年，星期二本本 章章 完完谢谢 谢谢 大大 家家！第83页，共84页，编辑于2022年，星期二第84页，共84页，编辑于2022年，星期二