第四章-无约束优化方法PPT课件

1、1,第四章 无约束优化方法,第1章所列举的机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。工程问题大都如此。 为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础,第一节 概 述,2,第四章 无约束优化方法,4）对于多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理

2、论意义，但无实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础,3,第四章 无约束优化方法,第一节 概 述,对于无约束优化问题的求解，可以直接应用第二章的极值条件来确定极值点位置。这就是把求函数极值的问题变成求解方程,无约束优化问题是,求n维设计变量,使目标函数,这是一个含有n个未知量，n个方程的方程组，并且一般是非线性的。对于 非线性方程组，一般是很难用解析方法求解的，需要采用数值计算方法逐 步求出非线性联立方程组的解,4,第四章 无约束优化方法,第一节 概 述,数值解法：是从给定的初始点x0出发，沿某一搜索方向d0进行搜索。确定最佳步长

3、，使函数值沿d0方向下降最大。依此方式按下述公式不断进行，形成迭代的下降算法,1）选择迭代方向即探索方向； 2）在确定的方向上选择适当步长迈步进行探索,各种无约束优化方法的区别就在于确定其搜索方向dk的方法不同。所以搜索方向的构成问题是无约束优化方法的关键,5,第四章 无约束优化方法,第一节 概 述,6,第四章 无约束优化方法,第一节 概 述,无约束优化方法可以分成两类： 一类是利用目标函数的一阶或二阶导数的无约束优化方 法（如最速下降法、共轭梯度法、牛顿法及变尺度法）； 另一类只利用目标函数的无约束优化方法（如坐标轮换 法、单形替换法及鲍威尔法等,7,第四章 无约束优化方法,第二节 最速下降

4、法,最速下降法的迭代公式,定义： 最速下降法就是采用使目标函数值下降得最快的负梯度方向 作为探索方向，来求目标函数的极小值的方法，又称为梯度法,8,第四章 无约束优化方法,第二节 最速下降法,为了使目标函数值沿搜索方向 能够获得最大的下降值，其步长因子 应取一维搜索的最佳步长。即有,根据一元函数极值的必要条件和多元复合函数求导公式，得,9,第四章 无约束优化方法,第二节 最速下降法,在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象，而且越接近极小点锯齿越

5、细,图4-2 最速下降法的搜索路径,10,第四章 无约束优化方法,第二节 最速下降法,最速下降法的迭代步骤,11,第四章 无约束优化方法,第二节 最速下降法,12,第四章 无约束优化方法,沿负梯度方向进行一维搜索，有,为一维搜索最佳步长，应满足极值必要条件,解 取初始点 则初始点处函数值及梯 度分别为,13,第四章 无约束优化方法,算出一维搜索最佳步长,第一次迭代设计点位置和函数值,继续作下去，经10次迭代后，得到最优解,14,第四章 无约束优化方法,这个问题的目标函数的等值线为一簇椭圆,迭代点从 走的是一段锯齿形路线，见图4-3,15,第四章 无约束优化方法,将上例中目标函数 引入变换,其等

6、值线由椭圆变成一簇同心圆,仍从 即 出发进行最速下降法寻优。此时,沿负梯度方向进行一维搜索,则函数f(X)变为,y1=x1, y2=5x2,16,第四章 无约束优化方法,由,从而算得第一次走步后设计点的位置及其相应的目标函数,17,第四章 无约束优化方法,经变换后，只需一次迭代，就可找到最优解,这是因为经过尺度变换,等值线由椭圆变成圆,18,第四章 无约束优化方法,第二节 最速下降法,最速下降法的特点： 1）对初始搜索点无严格要求； 2）收敛速度不快； 3）相邻两次迭代搜索方向互相垂直，在远离极值点处收敛快，在靠近极值点处收敛慢； 4）收敛速度与目标函数值的性质有关，对等值线是同心圆的目标函数

7、来说，经过一次迭代就可以达到极值点,19,第四章 无约束优化方法,第三节 牛顿型法,牛顿型法的基本思想： 利用二次曲线来逐点近似原目标函数，以二次曲线的极 小点来近似原目标函数的极小点并逐渐逼近该点,基本牛顿法的迭代公式,20,第四章 无约束优化方法,第三节 牛顿型法,基本牛顿法的迭代公式,21,第四章 无约束优化方法,第三节 牛顿型法,基本牛顿法的迭代公式,阻尼牛顿法的迭代公式,22,第四章 无约束优化方法,第三节 牛顿型法,阻尼牛顿法的迭代步骤,23,第四章 无约束优化方法,第三节 牛顿型法,阻尼牛顿法的迭代公式,24,第四章 无约束优化方法,第四节 共轭方向及共轭方向法,在下一次迭代时，

8、选择搜索方d1指向极小点x,共轭方向,以二元函数为例： 我们任意选择一个初始点x0点， 沿着某个下降方向d0作一维搜索,25,第四章 无约束优化方法,第四节 共轭方向及共轭方向法,共轭方向,正交,26,第四章 无约束优化方法,第四节 共轭方向及共轭方向法,共轭方向的性质,27,第四章 无约束优化方法,第四节 共轭方向及共轭方向法,共轭方向法的步骤,28,第四章 无约束优化方法,第四节 共轭方向及共轭方向法,共轭方向的形成 格拉姆-斯密特向量系共轭化的方法,n个线性无关的向量系vi（i=0,1，n-1,一组独立向量dr（r=0,1，n-1,29,第四章 无约束优化方法,第四节 共轭方向及共轭方向

