《04机械优化设计第四章(200156).ppt》由会员分享，可在线阅读，更多相关《04机械优化设计第四章(200156).ppt（154页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、*14.1概述概述概述概述4.2最速下降法最速下降法最速下降法最速下降法4.3牛顿型方法牛顿型方法牛顿型方法牛顿型方法4.4共轭方向及共轭方向法共轭方向及共轭方向法共轭方向及共轭方向法共轭方向及共轭方向法重点重点4.5共轭梯度法共轭梯度法共轭梯度法共轭梯度法4.6变尺度法变尺度法变尺度法变尺度法4.7坐标轮换法坐标轮换法坐标轮换法坐标轮换法4.8鲍威尔方法鲍威尔方法鲍威尔方法鲍威尔方法4.9单型替换法单型替换法单型替换法单型替换法第四章无约束优化方法第四章无约束优化方法*2 第第1章所列举的机械优化设计章所列举的机械优化设计问题大都是在一定问题大都是在一定限制条件下追求某一指标为最小，属于约束
2、优化问限制条件下追求某一指标为最小，属于约束优化问题。题。为什么要研究无约束优化问题？为什么要研究无约束优化问题？1）有些实际问题，其数学模型本身就是一个无约束问题；）有些实际问题，其数学模型本身就是一个无约束问题；2）通过熟悉它的解法可以为研究约束优化问题打下良好的）通过熟悉它的解法可以为研究约束优化问题打下良好的基础；基础；3）约束优化问题的求解可用通过一系列无约束优化方法来）约束优化问题的求解可用通过一系列无约束优化方法来达到。达到。所以无约束优化问题的解法是所以无约束优化问题的解法是优化设计方法的优化设计方法的基本组成部分基本组成部分，也是优化方法的基础。，也是优化方法的基础。*3 对
3、对于于多多维维无无约约束束问问题题来来说说，古古典典极极值值理理论论中中令令一一阶阶导导数数为为零零，但但要要求求二二阶阶可可微微，且且要要判判断断海海赛赛矩矩阵阵为为正正定定才才能能求求得得极极小小点点，这这种种方方法法有有理理论论意意义义，但但无无实实用用价价值值。和和一一维维问问题题一一样样，若若多多元元函函数数F(X)F(X)不不可可微微，亦亦无无法法求求解解。但但古古典典极极值值理理论论是无约束优化方法发展的基础。是无约束优化方法发展的基础。*41 1、无约束优化问题、无约束优化问题求 维设计变量 使目标函数，而对 没有任何限制条件。这就是把求函数极值的问题变成求解方程这就是把求函数
4、极值的问题变成求解方程的问题。即求的问题。即求X,X,使其满足使其满足*5 这是一个含有这是一个含有n n个未知量，个未知量，n n个方程的方程组（一个方程的方程组（一般是非线性的方程组），除了一些特殊情况外，求解般是非线性的方程组），除了一些特殊情况外，求解析解比较困难，一般需要采用数值方法求解。但是，析解比较困难，一般需要采用数值方法求解。但是，与其用数值计算方法求解非线性方程组，倒不如用数与其用数值计算方法求解非线性方程组，倒不如用数值计算方法直接求解无约束极值问题。值计算方法直接求解无约束极值问题。*6（1 1）利用极值条件来确定极值点的位置。）利用极值条件来确定极值点的位置。（2 2
5、）数值计算方法数值计算方法搜索方法搜索方法基本思想基本思想：从给定的初始点 出发，沿某一搜索方向 进行搜索，确定最佳步长 使函数值沿 下降最大。依此方式不断进行，形成迭代的下降算法：2 2、求解方法、求解方法 目前已研究出很多种无约束优化方法，它们的目前已研究出很多种无约束优化方法，它们的主要不同点在于主要不同点在于构造搜索方向构造搜索方向上的差别。上的差别。在上式中，在上式中，dk 是第是是第是 k+1次搜索或迭代方次搜索或迭代方向，称为向，称为搜索方向搜索方向（迭代方向）。（迭代方向）。*7数值方法数值方法*最常用的数值方法是搜索方法，其基本思想如下图所示：最常用的数值方法是搜索方法，其基
6、本思想如下图所示：*83、无、无 约约 束束 优优 化化 算算 法法 的的 粗粗 框框 图图是否一维搜索本章重点本章重点本章重点本章重点*9vdk 和和 ak的形成和确定方法不同就派生出不同的形成和确定方法不同就派生出不同的的n维无约束优化问题的数值解法。维无约束优化问题的数值解法。v根据构成搜索方向根据构成搜索方向dk所使用的信息性质的不所使用的信息性质的不同，无约束优化方法可以分为两类。同，无约束优化方法可以分为两类。1.利用目标函数的一阶或二阶导数信息利用目标函数的一阶或二阶导数信息构造构造搜索方向的无约束优化方法；搜索方向的无约束优化方法；2.只用目标函数值的信息只用目标函数值的信息构
7、造搜索方向的无构造搜索方向的无约束优化方法约束优化方法*10最速下降法最速下降法牛顿法牛顿法共轭方向法共轭方向法共轭梯度法共轭梯度法变尺度法变尺度法坐标轮换法坐标轮换法鲍威尔方法鲍威尔方法单型替换法单型替换法无无约约束束优优化化方方法法利用目标函数的导数信息利用目标函数值信息 用直接法寻找极小点时，不必求函数的导数，只要计算用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的（目标函数值。这类方法较适用于解决变量个数较少的（n 20）问题，一般情况下比间接法效率低。间接法除要计算）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标
8、函数的梯度，有的还要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。其海赛矩阵。间接法直接法*111 1、基本思想、基本思想 函数的负梯度方向是函数值在该点下降最快的方向。函数的负梯度方向是函数值在该点下降最快的方向。将将n n维问题转化为一系列维问题转化为一系列沿负梯度方向沿负梯度方向用一维搜索方法寻用一维搜索方法寻优的问题，即利用负梯度作为搜索方向，故称为最速下降优的问题，即利用负梯度作为搜索方向，故称为最速下降法或梯度法。法或梯度法。搜索方向取该点的负梯度方向即搜索方向取该点的负梯度方向即 ，使函，使函数值在该点附近的范围内下降最快。数值在该点附近的范围内下降最快。*1
9、22 2、最速下降法的原理、最速下降法的原理（1 1）使）使 ，按此规律不断走步，形成迭代算法：按此规律不断走步，形成迭代算法：（2 2）其步长因子）其步长因子 取一维搜索的取一维搜索的最佳步长最佳步长，即，即 根据一元函数极值的必要条件和多元复合函数求导公根据一元函数极值的必要条件和多元复合函数求导公式，得式，得或或*13由上式可知，在最速下降由上式可知，在最速下降法中，法中，相邻两个迭代点上相邻两个迭代点上的函数梯度相互垂直的函数梯度相互垂直。而而搜索方向就是负梯度方向，搜索方向就是负梯度方向，因此因此相邻两个搜索方向互相邻两个搜索方向互相垂直相垂直。v梯度法的搜索路线梯度法的搜索路线：q
10、最速下降法中，迭代点向最速下降法中，迭代点向函数极小点靠近的过程，函数极小点靠近的过程，走的是曲折的路线。这一走的是曲折的路线。这一次的搜索方向与前一次的次的搜索方向与前一次的搜索方向互相垂直，搜索方向互相垂直，形成形成“之之”字形的直齿锯齿现字形的直齿锯齿现象象，如图所示，如图所示最速下降法的搜索路径最速下降法的搜索路径*14在接近极小点的位置，由于锯齿现象使每次迭代行进在接近极小点的位置，由于锯齿现象使每次迭代行进的距离缩短，因而收敛速度减慢，这种情况似乎与的距离缩短，因而收敛速度减慢，这种情况似乎与“最速下降最速下降”的名称相矛盾，这主要是因为的名称相矛盾，这主要是因为梯度是函数梯度是函
11、数的局部性质的局部性质（从局部上看，在一点附近函数的下降是（从局部上看，在一点附近函数的下降是快的），但从整体上看则走了许多弯路，函数的下降快的），但从整体上看则走了许多弯路，函数的下降并不算快。并不算快。*15方法特点方法特点1 1）初始点可任选，每次迭代计算量小，存储量少，）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点；近局部极小点；2 2）任意相邻两点的搜索方向是正交的，它的迭代）任意相邻两点的搜索方向是正交的，
12、它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。步长变得很小，越走越慢。*16最最速速下下降降法法的的程程序序框框图图*17例：例：求目标函数求目标函数 的极小点的极小点解法解法1 1：取初始点取初始点，则初始点处的函数值，则初始点处的函数值及梯度分别为：及梯度分别为：为一维搜索最佳步长，应满足极值必要条件为一维搜索最佳步长，应满足极值必要条件*18则第一次迭代设计点位置和函数值则第一次迭代设计点位置和函数值经过经过1010次迭代后，得到最优解：次迭代后，得到最优解：该问题的目标函数的等值线为一族椭圆，迭代该问题的目标函数
13、的等值线为一族椭圆，迭代点走的是一段锯齿形路线，如下图。点走的是一段锯齿形路线，如下图。*19等直线为椭圆的迭代过程等直线为椭圆的迭代过程*20解法解法2 2：引入变化引入变化，则目标函数则目标函数 变为变为 ，经过坐标（尺度）变化后，只需要经过一次迭代，就可找到经过坐标（尺度）变化后，只需要经过一次迭代，就可找到最优解：最优解：Y Y0 0(2,10)*21等直线为圆的迭代过程等直线为圆的迭代过程*22讨论 可以看出二者的对角形矩阵不同，前者的等可以看出二者的对角形矩阵不同，前者的等值线为一族椭圆，后者的等值线为一族同心圆，值线为一族椭圆，后者的等值线为一族同心圆，这说明这说明对角形矩阵是表
14、示度量的矩阵或者是表对角形矩阵是表示度量的矩阵或者是表示尺度的矩阵示尺度的矩阵，最速下降法的收敛速度和变量，最速下降法的收敛速度和变量的尺度有很大关系。的尺度有很大关系。*233 3、最速下降法收敛速度的估计式、最速下降法收敛速度的估计式的海赛矩阵最大特征值上界的海赛矩阵最大特征值上界 的海赛矩阵最小特征值下界的海赛矩阵最小特征值下界 在适当条件下，有在适当条件下，有 当相邻两个迭代点之间满足上式时（右边的系数当相邻两个迭代点之间满足上式时（右边的系数为小于等于为小于等于1 1的正的常数），的正的常数），我们称相应的迭代方法是我们称相应的迭代方法是具有线性收敛速度的迭代法。因此，最速下降法是具
15、有具有线性收敛速度的迭代法。因此，最速下降法是具有线性收敛速度的选代法。线性收敛速度的选代法。*24梯度法的特点：梯度法的特点：（1 1）理论明确，程序简单，对初始点要求不严格；）理论明确，程序简单，对初始点要求不严格；（2 2）对一般函数而言，梯度法的收敛速度并不快，）对一般函数而言，梯度法的收敛速度并不快，因为最速下降法仅仅是指某点的一个因为最速下降法仅仅是指某点的一个局部性质局部性质；（3 3）梯度法相邻两次搜索方向的正交性决定了迭代）梯度法相邻两次搜索方向的正交性决定了迭代全过程的全过程的搜索路径呈锯齿形搜索路径呈锯齿形，在远离极小点时逼近速，在远离极小点时逼近速度较快，而在接近极小点
16、时逼近速度较慢；度较快，而在接近极小点时逼近速度较慢；（4 4）梯度法的）梯度法的收敛速度与目标函数的性质密切相关收敛速度与目标函数的性质密切相关。对于等值线（面）为同心圆（球）的目标函数，一次对于等值线（面）为同心圆（球）的目标函数，一次搜索即可达到极小点。搜索即可达到极小点。*25基本思想：基本思想：在在 领域内用一个二次函数领域内用一个二次函数 来近似来近似代替原目标函数，并将代替原目标函数，并将 的极小值作为目标函数的极小值作为目标函数 求优的下一个迭代点求优的下一个迭代点 。经多次迭代，使之逼近目标。经多次迭代，使之逼近目标函数函数 的极小点。的极小点。原始牛顿法原始牛顿法*26对于
17、多元函数对于多元函数，设，设 为为 极小点极小点 的第一的第一个近似点，个近似点，泰勒展开，保留到二次项，得泰勒展开，保留到二次项，得:设设 为为 的极小点，它作为的极小点，它作为 极小点极小点 的下一个近似点，根据极值必要条件：的下一个近似点，根据极值必要条件：即即 海赛矩阵海赛矩阵 1 1、牛顿法、牛顿法-多元函数求极值多元函数求极值的牛顿法迭代公式。的牛顿法迭代公式。原始牛顿方向原始牛顿方向*27 对于二次函数对于二次函数对于二次函数对于二次函数 ，其展开到二次项的泰勒展开，其展开到二次项的泰勒展开，其展开到二次项的泰勒展开，其展开到二次项的泰勒展开式就是其本身，式就是其本身，式就是其本
18、身，式就是其本身，海赛矩阵海赛矩阵海赛矩阵海赛矩阵G G G G是一个常矩阵，其中是一个常矩阵，其中是一个常矩阵，其中是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只各元素均为常数。因此，无论从任何点出发，只各元素均为常数。因此，无论从任何点出发，只各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。需一步就可找到极小点。需一步就可找到极小点。需一步就可找到极小点。如果某一迭代方法能使二次型函数在有限次迭如果某一迭代方法能使二次型函数在有限次迭如果某一迭代方法能使二次型函数在有限次迭如果某一迭代方法能使二次型函数在有限次迭代内达到极小点，称此迭代方法是代内达到极小点，称
19、此迭代方法是代内达到极小点，称此迭代方法是代内达到极小点，称此迭代方法是二次收敛二次收敛的。的。的。的。因此牛顿方法是二次收敛的。因此牛顿方法是二次收敛的。因此牛顿方法是二次收敛的。因此牛顿方法是二次收敛的。*28例例:用牛顿法求用牛顿法求 的极小值的极小值 解解：取初始点取初始点，则，则 代入牛顿法迭代公式可得代入牛顿法迭代公式可得:从而经过一次迭代即求得极小点和函数极小值。从而经过一次迭代即求得极小点和函数极小值。*29 从牛顿法迭代公式的推演中可以看到，迭代点的从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降位置是按照极值条件确定的，其中并未含有沿下
20、降方向搜寻的概念。方向搜寻的概念。因此对于非二次函数，如果采用因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升上述牛顿迭代公式，有时会使函数值上升。因此需要对牛顿法进行改进，引人数学因此需要对牛顿法进行改进，引人数学规划法的搜寻概念，产生了规划法的搜寻概念，产生了阻尼牛顿法阻尼牛顿法。*30 把把 看作一个搜索方向，看作一个搜索方向，称其为牛顿方向，称其为牛顿方向，则阻尼牛顿法的迭代公式为则阻尼牛顿法的迭代公式为：阻尼因子，即沿牛顿方向进行一维搜索的最佳步长，阻尼因子，即沿牛顿方向进行一维搜索的最佳步长，可通过如下极小化过程求得：可通过如下极小化过程求得：（1 1）阻尼牛顿法的
21、迭代公式）阻尼牛顿法的迭代公式 在牛顿法中，迭代点的位置是按照极值条件确定，并未在牛顿法中，迭代点的位置是按照极值条件确定，并未含有沿下降方向搜寻的概念，因此采用牛顿迭代公式，对含有沿下降方向搜寻的概念，因此采用牛顿迭代公式，对于非二次函数，有时会使函数值上升。于非二次函数，有时会使函数值上升。阻尼牛顿法阻尼牛顿法*31可以看出原始牛顿法就相当于阻尼牛顿法的步可以看出原始牛顿法就相当于阻尼牛顿法的步长因子取成固定值长因子取成固定值1的情况。的情况。阻尼牛顿法每次迭代都在牛顿方向上进行一维阻尼牛顿法每次迭代都在牛顿方向上进行一维搜索，避免了迭代后函数值上升的现象，从而搜索，避免了迭代后函数值上升
22、的现象，从而保持了牛顿法二次收敛的特性，而对初始点的保持了牛顿法二次收敛的特性，而对初始点的选取并没有苛刻的要求。选取并没有苛刻的要求。*32（2 2）阻尼牛顿法的计算步骤）阻尼牛顿法的计算步骤1 1）给定初始点）给定初始点 ，收敛精度，收敛精度 ，置，置 2 2）计算）计算 3 3）求）求 4 4）检查收敛精度。若）检查收敛精度。若，则，则 ，停机；，停机；否则置否则置 返回到返回到2 2），继续进行搜索。），继续进行搜索。*33（3）阻尼牛顿法的阻尼牛顿法的 程序框图程序框图*34v1、原始牛顿法和阻尼牛顿法统称为牛顿、原始牛顿法和阻尼牛顿法统称为牛顿型方法。牛顿法是型方法。牛顿法是二次收
23、敛的，收敛速度二次收敛的，收敛速度较快较快；v2、这类方法的主要缺点、这类方法的主要缺点计算复杂，工作计算复杂，工作量大，要求计算机存储量大：量大，要求计算机存储量大：1）每次迭代都要计算函数的海赛矩阵，并对）每次迭代都要计算函数的海赛矩阵，并对该矩阵求逆，工作量非常大。该矩阵求逆，工作量非常大。2）从计算机存储方面考虑，牛顿型方法所需）从计算机存储方面考虑，牛顿型方法所需的存储量也很大。一般计算量和存储量以的存储量也很大。一般计算量和存储量以n2比例增长。比例增长。牛顿法小结牛顿法小结*35v基于以下两方面的原因，基于以下两方面的原因，给牛顿法的运用给牛顿法的运用带来一定局限性带来一定局限性
24、使用条件苛刻，对于二阶不可微的使用条件苛刻，对于二阶不可微的f f(X X)也不也不适用。适用。若迭代点的海赛矩阵为奇异，则无法求若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向逆矩阵，不能构造牛顿法方向；为了保证牛顿方向是目标函数下降方向，海为了保证牛顿方向是目标函数下降方向，海赛矩阵的逆阵必须正定；赛矩阵的逆阵必须正定；*36函数只有在函数极值点附近，才能很接近一个函数只有在函数极值点附近，才能很接近一个二次函数，在此范围之外用二次函数近似代替二次函数，在此范围之外用二次函数近似代替原目标函数，误差较大，并不能保证迭代一次原目标函数，误差较大，并不能保证迭代一次就达到极小点。就
25、达到极小点。对于非二次函数，采用牛顿法时初始点不能任对于非二次函数，采用牛顿法时初始点不能任取，取，初始点应选在初始点应选在X X*附近附近，有一定难度而是要，有一定难度而是要求离极小点较近。否则，可能不收敛或收敛到求离极小点较近。否则，可能不收敛或收敛到非极小点。非极小点。虽然阻尼牛顿法有上述缺点，但在特定条件下虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。了思路和理论依据。*37梯度法与牛顿法的比较梯度法与牛顿法的比较一般迭代式：一般迭代式：梯度法：梯度法：牛顿法：牛顿法：阻尼牛顿法：阻尼牛顿法：*
26、38 设设G为为nxn阶实对称正定矩阵，如果有两个阶实对称正定矩阵，如果有两个n维向量维向量 和和 满足满足 ，则称向量，则称向量 与与 关于矩阵关于矩阵 G共轭，或称他们是共轭，或称他们是G的共轭方向。的共轭方向。当当G为单位矩阵时，为单位矩阵时，共轭方向的概念是在研究二次函数共轭方向的概念是在研究二次函数当当 为对称正定矩阵时引出的使搜索方向直指极小点。为对称正定矩阵时引出的使搜索方向直指极小点。为了克服最速下降法的锯齿现象，提高收敛速度，发展为了克服最速下降法的锯齿现象，提高收敛速度，发展了一类共轭方向法。搜索方向是共轭方向。即将相邻两次了一类共轭方向法。搜索方向是共轭方向。即将相邻两次
27、搜索方向由正交变为共轭。搜索方向由正交变为共轭。q1 1、共轭方向的概念、共轭方向的概念*39 首先考虑二维情况，首先考虑二维情况，如果按最速下降法，选择负梯度方如果按最速下降法，选择负梯度方向为搜索方向，会产生锯齿现象。向为搜索方向，会产生锯齿现象。为避免锯齿的发生，取下一次的迭代搜索方向直接指向为避免锯齿的发生，取下一次的迭代搜索方向直接指向极小点，如果选定这样的搜索方向，对于二元二次函数只极小点，如果选定这样的搜索方向，对于二元二次函数只需进行两次需进行两次d d0 0、d d1 1直线搜索就可以求到极小点。直线搜索就可以求到极小点。如果能选定这样的方向，则只如果能选定这样的方向，则只需
28、两步搜索得到极小点，即需两步搜索得到极小点，即*40结论结论：两个向量两个向量，对对是是共共轭轭向量向量。应满足什么条件？应满足什么条件？对于二次函数对于二次函数 在在 处取得极小点的必要条件处取得极小点的必要条件等式两边同左乘等式两边同左乘 得：得：和和 称为对称为对G的的共轭方向共轭方向。*41q2 2、共轭方向的性质、共轭方向的性质性性质质1 1 若若非非零零向向量量系系d0,d1,d2,dm-1是是对对G共共轭轭，则这则这m个向量是线性无关的。个向量是线性无关的。性质性质2 2 在在n维空间中互相共轭的非零向量的个数维空间中互相共轭的非零向量的个数不超过不超过n。性质性质3 3 从任意
29、初始点出发，顺次沿从任意初始点出发，顺次沿n个个G的共轭方的共轭方向向d0,d1,d2,进行一维搜索，最多经过进行一维搜索，最多经过n次迭代次迭代就可以找到的二次函数就可以找到的二次函数f(x)极小点。极小点。说明这种迭代说明这种迭代方法具有二次收敛性。方法具有二次收敛性。*42 1 1、共轭方向法的步骤、共轭方向法的步骤（1 1）选定初始点）选定初始点，下降方向，下降方向 和收敛精度和收敛精度，置，置（2 2）沿）沿 方向进行一维搜索，得方向进行一维搜索，得（3 3）判断）判断 是否满足，若满足则打印是否满足，若满足则打印 ，停机，否则转停机，否则转4 4）。）。（4 4）提供新的共轭方向）
30、提供新的共轭方向，使，使（5 5）置）置，转，转2 2）。）。q3 3、共轭方向法共轭方向法*432、共轭方向法程序框图、共轭方向法程序框图提供新的共轭方向使*443 3、格拉姆、格拉姆斯密特向量系共轭化法（共轭方向的确定）斯密特向量系共轭化法（共轭方向的确定）1 1、选定线性无关向量系、选定线性无关向量系 ，如，如n n个坐标轴的单个坐标轴的单位向量位向量；2 2、取、取 ，令，令 ，根据共，根据共轭轭条件得条件得3 3、递推可得：、递推可得：*45v例题求 的一组共轭向量组 。解：选三个坐标轴上的单位向量 作为一组线性无关向量组，即*46取设 则有*47故有设则有*48且故有经过验算有 故
31、 对 共轭。*49共轭方向法是二次收敛的；共轭方向法是二次收敛的；由于由于n维设计空间中最多只能有维设计空间中最多只能有n个线性无关的向量，所以个线性无关的向量，所以n维维优化问题的共轭方向最多只有优化问题的共轭方向最多只有n个，因此，用共轭方向法进行个，因此，用共轭方向法进行n步搜索后，若仍不能满足精度要求，继续产生共轭方向进行步搜索后，若仍不能满足精度要求，继续产生共轭方向进行迭代搜索就是没有意义的或效果很差。迭代搜索就是没有意义的或效果很差。而是令而是令 ，重新构造，重新构造n个共轭方向，开始新个共轭方向，开始新一轮的共轭方向法搜索，这样处理一般效果较好。一轮的共轭方向法搜索，这样处理一
32、般效果较好。*501 1、共轭梯度法是共轭方向法中的一种，该方法中每一个共、共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖与迭代点处的负梯度而构造出来。轭向量都是依赖与迭代点处的负梯度而构造出来。对对于二次函数于二次函数从点从点 出发，沿出发，沿G某一共轭方向某一共轭方向 作一维搜索作一维搜索,到达到达而在点而在点 、处的梯度分别为：处的梯度分别为：*51 点处的梯度点处的梯度 若若 和和对对G是共轭方向，则：是共轭方向，则：其中：其中：*52 得出共轭方向与梯度之间的关系。此式表明沿方向得出共轭方向与梯度之间的关系。此式表明沿方向进行一维搜索，其终点进行一维搜索，其终点 与始
33、点与始点 的梯度值差的梯度值差与与 的共轭方向的共轭方向 正交。正交。结论：结论：因此，共轭梯度法可以利用这个性质做到不必计算矩阵因此，共轭梯度法可以利用这个性质做到不必计算矩阵G 就能求共轭方向。就能求共轭方向。*532 2、共轭梯度法计算原理、共轭梯度法计算原理从从 出发，沿负梯度方向作一维搜索：出发，沿负梯度方向作一维搜索：设与设与 共轭的下一个方向共轭的下一个方向 是由是由 和点和点 的负梯的负梯度的线性组合构成，即：度的线性组合构成，即：共轭条件（与梯度的关系）：共轭条件（与梯度的关系）：将式（将式（1 1）代入（）代入（2 2）得：）得：（1 1）（2 2）*54因此可得共轭方向的
34、递推公式：因此可得共轭方向的递推公式：*553 3、共轭梯度法计算过程、共轭梯度法计算过程 （1 1）设初始点）设初始点 计算计算X1点处的梯度点处的梯度 。（2 2）求）求 的共轭方向的共轭方向d d1 1，作为下一步的搜索方向。把作为下一步的搜索方向。把d d1 1取成取成-g-g1 1与与d d0 0两个方向的线性组合两个方向的线性组合计算该点梯度计算该点梯度*56（3 3）在）在 g g0 0、g g1 1、g g2 2所构成的正交系中，求与所构成的正交系中，求与d d0 0及及d d1 1均共轭均共轭的方向的方向d d2 2。设设 式中式中 待定系数。待定系数。因为要求因为要求d d
35、2 2与与d d0 0和和d d1 1均共轭，根据共轭方向与梯度均共轭，根据共轭方向与梯度的关系，的关系，考虑到考虑到g g0 0、g g1 1、g g2 2相互正交，从而有相互正交，从而有*57设设 ，得，得因此因此从而得出从而得出*58 再沿再沿d2方向继续进行一维搜索，如此继续下去可方向继续进行一维搜索，如此继续下去可求得共轭方向的递推公式为求得共轭方向的递推公式为 沿着这些共轭方向一直搜索下去，直到最后迭代沿着这些共轭方向一直搜索下去，直到最后迭代点处梯度的模小于给定允许值为止。点处梯度的模小于给定允许值为止。v若目标函数为非二次函数，经若目标函数为非二次函数，经 n 次搜索还未达到最
36、优次搜索还未达到最优点时，则以最后得到的点作为初始点，重新计算共轭方点时，则以最后得到的点作为初始点，重新计算共轭方向，一直到满足精度要求为止。向，一直到满足精度要求为止。*594 4、共轭梯度法、共轭梯度法 程序框图程序框图*60，已知初始点，已知初始点1,11,1T Tl解：解：1）第一次沿负梯度方向搜寻）第一次沿负梯度方向搜寻l计算初始点处的梯度计算初始点处的梯度为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足l迭代精度迭代精度 。例题例题 4-4 求下列问题的极值求下列问题的极值*61得得:2）第二次迭代：）第二次迭代：代入目标函数代入目标函数*62得得因因收敛。收敛。由由从而有：
37、从而有：*63v方法讨论方法讨论从共轭梯度法的计算过程可以看出，第一个搜索从共轭梯度法的计算过程可以看出，第一个搜索方向取作负梯度方向，这就是最速下降法。其余方向取作负梯度方向，这就是最速下降法。其余各步的搜索方向是将负梯度偏转一个角度，也就各步的搜索方向是将负梯度偏转一个角度，也就是对负梯度进行修正。所以共轭梯度法实质上是是对负梯度进行修正。所以共轭梯度法实质上是对最速下降法进行的一种改进对最速下降法进行的一种改进，故它又被称作故它又被称作旋旋转梯度法转梯度法。*64共轭梯度法的优点是程序简单，存储量少，共轭梯度法的优点是程序简单，存储量少，具有最速下降法的优点，在收敛速度上比最具有最速下降
38、法的优点，在收敛速度上比最速下降法快，具有二次收敛性。速下降法快，具有二次收敛性。共轭方向的形成只与迭代点的梯度有关，与共轭方向的形成只与迭代点的梯度有关，与牛顿法相比，避免了求海赛矩阵及其逆阵的牛顿法相比，避免了求海赛矩阵及其逆阵的计算，大大减少了计算工作量。计算，大大减少了计算工作量。对于对于N维二次函数，最多经过维二次函数，最多经过n次迭代可收敛到极小点。次迭代可收敛到极小点。若为非二次函数，则如在迭代若为非二次函数，则如在迭代n次后得到的次后得到的Xn不是极小不是极小点，就应令点，就应令 ,，重新构造，重新构造n个共轭方个共轭方向，重复以上迭代过程。向，重复以上迭代过程。*65 DFP
39、变尺度法首先有戴维顿（变尺度法首先有戴维顿（Davidon）于）于1959年提出，又于年提出，又于1963年由弗莱彻（年由弗莱彻（Fletcher）和）和鲍维尔加以发展和完善，成为现代公认的较好的算鲍维尔加以发展和完善，成为现代公认的较好的算法之一。法之一。DFP法是基于牛顿法的思想又作了重要改进。法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。收敛速度。*66能否克服各自的缺点，综合发挥其优点？能否克服各自的缺点，综
40、合发挥其优点？2 2）阻尼牛顿法）阻尼牛顿法1 1）梯度法）梯度法*梯度法构造简单，只用到一阶偏导数，计算量小，初梯度法构造简单，只用到一阶偏导数，计算量小，初始点可任选，且开始几次迭代，目标函数值下降很快；始点可任选，且开始几次迭代，目标函数值下降很快；其主要缺点是迭代点接近其主要缺点是迭代点接近X*X*时，即使对二次正定函数收时，即使对二次正定函数收敛也非常慢。敛也非常慢。*牛顿法收敛很快，对于二次函数只需迭代一次便牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆阵，对维数较高
41、的但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。优化问题，其计算工作和存储量都太大。q1、问题的提出、问题的提出*67 对于一般函数对于一般函数 ，当用牛顿法寻求极小点时，当用牛顿法寻求极小点时，其牛顿迭代公式为：其牛顿迭代公式为：其中：其中：为了避免迭代公式中计算海赛矩阵的逆阵，用对称正为了避免迭代公式中计算海赛矩阵的逆阵，用对称正定矩阵定矩阵 近似近似 的逆，每迭代一次，尺度就的逆，每迭代一次，尺度就改变一次。而改变一次。而 的产生从给定的产生从给定 开始逐步修整得开始逐步修整得到。到。q2、变尺度法的基本思想、变尺度法的基本思想*68 变量的尺度变换是放
42、大或缩小各个坐标。通过变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降低到最低限度。尺度变换可以把函数的偏心程度降低到最低限度。尺度变换技巧能显著地改进几乎所有极小化方法尺度变换技巧能显著地改进几乎所有极小化方法的收敛性质。的收敛性质。例如在用最速下降法求例如在用最速下降法求 的极小的极小值时值时,需要进行需要进行10次迭代才能达到极小点次迭代才能达到极小点如作变换如作变换 y1=x1,y2=5x2把把 x2的尺度放大的尺度放大5倍，则目标函数等值线由一簇椭圆变成倍，则目标函数等值线由一簇椭圆变成一簇同心圆。一簇同心圆。消除了函数的偏心，用最速下降法只需一次迭代即可求得消
43、除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。极小点。q3、尺度矩阵的概念、尺度矩阵的概念*69对于一般二次函数对于一般二次函数 如果进行尺度变化如果进行尺度变化若矩阵若矩阵 是正定的，则总存在矩阵是正定的，则总存在矩阵 使使 目的：减少二次项的偏心目的：减少二次项的偏心 用矩阵用矩阵Q Q-1-1右乘等式右乘等式(1)(1)两边，得：两边，得：用矩阵用矩阵Q左乘等式左乘等式(2)两边，得：两边，得：(2)函数偏心度为函数偏心度为0*70所以所以 上式说明：上式说明：二次函数矩阵二次函数矩阵G的逆阵，可以通过尺度变换的逆阵，可以通过尺度变换矩阵矩阵Q来求得。来求得。-变尺度矩阵变尺度
44、矩阵牛顿迭代法公式变为：牛顿迭代法公式变为：*71牛顿迭代公式：牛顿迭代公式：记：记：搜索方向：搜索方向：迭代公式：迭代公式：-变尺度矩阵变尺度矩阵*72如在前面例子中如在前面例子中如取如取其中其中则在变换则在变换 后的坐标系中，矩阵后的坐标系中，矩阵G变为变为*73*74*75v那么牛顿型方法就可看成是经过尺度变换后的那么牛顿型方法就可看成是经过尺度变换后的最速下降法。经过尺度变换，使函数的偏心率最速下降法。经过尺度变换，使函数的偏心率减小到零，函数的等值面变为球面（或超球面）减小到零，函数的等值面变为球面（或超球面），使设计空间中任意点处函数的梯度都通过极，使设计空间中任意点处函数的梯度都
45、通过极小点，从而用最速下降法只需一次迭代就可达小点，从而用最速下降法只需一次迭代就可达到极小点。到极小点。v这就是对变换前的二次函数，在使用牛顿方法这就是对变换前的二次函数，在使用牛顿方法时，由于其牛顿方向直接指向极小点，因此只时，由于其牛顿方向直接指向极小点，因此只需一次迭代就能找到极小点的原因所在。需一次迭代就能找到极小点的原因所在。*76q4、变尺度矩阵的建立、变尺度矩阵的建立对于一般函数对于一般函数 ，当用牛顿法寻求极小点时，当用牛顿法寻求极小点时，其牛顿迭代公式为其牛顿迭代公式为 其中其中为了避免在迭代公式中计算海赛矩阵的逆为了避免在迭代公式中计算海赛矩阵的逆阵阵 ，可用在迭代中逐步
46、建立的变尺度矩阵，可用在迭代中逐步建立的变尺度矩阵 来替换来替换 ，即构造一个矩阵序列，即构造一个矩阵序列 来来逼近海赛逆矩阵序列逼近海赛逆矩阵序列 。每迭代一次，尺度。每迭代一次，尺度就改变一次，就改变一次，这正是这正是“变尺度变尺度”的含义的含义。*77为了使变尺度矩阵为了使变尺度矩阵 确实与确实与 Gk-1 近似，并具有近似，并具有容易计算的特点，必须对容易计算的特点，必须对 附加某些条件。附加某些条件。1.为保证迭代公式具有下降性质，要求为保证迭代公式具有下降性质，要求 中的每一个中的每一个矩阵都是对称正定的。矩阵都是对称正定的。因为若要求搜索方向因为若要求搜索方向 为下降方向，即为下
47、降方向，即要求要求 ，也就是，也就是 ，这样，这样 ，即，即 应为对称正定。应为对称正定。2.要求要求 之间的迭代具有简单的形式。之间的迭代具有简单的形式。显然显然Hk+1=Hk+Ek为最简单的形式，其中为最简单的形式，其中Ek 为校正矩为校正矩阵。上式称作校正公式。阵。上式称作校正公式。变尺度矩阵应满足的条件变尺度矩阵应满足的条件*783.3.要求要求 Hk 必须满足拟牛顿条件。必须满足拟牛顿条件。设迭代过程已进行到设迭代过程已进行到k+1步，步，xk+1,gk+1均已求出。对均已求出。对于具有正定矩阵于具有正定矩阵G的二次函数，的二次函数，可以求得可以求得即即而对具有正定海赛矩阵而对具有正
48、定海赛矩阵Gk+1的一般函数，在极小点的一般函数，在极小点附近可用二次函数很好地近似，所以考虑到如果迫附近可用二次函数很好地近似，所以考虑到如果迫使使Hk+1满足类似于上式的关系满足类似于上式的关系那么那么Hk就可以很好地近似于就可以很好地近似于 。因此，把上面的关。因此，把上面的关系式称作拟牛顿条件（或拟牛顿方程）。系式称作拟牛顿条件（或拟牛顿方程）。*79 v为简便起见，令为简便起见，令则拟牛顿条件可写成则拟牛顿条件可写成v根据上述拟牛顿条件，根据上述拟牛顿条件，不通过海赛矩阵求逆就可以构造不通过海赛矩阵求逆就可以构造一个矩阵一个矩阵Hk+1来逼近海赛矩阵的逆阵，这类方法统称作来逼近海赛矩
49、阵的逆阵，这类方法统称作拟牛顿法。拟牛顿法。v由于变尺度矩阵的建立应用了拟牛顿条件，所以变尺度由于变尺度矩阵的建立应用了拟牛顿条件，所以变尺度法属于拟牛顿法的一种。法属于拟牛顿法的一种。v变尺度法对于具有正定矩阵变尺度法对于具有正定矩阵G的二次函数，能产生对的二次函数，能产生对G共轭的搜索方向，共轭的搜索方向，因此变尺度法可以看成是一种共轭方因此变尺度法可以看成是一种共轭方向法。向法。拟牛顿条件拟牛顿条件*80（1 1）选定初始点）选定初始点 和收敛精度和收敛精度 ；（2 2）计算）计算 ，选取初始对称正定矩阵，选取初始对称正定矩阵 ，置置 ；（3 3）计算搜索方向）计算搜索方向 ；（4 4）
50、沿）沿 方向进行一维搜索方向进行一维搜索 ，计算，计算（5 5）判断是否满足迭代终止准则，若满足则）判断是否满足迭代终止准则，若满足则 ，停机，否则停机，否则6 6）；）；（6 6）当迭代）当迭代 次后还没有找到极小点时次后还没有找到极小点时,重置重置 为单位矩阵为单位矩阵 并以当前设计点位初始点并以当前设计点位初始点 ；（7 7）计算矩阵）计算矩阵，置，置，返回到，返回到3 3。q5、变尺度法的一般步骤、变尺度法的一般步骤*81v对于校正矩阵对于校正矩阵Ek，可由具体的公式来计算，可由具体的公式来计算，不同的公式对应不同的变尺度法。但不论哪不同的公式对应不同的变尺度法。但不论哪种变尺度法，种