现代设计方法优化设计ppt课件.ppt

现代设计方法 优化设计 有限元 1 序论第一部分优化设计第一章优化设计的数学基础1 1矢量1 2矩阵1 3多元函数第二章优化设计的基本概念第三章一维优化3 1单峰函数3 2黄金分割法3 3对分法4 4二次插值法第四章多维无约束优化4 1直接法4 2鲍威尔法4 3梯度法 最速下降法 4 4牛顿法 目录 2 目录 第五章多维有约束优化5 1概述5 2网格法5 3罚函数法第六章优化设计建模第七章机械优化设计示例 3 目录 第二部分有限元引言第一章弹性力学简介1 1求和约定1 2应力与应变1 2 1应力1 2 2应变1 2 3小变形弹性理论基本方程第二章有限元理论基础2 1变分法原理2 1 1变分法第一定理2 1 2泛函极值的求解 欧拉方程2 1 3求解变分问题的近似计算法 李兹 Ritz 法2 2虚功原理 虚功方程 与能量泛函2 3插值及单元位移2 4弹性力学有限元的矩阵方程 4 目录 第三章平面问题有限元3 1平面问题基本方程及有限元矩阵方程3 1 1基本方程3 1 2有限元矩阵方程3 2三角形场应变单元3 2 1离散化3 2 2位移模式3 2 3应变3 4刚度矩阵3 4 1单元刚度矩阵3 4 2总体刚度矩阵的组装3 4 3总体位移向量3 5单元的等效节点力与总体载荷向量3 5 1单元的等效节点力3 5 2总体载荷向量 5 目录 3 6刚度方程求解3 6 1边界条件处理3 7有限元分析的实施步骤3 8有限元计算收敛性第四章轴对称问题有限元4 1基本方程4 1 1平衡方程4 1 2几何方程4 1 3物理方程4 2三角形截面环单元4 3轴对称问题的有限元矩阵表达式4 3 1单元刚度矩阵4 3 2组装总体刚度矩阵4 3 3单元等效节点力 6 目录 第五章等参数单元5 1平面等参元5 1 1坐标变换及位移5 1 2应变及应变矩阵5 1 3单元刚度矩阵5 1 4单元等效节点力5 1 5高斯积分5 1 6等参元的完备性和协调性5 2轴对称等参元5 2 1坐标变换及位移5 2 2应变及应变矩阵5 2 3单元刚度矩阵5 2 4单元等效节点力5 3等参元的应力 应变计算 7 第六章杆件系统第七章薄板弯曲问题第八章结构动力学问题8 1结构动力学微分方程8 2结构动力学虚功方程8 3结构动力学有限元矩阵方程8 4结构自由振动有限元矩阵方程 模态分析 目录 8 序论 现代设计方法的基本内容 CADCAE 有限元分析 优化设计 可靠性设计逆向设计模块化设计设计专家系统价值工程虚拟设计 9 如何评价设计质量 m 1s 1s 可靠性 性能的波动在允许的设计界限内 稳健性 鲁棒性 降低在设计点上的敏感性 10 电视机有统一的系统设计和公差 任何不合格品都不卖给消费者调查显示 美国消费者一向喜欢日本产的电视机 Target 下限 上限 频率 SONYJapan SONYU S 日产电视机性能在期望值附近作小幅波动 方差很小 统计上看 大量的产品性能稳定 更加趋向设计目标 TARGET 美国产的电视机性能呈扁平分布 多数产品的质量是刚好落在界限内 11 例 悬臂梁减重优化 确定性优化 DesignVariables 10 BeamHeight 80mm10 FlangeWidth 50mmConstraint Stress 16MPaObjective MinimizeMass minimizearea 10 80 10 50 20 30 40 50 60 70 20 30 40 BeamHeight mm FlangeWidth mm Loadsatfreeend FlangeWidth BeamHeight 12 问题 已知安装角x存在不确定误差 在保证可靠性和稳健性前提下 求使应力f最小的x值 最大允许应力 危险区 安全区 概念 质量设计 稳健性 可靠性优化 13 第一章优化设计的数学基础 1 1矢量Vector定义 有大小和方向的量1 1 1二维矢量 x2 x1 P x1 x2 P x1 x2 O 1 1 2n维矢量 14 第一章优化设计的数学基础 1 2矩阵1 2 1定义由一组数按一定次序排列成的具有m行n列的表 15 第一章优化设计的数学基础 1 2 2逆矩阵Lattice若则B为A的逆矩阵逆矩阵的求法 A 为A的伴随矩阵 16 第一章优化设计的数学基础 1 2 3矩阵的正定与负定二次型对若 A为正定 A为半正定 A为负定 A为半负定不定 17 第一章优化设计的数学基础 矩阵正 负定的判定对称矩阵A正定的充要条件 其行列式各阶主子式之值均大于0 对称矩阵A负定的充要条件 各阶主子式的值 应负 正交替地变化符号 1 3多元函数1 3 1梯度 函数增加最快的方向 18 第一章优化设计的数学基础 1 3 2多元函数的二阶偏导与海赛矩阵1 3 3函数的泰勒级数展开 19 第一章优化设计的数学基础 1 3 4多元函数极值极值定义 在X0点的某邻域内 若 X0为严格极大值点 X0为严格极小值点 极值存在的必要条件 梯度为 0 T向量 极值存在的充分条件 H X0 正定 F X0 为极小值 H X0 负定 F X0 为极大值 20 第二章优化设计的基本概念 参数优化 优化结构的参数拓扑优化 优化拓扑结构1 设计变量设计过程中 其数值可以改变的能够描述结构特性的独立变量 传动比 尺寸 2 目标函数目标函数是比较和选择各种不同设计方案的量化指标 是设计变量的函数 质量 成本 利润 速度 21 第二章优化设计的基本概念 3 约束条件对设计变量取值范围的约束 强度 刚度 固有频率 4 设计空间和可行域设计空间 由设计变量构成的n维实空间可行域 设计空间内 满足约束条件的子空间5 数学描述 不等式约束等式约束变量取值范围约束 22 第二章优化设计的基本概念 6 例 X X F X 等值线 g1 X g2 X x1 x2 可行域 23 7 注意事项设计变量1 以主要影响因素作为设计变量 2 根据优化问题的特殊性选择设计变量 3 注意独立变量和相关变量 尽量不包括相关变量 4 变量群转换 减少变量数目 如变量在目标函数中以x1x2形式存在 可令y x1x2 5 必须的设计变量不能遗漏 6 冗余变量 相关变量 齿轮设计变量为i z m b 齿轮孔径为冗余变量 24 约束函数1 不能矛盾 2 可行域不能无界 3 避免多余约束 4 尽量给定设计变量取值上下界 缩小可行域 5 谨慎对待等式约束 6 近似约束 不能用精确数学表达式描述的约束的处理 7 不能遗漏必要的约束 如压簧优化设计忽略了工作状态下 相邻圈间间隙值约束 8 全部设计变量必须包含在约束函数集中 25 目标函数1 目标函数必须包含全部或部分设计变量 2 当必须采用多目标优化时 可选择其中一个主要的目标作单目标优化 其它目标按满足一定值要求的约束处理 优化后在选另一目标优化 3 近似目标函数 借助实验数据处理建立目标函数 4 转移或替代目标函数 如以中心距作为减速器重量的替代目标函数 5 单体设计对象的多目标评价 设计变量和约束条件不变 建立多个不同的目标函数并分别优化 得到一组优化方案 优中择优 6 目标函数的规一化 minF X 26 8 优化问题求解方法 搜索法9 收敛判据1 相邻两轮搜索得到的近似极值点 相对距离 小于某一小的正数 2 F X 可微 则梯度绝对值小于某一小的正数 27 解析法搜索法直接法 区间缩减法 黄金分割法 对分法间接法 插值法 二次插值 三次插值一维优化在多维优化中作用 确定最优步长 28 3 1单峰函数3 1 1单峰函数在给定区间内仅有一个极小值点的函数多峰与单峰的关系多峰函数区间分割成数个单峰区间 按单峰函数求极值点单峰函数极值点求解单值区间缩小 x1 x2 2为极值点 29 3 1 2初始单值区间确定算法进退步法 探索步长加倍 单峰区间 x2 x4 x5 x3 30 一阶导数法 f x 连续可微 以h 2h 4h h 0为步长 若f xk 2 0或f xk 2 0 f xk 2则 xk 2 xk 或 xkxk 2 为单峰区间 xk 2xk 1xk h2h f 0 31 3 2黄金分割法3 2 1区间缩小求解极值点的基本思路按一定规则在 a b 内取两个点x1 x2 ax1x2bax1x2bax1x2b a b c f x1 f x2 f x1 f x2 a b a x2 a b x1 b a b a x2 或 x1 b 32 3 2 2取点规则 黄金分割法 0 618法 均匀缩短率对称取点 黄金分割 将一线段分割成两段 使得整段长度L与较长段x 的比值等于较长段x与较短段L x 的比值 L ax1x2b 33 3 2 3区间收缩参见3 21 34 3 2 4收敛判据常用判据1 2 3 4 判据的使用1 3 或2 4 组合使用 并从a b a b 2中选最优者 abab 35 3 3对分法3 3 1中心对分法 可微 比较的符号 将区间 a b 缩短一半 3 3 2两点对分法 可不可微 a a b 2b ax1x2b f1f2 a b 2 36 3 4二次插值法二次插值 二次多项式逼近3 4 1方法原理二次多项式逼近目标函数 以二次多项式的极小值点作为目标函数的近似最优点 3 4 2二次多项式构造单峰区间 x1 x3 内存在极小值点 在 x1 x3 内取点x2 则过x1 x2 x3构造其极小值点为x x1x2x x x3 f x p x 37 3 4 3区间缩小原理比较f x 和f x2 以其中较小者对应的点为新的x2点 新x2左右相邻的点分别为新x1 新x3 3 4 4收敛判据 见黄金分割法习题初始区间 a b 0 5 1 5 绝对精度分别用解析法 黄金分割法 中心对分法 两点对分法求解 38 分类 1 直接法 不需计算导数 2 间接法 需计算导数 4 1坐标轮换法 坐标方向为搜索方向 4 1 1原理将n维问题转化为依次沿n个坐标方向轮回进行一维搜索 39 40 4 1 2算法1 任选初始点设定初始步长置搜索方向2 以为初始点 沿方向作试探 步长计算 若说明试探成功 否则 若 置 若 41 则作一维搜索求最优步长和优化点若沿坐标轴正负方向试探均失败 则迭代点不变3 以为起点 按1 沿方向搜索 得沿n个坐标方向进行完一轮一维搜索后 得4 以作第二轮得起始点 重复2 3 得第二轮搜索终点 5 如果从某轮起始点出发 依次沿n个坐标轴的正负方向试探均失败 则缩短试探步长 如减半 返回2 当探索步长足够小 满足收敛判据时 终止迭代 所得点即为优化结果X 42 4 1 3讨论1 计算量小 程序简单 计算效率低 适合变量n 10的情况 2 若目标函数具有脊线 算法将出现病态 沿两个坐标方向均不能使函数数值下降 误认为最优点 脊线 43 4 2鲍威尔法 共轭方向为搜索方向 4 2 1共轭方向1 定义A为n阶正定矩阵 若两个n维矢量满足则称S1和S2对矩阵A共轭 共轭矢量方向为共轭方向 对于n个n维矢量Si i 1 2 n Si不为0 若满足则称n个n维矢量Si i 1 2 n为对矩阵A共轭 2 共轭方向与函数的极小值点关系考察正定二次函数其等值线为同心椭圆族 44 S2 S1 S1 X1 X2 X1 0 X2 0 x1 x2 从X1 0 出发沿S1方向作一维搜索 得最优点X1 与椭圆相切 从X2 0 出发沿S1方向作一维搜索 得最优点X2 连接X1 X2得矢量S2 S2过椭圆族中心 即目标函数极小值点X 且S1 S2对A正交 沿S1的共轭方向S2可搜索到正定二元二次函数极值点 X 45 4 2 2原始鲍威尔法S1 S2 S3为共 轭方向 参见前页 搜索方向 x1 x3 x2 e1 e2 e3 X0 1 S1 e2 e3 S1 X1 1 X2 1 X3 1 X0 2 X1 2 X2 2 X3 2 X0 3 S2 e3 S1 S2 S3 X1 3 X2 3 X3 3 X0 4 第1轮 第2轮 第3轮 46 原始鲍威尔法的严重缺陷 当某一轮方向组中的矢量系出现线性相关时 特别是接近X 时 会出现退化 无法获得极小值点 4 2 3改进鲍威尔法与原始鲍威尔法的区别 每构造一个新方向 根据判别条件决定是否替换原来的某个方向 构造k 1轮方向组时 是否淘汰前一轮的某一个方向Sm k 根据下面二个条件判断 第k轮初始点函数值 第k轮最后一个方向搜索终点函数值 X0 k 对Xn k 映射点Xn 1 k 的函数值 一维搜索中函数值下降最大者 其方向为Sm k 47 条件式a b 同时或两者之一成立 第k 1轮仍沿用第k轮的方向组 取Xn k F2 F3 或映射点Xn 1 k F3 F2 作为k 1轮的初始点 条件式a b 同时不成立 淘汰Sm k 第k轮的新方向Sn 1 k 补入k 1轮方向组的最后 组成k 1轮搜索的方向组 函数值下降最大方向 取第k轮沿方向Sn 1 k 搜索得到的极小值点X k 作为k 1轮搜索的初始点 改进鲍威尔法的搜索方向组不一定是共轭方向组 而是共轭程度高的方向组 这种改进方向组在随后各轮搜索中 共轭程度将越来越高 仅要求第1轮方向组线性独立 避免原始鲍威尔法的方向组线性相关退化现象 48 4 2 4收敛判据4 3最速下降法 梯度法 4 3 1方法原理将n维优化问题转化为沿负梯度方向的一维搜索求优 1 搜索方向 最优步长及迭代公式2 收敛判据 49 4 3 2梯度法的特点1 对初始点没有要求 可任选2 相邻两点的搜索方向正交 亦即 梯度法迭代路径为绕道逼近极小点 负梯度方向仅是局部下降最快 不是最好的下降方向 梯度法不是最有效的算法 50 4 4牛顿法4 4 1原始牛顿法1 基本思想在X k 的邻域内 用二次泰勒多项式近似原目标函数F X 以该二次多项式的极小点作为F X 的下一个迭代点X k 1 并逐渐逼近F X 的极小点X 要求 F X 连续 且存在一 二阶偏导数 51 4 4 2阻尼牛顿法1 原始牛顿法的缺点搜索步长恒定 且过大 可能出现目标函数值上升情况F X k 1 F X k 不是严格的下降算法 原因 X k 1 是近似二次式在牛顿方向上的极小点 而非F X 在牛顿方向上的极小点 2 对牛顿法的修正 阻尼牛顿法修正方法 在牛顿方向上作一维搜索求最优步长 当F X 的海赛矩阵Hk在迭代点处正定情况下 阻尼牛顿法可以保证每次迭代 迭代点的函数值都下降 Hk在迭代点处不定情况下 函数值不会上升 但不一定下降 Hk在迭代点处奇异情况下 不能求逆 无法构造牛顿方向 要求F X 二阶可微 需计算梯度 海赛矩阵及其逆矩阵 计算量大 4 4 3收敛判据同梯度法 52 53 4 5DFP变尺度法 拟牛顿法 基于牛顿法的思想进行了重要改进 4 5 1基本思想综合梯度法和牛顿法的优有点 克服梯度法收敛速度慢和牛顿法收敛快但稳定性差且计算量大的缺点 比较梯度法和牛顿法 54 Ak为n n对称矩阵 Ak为单位矩阵时 上式为梯度法 Ak Hk 1时 上式为阻尼牛顿法 拟牛顿法的基本思想 用某种方法 人为构造一n阶对称矩阵Ak A X k 近似替代牛顿法的Hk 1 通过迭代不断修正Ak 使AkHk 1 由于是不断变化的 它使搜索方向不断向牛顿方向逼近 故可把看作是变化的尺度矩阵 这就是变尺度法叫法的由来 梯度法和牛顿法也属于变尺度法的范畴 Ak应满足的条件 1 正定保证迭代过程中函数值始终下降 要求S k 与gk夹角为锐角 即 55 2 拟牛顿条件 使AkHk 1 Ak 1可以由第k步的信息递推构造由得即 56 4 5 2Ak序列的生成 DFP递推公式 57 4 5 3算法1 任选初始点X 0 收敛精度2 置k 0 Ak E 单位矩阵 3 沿4 5 用DFP公式求Ak 1 6 置 若k n 变量数目 转到3 否则返回到2 开始下一轮 从负梯度法重开始 有利于收敛 7 输出结果X F X 结束 58 4 6共轭梯度法将梯度法和共轭方向法结合起来 每一轮搜索的第一步沿负梯度方向搜索 后续各步沿上一步的共轭方向搜索 具有二次收敛速度 每一轮搜索n步 第一步的搜索方向 负梯度方向以后各步的搜索方向 共轭方向的确定 应使n维实空间中的两个非0向量S k 和S k 1 关于矩阵A共轭 即应使对于正定二次函数有 59 二式相减而则可得即因为一正交系 故有则 60 61 算法l 任选初始点X 0 给定收敛精度 和维数n 2 令 求迭代初始点X 0 的梯度g0取第一次搜索的方向S 0 为初始点的负梯度3 进行一维搜索 求最优步长 k 并求出新点4 计算X k 1 点的梯度5 收敛检查 满足条件则 计算结束 否则继续下一步 6 判断k 1是否等于n 若k 1 n 则令X 0 X k 1 转步骤2 若k 1 n 则继续下一步 7 计算 62 8 确定下一步的搜索方向令 返回步骤3 讨论共轭梯度法具有超线性收敛速度 1 收敛速度阶数 2 计算效率高于梯度法 低于牛顿法 但对初始点没有特殊要求 不需计算二阶偏导数矩阵及其逆矩阵 计算量与梯度法相当 小于牛顿法 适用于各种规模的问题 63 4 7单纯形法原理函数的导数是函数性态的反映 它对选择搜索方向提供了有用的信息 在不计算导数的情况下 先算出若干点处的函数值 从它们之间的大小关系中也可以看出函数变化的大概趋势 为寻求函数的下降方向提供依据 这里所说的若干点 一般取在单纯形的顶点上 所谓单纯形是指在n维空间中具有n 1个顶点的简单图形或凸多面体 利用单纯形的顶点 计算其函数值并加以比较 从中确定有利的搜索方向和步长 找出具有最大值的顶点并构造目标函数的下降方向 求出最小值点 以该点取代单纯形的最大值的顶点 重新构造单纯形 随着这种取代过程的不断进行 新的单纯形不断向极小点收缩 这样经过若干次迭代 即可得到满足精度要求的近似解 这就是单纯形法的基本思想 64 65 算法选择新的比较好的点替代最差点的算法有4种 反射 扩张 压缩和收缩 现以二元函数F X F x1 x2 为例 说明单纯形法的算法 在x1 x2平面上取不在同一直线上的三点XH XG XL 以它们为顶点组成一单纯形 即三角形 XHXGXL 计算各顶点函数值 设F XH F XG F XL 说明XL点最好 XH点最差 为了寻找极小点 一般说来 应向最差点的反对称方向进行搜索 即通过XH并穿过XGXL的中点XC的方向进行搜索 在此方向上取作XH点相对于XC点的反射点XRXR XC XC XH 2XC XH计算反射点的函数值F XR 可能出现以下几种情形 l F XR F XL 即反射点比最好点还好 说明搜索方向正确 还可以往前迈进一步 也就是可以扩张 这时取扩张点XE XC k XC XH k 扩张因子 一般取k l 2 2 0 如果F XE F XR 说明扩张有利 就以XE代替XH构成新单纯形XEXGXL 否则说明扩张不利 舍弃XE 仍以XR代替XH构成新单纯形XRXGXL 66 2 F XL F XR F XG 即反射点比最好点差 但比次差点好 说明反射可行 则以反射点代替最差点 仍构成新单纯形XRXGXL 3 F XG F XR F XH 即反射点比次差点差 但比最差点好 说明XR走得太远 应缩回一些 即压缩 这时取压缩点XK XC m XR XC m 收缩因子 常取成m 0 5 如果F XK F XH 则用XK代替XH构成新单纯形XKXGXL 4 F XR F XH 即反射点比最差点还差 这时应压缩得更多一些 即将新点收缩在XHXC之间 取压缩点XK XC m XC XH 如果F XK F XH 则用XK 代替XH构成新单纯形XK XGXL 5 F X F XH 即若XHXC方向上的所有点都比最差点差 则表明不能沿此方向搜索 这时应以XL为中心收缩 使顶点XH XG向XL移近一半距离 得新单纯形XH XG XL 如图所示 67 从以上各步得到新的单纯形后 再重复开始新一轮构造单纯形 逐渐缩小单纯形直至满足精度要求 68 计算步骤1 构造初始单纯形 选初始点X0 从X0出发沿各坐标轴方向走步长h 得n个顶点Xi i 1 2 n 与X0构成初始单纯形 这样可以保证此单纯形各棱是n个线性无关的向量 否则就会使搜索范围局限在某个较低维的空间内 有可能找不到极小点 2 计算各顶点函数值 Fi F Xi 3 比较函数值的大小 确定最好点XL 最差点XH和次差点XG FL F XL minF Xi i 1 2 n FH F XH maxF Xi i 1 2 n FG F XG maxF Xi i 1 2 n i H 4 检验是否满足精度要求满足要求 则X XL 计算结束 否则 继续步骤5 5 计算除XH点之外各点的 重心 Xn 1 69 和反射点当时 以Xn 2代替XH Fn 2代替FH 构成一新单纯形 然后返回步骤2 6 扩张 当Fn 2 FL时 取扩张点并计算其函数值Fn 3 若Fn 3 Fn 2 则以Xn 3代替XH Fn 3代替FH 构成新单纯形 否则 以Xn 2代替XH Fn 2代替FH 构成新单纯形 然后返回步骤2 7 压缩 当Fn 2 FG时则需收缩 如果Fn 2 FH 则取收缩点否则 若F XR F XH 在上式中以XH代替Xn 2 计算其函数值Fn 4 若Fn 4 FH 则以Xn 4代替XH Fn 4代替FH 构成新单纯形 然后返回步骤3 否则接步骤8 70 8 收缩单纯形 最好点不动 其它点向最好点移近为原距离的一半 即 i 1 2 n 构成新单纯形 然后返回步骤2继续计算 习题分别用鲍威尔法 改进鲍威尔法 梯度法 阻尼牛顿法 DFP变尺度法 单纯形法 共轭梯度法求解 迭代2次 71 坐标轮换法将n维问题转化为依次沿n个坐标方向轮回进行一维搜索 收敛速度较慢 适合n 10的小型无约束优化问题 若目标函数具有 脊线 算法将出现病态 沿两个坐标方向均不能使函数数鲍威尔 Powell 法属于模式搜索法 搜索方向不一定是共轭方向组 而是共轭程度越来越高的方向组 改进共轭方向 避免原始鲍威尔法 共轭方向法 的方向组线性相关退化现象 对初始点没有特殊要求 具有超线性收敛速度 适合中小型无约束优化问题 单纯形法对n维问题 构造由n 1线性独立的点为顶点的凸单纯形 找出具有最大值的顶点并构造目标函数的下降方向 求出最小值点 以该点取代单纯形的最大值的顶点 重新构造单纯形 适用于中小型无约束优化问题或目标函数没有数学表达式而只有其具体算法的情况 72 最速下降法 梯度法 搜索方向为目标函数负梯度方向 计算效率优于坐标轮换法 开始几步搜索下降快 但愈接近极值点下降愈慢 对初始点的选择要求不高 适合与其它方法结合使用 开始采用最速下降法 接近极值点时采用其它方法 如牛顿法 牛顿法 Newton Raphson法 用泰勒二次多项式近似原目标函数 以该二次多项式的极小点近似目标函数的极小点并逐渐逼近该极小点 搜索方向为牛顿方向 步长为1 要求目标函数连续 存在一 二阶偏导数 且海赛 Hessian 矩阵非奇异 初始点选择适当时 是收敛最快的算法 对初始点选择要求高 计算量大 阻尼牛顿法 修正牛顿法或广义牛顿法 搜索方向为牛顿方向 沿牛顿方向对步长做一维搜索优化 其它特点与牛顿法相同 73 共轭梯度法第一步搜索沿负梯度方向 最速下降方向 然后沿负梯度的共轭方向搜索 计算效率介于梯度法和牛顿法之间 对初始点没有特殊要求 不需计算二阶偏导数矩阵及其逆矩阵 计算量与梯度法相当 适用于各种规模的问题 变尺度法 DFP法及BFGS法 拟牛顿法 基于牛顿法的思想进行了重要改进 为公认的求解无约束优化问题的有效方法 适用于各种规模的问题 DFP法有时存在数值稳定性不够理想的问题 BFGS法数值稳定性较好 74 分类1 直接法直接利用迭代点和目标函数值构造搜索方向 网格法 分层降维枚举法 2 间接法需计算梯度构造搜索方向 将约束优化问题转化为无约束优化问题求解 罚函数法 内点 外点 混合 75 5 1目标函数的约束极值问题目标函数的约束极值 又称为条件极值 与前面所讨论的无约束条件下函数的极值问题的区别在于它是带有约束的条件下的函数极值问题 在约束条件下所求得的函数极值点 称为约束极值点 对于带有约束条件的目标函数 其求最优解的过程可归结为 寻求一组设计变量 在满足约束方程的条件下 使目标函数值最小 这样求得的最优点X 称为约束最优点 两者重合两者不重合自然极值点与约束最优点的相互关系 76 a b 可行域形状对约束最优解的影响 a 可行域为凸集 b 可行域为非凸集 77 目标函数或约束函数的非凸性使约束极值点增多情况Kuhn Tucker最优胜条件简称为Kuhn Tucker条件或K T条件 可有效地用于对约束极值点存在条件的分析 检验 K T条件如下 设X 为非线性规划问题 78 的约束极值点 且在全部等式约束及不等式约束条件中共有q个约束条件为起作用约束 即 i j i j 1 2 q p 如果在X 处诸起作用约束的梯度向量 i j 1 2 q p 线性无关 则存在向量使下述条件成立 为非零 非负的乘子为非零的乘子 拉格朗日乘子向量 满足Kuhn Tucker条件的点 称为Kuhn Tucker点 在一般的非线性规划问题中 Kuhn Tucker点虽是约束极值点 但不定是全域最优点即K T条件不是最优解的充分条件 但对于目标函数F X 为凸函数 可行域D为凸集的凸规划问题来说 Kuhn Tucker条件不仅是确定约束极值点的必要条件 同时也是全域最优解的充分条件 而且凸规划问题有唯一的Kuhn Tucker点 但它所对应的拉格朗日乘子向量不一定是唯一的 79 K T条件的几何意义Kuhn Tucker条件条件表明 若点X 是函数F X 的极值点 要么 X 点位于可行域内 要么X 点位于某些约束的边界上 而在点X 目标函数的负梯度落在起作用约束梯度所成的夹角锥体之内 也就是说 目标函数的负梯度等于起作用约束梯度线性组合 80 例 用Kuhn Tucker条件证明二维目标函数在不等式约束 的约束条件下 点为其约束极值点 a 求证约束极值点 b 在约束极值点处K T条件不成立的情况 81 1 由图可知 在点处起作用的约束函数有和 2 求有关函数在点的梯度 3 代入式 2 25 检验 82 即 故满足K T条件 即点确为约束极值点 而且由于本题为凸规划 所以它也是全局最优点 例 试分析约束最优化问题的约束最优解及其Kuhn Tucker条件 图 b 给出了可行域 由图不难看出是约束最优点 起作用约束函数有和 但由于 显然不可能找到 使Kuhn Tucker条件 83 成立 这一矛盾产生的原因是由于即二者为线性相关而在Kuhn Tucker点起作用约束的梯度向量应是线性无关的 84 5 2网格法5 2 1原理1 在设计变量的界线区间内均匀地划分网格 计算节点上的目标函数值和约束函数值 舍去不满足约束条件的节点 比较满足约束条件的节点的目标函数值 找出目标函数值最小的节点 2 以该最小值节点相邻的各节点为新的设计变量界线区间 细化网格 重复1 直至满足精度 收敛 要求 网格分割间距 X X 1 初始网格 二次网格 X 2 85 5 2 2网格法的特点1 不适合于等式约束 2 对连续变量和离散变量均适用 3 总能搜索到解 4 算法简单 计算量大 适合设计变量较少的情况 5 2 3分层降维枚举法 改进的网格法 将设计变量分层处理 每一层有少量设计变量 前一层的设计变量的解作为常量进入下一层的求解过程 从而减少网格节点数量 减少计算量 要求 优化模型必须能分层 86 5 3罚函数法5 3 1罚函数法的基本思路1 拉格朗日乘子法构造函数 的无约束极值问题 87 2 罚函数法借鉴拉各朗日乘子法 将约束优化转化为序列无约束极小化问题 88 3 罚函数求解过程 序列无约束极小化方法 SUMT法 a 定义G和E的形式 选择r k M k 的递推序列及初始点X 0 b 从r 0 M 0 开始 以X 0 为初始点求P 0 的无约束优化点X 0 随后以递推方式 以r k M k 和初始点X k 1 求P k 的无约束优化点X k 得优化点序列 X k c 优化点序列 X k 不断逼近最优解 满足收敛准则 X k 即为有约束优化得最优解 4 罚函数法分类内点法 在可行域内迭代 逼近最优解 适合于不等式约束 外点法 在可行域外迭代 逼近最优解 适合于不等式约束和等式约束 混合法 适合于不等式约束和等式约束 89 5 3 2内点法1 例构造泛函 罚函数极值 90 91 f P7654321 0123456789x x 1 0 f x x 2 r k 1 r k 0 25 r k 0 0025 x 21 0r 3 r 2 r 1 r 0 r k r k 递减时x k 逼近x f和P的曲线 92 2 内点法泛函与罚函数构造1 是可行域D上的连续函数 采用需要梯度的优化方法时 需可导 2 当X在可行域D内远离约束边界时 具有相当小的正值 X靠近约束边界 具有很大的正值 趋向无穷大 93 3 X的取值只能在可行域内 否则泛函G将不满足不为负值的要求 4 罚因子r k 的作用 F X 的有约束极值点可能在可行域靠近边界处或就在边界上 此时尽管泛函G的数值很大 但罚因子是不断递减的正值 经多次迭代 X k 向X 接近时 惩罚项r k G是很小的的正值 趋向0 可以保证罚函数P X 的无约束极值点序列收敛于F X 约束极值点 3 算法1 在可行域内任选一严格初始内点X 0 最好不要靠近约束边界 2 选一适当大的初始罚因子r 0 求罚函数P X r 0 的无约束极值点X 0 选一罚因子递减率0 c 1 递减后的罚因子r 1 cr 0 以X 0 为初始点 求罚函数P X r 1 的无约束极值点X 1 3 按r k cr k 1 k 1 2 逐次递减罚因子 并依次取上一次迭代的极值点X k 1 作为本次迭代的初始点 重复上述步骤 直至满足收敛精度 即得最优解X 和最优值F X 94 4 内点法讨论1 初始点为严格内点 2 不适用于等式约束 如等式约束不要求严格满足时可处理为 3 初始罚因子对收敛性影响大 但难以选择 一般用试算法调整 4 罚因子递减率大小对收敛性影响不大 c 0 1 0 02 5 进行罚函数的无约束优化的一维搜索时 应保证不超出可行域 每作一次一维搜索 都要检查是否破坏约束 如不破坏 可继续进行 否则 缩短寻优区间 直至满足约束 6 内点法的规律性 a P X k r k 为严格单调下降数列 且其极限为F X b F X k 为单调非增数列 95 c G g X k 为单调非降数列7 可以得到多个优化方案 X k F X k 5 收敛判据前后两次迭代的极小值点间的 距离 或 相对距离 满足精度要求 96 5 3 3外点法1例构造泛函和罚函数x取值即可在可行域内 也可在可行域外 M k 为外点法的罚因子 是递增序列 97 求P的无约束极值点 98 99 2 外点法泛函与罚函数构造优化模型 泛函的构造 要求 a 泛函应是Rn中的连续函数 b X在可行域外远离约束边界时 泛函有相当大的正值 离边界越远 其正值越大 X在可行域外靠近约束边界时 泛函有较小的正值 在边界上和可行域内 其值为0 1 不等式约束 100 2 等式约束 罚函数构造 3 算法1 任选初始点X 0 内点 外点均可 选定适当的初始罚因子M 0 和递增率c 求P X M 0 的无约束优化点X 0 2 以X 0 作为下一次迭代的初始点 取M 1 c M 0 为递增的罚因子 求P X M 1 的无约束优化点X 1 3 按M k c M k 1 k 1 2 逐次递增罚因子 依次取上一次的优化点X k 1 为本次迭代的初始点 求P X M k 的无约束优化点X k 直至满足收敛精度 收敛判据与内点法相同 101 4 外点法讨论1 优点 初始点可任选 2 M 0 宜选较小值 罚函数较平滑 极值点易求 c 对收敛性影响不大 3 不存在内点法中的一维搜索超界问题 4 最优解的特点对于精确解在约束边界上的情况 由于外点法从可行域外逐步逼近约束边界 不可能正好收敛于边界上 而只能收敛到边界外某个精度的小区域中 对工程问题 不太保险 如应力约束 对此 可将约束紧缩一个裕量 加以解决 102 5 外点法的规律性a b c 103 6 内 外点法的比较 罚因子为递增 递增率c 1 罚因子为递减 递减率0 c 1 6 初始罚因子数值要适当 初始罚因子数值要适当 5 一般收敛较快 一般收敛较慢 4 仅最优解为可行设计方案 仅一个方案 迭代过程中 各个优化点均可作为可行设计方案 有多个方案 3 对等式约束和不等式约束均适用 不适于等式约束 2 可以任选 但应使各函数有定义 初始点必须为严格内点 1 外点法 内点法 项目 104 5 3 4混合罚函数法1 泛函和罚函数的构造选定初始点后 对已经满足的不等式约束用内点法构造惩罚项 对等式约束和未被满足的不等式约束用外点法构造惩罚项 105 2 初始点选取的外推法可将若上述函数关系存在 则有r k 0求得的X k 必为问题的最优解 外推法的基本思想 利用少数几个 r k 求得相应的序列 X k 后 利用这些信息 用多项式展开作函数逼近 向的方向外推 求得的的外推点虽非最优解 但一般总是靠近最优解的点 以外推点作为下一次无约束优化的初始点 可以加快收敛 一级外推与二级外推 见右图 3 收敛判据相邻两个外推点 相对距离 小于某一正小数 精度 106 4 算法1 任选初始点X 0 及合适初始罚因子 2 针对X 0 对约束的满足情况 构造罚函数P X r 1 3 求P X r 1 的无约束极小点X 1 4 若k 1 则令k k 1 r k cr k 1 取 转向步骤2 以上次的无约束极小点X 1 作为初始点求第二个无约束极小点X 2 否则转向步骤5 5 进行两次无约束极小化后 作一级外推 若不满足收敛精度 则以该一级外推点作为第三次无约束优化的初始点 求得第三个无约束极小点X k 2 然后作二次外推 求得二次外推点 以此外推点作为第四次无约束极小化的初始点 6 收敛性检查 满足精度要求 以最后一个外推点为最优解的最终近似 否则转向步骤7 7 令k k 1 转向步骤5 构造下一个罚因子r k cr k 1 继续无约束极小化过程 107 5 4增广拉格朗日 Lagrange 乘子法罚函数法算法编程较易且方法比较有效 但它们的缺点是当迭代次数时 罚函数靠近边界处的几何形状越来越陡 给数值计算带来困难 为此 1969年Powell和Hestenes提出了增广Lagrange乘子法 简称ALM法 AugmentedLagrangeMethod 又称为MOM法 MethodofMultiplier 后来Fletcher对它又作了改进 许多学者对它进行了研究 使它成为在收敛速度和数值稳定性方面均优于惩罚函数法的有效方法 Powell认为 作为最优化工具 使用不包括拉格朗日乘子的SUMT法已成为过时 增广Lagrange乘子法的作法是将拉格朗日乘子引入惩罚函数法的惩罚项中 或者说将惩罚项引入拉格朗日函数中 以试图通过调节拉格朗日乘子 避免惩罚函数法中出现的几何形状造成的数值计算困难 108 一 增广拉格朗日函数1 等式约束问题的拉格朗日函数为将等式约束的的罚函数的惩罚项引入上式 得增广拉格朗日函数 式中 拉格朗日乘子 显然 是罚函数与拉格朗日函数的结合 当时 上式即为罚函数 当时 上式又变为拉格朗日函数 109 2 不等式约束问题通过引入松弛变量 将不等式变为等式来处理相应的增广拉格朗日函数为当引入的松弛变量较多时 使问题的设计变量总数大为增加 为了减少变量总数 可将上式改写成另一种形式 现推导如下 110 极小点的必要条件为得若若因此得上式相当于 111 将此式代入增广拉格朗日函数式 消去松驰变量wj 记消去wj后的增广拉格朗日函数为具有对X的连续一阶导数 而二阶导数在处是不连续的 故应谨慎地使用二阶方法去求解式的无约束最优解 3 一般约束问题相应的增广拉格朗日函数为 112 二 增广拉格朗日函数的无约束极小点求解1 等式约束问题拉格朗日函数的极值点存在的必要条件为另外 对于X 有 因为X 满足 所以是的极小点 113 因此 增广拉格朗日函数的极小点存在的必要条件为这意味着 及F X 具有相同的极小点X 的无约束极小问题等价于原等式约束的优化问题 上式中的拉格朗日因子 的值是在迭代过程中使 逼近 得到的 通常的做法是 当k 0时 k 0 M k 取适当大的正数 在 k 和M k 为固定常数的条件下求的极小点 114 k 1 的值 可根据的极值条件 上式 构造下面的迭代式求得对于M k 不必每一次构造都改变 当 k 收敛太慢或不收敛时 可适当增大M k 但要小于某个有限上界 以免出现数值计算中的病态问题 下一步再以 k 1 和M k 1 为新的固定常数 以X k 为初始点 求的无约束极小点 如此反复迭代下去 直至达到精度要求 收敛准则可采用 点距 目标函数差值 或 k 1 递推式构造过程如下 考虑 得 115 计算步骤如下 1 给定 2 求解无约束优化问题 3 收敛检查 达到精度要求 计算结束 否则继续下一步 4 计算和M k 1 CM k 若M k 1 令M k 1 5 转步骤 2 116 2 不等式约束问题不等式约束的增广拉格朗日函数的极小点求解的拉格朗日乘子的迭代式为其它算法和计算步骤与等式约束的增广拉格朗日函数的极小点求解类似 3 一般约束问题包括等式和不等式约束的增广拉格朗日函数的极小点求解的拉格朗日乘子的迭代式为其它算法和计算步骤与等式约束的增广拉格朗日函数的极小点求解类似 117 5 3 5约束极值存在的必要条件和充分条件1 必要条件 Kuhn Tucker K T条件 对约束极值 优化 问题 若X 是上述问题的一个极小点 且则存在乘子 K T条件 118 2 充分条件若X 是可行域内一点 若存在K T条件成立 且对任何满足下式的向量V的均有则X 为约束优化问题的一个严格局部极小点 119 5 5随机方向法一 原理随机方向法是一种直接解法 它的基本思路是在可行域内选择一个初始点X 0 利用随机数的概率特性 产生若干个随机方向 以适当步长 沿随机方向探索 从中选择一个能使目标函数值下降最快的随机方向作为可行搜索方向 记作S 0 从初始点X 0 出发 沿S 0 方向以适当步长进行搜索 直至函数值不再下降且满足约束条件 得到新点X 1 至此完成一次迭代 然后 将起始点移至X 1 重复以上过程 得到序列 经过若干次迭代计算后 最终取得约束最优解 随机方向法的迭代公式为且X k 1 应满足 120 随机方向法原理图 121 二 算法1 随机数的产生首先令 取r 2657863 r为小于r1正奇数 然后按以下步骤计算令若 若 若q即为 0 1 区间内的伪随机数 利用q 可求得任意区间 a b 内的伪随机数x 122 2 初始点的选择随机方向法的初始点X 0 必须是一个可行点 即满足全部不等式约束条件的点 当约束条件较为复杂 用人工不易选择可行初始点时 可用随机选择的方法来产生 其计算步骤如下 l 给定设计变量的下限值和上限值 即2 在区间 0 l 内产生n个伪随机数qi i 1 2 n 3 计算随机点X的各分量4 判别随机点X是否可行 若随机点X为可行点 则取初始点 若随机点X为非可行点 则转步骤3 重新计算 直到产生的随机点是可行点为止 123 3 可行搜索方向的产生在随机方向法中 产生可行搜索方向的方法是从N N n 个随机方向中 探索选取一个较好的方向 其计算步骤为 假定当前迭代为第k次 1 在 1 1 区间内产生伪随机数 按下式计算随机单位向量ej2 在以点X k 为中心 以试验步长 一般取0 1 0 01等 为半径的超球面上按下式生成N个随机点3 检验N个随机点Xj是否为可行点 计算可行随机点的目标函数值 比较其大小 选出目标函数值最小的点XL 124 4 检验XL当XL满足上式时 可行搜索方向条件 可行搜索方向为若 则将步长缩小 然后转步骤2 重新计算 直至满足条件为止 如果缩小到很小 例如 仍然找不到 个满足条件的XL 则说明X k 是一个局部极小点 4 搜索方法以X k 为始点沿S k 方向索以步长搜索 若搜索所得新点继续满足约束条件和函数值下降性要求 则从新点出发加大步长 继续搜索 否则 从新点出发缩小步长 继续搜索 直至函数值不再下降且满足约束条件 125 三 计算步骤1 选择一个可行初始点X 0 2 生成N个n维随机单位向量ej3 计算出N个随机点Xj 4 求出XL 生成可行搜索方向S k 若时 还不能找到可行搜索方向 则计算结束 约束最优解X X k 5 从X k 出发 沿可行搜索方向S k 搜索 直至搜索到一个满足全部约束条件 且目标函数值不再下降的新点X k 1 6 收敛检查 满足条件时 迭代结束 约束最优解X X k 1 否则 转步骤2 126 127 二 算法1 形成初始复合形 1 在设计变量少 约束函数简单的情况下 由设计者决定k个可行点 构成初始复合形 2 当设计变量较多或约束函数复杂时 由设计者决定k个可行点常常很困难 这时可采用以下方法生成初始复合形 1 选定一个可行点作为初始顶点 控制初始复合形的位置 其余的k l个可行点用随机法产生 各顶点按下式计算 复合形的第k个顶点 设计变量的上 下限 0 1 区间内的伪随机数 128 2 用式 2 计算得到的k l个随机点不一定都在可行域内 因此要设法将非可行点移到可行域内 通常采用的方法如下 先求出可行域内q个顶点的中心XC 然后将非可行点向中心点XC移动 得新点一般取 若某一点仍为不可行点 则利用上式 使其继续向中心点移动 只要中心点为可行点 k l个点经过上述的处理后 最终全部成为可行点 并构成初始复合形 3 由计算机自动生成初始复合形的全部顶点 其方法是首先随机产生一个可行点 然后按第二种方法产生其余的k l个可行点 这种方法对设计者来说最为简单 但因初始复合形在可行域内的位置不能控制 可能会给以后的计算带来困难 129 2 复合形法的搜索方法和计算步骤 1 计算各顶点函数值 Fi F Xi 比较函数值的大小 确定最好点XL 最差点XH 次差点XG 2 计算XH点之外各点的 重心 XC 130 3 如果XC在可行域内 则沿XHXC方向上作XH点相对于XC点的反射点XR XR XC XC XH 式中 反射系数 一般取 1 3 判别反射点XR是否为可行点 如在可行域外 则将 减半 重新计算反射点 直至满足全部约束 4 如果中心点XC不在可行域之内 可行域则可能为非凸集 如图 为了将XC移至可行域内 以XC和XL为界的超正方体 重新利用伪随机数产生k个新的顶点 构成新的复合形 算法和计算步骤见形成初始复合形一节 此时 变量的上 下限修改为 若xLi xCi i 1 2 n 则 i 1 2 n 否则相反 重复 1 2 直至XC及XH点相对于XC点的反射点XR都进入可行域 5 计算F XR 如果F XR F XH 则用XR代替XH构成新单纯形 转入 1 开始下一轮搜索 否则继续 6 131 6 如果F XR F XH 则将 减半 重新计算XR 直至F XR F XH 若F XR F XH 且XR为可行点 转 5 若经过若干次 减半的计算 使 值小于给定