《现代设计方法教学课件作者张大可第4章节无约束优化方法课件幻灯片》由会员分享，可在线阅读，更多相关《现代设计方法教学课件作者张大可第4章节无约束优化方法课件幻灯片（27页珍藏版）》请在金锄头文库上搜索。
1、第4章 无约束优化方法,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,2,4.1 简述, 无约束优化方法是优化技术中最为重要和基本的内容之一，是优化技术的基础 约束优化问题可通过对约束条件的处理而转化为无约束问题 通过对无约束优化方法的研究可以为求解约束优化问题提供良好的概念和基础。,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,3, 无约束优化问题的一般形式为：,求 n 维设计变量,使目标函数值为：, 数学规划法求解无约束优化问题的策略, 各种不同的无约束优化方法的区别，主要在于建立搜索方向 的不同。, 建立搜索方向 时需要对函数求导数的方法，称为间接法（也称解析法）
2、；反之，则称为直接法。,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,4, 坐标轮换法是一种将 n 维问题转化为一系列一维问题的降维处理方法，属于直接法。,4.2 坐标轮换法,4.2.1 基本思想,是将搜索方向 S 依次取为按序号排列的一系列坐标轴方向，对于n维问题，当分别沿 n 个坐标轴方向依次搜索过一次以后，即完成一轮迭代。若尚未达到预先设定的精度要求，则进行下一轮迭代，直至满足精度要求为止。, 既可以用于求解无约束优化问题； 又可经过适当的处理后用于求解约束优化问题,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,5,图4-1 二维问题的坐标轮换法迭代过程,现代设计
3、方法第4章 无约束优化方法,重庆大学机械工程学院,6,4.2.2 迭代步骤,（1）任选一个初始点 作为第一轮的起点 ，令K=1, 设置 个坐标轴方向的单位矢量,（2）进行如下迭代计算,式中K为迭代轮数的序号； 为K轮迭代中进行一维搜索的序号，依次取 ； 为一维搜索的步长，通过一维求优的方法计算确定。,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,7,（3）判别是否可以终止迭代，即,若满足该条件，即可终止迭代，并输出最优解,否则，令 ，返回步骤（2）进行下一轮迭代。, 无约束优化问题求优迭代终止准则中任何一个皆适用 注意，点距准则或函数值下降准则中的所采用的两个比较点 应该是某一轮迭
4、代的起始点和终止点，而不是在某个搜索方向 进行一次搜索的前后两个迭代点。,4.2.3 迭代终止准则,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,8, 简单，易掌握，但效率低，只用于低维数（n10）问题求解； 收敛效果受目标函数等值线形状的影响很大，如迭代点刚好落在 目标函数等值线的“脊线”上时，则求优失败。,4.2.4 坐标轮换法的特点,(a) (b) 图 4-2,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,9,4.3 单纯形法,单纯形，是指在n 维空间中由n+1个线性独立的点构成的凸多边形或凸多面体。, 根据问题的维数 n，建立由 n+1个顶点构成的单纯形，计算出
5、这些顶点的目标函数值并比较其大小，确定出它们中函数值最大的点 以及函数值下降的方向（函数值最大点 与另外 n 个顶点的平均坐标点 之连线方向），从 点沿该方向进行一维搜索，将找到一个新的比较好的点取代函数值最大的点 ，从而构成新的单纯形。,单纯形的基本思想：, 随着这种取代过程不断进行，单纯形将不断改变其形状和大小并逐渐向着极小点收缩，最终单纯形的所有顶点将无限逼近函数的极小点。, 单纯形法是一种直接法。,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,10,4.3.1 基本步骤,单纯形法的搜索过程，如图4-5所示（以二维问题为例）：,在二维 （n=2）空间中取三个不共线的点（即 n
6、+1 个点），分别命名为 ，以它们为顶点构成单纯形三角形；,此三点的命名遵循如下规则：,1反射,计算出除 以外的所有其余各顶点的形心 ，并在 和 连线的延长线取一反射点 ，即,式中： 为反射系数，一般可取 。,图4-3 单纯形法的基本步骤,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,11,2扩张,若 ，即反射点的函数值小于次好点的函数值，表明所取搜索方向正确，可以进一步扩张，在更远处取新点 ，,式中： 为扩张系数，通常取 。,（1）如果 ，说明扩张不利，则舍去 ， 用 替代 ，构成新的单纯形 。 （2）如果 ，说明扩张有利，则用 替代 ，构成新的单纯形 。,图4-4 单纯形法的搜
7、索过程,3收缩,如果 ，表明 取得太远，应缩回一些，向后收缩得到收缩点 。,式中： 为收缩系数，通常取 。,图4-4 单纯形法的搜索过程,如果 ，则以 替代 ，构成新的单纯形 。,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,13,4 缩边,若 ，可以认为在该方向上很难找到合适的新点，单纯形应 以 为中心缩短边长，使所有点向 靠拢（缩边），如图4-5所示 和 ，即除点 不变外，其余各顶点坐标按如下公式计算：,（i = 0，1，2，n）,4.3.2 迭代终止条件,可在以下三种中任选其一：,（3）,（2）,（1）,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,14,4.4
8、梯度法（最速下降法）,梯度方向是函数值增加最快的方向，而负梯度方向则是函数值下降最快的方向。梯度法就是采用负梯度方向作为搜索方向，也被称作最速下降法或Cauchy法。,数学规划法求优的一般迭代公式为,当,则有,（k = 0，1，2，）,即为梯度法的迭代公式。,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,15,根据数学规划法求优的基本原理，为了使目标函数值沿搜索方向 能获得最大的下降值，其步长因子 应取一维搜索的最佳步长，即：,4.4.1 迭代步骤,（1）选取一个初始点 ，给定迭代精度 。 （2）计算 点的梯度及其模,（3）迭代终止条件判断,若满足，则迭代终止，得到最优解： ，若不
9、满足，转下一步。,？,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,16,（4）计算下一个迭代点,式中：步长因子 应由一维搜索 求得。,（5）令 ，返回第2步。,图4-5 梯度法流程图,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,17,4.4.2 梯度法的特点, 相邻两次搜索方向正交；,图4-6, 由于梯度的局部性质，从整个迭代过程来看，负梯度方向并非函数值下降最快的方向；,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,18, 对于如下两种特殊情况，采用梯度法一次一维搜索即可达到全域极小点：,(a) (b) 图 4-7,现代设计方法第4章 无约束优化方法,
10、重庆大学机械工程学院,19,例4-2 试用梯度法求解无约束优化问题 min,给定初始点 ，迭代精度取 。,解： 计算初始点处目标函数的梯度,不满足迭代终止条件,进行第一次迭代：以 为起点沿其负梯度方向作一维搜索求最优,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,20,得到,迭代点的梯度,计算梯度的模,不满足精度要求，需继续进行迭代，各次迭代结果见表4-1。,第五次迭代以后，满足迭代终止条件，即 ，得最优解为：,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,21,表4-1,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,22,4.4.3 共轭梯度法,1共轭方向
11、及其性质,定义 设A为nn阶对称正定矩阵，在n维空间中有m个非零向量 、 、 满足,（i、j = 0，1，2，, m-1）(i j),则称 、 、 对A共轭，或称它们是A的共轭方向。,当A = E（单位矩阵）时， 即为 与 的内积为零，亦即 、 正交 可见，共轭是正交的推广，正交是共轭的特例。,性质1： 如非零向量系 、 、 对A共轭，则这m个向量线性无关。,性质2： 在n维空间中相互共轭的非零向量不超过n个。,性质3： 从任意初始点 出发，顺次沿A的共轭方向 、 、 进行一维搜索，最多经过n次迭代，即可找到二次函数的极小点，且与搜索方向的选取次序无关。该性质表明此种迭代方法具有二次收敛性。,
12、现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,23, 根据共轭方向的性质，当目标函数为二次函数时，只要我们能够在初始点处建立起该目标函数海赛矩阵的 n 个共轭方向，从该点出发，顺次沿这些共轭方向进行一维搜索，最多经过 n 次迭代即可找到目标函数的极小点。若目标函数为高于二次的函数，则以上一轮迭代的终点为本次迭代的起点，再建立起目标函数在该起点 的海赛矩阵的 n 个共轭方向，从该点出发，顺次沿这些共轭方向进行一维搜索， 直至满足精度要求为止。这就是共轭方向法。,2共轭梯度法的基本思想, 共轭方向法种类很多，它们之间的主要区别在于构造共轭方向的方法不同。下面介绍一种利用两次相邻迭代点的
13、梯度来构造共轭方向的方法，称为共轭梯度法。,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,24,构造一个新的搜索方向,共轭方向法的基本思想是：,（k = 0、1、2）,即为 与 的线性组合，如图4-8示。要求 与 对A共轭，即,图 4-8,其中A为目标函数在 点处的海赛矩阵，是一个nn 阶的对称正定矩阵。,由上两式可得： ，此式应以适当简化。,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,25,3 的确定,由梯度的性质可推得，,即,现代设计方法第4章 无约束优化方法,重庆大学机械工程学院,26,4共轭梯度法基本步骤,第一次搜索取负梯度方向，其余方向取每次构建的共轭方向 形成共轭梯度法的基本步骤如下：,（1）设初始点为 ，第一个搜索方向取 点的负梯度方向 进行一维搜索，得到一个最小点 ；,（2）按 构造新的搜索方向 ，以 为起点， 沿 向进行一维搜索，得到一个最小点 ；,（3）重复步骤（2），不断构造新的共轭方向并沿这些方向进行一维搜索， 找到新的迭代点，直至满足收敛精度为止。,共轭梯度法实质上是对梯度法的一种改进，它的搜索方向可以认为是将负梯度偏转一个角度，所以又被称作旋转梯度法。,谢谢！,重庆大学 机械工程学院,
