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

《第四章无约束优化方法课件》由会员分享，可在线阅读，更多相关《第四章无约束优化方法课件（157页珍藏版）》请在金锄头文库上搜索。

1、,第四章 无约束优化方法,4.1,概述,4.2,最速下降法,4.3,牛顿型方法,4.4,共轭方向及共轭方向法,重点,4.5,共轭梯度法,4.6,变尺度法,4.7,坐标轮换法,4.8,鲍威尔方法,4.9,单型替换法,机械优化设计问题大都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。工程问题大都如此。 为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基

2、础。,4.1 概述,（4）对于多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论意义，但无实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础。,目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。,无约束优化问题的数学模型是：,求n维设计变量,使目标函数,无约束优化问题的求解 解析法 对于此类问题的求解，可以直接应用目标函数极值条件来确定极值点。把求解目标函数极值的问题变成求解下列方程,这是一个含有 个未知量， 个方程的方程组（一般是非线性的方程组）

3、，除了一些特殊情况外，求解析解比较困难，一般需要采用数值方法求解。但是，与其用数值计算方法求解非线性方程组，倒不如用数值计算方法直接求解无约束极值问题。,数值方法* 最常用的数值方法是数学规划方法，其基本思想是从绐定的初始点 出发，沿某一搜索方向 进行搜索，确定最佳步长 使函数值沿方向 下降最大。按照这样的方式按下述公式不断进行，形成迭代的下降算法 在上式中， 是第是 次搜索或迭代方向，称为搜索方向（迭代方向）。,数值方法* 最常用的数值方法是搜索方法，其基本思想如下图所示：,无约束优化算法的粗框图,开始,一维搜索,本章重点,各种无约束优化方法的主要区别就在于确定其搜索方向 的方法不同，搜索方

4、向的构成问题是无约束优化方法的关键。 和 的形成和确定方法不同就派生出不同的 维无约束优化问题的数值解法。 根据构成搜索方向 所使用的信息性质的不同，无约束优化方法可以分为两类。 利用目标函数的一阶或二阶导数信息构造搜索方向的无约束优化方法； 只用目标函数值的信息构造搜索方向的无约束优化方法,最速下降法,牛顿法,共轭方向法,共轭梯度法,变尺度法,坐标轮换法,鲍威尔方法,单型替换法,无约束优化方法,利用目标函数的导数信息,利用目标函数值信息,用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的（n 20）问题，一般情况下比间接法效率低。间接法除要计算目标

5、函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。,4.2 最速下降法,基于上述思想，形成如下迭代算法： 最速下降法是以负梯度方向作为搜索方向，所以最速下降法又称为梯度法。,最速下降法是一个求解极值问题的古老算法，1847年由柯西（Cauchy）提出。,最速下降法的基本思想 优化设计的目的是追求目标函数值 最小，因此如果从某点X 出发，其搜索方向 d 取该点的负梯度方向 （最速下降方向），那么就可以使函数值在该点附近的范围内下降最快。,为了使目标函数值沿搜索方向 能够获得最大的下降值，其步长因子 应取一维搜索的最佳步长。即有,根据一元函数极值的必要条件和多元复合函数求导公式，得,最佳步

6、长的确定,由上式可知，在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。 梯度法的搜索路线： 最速下降法中，迭代点向函数极小点靠近的过程，走的是曲折的路线。这一次的搜索方向与前一次的搜索方向互相垂直，形成“之”字形的直齿锯齿现象，如图所示,在接近极小点的位置，由于锯齿现象使每次迭代行进的距离缩短，因而收敛速度减慢，这种情况似乎与“最速下降”的名称相矛盾，这主要是因为梯度是函数的局部性质（从局部上看，在一点附近函数的下降是快的），但从整体上看则走了许多弯路，函数的下降并不算快。,sk,梯度法的算法程序框图,例题,这个问题的目标函数的等值线

7、为一簇椭圆,迭代点从 走的是一段锯齿形路线，见图4-3。,图4-3,将上例中目标函数 引入变换,其等值线由椭圆变成一簇同心圆。,仍从 即 出发进行最速下降法寻优。此时：,沿负梯度方向进行一维搜索：,则函数f(X)变为：,y1=x1, y2=5x2,由,从而算得一步计算后设计点的位置及其目标函数：,经变换后，只需一次迭代，就可找到最优解。,这是因为经过尺度变换：,等值线由椭圆变成圆。,梯度法小结,（1）理论明确，程序简单，对初始点要求不严格。 （2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。 （3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路

8、线呈直齿锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。,（4）梯度法的收敛速度与目标函数的性质密切相关。 如目标函数的等值线所形成的椭圆族越扁，迭代次数就越多，搜索难于达到极小点； 对于等值线(面)为同心圆（球）的目标函数，或初始点选在椭圆族对称轴上等特例，一次搜索即可达到极小点。,最速下降法的收敛速度和变量的尺度关系很大，这一点可从最速下降法收敛速度的估计式上看出来。在适当条件下，有 式中 的海赛矩阵最大特征值上界； 其最小特征值下界。,当相邻两个迭代点之间满足上式时（右边的系数为小于等于1的正的常数），我们称相应的迭代方法是具有线性收敛速度的迭代法。因此，最速下降法是具

9、有线性收敛速度的选代法。,鉴于应用最速下降法可以使目标函数在开头几步下降很快，所以它可与其它无约束优化方法配合使用。 即在开始阶段用梯度法求得一个较优的初始点，然后用其它收敛快的方法继续寻找极小点。,4-2 牛顿法及其改进,设 为 的极小点,原始牛顿法,这就是多元函数求极值的牛顿法迭代公式。,对于二次函数 ，其展开到二次项的泰勒展开式就是其本身，海赛矩阵G是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。 如果某一迭代方法能使二次型函数在有限次迭代内达到极小点，称此迭代方法是二次收敛的。因此牛顿方法是二次收敛的。,定步长,例42 求目标函数 的极小点。 解 取初

