机械优化设计第四章无约束优化方法第四章无约束优化方法一、概述一、概述二、最速下降法（梯度法）二、最速下降法（梯度法）三、牛顿型方法（牛顿法和阻尼牛顿法）三、牛顿型方法（牛顿法和阻尼牛顿法）四、共轭方向和共轭方向法四、共轭方向和共轭方向法五、共轭梯度法五、共轭梯度法六、变尺度法六、变尺度法七、坐标轮换法七、坐标轮换法Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计 实际中的工程问题大都是在一定限制条件下追求实际中的工程问题大都是在一定限制条件下追求某一指标为最小，属于约束优化问题。某一指标为最小，属于约束优化问题。 为什么要研究无约束优化问题？为什么要研究无约束优化问题？1）有些实际问题，其数学模型本身就是一个无约束问题；）有些实际问题，其数学模型本身就是一个无约束问题；2）通过熟悉它的解法可以为研究约束优化问题打下良好的）通过熟悉它的解法可以为研究约束优化问题打下良好的基础；基础；3）约束优化问题的求解可用通过一系列无约束优化方法来）约束优化问题的求解可用通过一系列无约束优化方法来达到。达到。所以无约束优化问题的解法是所以无约束优化问题的解法是优化设计方法的基本优化设计方法的基本组成部分组成部分，也是优化方法的基础。，也是优化方法的基础。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计1 1、无约束优化问题、无约束优化问题求 维设计变量 使目标函数 ，而对 没有任何限制条件。2 2、求解方法、求解方法（1 1）利用极值条件来确定极值点的位置。）利用极值条件来确定极值点的位置。 （2 2）数值计算方法数值计算方法搜索方法搜索方法基本思想基本思想：从给定的初始点 出发，沿某一搜索方向 进行搜索，确定最佳步长 使函数值沿 下降最大。依此方式不断进行，形成迭代的下降算法：一、概述一、概述Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计3 3、算法框图、算法框图 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计4 4、无约束优化方法的分类、无约束优化方法的分类根据确定其搜索方向根据确定其搜索方向 方法不同，可分为：方法不同，可分为： （2 2）利用目标函数的一阶或二阶导数的无约束优化方法）利用目标函数的一阶或二阶导数的无约束优化方法（或称（或称间接法间接法）如：）如：最速下降法（梯度法）、共轭梯度法、最速下降法（梯度法）、共轭梯度法、牛顿法及变尺度法；牛顿法及变尺度法； 间接法间接法除了要计算目标函数值外，还要计算目标函数的除了要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵；梯度，有的还要计算其海赛矩阵；（1 1）只利用目标函数值的无约束优化方法（或称）只利用目标函数值的无约束优化方法（或称直接法，直接法，即不使用导数信息），如：即不使用导数信息），如：坐标轮换法、单形替换法及鲍威坐标轮换法、单形替换法及鲍威（PowellPowell）法。）法。 直接法直接法不必求函数导数，只计算目标函数值。适用于求不必求函数导数，只计算目标函数值。适用于求解变量个数较少（小于解变量个数较少（小于2020）的问题，一般情况下效率较低。）的问题，一般情况下效率较低。搜索方向的构成问题是无约束优化方法的关键。搜索方向的构成问题是无约束优化方法的关键。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计二、最速下降法（梯度法）二、最速下降法（梯度法）1 1、基本思想、基本思想 函数的负梯度方向是函数值在该点下降最快的方向。函数的负梯度方向是函数值在该点下降最快的方向。将将n n维问题转化为一系列维问题转化为一系列沿负梯度方向沿负梯度方向用一维搜索方法寻用一维搜索方法寻优的问题，即利用负梯度作为搜索方向，故称为最速下降优的问题，即利用负梯度作为搜索方向，故称为最速下降法或梯度法。法或梯度法。 搜索方向取该点的负梯度方向即搜索方向取该点的负梯度方向即 ，使函，使函数值在该点附近的范围内下降最快。数值在该点附近的范围内下降最快。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计2 2、最速下降法的原理、最速下降法的原理（1 1）使）使 ，按此规律不断走步，形成迭代算法：按此规律不断走步，形成迭代算法： （2 2）其步长因子）其步长因子 取一维搜索的取一维搜索的最佳步长最佳步长，即，即 根据一元函数极值的必要条件和多元复合函数求导公根据一元函数极值的必要条件和多元复合函数求导公式，得式，得或或Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计 由此可知，在最速下降由此可知，在最速下降法中，相邻两个迭代点上法中，相邻两个迭代点上的函数梯度相互垂直。而的函数梯度相互垂直。而搜索方向就是负梯度方向，搜索方向就是负梯度方向，因此相邻两个搜索方向互因此相邻两个搜索方向互相垂直相垂直。这就是说在迭代。这就是说在迭代点向函数极小点靠近的过点向函数极小点靠近的过程，走的是曲折的路线，程，走的是曲折的路线，形成形成“之之”字形的锯齿现字形的锯齿现象，而且越接近极小点锯象，而且越接近极小点锯齿越细。齿越细。最速下降法的搜索路径最速下降法的搜索路径函数梯度为局部性质，因此并非函数梯度为局部性质，因此并非“最快最快”。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计梯度法的迭代历程梯度法的迭代历程Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计方法特点方法特点1 1）初始点可任选，每次迭代计算量小，存储量少，）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点；近局部极小点；2 2）任意相邻两点的搜索方向是正交的，它的迭代）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。步长变得很小，越走越慢。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计最最速速下下降降法法的的程程序序框框图图Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计例：例：求目标函数求目标函数 的极小点的极小点解法解法1 1：取初始点取初始点 ，则初始点处的函数值，则初始点处的函数值及梯度分别为：及梯度分别为：为一维搜索最佳步长，应满足极值必要条件为一维搜索最佳步长，应满足极值必要条件Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计则第一次迭代设计点位置和函数值则第一次迭代设计点位置和函数值经过经过1010次迭代后，得到最优解：次迭代后，得到最优解： 该问题的目标函数的等值线为一族椭圆，迭代该问题的目标函数的等值线为一族椭圆，迭代点走的是一段锯齿形路线。点走的是一段锯齿形路线。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计解法解法2 2：引入变化引入变化 ，则目标函数则目标函数 变为变为 ，经过坐标（尺度）变化后，只需要经过一次迭代，就可找到经过坐标（尺度）变化后，只需要经过一次迭代，就可找到最优解：最优解：Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计不同等值线的迭代过程不同等值线的迭代过程Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计讨论 可以看出二者的对角形矩阵不同，前者的可以看出二者的对角形矩阵不同，前者的等值线为一族椭圆，后者的等值线为一族同心等值线为一族椭圆，后者的等值线为一族同心圆，这说明圆，这说明对角形矩阵是表示度量的矩阵或者对角形矩阵是表示度量的矩阵或者是表示尺度的矩阵是表示尺度的矩阵，最速下降法的收敛速度和，最速下降法的收敛速度和变量的尺度有很大关系。变量的尺度有很大关系。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计3 3、最速下降法收敛速度的估计式、最速下降法收敛速度的估计式的海赛矩阵最大特征值上界的海赛矩阵最大特征值上界 的海赛矩阵最小特征值下界的海赛矩阵最小特征值下界 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计梯度法的特点：梯度法的特点：（1 1）理论明确，程序简单，对初始点要求不严格；）理论明确，程序简单，对初始点要求不严格；（2 2）对一般函数而言，梯度法的收敛速度并不快，）对一般函数而言，梯度法的收敛速度并不快，因为最速下降法仅仅是指某点的一个因为最速下降法仅仅是指某点的一个局部性质局部性质；（3 3）梯度法相邻两次搜索方向的正交性决定了迭代）梯度法相邻两次搜索方向的正交性决定了迭代全过程的全过程的搜索路径呈锯齿形搜索路径呈锯齿形，在远离极小点时逼近速，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢；度较快，而在接近极小点时逼近速度较慢；（4 4）梯度法的）梯度法的收敛速度与目标函数的性质密切相关收敛速度与目标函数的性质密切相关。对于等值线（面）为同心圆（球）的目标函数，一次对于等值线（面）为同心圆（球）的目标函数，一次搜索即可达到极小点。搜索即可达到极小点。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计三、牛顿型方法三、牛顿型方法基本思想：基本思想：在在 领域内用一个二次函数领域内用一个二次函数 来近似来近似代替原目标函数，并将代替原目标函数，并将 的极小值作为目标函数的极小值作为目标函数 求优的下一个迭代点求优的下一个迭代点 。经多次迭代，使之逼近目标。经多次迭代，使之逼近目标函数函数 的极小点。的极小点。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计对于多元函数对于多元函数 ，设，设 为为 极小点极小点 的第一的第一个近似点，个近似点，泰勒展开，保留到二次项，得泰勒展开，保留到二次项，得: :设设 为为 的极小点，它作为的极小点，它作为 极小点极小点 的下一个近似点，根据极值必要条件：的下一个近似点，根据极值必要条件：即即 海赛矩阵海赛矩阵 1 1、牛顿法、牛顿法对于二次函数，海赛矩阵是常矩阵，故从任何点出发，只需一步可找到对于二次函数，海赛矩阵是常矩阵，故从任何点出发，只需一步可找到极小点。极小点。-多元函数求极值的多元函数求极值的牛顿法迭代公式。牛顿法迭代公式。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计例例: :用牛顿法求用牛顿法求 的极小值的极小值 解解：取初始点取初始点 ，则，则 代入牛顿法迭代公式可得代入牛顿法迭代公式可得: :从而经过一次迭代即求得极小点和函数极小值。从而经过一次迭代即求得极小点和函数极小值。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计2 2、阻尼牛顿法、阻尼牛顿法 把把 看作一个搜索方向，看作一个搜索方向，称其为牛顿方向，称其为牛顿方向，则阻尼牛顿法的迭代公式为则阻尼牛顿法的迭代公式为：阻尼因子，即沿牛顿方向进行一维搜索的最佳步长，阻尼因子，即沿牛顿方向进行一维搜索的最佳步长，可通过如下极小化过程求得：可通过如下极小化过程求得： （1 1）阻尼牛顿法的迭代公式）阻尼牛顿法的迭代公式 在牛顿法中，迭代点的位置是按照极值条件确定，并未在牛顿法中，迭代点的位置是按照极值条件确定，并未含有沿下降方向搜寻的概念，因此采用牛顿迭代公式，对含有沿下降方向搜寻的概念，因此采用牛顿迭代公式，对于非二次函数，有时会使函数值上升。于非二次函数，有时会使函数值上升。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计（2 2）阻尼牛顿法的计算步骤）阻尼牛顿法的计算步骤1 1）给定初始点）给定初始点 ，收敛精度，收敛精度 ，置，置 2 2）计算）计算 3 3）求）求 4 4）检查收敛精度。若）检查收敛精度。若 ，则，则 ，停机；，停机； 否则置否则置 返回到返回到2 2），继续进行搜索。），继续进行搜索。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计（3）阻尼牛顿法的阻尼牛顿法的 程序框图程序框图 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计方法特点：方法特点：1 1）初始点应选在极小点附近，有一定难度；）初始点应选在极小点附近，有一定难度；2 2）尽管每次迭代都不会是函数上升，但不能保证每次）尽管每次迭代都不会是函数上升，但不能保证每次都下降；都下降；3 3）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；能构造牛顿法方向；4 4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外对于二阶不可微函数也不适用。算量和存储量大。此外对于二阶不可微函数也不适用。 虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，可为其他算法提供思路和理论依据。敛最快的优点，可为其他算法提供思路和理论依据。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计梯度法与牛顿法的比较梯度法与牛顿法的比较一般迭代式：一般迭代式：梯度法：梯度法：牛顿法：牛顿法：阻尼牛顿法：阻尼牛顿法：Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计四、共轭方向和共轭方向法四、共轭方向和共轭方向法（一）（一）共轭方向共轭方向的概念的概念 设设G为为nxn阶实对称正定矩阵，如果有两个阶实对称正定矩阵，如果有两个n维向量维向量 和和 满足满足 ，则称向量，则称向量 与与 关于矩阵关于矩阵 G共轭，或称他们是共轭，或称他们是G的共轭方向。的共轭方向。当当G为单位矩阵时，为单位矩阵时，共轭方向的概念是在研究二次函数共轭方向的概念是在研究二次函数当当 为对称正定矩阵时引出的使搜索方向直指极小点。为对称正定矩阵时引出的使搜索方向直指极小点。 为了克服最速下降法的锯齿现象，提高收敛速度，发展了为了克服最速下降法的锯齿现象，提高收敛速度，发展了一类共轭方向法。搜索方向是共轭方向。即将相邻两次搜一类共轭方向法。搜索方向是共轭方向。即将相邻两次搜索方向由正交变为共轭。索方向由正交变为共轭。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计 首先考虑二维情况，首先考虑二维情况，如果按最速下降法，选择负梯度方如果按最速下降法，选择负梯度方向为搜索方向，会产生锯齿现象。向为搜索方向，会产生锯齿现象。 为避免锯齿的发生，取下一次的迭代搜索方向直接指向为避免锯齿的发生，取下一次的迭代搜索方向直接指向极小点，如果选定这样的搜索方向，对于二元二次函数只极小点，如果选定这样的搜索方向，对于二元二次函数只需进行两次直线搜索就可以求到极小点。需进行两次直线搜索就可以求到极小点。如果能选定这样的方向，则只如果能选定这样的方向，则只需两步搜索得到极小点，即需两步搜索得到极小点，即Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计结论：两个向量两个向量 ，对是是共共轭向量向量。应满足什么条件？应满足什么条件？对于二次函数对于二次函数 在在 处取得极小点的必要条件处取得极小点的必要条件等式两边同左乘等式两边同左乘 得：得：和和 称为对称为对G的的共轭方向共轭方向。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计（三）共轭方向法（三）共轭方向法 1 1、共轭方向法的步骤、共轭方向法的步骤（1 1）选定初始点）选定初始点 ，下降方向，下降方向 和收敛精度和收敛精度 ，置，置 （2 2）沿）沿 方向进行一维搜索，得方向进行一维搜索，得 （3 3）判断）判断 是否满足，若满足则打印是否满足，若满足则打印 ， 停机，否则转停机，否则转4 4）。）。（4 4）提供新的共轭方向）提供新的共轭方向 ，使，使 （5 5）置）置 ，转，转2 2）。）。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计2、共轭方向法、共轭方向法 程序框图程序框图Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计3 3、格拉姆、格拉姆斯密特向量系共轭化法（共轭方向的确定）斯密特向量系共轭化法（共轭方向的确定） 1 1、选定线性无关向量系、选定线性无关向量系 ，如，如n n个坐标轴的单个坐标轴的单位向量位向量；2 2、取、取 ，令，令 ，根据共，根据共轭条件得条件得3 3、递推可得：、递推可得：Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计五、共轭梯度法五、共轭梯度法1 1、共轭梯度法是共轭方向法中的一种，该方法中每一个共、共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖与迭代点处的负梯度而构造出来。轭向量都是依赖与迭代点处的负梯度而构造出来。对于二次函数于二次函数从点从点 出发，沿出发，沿G某一共轭方向某一共轭方向 作一维搜索作一维搜索,到达到达而在点而在点 、 处的梯度分别为：处的梯度分别为：Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计 点处的梯度点处的梯度 若若 和和对对G是共轭方向，则：是共轭方向，则：其中：其中： Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计 得出共轭方向与梯度之间的关系。此式表明沿方向得出共轭方向与梯度之间的关系。此式表明沿方向进行一维搜索，其终点进行一维搜索，其终点 与始点与始点 的梯度值差的梯度值差与与 的共轭方向的共轭方向 正交。正交。结论：结论：Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计2 2、共轭梯度法计算原理、共轭梯度法计算原理从从 出发，沿负梯度方向作一维搜索：出发，沿负梯度方向作一维搜索：设与设与 共轭的下一个方向共轭的下一个方向 是由是由 和点和点 的负梯的负梯度的线性组合构成，即：度的线性组合构成，即：共轭条件（与梯度的关系）：共轭条件（与梯度的关系）：将式（将式（1 1）代入（）代入（2 2）得：）得：（1 1）（2 2）Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计因此可得共轭方向的递推公式：因此可得共轭方向的递推公式：Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计3 3、共轭梯度法计算过程、共轭梯度法计算过程 （1 1）设初始点）设初始点 计算计算（2 2）求）求 的共轭方向的共轭方向 计算计算（3 3）求与）求与 和和 均共轭的方向均共轭的方向 （4 4）再沿）再沿 方向进行一维搜索，如此继续下去，方向进行一维搜索，如此继续下去， 可求得共轭方向的递推公式为：可求得共轭方向的递推公式为： Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计4 4、共轭梯度法、共轭梯度法 程序框图程序框图Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计六、变尺度法六、变尺度法1 1、问题的提出、问题的提出能否克服各自的缺点，综合发挥其优点？能否克服各自的缺点，综合发挥其优点？2 2）阻尼牛顿法）阻尼牛顿法1 1）梯度法）梯度法* * 简单，开始时目标函数值下降较快，但越来越慢。简单，开始时目标函数值下降较快，但越来越慢。* * 目标函数值在最优点附近时收敛快，但要用到二目标函数值在最优点附近时收敛快，但要用到二阶导数和矩阵求逆。阶导数和矩阵求逆。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计2 2、变尺度法的基本思想、变尺度法的基本思想 对于一般函数对于一般函数 ，当用牛顿法寻求极小点时，当用牛顿法寻求极小点时， 其牛顿迭代公式为：其牛顿迭代公式为： 其中：其中： 为了避免迭代公式中计算海赛矩阵的逆阵，用对为了避免迭代公式中计算海赛矩阵的逆阵，用对称正定矩阵称正定矩阵 近似近似 的逆，每迭代一次，尺度的逆，每迭代一次，尺度就改变一次。而就改变一次。而 的产生从给定的产生从给定 开始逐步修整开始逐步修整得到。得到。 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计3 3、尺度矩阵的概念、尺度矩阵的概念对于一般二次函数对于一般二次函数 如进行尺度变化如进行尺度变化若矩阵若矩阵 是正定的，则总存在矩阵是正定的，则总存在矩阵 使使 可得可得 牛顿迭代法公式变为：牛顿迭代法公式变为： 牛顿法可以看成经过尺度变化后的梯度法牛顿法可以看成经过尺度变化后的梯度法 -尺度矩阵尺度矩阵 变量的尺度变换是放大或缩小各个坐标。变量的尺度变换是放大或缩小各个坐标。通过尺度变通过尺度变换可以把函数的偏心程度降低到最低限度。换可以把函数的偏心程度降低到最低限度。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计是需要构造是需要构造 的一个对称方阵，的一个对称方阵，如果如果 ，则得到梯度法；，则得到梯度法；如果如果 ，则得到阻尼牛顿法；，则得到阻尼牛顿法；当矩阵当矩阵 不断地迭代而能很好地逼近不断地迭代而能很好地逼近 时，时，就可以不再需要计算二阶导数。就可以不再需要计算二阶导数。变尺度法的关键在于尺度矩阵的产生。变尺度法的关键在于尺度矩阵的产生。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计 （2 2）变尺度矩阵应满足的条件）变尺度矩阵应满足的条件 1 1）为了保证迭代公式具有下降性质，要求）为了保证迭代公式具有下降性质，要求 中的每一个矩阵都是对称正定的；中的每一个矩阵都是对称正定的；2 2）要求）要求 之间的迭代具有简单的形式：之间的迭代具有简单的形式： 3 3）要求）要求 必须满足拟牛顿条件。必须满足拟牛顿条件。 令令 拟牛顿条件拟牛顿条件即通过修正矩阵即通过修正矩阵 的不断修正，使其在迭代中不断的不断修正，使其在迭代中不断逼近逼近 。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计4 4、变尺度法的一般步骤、变尺度法的一般步骤（1 1）选定初始点）选定初始点 和收敛精度和收敛精度 ； （2 2）计算）计算 ，选取初始对称正定矩阵，选取初始对称正定矩阵 ， 置置 ； （3 3）计算搜索方向）计算搜索方向 ； （4 4）沿）沿 方向进行一维搜索方向进行一维搜索 ，计算，计算（5 5）判断是否满足迭代终止准则，若满足则）判断是否满足迭代终止准则，若满足则 ， 停机，否则停机，否则6 6）；）； （6 6）当迭代）当迭代 次后还没有找到极小点时次后还没有找到极小点时, ,重置重置 为单位矩阵为单位矩阵 并以当前设计点位初始点并以当前设计点位初始点 ；（7 7）计算矩阵）计算矩阵 ，置，置 ，返回到，返回到3 3。 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计5 5、变尺度法、变尺度法计算程序框图计算程序框图Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计5 5、DFPDFP算法算法 DFP DFP算法的计算步骤和变尺度法的一半步骤相同，只是算法的计算步骤和变尺度法的一半步骤相同，只是具体计算校正矩阵时按公式：具体计算校正矩阵时按公式： 例：用例：用DFPDFP算法求算法求 的极值解。（求解过程详见教材）的极值解。（求解过程详见教材） DFP DFP算法是由戴维顿（算法是由戴维顿（DavidonDavidon）于）于19531953年提出，又于年提出，又于19631963年由弗莱彻年由弗莱彻(Fletcher)(Fletcher)和鲍威尔加以发展，称为现代和鲍威尔加以发展，称为现代公认较好的算法之一。公认较好的算法之一。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计七、坐标轮换法七、坐标轮换法 坐标轮换法坐标轮换法是在每次搜索只允许一个变量变是在每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量（其余变量视为常量）的优化问题，转化成单变量（其余变量视为常量）的优化问题，因此又称这种方法为因此又称这种方法为变量轮换法变量轮换法。轮换过程中。轮换过程中不不需要目标函数的导数，只需要目标函数信息值需要目标函数的导数，只需要目标函数信息值。属于直接法的无约束最优化方法。属于直接法的无约束最优化方法。 此类方法适用于此类方法适用于不知道目标函数的数学表达不知道目标函数的数学表达式而仅知其目标函数值信息的情况式而仅知其目标函数值信息的情况。这也是直接。这也是直接法的一个优点。法的一个优点。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计1、坐标轮换法的寻优过程、坐标轮换法的寻优过程 （1 1）从初始点）从初始点 出发，沿第一个坐标方向搜索，即出发，沿第一个坐标方向搜索，即 ，得，得 按照一维搜索方法确定按照一维搜索方法确定最佳步长因子最佳步长因子 满足满足 （2 2）从）从 出发，沿出发，沿 方向搜索得方向搜索得 其中：步长因子其中：步长因子 满足：满足： 为一轮为一轮 终点。终点。 （3 3）检验始终点的距离是否满足）检验始终点的距离是否满足精度要求。满足结束；不满足精度要求。满足结束；不满足 ，开始新一轮。，开始新一轮。 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计结论：结论：对于对于 个变量的函数，若在第个变量的函数，若在第 轮沿第个轮沿第个 坐标坐标方向方向 进行搜索，其迭代公式为：进行搜索，其迭代公式为： 其中搜索方向取坐标方向，即其中搜索方向取坐标方向，即 若若 则则 ，否则，否则 进行下进行下 一轮搜索，一直到满足精度应要求为止。一轮搜索，一直到满足精度应要求为止。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计2 2、程序框图、程序框图 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计3 3、坐标轮换法的特点、坐标轮换法的特点（1 1）收敛效果与目标函数等值线的形状有很大关系。）收敛效果与目标函数等值线的形状有很大关系。（2 2）搜索只能轮流沿着坐标方向搜索，要经过多次）搜索只能轮流沿着坐标方向搜索，要经过多次曲折迂回的路径才能达到极小点，在极值点附近收曲折迂回的路径才能达到极小点，在极值点附近收敛速度很慢。敛速度很慢。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计八、八、 鲍威尔（鲍威尔（PowellPowell）方法）方法( (方向加速法方向加速法) ) 自学自学概述：概述：PowellPowell法是以法是以共轭方向为基础共轭方向为基础的收敛较快的收敛较快的直接法之一，是一种十分有效的算法。的直接法之一，是一种十分有效的算法。 1964 1964年，年，PowellPowell提出这种算法，其基本思想是提出这种算法，其基本思想是直接利用迭代点的目标函数值直接利用迭代点的目标函数值来构造共轭方向，来构造共轭方向，然后，从任一初始点开始，然后，从任一初始点开始，逐次沿共轭方向作一逐次沿共轭方向作一维搜索求极小点维搜索求极小点。并在以后的实践中进行了改进。并在以后的实践中进行了改进。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计对于二次函数于二次函数基本思想：基本思想：在不用在不用导数的前提下，在迭代中逐次构造数的前提下，在迭代中逐次构造G G的共的共轭方向。方向。1、共轭方向的生成、共轭方向的生成设设 为从不为从不同点出发，沿同一方同点出发，沿同一方向向 进行一维搜索进行一维搜索而得到的两个极小点。而得到的两个极小点。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计由梯度和等值面垂直的性质，由梯度和等值面垂直的性质， 和和 两点处两点处的梯度的梯度 之间存在关系：之间存在关系：另一方面，对于上述二次函数，其另一方面，对于上述二次函数，其 两点处的梯两点处的梯度可表示为：度可表示为：将两式相减可得：将两式相减可得：取方向取方向结论结论：这说明要沿：这说明要沿 方向分别对函数作两次一维搜索，方向分别对函数作两次一维搜索，得到两个极小点得到两个极小点 ，那么这两点的连线所给出的方，那么这两点的连线所给出的方向向 就是与就是与 一起对一起对G G共轭的方向。共轭的方向。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计2、基本算法（以二维情况为例）、基本算法（以二维情况为例）1）任选一初始点）任选一初始点x0，再选两个线性无关的向再选两个线性无关的向量如坐标轴的单位向量量如坐标轴的单位向量e1=1,0T和和e1=0,1e1=0,1T T本本作为初始搜索方向；作为初始搜索方向；2）从）从x0出发，顺次沿出发，顺次沿e1，e2作一维搜索，得作一维搜索，得到到 点，两点连线点，两点连线得一新方向得一新方向Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计用用d1代替代替e1形成两个线形成两个线性无关向量性无关向量d1，e2，作，作为下一轮迭代的搜索方为下一轮迭代的搜索方向。再从向。再从 出发，沿出发，沿d1 作一维搜索得点作一维搜索得点 ，作，作为下一轮迭代的初始点。为下一轮迭代的初始点。3）从）从 出发，顺次沿出发，顺次沿e2，d1作一维搜索，得作一维搜索，得到到 点，两点连线点，两点连线得一新方向得一新方向沿沿 作一维搜索得点作一维搜索得点基本迭代格式包括基本迭代格式包括共轭方向产生共轭方向产生和和方向替换方向替换两个主要步骤。两个主要步骤。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计把二维情况的基本算法扩展到把二维情况的基本算法扩展到n n维，维，PowellPowell的算法要点：的算法要点：在每一轮迭代中总有一个起始点（第一轮的起始点是任选）在每一轮迭代中总有一个起始点（第一轮的起始点是任选）和和n n个线性独立的搜索方向。从起始点出发顺次沿个线性独立的搜索方向。从起始点出发顺次沿n n个方向作个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。一维搜索得一终点，由始点和终点决定了一个新的搜索方向。用这个方向替换原来用这个方向替换原来n n个方向中的一个，于是形成新的搜索个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。代的始点。这样就形成算法的循环。由于这种方法在迭代中生成共轭方向，而共轭方向是较好由于这种方法在迭代中生成共轭方向，而共轭方向是较好的搜索方向，故的搜索方向，故powellpowell法又称为方向加速法。法又称为方向加速法。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计三、改进的算法三、改进的算法 在鲍维尔基本算法中，每一轮迭代都用连结始点和终点在鲍维尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原来向量组中的第一个向量，而所产生出的搜索方向去替换原来向量组中的第一个向量，而不管它的不管它的“好坏好坏”。这是产生向量组线性相关的原因所在。这是产生向量组线性相关的原因所在。改进的算法是：改进的算法是：首先判断原向量组是否需要替换。如需要首先判断原向量组是否需要替换。如需要替换，还需进一步判断原向量组中哪个向量最坏，然后再用新替换，还需进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。 上述算法仅具有上述算法仅具有理论意义理论意义，这是因为在迭代的，这是因为在迭代的n n个搜索方个搜索方向有时会变成线性相关而不能形成共轭方向。这时组不成向有时会变成线性相关而不能形成共轭方向。这时组不成n n维空间，可能求不到极小点，故上述算法有待改进。维空间，可能求不到极小点，故上述算法有待改进。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.机械优化设计Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.