无约束最优化方法幻灯片.ppt

《无约束最优化方法幻灯片.ppt》由会员分享，可在线阅读，更多相关《无约束最优化方法幻灯片.ppt（118页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、无约束最优化方法第1页，共118页，编辑于2022年，星期六主主要要内内容容l5.1最速下降法最速下降法 l5.2共轭梯度法共轭梯度法 l5.3牛顿法牛顿法 l5.4变尺度法变尺度法 l5.5步长加速法步长加速法 l5.6旋转方向法旋转方向法l5.7方向加速法方向加速法 l5.8信赖域方法信赖域方法 l5.9最小二乘法最小二乘法 第2页，共118页，编辑于2022年，星期六l无约束最优化问题的求解方法：无约束最优化问题的求解方法：解析法解析法和和直接直接法法。l解析法需要计算函数的梯度，直接法仅通过解析法需要计算函数的梯度，直接法仅通过比较目标函数值的大小来移动迭代点。比较目标函数值的大小来移

2、动迭代点。l一般来说，无约束最优化问题的求解是通过一般来说，无约束最优化问题的求解是通过一系列一系列一维搜索一维搜索来实现。来实现。l如何选择搜索方向如何选择搜索方向是求解无约束最优化问题是求解无约束最优化问题的的核心问题核心问题，搜索方向的不同选择，形成，搜索方向的不同选择，形成不同的求解方法。不同的求解方法。第3页，共118页，编辑于2022年，星期六5.1最速下降法最速下降法 5.1.1 最速下降法原理最速下降法原理第4页，共118页，编辑于2022年，星期六第5页，共118页，编辑于2022年，星期六5.1.2 最速下降法的计算步骤最速下降法的计算步骤第6页，共118页，编辑于2022

3、年，星期六第7页，共118页，编辑于2022年，星期六第8页，共118页，编辑于2022年，星期六clearsyms x1 x2;%定义符号变量定义符号变量fx=2*x12+x22;%定义符号函数定义符号函数X0=1,1;%初值初值g=jacobian(fx,x1,x2);%求符号函数的梯度求符号函数的梯度H=jacobian(g,x1,x2);%求符号函数的海塞矩阵求符号函数的海塞矩阵x1=X0(1,1);x2=X0(1,2);%赋初值赋初值g0=eval(g);H0=eval(H);%求符号函数在求符号函数在x1=1、x2=1梯度、海塞矩阵梯度、海塞矩阵k=0;fprintf(n)whil