9、法,30,第四章 无约束优化方法,第五节 共轭梯度法,共轭梯度法： 先沿最速下降方向(负梯度方向)探索第一步，然后沿与该负梯度方向相共轭的方向进行探索,31,第四章 无约束优化方法,第五节 共轭梯度法,共轭方向与梯度之间的关系,它表示沿着方向dk做一维搜索， 它的终点xk+1与始点xk的梯度之差 与dk的共轭方向dj正交,32,第四章 无约束优化方法,第五节 共轭梯度法,共轭梯度法递推公式,33,第四章 无约束优化方法,第五节 共轭梯度法,共轭梯度法步骤,34,第四章 无约束优化方法,第五节 共轭梯度法,共轭梯度法步骤,35,第四章 无约束优化方法,第五节 共轭梯度法,共轭梯度法,36,设法构

10、造出一个对称正定矩阵 来代替 ，并在迭代过程中使 逐渐逼近 ,那么就简化了牛顿法的计算，并且保持了牛顿法收敛快的优点,第四章 无约束优化方法,第六节 变尺度法（拟牛顿法,变尺度法的基本思想,37,第四章 无约束优化方法,第六节 变尺度法（拟牛顿法,尺度矩阵,G 正定,目的：目标函数的偏心率减小到零,38,第四章 无约束优化方法,第六节 变尺度法（拟牛顿法,变尺度矩阵的建立,变尺度法的迭代公式,搜索方向,尺度矩阵应具备的条件,1）为正定对称矩阵； 2）具有简单的迭代形式: 3）满足拟牛顿条件： 令 则,39,第四章 无约束优化方法,第六节 变尺度法（拟牛顿法,变尺度法的一般步骤,40,第四章 无

11、约束优化方法,第六节 变尺度法（拟牛顿法,变尺度法的流程图,41,第四章 无约束优化方法,第六节 变尺度法（拟牛顿法,DFP算法,DFP算法的校正公式,42,第四章 无约束优化方法,第六节 变尺度法（拟牛顿法,DFP算法,43,第四章 无约束优化方法,第七节 坐标轮换法,基本思想： 每次仅对多元函数的一个变量沿其坐标轴进行一维探索，其余各变量均固定不动，并依次轮换进行一维探索的坐标轴，完成第一轮探索后再重新进行第二轮探索，直到找到目标函数在全域上的最小点为止。 目的：将一个多维的无约束最优化问题，转化为一系列的一维问题来求解,44,第四章 无约束优化方法,第七节 坐标轮换法,二维问题,45,第

12、四章 无约束优化方法,第七节 坐标轮换法,第k轮迭代公式,46,第四章 无约束优化方法,第七节 坐标轮换法,步长的几种取法,随机选择方法 加速步长法 最优步长法（一维搜索方法，如：黄金分割法、二次插值法，来确定最优步长,47,第四章 无约束优化方法,第七节 坐标轮换法,加速步长法,48,第四章 无约束优化方法,第七节 坐标轮换法,坐标轮换法的流程图,49,第四章 无约束优化方法,第七节 坐标轮换法,坐标轮换法的特点,计算简单、概念清楚、易于掌握；但搜索路线较长（需要经过多次曲折迂回的路径才能达到极值点），计算率较低，特别是当维数很高时很费时，所以坐标轮换法只能用于低维（n10）的优化问题求解。

13、此外，坐标轮换法的效率在很大程度上取决于目标函数的性态，也就是等值线的形态与坐标轴的关系,50,第四章 无约束优化方法,第八节 鲍威尔法,鲍威尔法的基本思想： 直接利用迭代点的目标函数值来构造共轭方向，然后再从任一初始点出发，逐次的共轭方向作一维搜索求极值点,51,第四章 无约束优化方法,第八节 鲍威尔法,共轭方向的生成,结论：从不同的两点出发，沿同一方向进行两次一维搜索，所得两个极小点的连线方向便是原方向共轭的另一方向,52,第四章 无约束优化方法,第八节 鲍威尔法,共轭方向的生成,二维情况： 任意点出发沿着x1轴方向和AB方向搜索，即可得到极小点,53,第四章 无约束优化方法,第八节 鲍威

14、尔法,基本POWELL法（二维,54,第四章 无约束优化方法,第八节 鲍威尔法,基本POWELL法（n维,1）从初始点出发，首先沿着n个坐标轴方向进行一维搜索，得到一个终点； 2）由初始点和终点连线形成一个新方向，该方向排在原方向组的最后，去掉原方向组的的第一个方向，形成新的方向组； 3）从上一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。 4）从新的始点出发，沿着新的方向组做一维搜索。 如此反复进行n轮搜索后，可找到n个共轭方向，若目标函数是正定二次型函数，则经过n轮后就可以找到极小点,55,第四章 无约束优化方法,第八节 鲍威尔法,改进POWELL法,获得新方向构成新方向组时,不是轮换地去掉原来的方向,而是经判别后,在n+1个方向中留下最接近共轭的n个方向,56,1）给定初始点 ，选取初始方向组，它由n个线性无关的向量组成 置k=0 2）从 出发顺次沿 作一维搜索得 接着以 为起点，沿方向 移动一个距离 得到 并分别求出,改进POWELL算法的步骤,一轮迭代的始点,一轮迭代的