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