10、始点,经过一次迭代即求得极小点,函数极小值,从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升 。,因此需要对牛顿法进行改进，引人数学规划法的搜寻概念，产生了阻尼牛顿法。,阻尼牛顿法,阻尼因子 ，沿牛顿方向进行一维搜索的最佳步长，由下式求得：,如果我们把 看作是 一个搜索方向，并称其为牛顿方向，则阻尼牛顿法采取如下的迭代公式,可以看出原始牛顿法就相当于阻尼牛顿法的步长因子取成固定值1的情况。 阻尼牛顿法每次迭代都在牛顿方向上进行一维搜索，避免了迭代后函数值上升的现象，从而保持了牛

11、顿法二次收敛的特性，而对初始点的选取并没有苛刻的要求。,阻尼牛顿法程序框图,1、原始牛顿法和阻尼牛顿法统称为牛顿型方法。牛顿法是二次收敛的，收敛速度较快； 2、这类方法的主要缺点计算复杂，工作量大，要求计算机存储量大： 1）每次迭代都要计算函数的海赛矩阵，并对该矩阵求逆，工作量非常大。 2）从计算机存储方面考虑，牛顿型方法所需的存储量也很大。一般计算量和存储量以n2比例增长,牛顿法小结,基于以下两方面的原因， 给牛顿法的运用带来一定局限性 使用条件苛刻，对于二阶不可微的f(X)也不适用。若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向； 为了保证牛顿方向是目标函数下降方向，海赛矩阵

12、的逆阵必须正定；,函数只有在函数极值点附近，才能很接近一个二次函数，在此范围之外用二次函数近似代替原目标函数，误差较大，并不能保证迭代一次就达到极小点 对于非二次函数，采用牛顿法时初始点不能任取，初始点应选在X*附近，有一定难度而是要求离极小点较近。否则，可能不收敛或收敛到非极小点。 虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。,一般迭代式：,梯度法：,原始牛顿法：,牛顿法：,梯度法与牛顿法,4.4 共轭方向及共轭方向法,概述 由于最速下降法存在“锯齿”现象，为了提高收敛速度，发展了一类共轭方向法。这类方法的搜索方向取的是共轭方向。 共轭方

13、向是优化方法研究中的一个重要概念，许多效果较好的优化方法都是以共轭方向作为其搜索方向的。,考虑以上二次函数为二维的情况 由平面解析几何知识可知二元二次函数的等值线为一族椭圆。,共轭方向的概念是在研究二次函数 引入的（其中 G 为对称正定矩阵）,任选取初始点x0沿某个下降方向d0作一维搜索，得x1,共轭方向的概念,因为 是沿d0方向搜索的最佳步长，即在点x1处函数f（x）沿方向d0的方向导数为零。考虑到点x1处方向导数与梯度之间的关系，故有,即： 与某一等值线相切于 点,如果按最速下降法，选择负梯度方向 为搜索方向，则将发生锯齿现象 。,现取下一次的迭代搜索方向d1直指极小点x*。,0d0,x,

14、0,x1,x*,1,1,1d1,d1,如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行d0、d1两次直线搜索就可以求到极小点x* ，即有,那么这样的d1方向应该满足什么条件呢 ?,0d0,x,0,x1,x*,1,1,1d1,d1,对于前述的二次函数:,当 时，,x*是f(x)极小点，应满足极值必要条件，故有,将等式两边同时左乘 得：,有,就是使d1直指极小点x* ， d1所必须满足的条件 。,两个向量d0和d1称为G的共轭向量，或称d0和d1对G是共轭方向。,共轭方向的定义 设 为 对称正定矩阵，若 维空间中有 个非零向量 满足 则称 对 共轭，或称它们是 的共轭方向。 当 （单位

15、矩阵）时，上式变成 故向量 互相正交。由此可见，共轭概念是正交概念的推广，正交是共轭的特例。,例子,共轭方向的性质,性质1 若非零向量系d0,d1,d2,dm-1是对G共轭，则这m个向量是线性无关的。,性质2 在n维空间中互相共轭的非零向量的个数不超过n。,性质3 从任意初始点出发，顺次沿n个G的共轭方向d0,d1, d2,进行一维搜索，最多经过n次迭代就可以找到的二次函数f(x)极小点。 说明这种迭代方法具有二次收敛性。,以共轭方向的性质3为基础可以建立共轭方向法，它提供了求二次函数极小点的原则方法。其步骤是： 选定初始点 ，下降方向 和收敛精度 ，置 。 沿 方向进行一维搜索，得 。 判断 是否满足，若满足则打印 ，程序结束；否则转4。 提供新的共轭方向 ，使 ， 其中 置 ，转2。,共轭方向法,提供新的共轭方向 使,共轭方向法的程序框图（P67）,在无约束方法中许多算法都是以共轭方向作为搜索方向，它们具有许多特点。根据构造共轭方向的原理不同，可以形成不同的共轭方向法。 （如共轭梯度法，鲍威尔（Powell）法等）,共轭方向的形成 格拉姆斯密特（Gram-Schmidt）向量组共轭化方法（格拉姆斯密特向量组正交化方法的推广）,例题 求 的一组共轭向量组 。 解：选三个坐标轴上的单位向量 作为一组线性无关向量组，即,取 设 则有,故有 设 则有,且 故有,经过验算有