4、e norm(g0)eps%停机判断条件停机判断条件 lamda=g0*g0/(g0*H0*g0);%求求lamda fprintf(k=%2d,lamda=%19.16f,x1=%19.16f,x2=%19.16f,fx=%19.16f,norm(p)=%19.16fn,k,lamda,x1,x2,eval(fx),norm(g0)X0=X0-lamda*g0;x1=X0(1,1);x2=X0(1,2);g0=eval(g);H0=eval(H);k=k+1;end第9页，共118页，编辑于2022年，星期六5.1.3 最速下降法的收敛性最速下降法的收敛性第10页，共118页，编辑于2022

5、年，星期六第11页，共118页，编辑于2022年，星期六l由定理由定理5-1知，在最速下降法中，前后两次的搜索知，在最速下降法中，前后两次的搜索方向垂直（见图方向垂直（见图5-1）。）。l锯齿形的搜索轨迹使最速下降法效率低下。锯齿形的搜索轨迹使最速下降法效率低下。l最速下方向反映了目标函数的一种局部性质。从最速下方向反映了目标函数的一种局部性质。从局部看，最速下降方向的确是函数值下降最快的局部看，最速下降方向的确是函数值下降最快的方向，选择这样的方向进行搜索是有利的，方向，选择这样的方向进行搜索是有利的，l从全局看，由于锯齿现象的出现，当在极小点附从全局看，由于锯齿现象的出现，当在极小点附近时

6、，即使向着极小点移动不太大的距离，也要近时，即使向着极小点移动不太大的距离，也要经历不少的弯路，从而使收敛速度大为减慢。经历不少的弯路，从而使收敛速度大为减慢。第12页，共118页，编辑于2022年，星期六l最速下降法不仅简单，而且具有全局收敛性，最速下降法不仅简单，而且具有全局收敛性，并且是并且是线性收敛线性收敛的。的。l为避免锯齿现象对收敛速度的影响，在计算初为避免锯齿现象对收敛速度的影响，在计算初期可使用最速下降法，在迭代一段时间以后，期可使用最速下降法，在迭代一段时间以后，改用其它更有效的方法，如牛顿法等。改用其它更有效的方法，如牛顿法等。l对一般的下降算法，只要搜索方向与迭代点处对一

7、般的下降算法，只要搜索方向与迭代点处的负梯度方向的夹角小于的负梯度方向的夹角小于90，使用精确一维搜，使用精确一维搜索和不精确一维搜索在一定的条件下，可以证索和不精确一维搜索在一定的条件下，可以证明下降算法具有全局收敛性。明下降算法具有全局收敛性。第13页，共118页，编辑于2022年，星期六l共共轭轭梯梯度度法法最最初初由由Hesteness和和Stiefel于于1952年年为为求求解解线线性性方方程程组组而而提提出出，1964年年Fietcher和和Reever在在此此基基础础上上，首首先先提提出了求解无约束最优化问题的出了求解无约束最优化问题的共轭梯度法共轭梯度法。l共共轭轭梯梯度度法法

8、的的基基本本思思想想：把把共共轭轭性性与与最最速速下下降降法法相相结结合合，利利用用已已知知点点处处的的梯梯度度构构造造一一组组共共轭轭方方向向，并并沿沿这这组组方方向向进进行行一一维搜索，求出目标函数的极小点。维搜索，求出目标函数的极小点。l该该方方法法具具有有收收敛敛速速度度快快、存存储储空空间间小小等等特特点点，尤尤其其是是对对于于正正定二次函数定二次函数能在有限步内达到极小点，即具有能在有限步内达到极小点，即具有二次终结性二次终结性。5.2共轭梯度法共轭梯度法 第14页，共118页，编辑于2022年，星期六5.2共轭梯度法共轭梯度法 5.2.1 共轭方向与共轭方向法共轭方向与共轭方向法

9、 第15页，共118页，编辑于2022年，星期六第16页，共118页，编辑于2022年，星期六第17页，共118页，编辑于2022年，星期六第18页，共118页，编辑于2022年，星期六第19页，共118页，编辑于2022年，星期六复习复习 第20页，共118页，编辑于2022年，星期六复习复习 第21页，共118页，编辑于2022年，星期六复习复习 第22页，共118页，编辑于2022年，星期六第23页，共118页，编辑于2022年，星期六你能找到A共轭方向吗？第24页，共118页，编辑于2022年，星期六第25页，共118页，编辑于2022年，星期六第26页，共118页，编辑于2022年，

10、星期六第27页，共118页，编辑于2022年，星期六第28页，共118页，编辑于2022年，星期六P(0)和p(1)正交吗？第29页，共118页，编辑于2022年，星期六（5-2）第30页，共118页，编辑于2022年，星期六5.2.2 正定二次函数的共轭梯度法正定二次函数的共轭梯度法 第31页，共118页，编辑于2022年，星期六第32页，共118页，编辑于2022年，星期六第33页，共118页，编辑于2022年，星期六第34页，共118页，编辑于2022年，星期六第35页，共118页，编辑于2022年，星期六第36页，共118页，编辑于2022年，星期六5.2.3 共轭梯度法的计算步骤共轭

11、梯度法的计算步骤 第37页，共118页，编辑于2022年，星期六5.2.4 非二次函数的共轭梯度法非二次函数的共轭梯度法 第38页，共118页，编辑于2022年，星期六复习复习 第39页，共118页，编辑于2022年，星期六第40页，共118页，编辑于2022年，星期六5.2.5 共轭梯度法的收敛性共轭梯度法的收敛性第41页，共118页，编辑于2022年，星期六第42页，共118页，编辑于2022年，星期六第43页，共118页，编辑于2022年，星期六第44页，共118页，编辑于2022年，星期六第45页，共118页，编辑于2022年，星期六5.3牛顿法牛顿法 l对一维搜索方法中的牛顿法加以推

12、广，就得到了求解无约束优化问题的牛顿法。l该方法具有收敛速度快的特点，l在牛顿法基础上的改进算法如阻尼牛顿法在实际中被广泛应用。第46页，共118页，编辑于2022年，星期六5.3.1牛顿法原理牛顿法原理利用二次函数近似目标函数。第47页，共118页，编辑于2022年，星期六第48页，共118页，编辑于2022年，星期六第49页，共118页，编辑于2022年，星期六第50页，共118页，编辑于2022年，星期六第51页，共118页，编辑于2022年，星期六第52页，共118页，编辑于2022年，星期六第53页，共118页，编辑于2022年，星期六5.3.2牛顿法的特点与收敛性牛顿法的特点与收敛

13、性牛顿法优点：牛顿法优点：牛顿法具有二阶收敛速度。对二次正定函数，仅需一牛顿法具有二阶收敛速度。对二次正定函数，仅需一步迭代即可达到最优解，具有二次终结性。步迭代即可达到最优解，具有二次终结性。牛顿法缺点：牛顿法缺点：（1）牛顿法是局部收敛的，即初始点选择不当，可能会导致不收）牛顿法是局部收敛的，即初始点选择不当，可能会导致不收敛；敛；（2）牛顿法不是下降算法，当二阶）牛顿法不是下降算法，当二阶Hesse阵非正定时，不能保证是下降方阵非正定时，不能保证是下降方向；向；（3）二阶）二阶Hesse阵必须可逆，否则算法将无法进行下去；阵必须可逆，否则算法将无法进行下去；（4）对函数分析性质要求苛刻，

14、计算量大，仅适合小规模优化问题。）对函数分析性质要求苛刻，计算量大，仅适合小规模优化问题。由于牛顿法有良好收敛速度，人们对它的缺点进行了多方面改进和修正。由于牛顿法有良好收敛速度，人们对它的缺点进行了多方面改进和修正。第54页，共118页，编辑于2022年，星期六5.3.3 牛顿法的改进牛顿法的改进 1.阻尼（广义）牛顿法阻尼（广义）牛顿法第55页，共118页，编辑于2022年，星期六第56页，共118页，编辑于2022年，星期六2.Goldstein-Price方法方法第57页，共118页，编辑于2022年，星期六第58页，共118页，编辑于2022年，星期六5.4 变尺度法变尺度法 第59

15、页，共118页，编辑于2022年，星期六5.4.1 变尺度法原理变尺度法原理 第60页，共118页，编辑于2022年，星期六第61页，共118页，编辑于2022年，星期六5.4.2 DFP变尺度法变尺度法 第62页，共118页，编辑于2022年，星期六第63页，共118页，编辑于2022年，星期六第64页，共118页，编辑于2022年，星期六5.4.3 BFGS变尺度法与初始尺度矩阵的修正变尺度法与初始尺度矩阵的修正 第65页，共118页，编辑于2022年，星期六第66页，共118页，编辑于2022年，星期六5.4.4变尺度法的计算步骤变尺度法的计算步骤第67页，共118页，编辑于2022年，

16、星期六第68页，共118页，编辑于2022年，星期六第69页，共118页，编辑于2022年，星期六第70页，共118页，编辑于2022年，星期六第71页，共118页，编辑于2022年，星期六第72页，共118页，编辑于2022年，星期六第73页，共118页，编辑于2022年，星期六使用使用MATLAB软件实现软件实现DFP算法算法第74页，共118页，编辑于2022年，星期六例例5-5 最优解搜索过程最优解搜索过程 第75页，共118页，编辑于2022年，星期六例例5-5 三维图三维图 第76页，共118页，编辑于2022年，星期六5.4.5 变尺度法的性质与收敛性变尺度法的性质与收敛性 第7

17、7页，共118页，编辑于2022年，星期六5.5步长加速法步长加速法 l解析法：最速下降法、共轭梯度法解析法：最速下降法、共轭梯度法、牛顿法、牛顿法 和变尺度法需和变尺度法需要计算目标函数的梯度。要计算目标函数的梯度。l直接法：不需要求目标函数的梯度。直接法：不需要求目标函数的梯度。5.5.1步长加速法的基本思想步长加速法的基本思想 l 又称又称模式搜索法模式搜索法（Pattern Search Method）。）。l由胡克（由胡克（Hooke）和基夫斯（）和基夫斯（Jeeves）于）于1961年提出的。年提出的。l它不仅易于编制计算机程序，而且具有追循谷线加速移向最优点的性它不仅易于编制计算

18、机程序，而且具有追循谷线加速移向最优点的性质。质。l基本思想从几何上讲，就是寻找具有较小函数值的基本思想从几何上讲，就是寻找具有较小函数值的“山谷山谷”，力图，力图使迭代产生的序列沿使迭代产生的序列沿“山谷山谷”逼近极小点。逼近极小点。第78页，共118页，编辑于2022年，星期六5.5.2步长加速法的搜索过程步长加速法的搜索过程 l步长加速法由步长加速法由“探测移动探测移动”和和“模式搜索模式搜索”两个交替的动作构成。两个交替的动作构成。探测移动：依次沿探测移动：依次沿n个坐标轴进行，用以确定新的基点和有利于函个坐标轴进行，用以确定新的基点和有利于函数值下降的方向。数值下降的方向。模式搜索：

19、沿相邻两个基点连线方向进行，试图顺着模式搜索：沿相邻两个基点连线方向进行，试图顺着“山谷山谷”使函数使函数值下降的更快（见图值下降的更快（见图5-4）。）。第79页，共118页，编辑于2022年，星期六第80页，共118页，编辑于2022年，星期六第81页，共118页，编辑于2022年，星期六5.5.3步长加速法的计算步骤步长加速法的计算步骤 第82页，共118页，编辑于2022年，星期六第83页，共118页，编辑于2022年，星期六第84页，共118页，编辑于2022年，星期六第85页，共118页，编辑于2022年，星期六5.6旋转方向法旋转方向法 5.6.1旋转方向法的基本思想旋转方向法的

20、基本思想 第86页，共118页，编辑于2022年，星期六5.6.2旋转方向法的搜索过程旋转方向法的搜索过程 第87页，共118页，编辑于2022年，星期六第88页，共118页，编辑于2022年，星期六第89页，共118页，编辑于2022年，星期六5.6.3旋转方向法的计算步骤旋转方向法的计算步骤 第90页，共118页，编辑于2022年，星期六第91页，共118页，编辑于2022年，星期六第92页，共118页，编辑于2022年，星期六第93页，共118页，编辑于2022年，星期六第94页，共118页，编辑于2022年，星期六请读者比较步长加速法和旋转方向法的区别第95页，共118页，编辑于202

21、2年，星期六5.7 方向加速方向加速(powell)法法 5.7.1 方向加速法的基本思想方向加速法的基本思想方向加速（Powell）法的基本思想：把整个搜索（计算）过程分为若干个阶段（轮），每个轮迭代由n+1次一维搜索组成。即在算法的每一轮中，先依次沿着n个已知的方向搜索，得到一个最好点，然后沿该轮的初始点与该最好点连线方向进行搜索，求得这一轮的最好点。再用最后的搜索方向取代前n个方向之一，进行下一轮的迭代。Powell法的特点：理论体系严密，本质是共轭方向法 在一定条件下具有二次终结性第96页，共118页，编辑于2022年，星期六5.7.2 基本基本powell法的计算步骤法的计算步骤 第

22、97页，共118页，编辑于2022年，星期六第98页，共118页，编辑于2022年，星期六5.7.3 powell法的二次终结性法的二次终结性 第99页，共118页，编辑于2022年，星期六第100页，共118页，编辑于2022年，星期六5.7.4 改进的改进的powell法法 第101页，共118页，编辑于2022年，星期六5.8 信赖域法信赖域法 5.8.1 信赖域法的基本思想信赖域法的基本思想 无约束最优化问题的一般求解策略是，给定点后，定义搜索方向，再从出发沿作一维搜索，得到新的点。信赖域方法另辟蹊径，其基本思想：给定点后，确定一个变化范围，通常取以为中心的球域（称为信赖域），在此域内

23、优化目标函数的二次逼近式，按一定的模式求出后继点。如果不满足精度要求，再定义以为中心的信赖域，并在此域内优化新的二次逼近式，直到满足精度要求为止。信赖域方法是Powell于1970年提出来的，是一种新的能保证全局收敛的算法。该方法不仅不需要进行线性搜索，而且也不必关心目标函数的Hesse阵的正定性。第102页，共118页，编辑于2022年，星期六第103页，共118页，编辑于2022年，星期六第104页，共118页，编辑于2022年，星期六第105页，共118页，编辑于2022年，星期六5.8.2 信赖域法的计算步骤信赖域法的计算步骤第106页，共118页，编辑于2022年，星期六第107页，

24、共118页，编辑于2022年，星期六第108页，共118页，编辑于2022年，星期六5.9最小二乘法最小二乘法 第109页，共118页，编辑于2022年，星期六5.9.1线性最小二乘问题线性最小二乘问题 第110页，共118页，编辑于2022年，星期六第111页，共118页，编辑于2022年，星期六第112页，共118页，编辑于2022年，星期六5.9.2 非线性最小二乘问题非线性最小二乘问题第113页，共118页，编辑于2022年，星期六第114页，共118页，编辑于2022年，星期六第115页，共118页，编辑于2022年，星期六第116页，共118页，编辑于2022年，星期六第117页，共118页，编辑于2022年，星期六5.9.3 非线性最小二乘问题的阻尼非线性最小二乘问题的阻尼Causs-Newton法计算步法计算步骤骤 第118页，共118页，编辑于2022年，星期六