第二章 优化设计.ppt

第2章优化设计 OptimalDesign 进行最优化设计时 首先必须将实际问题加以数学描述 形成一组由数学表达式组成的数学模型 然后选择一种最优化数值计算方法和计算机程序 在计算机上进行寻优运算求解 得到一组最佳的设计参数 这组设计参数就是设计的最优解 例2 1如图2 1所示 有一圆形等截面的销轴 一端固定 一端作用着集中载荷F 1000N和转矩T 100N m 由于结构需要 轴的长度l不得小于8cm 已知销轴材料的许用弯曲应力 W 120MPa 许用扭转切应力 80MPa 允许挠度 f 0 01cm 密度 7 8t m3 弹性模量E 2 10580MPa 下面通过三个简单的优化设计实例 说明优化数学模型的一般形式及其有关概念 图2 1圆形等截面的销轴 现要求在满足使用要求的条件下 试设计一个用料最省 销轴质量最轻 的方案 2 1 2优化设计的数学模型 解 根据上述问题 该销轴的力学模型是一个悬臂梁 设销轴直径为d 长度为 体积为V 则该问题的物理表达式如下 可见销轴用料取决于其直径d和长度 这是一个合理选择d和而使体积V最小的优化设计问题 2 满足的条件 强度条件 弯曲强度 扭转强度式 刚度条件 挠度表达式 1 销轴用料最省 即体积最小 结构尺寸边界条件 将题意的有关已知数值代入 按优化数学模型的规范形式 可归纳为如下数学模型 设 设计变量 目标函数的极小化 约束条件 综上所述 这是一个具有4个约束条件的二维非线性的约束优化问题 例2 2现用薄钢板制造一体积为5 长度不小于4m的无上盖的立方体货箱 要求该货箱的钢板耗费量最少 试确定货箱的长 宽和高的尺寸 例2 2现用薄钢板制造一体积为5 长度不小于4m的无上盖的立方体货箱 要求该货箱的钢板耗费量最少 试确定货箱的长 宽和高的尺寸 解 分析可知 钢板的耗费量与货箱的表面积成正比 设货箱的长 宽 高分别为 货箱的表面积为S 则该问题的物理表达式为 1 货箱的钢板耗费量 即货箱的表面积用料 最少 可见货箱的表面积取决于货箱的长度 宽度和高度 2 满足的条件 按优化数学模型的规范形式 可归纳为如下数学模型 设计变量 目标函数的极小化 约束条件 由等式约束条件 该问题的优化数学模型应写为 设计变量 目标函数的极小化 约束条件 这样 使该优化问题的数学模型更为准确 精炼 二 优化问题的分类优化问题按照目标函数的性质和约束条件可分为无约束问题和有约束问题两大类 无约束问题按照目标函数包含的单变量或多变量来分类 解无约束问题 基本上有两种方法 直接搜索法 如Powell法 单纯形法等梯度法 需要有目标函数及其导数的解析式有约束类型有三种类型 线性目标函数和线性约束 线性规划 要求目标函数和约束条件都是线性函数 整数规划 限制一些变量取离散或整数值 非线性的目标函数和线性约束 二次规划 目标函数是二次函数 凸规划 目标函数是特定的非线性函数 满足凸性特征 线性分式规划非线性目标函数和非线性约束条件 变换法 线性逼近法 直接搜索法三 优化设计的数学模型1 识别要确定的未知变量 设计或决策变量 并用代数符号表示它们2 识别目标或判别标准 并将其表示为要最大化或最小化的函数3 识别问题的约束或限制 并将它们表示成未知变量的线性或非线性的等式或不等式组 例2 3某车间生产甲 乙两种产品 生产甲种产品每件需使用材料9kg 3个工时 4kw电 可获利润60元 生产乙种产品每件需用材料4kg 10个工时 5kw电 可获利120元 若每天能供应材料360kg 有300个工时 能供200kw电 试确定两种产品每天的产量 以使每天可能获得的利润最大 例2 3某车间生产甲 乙两种产品 生产甲种产品每件需使用材料9kg 3个工时 4kw电 可获利润60元 生产乙种产品每件需用材料4kg 10个工时 5kw电 可获利120元 若每天能供应材料360kg 有300个工时 能供200kw电 试确定两种产品每天的产量 以使每天可能获得的利润最大 每天实际消耗的材料 工时和电力可分别用以下约束函数表示 解 这是一个生产计划问题 可归结为既满足各项生产条件 又使每天所能获得的利润达到最大的优化设计问题 设每天生产的甲 乙两种产品分别为件 每天获得的利润可用函数表示 即 于是上述生产计划问题的优化数学模型应写为 设计变量 目标函数的极小化 约束条件 工时约束 电力约束 材料约束 由于目标函数和所有约束函数均为设计变量的线性函数 故此优化问题属线性约束优化问题 从以上三个实例可以看出 优化设计的数学模型需要用设计变量 目标函数和约束条件等基本概念才能予以完整的描述 可以写成以下统一形式 求设计变量 2 1 使极小化函数 2 2 满足约束条件 其中 称为不等式约束条件 称为等式约束条件 若用向量 表示设计变量 用min max 表示极小化和极大化 s t subjectedto的英文缩写 表示 满足于 m p 分别表示不等式约束和等式约束的个数 当涉及问题要求极大化f X 目标函数时 只要将式中目标函数改写为 f X 即可 因为和具有相同的解 同样 当不等式约束为 时 只要将不等式两端同乘以 1 即可得到 的一般形式 一个完整的规格化的优化数学模型应包含有三部分内容 即设计变量X 目标函数 约束条件和 它们又被称为 优化数学模型的三要素 下面就优化数学模型三要素的有关问题说明如下 在优化设计过程中需要调整和优选的参数 称为设计变量 可表示为 由于实际工程设计对象的不同 则选取的设计变量也就不同 它可以是几何参数 如零件外形尺寸 截面尺寸 机构的运动尺寸等 也可以是某些物理量 如零部件的重量 体积 力与力矩 惯性矩等 还可以是代表机器工作性能的导出量 如应力 变形等 设计变量是一组相互独立的基本参数 一般用向量X来表示 设计变量的每一个分量都是相互独立的 以n个设计变量为坐标轴所构成的实数空间称为设计空间 或称n维实欧式空间 用Rn表示 四 设计变量 设计变量的个数 称为维数 自由度 它决定了优化问题的大小范围 当 n 2 10为小型优化问题 n 10 50为中型优化问题 n 50为大型优化问题 设计变量可分为连续变量和离散变量 五 约束条件 约束条件是设计变量选取的限制条件 或称设计约束 按照约束条件的形式不同 约束有不等式和等式约束两类 一般表达式为 不等式约束 等式约束 按照设计约束的性质不同 约束又可分为如下两类 性能约束 是根据设计性能或指标要求而确定的一种约束条件 例如零件的工作应力 变形的限制条件以及对运动学参数如位移 速度 加速度值的限制条件均属性能约束 边界约束 则是对设计变量取值范围的限制 例如对齿轮的模数 齿数的上 下限的限制以及对构件长度尺寸的限制都是边界约束 六 目标函数 目标函数是用来评价设计方案优劣的标准 又称评价函数 它是设计变量的函数 常记为 确定目标函数 是优化设计中最重要的决策之一 因为这不仅直接影响优化方案的质量 而且还影响到优化过程 目标函数可以根据工程问题的要求从不同角度来建立 例如 机械零件设计中的重量 体积 效率 可靠性 几何尺寸 承载能力 机械设计中的运动误差 功率 应力 动力特性 产品设计中的成本 寿命等 优化设计就是要寻求一个最优设计方案 即最优点X 从而使目标函数达到最优值 在优化设计中 一般取最优值为目标函数的最小值 一个优化问题 可以用一个目标函数来衡量 称之为单目标优化问题 也可以用多个目标函数来衡量 称之为多目标优化问题 目标函数可以通过等值线 面 在设计空间中表现出来 现以二维优化问题为例 来说明目标函数的等值线 面 的几何意义 图2 3二维目标函数的等值线 由于每一条曲线上的各点都具有相等的目标函数值 所以这些曲线称为目标函数的等值线 如图2 3所示 当目标函数f x 等于某一值ci i 1 2 时 就可得到一条等值线 它是在设计平面上由f x Ci的无数个设计点X所连成 当f x 为不等的函数值c1 c2 时 可以得到一族等值线 所谓目标函数的等值线 面 就是当目标函数f X 的值依次等于一系列常数 i 1 2 时 设计变量X取得一系列值的集合 对于一个目标函数来说 它可以有无穷多条的等值线 可以说等值线充满了设计空间 由图可见 等值线族反映了目标函数值的变化规律 等值线越向里面 目标函数值越小 对于有中心的曲线族来说 等值线族的共同中心就是目标函数的无约束极小点 故从几何意义上来说 求目标函数无约束极小点也就是求其等值线族的共同中心 等值线有以下几个特点 1 不同值的等值线不相交 2 除极值点外 在设计空间内 等值线不会中断 3 等值线充满整个设计空间 4 等值线分布的疏或密 反应出函数值变化的慢或快 5 一般来说 在极值点附近 等值线近似是同心椭圆族 极值点就是椭圆的中心点 在设计空间内 目标函数值相等点的连线 对于二维优化问题 构成了等值线 对于三维优化问题 构成了等值面 对于四维以上的优化问题 则构成了等值超曲面 a 问题的立体图 b 设计空间关系图图2 6二维优化问题的几何解 真题 2004 设计体积500cm3的圆柱型包装盒 按用料最省的原则要确定其高度H和直径D 其设计变量是 A 重量B 面积C 体积D 直径E 高度 2006 2007 组成优化数学模型的基本要素有 A 设计变量B 目标函数C 极值D 设计空间E 约束条件 ABE 2008 二维线性规则问题maxF X 15x1 20 x2 3 约束条件为g1 X 5x1 2x2 10 g2 X 2x1 4x2 8 g3 X x1 0 g4 X x2 0 其最优值为 A 1 5 1 25 B 0 2 C 4 0 D 1 25 1 5 A 2009 以下优化设计问题是线性规划问题的是 A 目标函数 约束条件 B 目标函数约束条件C 目标函数约束条件D 目标函数约束条件 2009 某小型商店从一电器生产厂家购进电冰箱和电视机分别为X1和X2台 电冰箱每台占地1 5m2 进价500元 台 可获利180元 电视机每台占地1m2 进价1200元 台 可获利210元 在商店现有进货资金2万元 仓库50m2的情况下 该商店电冰箱和电视机应分别购进多少台 才能使利润最大 并把结果进行取整 2010 在介绍有关优化算法时 常常要用到函数的梯度和海森 Hessian 矩阵的概念 这里简要介绍之 1 多元函数的梯度 已知一n元函数 则该函数在点处的梯度可记为 2 19 函数的梯度在优化设计中有着十分重要的作用 由于梯度是一个向量 而梯度方向是函数具有最大变化率的方向 亦即梯度方向是指函数的最速上升方向 而负梯度一则为函数的最速下降方向 如图2 11所示 2 2优化方法的数学基础 略 图2 11梯度方向与等值线的关系 真题 2004 函数在点 3 2 T处的梯度为 2003 函数在点 1 0 T处的梯度为 2007 函数在点 3 2 T处的梯度为 2010 2006 2008 目标函数在点 1 2 T处沿与X轴成60度的方向导数为 2008 函数在点 2 1 T处的梯度的模为 2009 在某点 目标函数值下降最快的方向是函数的方向 负梯度 2 多元函数的海森矩阵 已知一n元函数 则该函数在点的所有二阶偏导数组成的矩阵 称为函数在点的二阶偏导数矩阵或海森 Hessian 矩阵 经常记作 该二阶偏导数矩阵的组成形式如下 2 21 由于n元函数的偏导数有n n个 而且偏导数的值与求导次序无关 所以函数的二阶偏导数矩阵是一个n n阶的对称矩阵 海森矩阵在判别多元函数极值的充分条件以及在牛顿法构造牛顿搜索方向时都有重要用途 2005 F X 为单值 连续 可微且无约束的一元函数 则在点X x 处有极小值的充分条件是 A B C D 2005 函数在极值点处 A 梯度为零矢量B 函数值肯定大于C 梯度为非零矢量D 函数值肯定小于零 2005 对于有n个变量组成的函数 它的Hessian矩阵是n n阶的二阶偏导数 2007 多目标函数F X 在点X 处的梯度 F X 0是极值点存在的 A 一般条件B 充分必要条件C 充分条件D 必要条件 2006 多元目标函数F X 在点X 处的梯度 F X 0是极值点存在的条件 2003 多元函数F X 在点X 处存在极大值的充分必要条件是 在X 处Hessian矩阵 A 等于零B 大于零C 负定D 正定 2006 2007 具有n个变量的函数F X 的Hessian矩阵是n n阶的二阶偏导数矩阵 该矩阵是 A 非对称矩阵B 对称矩阵C 三角矩阵D 分块矩阵 2009 函数的极值点为 2009 对于多元函数 用Hessian矩阵判定其极值点X 的类型 以下说法正确的是 Hessian矩阵正定 X 为极小值点B Hessian矩阵正定 X 为极大值点C Hessian矩阵负定 X 为极小值点D Hessian矩阵负定 X 为极小值点E Hessian矩阵不定 X 为鞍点 2010 函数凹凸的定义 问题 如何研究曲线的弯曲方向 任意弧段位于所张弦的上方 任意点的切线在曲线上方 任意弧段位于所张弦的下方 任意点的切线在曲线下方 凸函数 凹函数 设A x1 f x1 B x2 f x2 则线段AB间的任意点C x y 可表示为 x C 凸函数 凸函数的数学表达式为 定义 如果不等式改为严格不等式 则相应的函数称为严格凸函数和严格凹函数 判断函数f x 为凸函数的充要条件 方法1 若函数f x 在D上具有一阶的连续导数 对任意两点x 1 x 2 f x 为凸函数的充要条件是 恒成立 方法2 若函数f X 在D上具有二阶的连续导数 则f X 为凸函数的充要条件是 H X 处处半正定 凸性形态表现为下凸时 函数为凸函数 凸性表现为上凸时 函数为凹函数 即此二次型为半正定 即H为半正定 若为正定 即去掉等号 则为严格凸函数 H X 为正定 则为严格的凸函数 凸规划对于非线性规划若其中f x 和gu x 均为凸函数 对于 约束为凹函数 则这样的规划问题称为凸规划 2008 2004 判断函数是否为凸函数 5分 3 有约束目标函数极值的存在性目标函数有约束极值还是无约束极值 主要取决于约束条件对极值和极值点的影响 同样的目标函数对于不同的约束条件 可能出现不同的最优值和最优点 其原因在于不同的约束条件限制了设计变量不同的取值范围 有约束最优问题需要解决的问题判断约束极值点存在的条件 判断找到的极值点是全局最优点还是局部最优点 A 无约束最优点为可行域的内点 此时目标函数的最优点就是约束问题的最优点 约束最优点和无约束最优点的相互关系 B 无约束最优点在可行域外 约束问题的最优点是约束边界上的一点 该点是约束边界与目标函数一条等值线 面 的切点 K T Kuhn Tucker 条件 满足K T条件的点称为K T点 对于一般非线性规划问题 K T点一定是约束极值点 但却不一定是全域最优点 一般采用多初始点下的极值点是否都逼近同一点 可看成最优点 的近似方法来判别 但是 对于目标函数为凸函数 可行域为凸集的凸规划问题 K T点一定是全域最优点 这个判别准则称为库恩 塔克条件 其几何意义为 起作用约束的梯度矢量 在设计空间构成一个椎体 目标函数的负梯度应包含在此椎体内 库恩 塔克条件是约束优化问题极值的必要条件 而不是充分条件 只有目标函数为凸函数 约束函数也是凸函数 或是凹函数 时 即凸规划问题时 其局部最优点就是全局最优点 则库恩 塔克条件是该极值的必要充分条件 例6 用K T条件判断点是否是下列约束优化问题的约束极值点 1 判断约束条件是否是起作用的约束 2003 什么是库恩 塔克条件 其几何意义是什么 库恩 塔克条件 2007 约束优化问题满足约束条件 试用Kuhn Tucker条件判断点是否是约束最优点 2008 已知目标函数约束条件为试用Kuhn Tucker条件判断点和是否为该有约束问题的极值点 2010 2006 2006 迭代过程是否结束通常的判断方法有 A 设计变量在相邻两点之间的移动距离充分小B 相邻两点目标函数值之差充分小C 目标函数的导数等于零D 目标函数梯度充分小E 目标函数值等于零 求解一维目标函数最优解的过程 称为一维优化 或一维搜索 所使用的方法称为一维优化方法 一维优化方法 它不仅可用来解决一维目标函数的求优问题 且常用于多维优化问题在既定方向上寻求最优步长的一维搜索 由前数值迭代法可知 求某目标函数的最优值时 迭代过程每一步的格式都是从某一定点出发 沿着某一使目标函数下降的规定方向搜索 以找出此方向的极小点 这一过程是各种最优化方法的一种基本过程 在此过程中因 已确定 要使目标函数值为最小 只需找到一个合适的步长就可以了 这也就是说 在任何一次迭代计算过程中 当起步点和搜索方向确定之后 就把求多维目标函数极小值这个多维问题 化解为求一个变量 步长因子 的最优值的一维问题 2 3一维优化方法 一维搜索方法主要有 一维搜索方法一般分两步进行 首先在方向上确定一个包含函数极小点的初始区间 即确定函数的搜索区间 该区间必须是单峰区间 然后采用缩小区间或插值逼近的方法得到最优步长 即求出该搜索区间内的最优步长和一维极小点 二次插值 黄金分割法 0 618法 三次插值法等 本节介绍最常用的黄金分割法和二次插值法 根据函数的变化情况 可将区间分为单峰区间和多峰区间 所谓单峰区间 就是在该区间内的函数变化只有一个峰值 即函数的极小值 如图2 18所示 即在单峰区间内的极小值点X 的左侧 函数呈下降趋势 而在极小值点X 的右侧 函数呈上升趋势 也就是说 单峰区间的函数值呈 高 低 高 的变化特征 设区间 1 3 为单峰区间 而 2为该区间内的一点 若有 1 2 3成立 则必有f 1 f 2 f 3 同时成立 图2 18单峰区间 2 3 1黄金分割法 如果函数具有多个极小点 则表现为多峰函数 此时 需要对变量取值范围进行适当的划分 使每一个子空间只包含一个极小点 才能进行一维搜索 一维搜索时 同样需要在每个子空间内寻找单峰区间 注意 该算法的基本思路是源于试探法 通过比较单峰区间内两个插点的函数值 不断舍弃单峰区间的左端或右端一部分 使区间按照固定区间缩短率 缩小后的新区间与原区间长度之比 逐步缩短 直到极小点所在的区间缩短到给定的误差范围内 而得到近似最优解 黄金分割法 又称0 618法 它是一种等比例缩短区间的直接搜索方法 如图2 21所示 为使a b区间缩小 在单峰区间 a b 内插入两个内分点 且满足 并计算它的函数值f 1 f 2 比较它们的大小 可能发生以下情况 1 若f 1 f 2 则由于函数的单峰性 极小点必位于区间 a 2 内 因而可以去掉区间 a2 b 得到缩短了的搜索区间 a a2 如图2 21 a 所示 2 若f 1 f 2 显然 极小点必位于 1 b 内 因而可去掉区间 a 1 得到新区间 1 b 如图2 21 b 所示 图2 21黄金分割法的试探法原理 3 若f 1 f 2 极小点应在区间 1 2 内 因而可去掉 a 1 或 2 b 甚至将此二段都去掉 如图2 21 c 所示 对于上述缩短后的新区间 可在其内再取一个新点 3 然后将此点和该区间内剩下的那一点进行函数值大小的比较 以再次按照上述方法 进一步缩短区间 这样不断进行下去 直到所保留的区间缩小到给定的误差范围内 而得到近似最优解 黄金分割法的内插点选取原则是 每次区间缩短都取相等的区间缩短率 按照这一原则 其区间缩短率都是取 0 618 即该法是按区间全长的0 618倍的关系来选取两个对称内插点 1 2的 图2 220 618法新 旧区间的几何关系 为缩短区间 黄金分割法要求在区间 a b 上对称地取两个内分点 1和 2 设两个对称内分点交错离两端点距离为 则 首次区间缩短率为 再次区间缩短率为 如图2 22所示 设原区间 a b 长度为L 区间缩短率为 1 给定初始单峰区间 a b 和收敛精度 2 在区间 a b 内取两个内插点并计算其函数值 若f1 f2 则取 a 为新区间 而则作为新区间内的第一个试算点 即令 3 比较函数值f1和f2的大小 综上所述 黄金分割法的计算步骤如下 而另一试算点可按下式计算出来 而另一试算点可按下式计算出 若f1 f2 则取 b 为新区间 而作为新区间内的第一个试算点 即令 图2 23黄金分割法的计算框图 4 迭代终止条件判别若满足b a 则转下一步 否则返回步骤 3 进行下一次迭代计算 进一步缩短区间 5 输出最优解 黄金分割法的计算框图 如图2 23所示 2003 函数F X 为在区间 10 20 内有极小值的单峰函数 进行一维搜索时 取两点13和16 若F 13 F 16 则缩小后的区间为 A 10 16 B 10 13 C 13 16 D 16 20 A 2004 在单峰搜索区间 a b 内 任取两个试算点a1 a2 若两点的函数值F a1 F a2 则缩小后的区间为 a1 b 2005 用0 618法求函数的极小值点 初始搜索区间为 20 20 第一步迭代后的新区间为 A 4 72 20 B 20 4 72 C 4 72 20 D 20 4 72 A 2006 2006 有一边长为8cm的正方形铁皮 在四角减去相同的小正方形 折成一个无盖盒子 减去小正方形的边长为多少时铁盒的容积最大 1 建立问题的数学模型 2 设初始搜索区间为 a b 0 3 用0 618法计算两步 解 1 建立数学模型设计变量 减去的小正方形的边长为x目标函数 maxF X 8 2x 2x约束条件 g1 x 2x 8F b1 则新的搜索区间为 ab 0 1 854 第二次迭代在新的搜索区间内a1 a 0 382 b a 0 0 382 1 854 0 0 708b1 1 146F a1 30 691F b1 37 388因F a1 F b1 则新的搜索区间为 ab 0 708 1 854 2007 0 618法在迭代运算过程中 迭代区间不断缩小 其区间缩小率在迭代运算过程中是 A 逐步变小B 不变C 逐步变大D 不确定 B 2009 在长为L的区间 a b 上用黄金分割法进行一维搜索 第一次搜索的两个点为a1 a2 若F a1 F a2 则第二次搜索区间缩小为 A 0 382LB 0 236LC 0 5LD 0 618L B 2010 图2 24二次插值法的原理及区间缩小过程 2 32 为求得 应设法求得式 2 32 中的待定系数B和C 解得 此函数可以很容易地求得它的极小点 令其一阶导数等于零 即 由上可知 在已知一个单峰搜索区间内的三点值后 便可通过二次搜值方法求得极小点的近似值 由于在求时 是采用原函数的近似函数 因而求得的不一定与原函数的极值点重合 见图2 24 为了求得满足预定精度要求的原函数的近似极小点 一般要进行多次迭代 为此 可根据前述的序列消去原理 在已有的四个点及中选择新的三个点 得到一个缩小了的单峰区间 并利用此单峰区间的三个点 再一次进行插值 如此进行下去 直至达到给定的精度为止 二次插值法的计算步骤如下 1 给定初始搜索区间和计算精度 2 在区间内取一内点 有下面两种取法 等距原则取点 不等距原则取点 计算三点的函数值 3 计算二次插值多项式的极小点与极小值 图2 25二次插值法程序框图 2005 在单峰搜索区间 x1 x3 内采用二次插值法求函数极小值 在区间内取一点x2作二次插值计算得 若x2F 则新区间为 A x1 B x1 x2 C x2 x3 D x3 C 用二次插值法求解目标函数F X x2 10 x 36的极小值 给定初始区间 x1 x3 0 10 允许误差为0 001 用二次插值法求解目标函数F X x2 10 x 36的极小值 给定初始区间 x1 x3 0 10 允许误差 为0 001解 取x2 x1 x3 2 5计算三点的函数值F1 36F2 11F3 36进行插值计算 5因 迭代终止最优解 解析法这类方法是需要利用函数的一阶偏导数甚至二阶偏导数构造搜索方向 如梯度法 共轭梯度法 牛顿法和变尺度法等 由于需要计算偏导数 故这类方法计算量大 但收敛较快 直接法这类方法是仅利用迭代点的函数值来构造搜索方向 如坐标轮换法 powell法和单纯形法等 由于只需要计算函数值 对于无法求导或求导困难的函数 则这类方法就有突出的优越性 但是其收敛速度较慢 图2 29基本鲍威尔法的迭代过程 取初始点作为迭代计算的出发点 即令 先沿坐标轴的方向作一维搜索 求得此方向上的极小点 作一维搜索 求得该方向上的极小点 然后 再沿坐标方向 二维问题基本鲍威尔法的迭代过程 如图2 29所示 上式中各符号意义 如图2 30所示 图2 30修正鲍威尔法的方向淘汰 实践证明 上述修正鲍威尔法保证了非线性函数寻优计算可靠的收敛性 图2 31鲍威尔法的计算框图 2003 对于函数F x x12 2x22 从初始点x 0 1 1 T出发 沿方向s 0 1 2 T进行一维搜索 最优步长因子为 A 10 16B 5 9C 9 34D 1 2 B 真题 2005 2007 Powell法是以方向作为搜索方向的 2007 如果目标函数的导数求解困难时 适宜选择的优化方法为 A Powell法B 梯度法C 变尺度法D 共轭梯度法 共轭 A 2008 求解无约束优化问题时 若目标函数的导数计算困难或者不存在连续的一阶偏导数 则下列方法效果最好的为 A 复合形法B Powell法C 梯度法D 变尺度法 2008 下列矢量中 与S0 1 0 T关于共轭的矢量为 A S1 0 1 TB S2 1 1 TC S3 1 3 TD S4 3 1 T C 2007 为什么选用共轭方向作为搜索方向可以取得良好的效果 2009 Powell法在每一轮形成新的搜索方向时存在何种问题导致不收敛 如何修正 2010 二 梯度法 1 基本思想 梯度方向是函数值增加最快的方向 而负梯度方向是函数下降最快的方向 所以梯度法以负梯度方向为搜索方向 每次迭代都沿着负梯度方向一维搜索 直到满足精度要求为止 因此 梯度法又称为最速下降法 最速下降法 设在某次迭代中已取得迭代点X k 从该点出发 取负梯度方向为搜索方向S k 即 这样 第k 1次迭代计算所得的新点为 上式即为梯度法迭代公式 因为X k 已知 故和不难求出 只要知道步长后 就可以得到新点X k 1 由于每次迭代能保证 如此反复计算 最后总能达到最优点X 为了使目标函数值在搜索方向S k 上获得最多的下降 每次迭代都进行一维搜索求最优步长 即求 2 迭代步骤 1 任选初始点X 0 计算精度 令k 0 2 计算和 3 收敛判断 A 若 则X k 为近似最优点 停止迭代 输出最优解和 B 若 则转下一步继续迭代 4 令 5 确定最优步长因子 使6 计算 7 令k k 1 转2 例10 用梯度法求函数的极小值 初始点 计算精度 举例用梯度法求函数的极小值 初始点 计算精度 解 1 计算梯度 2 计算函数在点的梯度及梯度的模 3 因为 不满足精度指标 4 从出发 沿着方向一维搜索 将代入目标函数并求其极小值式中为单变量 的一维函数 令 所以求得一维优化的最优步长 5 新点 6 计算目标函数在点的梯度及梯度的模由于已满足精度要求 故停止迭代下去 得到最优解为 解 1 如果转 2 否则转 5 例11 用一阶梯度法求目标函数f X x12 4x22在初始点X 0 22 T 迭代精度 1 10 2下的最优解 2 3 并转 1 4 第7次迭代后 成立 停止迭代 5 取时 f X 2 596 10 6 0 比较上面两个例题 能得出什么样的结论 梯度法的特点 负梯度方向只是函数值在点X k 的邻域内下降最快的方向 离开该邻域以后函数值不一定下降最快 因此 采用负梯度方向 从局部看函数值下降快 从全局看却要走很多弯路 因此 梯度法的收敛速度较慢 梯度法的迭代过程 每相邻两步的搜索方向是垂直的 也就是说梯度法的迭代路线是呈锯齿形前进的 梯度法迭代过程中 当迭代点离理论极小点较远时 一次迭代的函数值下降量大 迭代点离极小点越近 函数值下降的速度就越慢 因此 梯度法常与其它优化方法结合使用 即第一步采用梯度法 后面采用其它的方法确定搜索方向 梯度法的收敛速度与目标函数的性质有关 如果目标函数的等值线 面 为同心圆 球 则无论从哪里出发 只需要一次搜索就能达到极小点 3 梯度法 一 梯度方向 可取最优步长或下降步长 二 基本思想 梯度方向是目标函数上升最快的方向 负梯度方向则是最速下降方向 2 迭代公式 1 沿负梯度方向搜索 三 终止判别条件 共轭梯度法 共轭梯度法是二次收敛的 对二元二次函数仅需两次搜索便可达到极值点 2 迭代步骤 1 给定初始点X 0 令k 0 2 计算令 3 计算新的迭代点 迭代公式 令求最优步长 4 计算 令共轭系数 5 第二次搜索的方向 2008 2005 2004年 1 库恩塔克条件 2006 有一边长为8cm的正方形铁皮 在四角减去相同的小正方形 折成一个无盖盒子 减去小正方形的边长为多少时铁盒的容积最大 1 建立问题的数学模型 2 设初始搜索区间为 a b 0 3 用0 618法计算两步 2 黄金分割法 解 1 建立数学模型设计变量 减去的小正方形的边长为x目标函数 maxF X 8 2x 2x约束条件 g1 x 2x 8F b1 则新的搜索区间为 ab 0 1 854 第二次迭代在新的搜索区间内a1 a 0 382 b a 0 0 382 1 854 0 0 708b1 1 146F a1 30 691F b1 37 388因F a1 F b1 则新的搜索区间为 ab 0 708 1 854 3 用二次插值法求解目标函数F X x2 10 x 36的极小值 给定初始区间 x1 x3 0 10 允许误差为0 001 解 取x2 x1 x3 2 5计算三点的函数值F1 36F2 11F3 36进行插值计算 5因 迭代终止最优解 4 Powell法 5 共轭梯度法 四 变尺度法 梯度法构造简单 只用到一阶偏导数 计算量小 迭代初期收敛速度快 但当迭代点到最优点附近时收敛速度极慢 变尺度法是在梯度法和牛顿法的基础上发展起来的一种优化方法 用得较多的是DFP Davidon Fletcher Powell 变尺度法 1 基本思想 牛顿法收敛很快 对二次函数只需迭代一次就能达到最优点 对非二次函数也能较快达到最优点 但牛顿法计算量和存储量偏大 而且某些函数可能根本无法计算二阶偏导数矩阵及其逆阵 为了综合梯度法和牛顿法的优点 扬长避短 产生了变尺度法 变尺度法的搜索方向为 变尺度法的基本迭代公式为 DFT变尺度法在函数F X 的梯度矢量容易求出的情况下 非常有效 特别适用于高维 n 100 问题 其收敛快 效果好 求解无约束问题的主要方法有 第五节有约束优化设计的方法 有约束优化设计的方法根据对约束条件的处理方法不同 分为 直接法和间接法两大类 直接法的基本思想是设法使每一次的迭代点都在可行域内 并逐步降低目标函数值 直到最后得到一个在可行域内的约束最优解 即在迭代过程中 搜索方向和迭代步长都要经过可行性和适用性条件的检查 属于直接法的有 复合形法 简约梯度法等 间接法的基本思想是把有约束的问题通过一定形式的变换 转化成无约束优化问题 然后用无约束方法求解 属于此类常见的有罚函数法 消元法 拉格朗日乘子法 等 一 复合形法 基本思路在可行域内选取若干初始点并以之为顶点构成一个多面体 复合形 然后比较各顶点的函数值 去掉最坏点 代之以好的新点 并构成新的复合形 以逼近最优点 如图所示基本过程 映射点 去除坏点 先计算除最坏点外各顶点的几何中心 然后再作映射计算 收缩 保证映射点的 可行 与 下降 X1为最坏点 映射系数常取 若发现映射点不适用 可行 则将减半后重新映射 二 初始复合形的构成 1 复合形顶点数K的选择 一 复合形法对于n维问题 复合形法顶点数不能少于n 1个 通常取 对于二维问题 复合形为由三 即n 1 个顶点构成的三角形 或为由四个顶点构成的四边形 对于三维问题 复合形为由四个顶点构成的四面体 或由五个或六 即2n 个顶点构成的五面体 对于n维问题 复合形则为由n 1 2n个顶点构成的一个不规则的多面体 2008 二 约束优化问题的间接求解法 惩罚函数法 惩罚函数法是求解约束优化问题的间接法的一种 它是将目标函数和约束条件构造成一个新的目标函数 将约束最优化问题转化为无约束最优化问题 然后利用各种有效的无约束最优化解法求解而得到约束最优化的近似解 这是一种使用广泛的有效的间接解法 1 惩罚函数法的基本思路 将不等式约束 等式约束和待定系数 加权因子 经加权转化后 与原目标函数f X 一起组成一个新的目标函数 惩罚函数 然后对它求最优解 把其中不等式和等式约束函数值经加权处理后 和原目标函数结合新的目标函数 惩罚函数中的后两项称为惩罚项 惩罚项满足下列要求 当满足约束条件时 惩罚项的值很小或为0 当不满足约束条件时 惩罚项的值很大 即对不满足约束条件的点的函数值进行惩罚 新目标函数中 称为惩罚因子或加权因子 它们是一系列的按一定规则变化的值 当按照一定的法则改变的数值时 就构成了一系列的无约束优化问题 求解这些优化问题可得到一系列的无约束的迭代点 使其一步步迭代 不断地逼近原约束优化问题的最优解 数学上可以证明 当惩罚函数满足 时 上述惩罚函数在过程中产生的极小点序列将逐渐逼近于原约束优化问题的最优解 即 惩罚函数法又称序列无约束极小化方法 常称SUMT sequentialunconstrainedminimizationtechnique 根据惩罚项的构成形式 惩罚函数法可分为 外点惩罚函数法内点惩罚函数法混合惩罚函数法 2 内点惩罚函数法 1 特征该法是求解不等式约束最优化问题的一种有效的方法 但不能处理等式约束 其特点是将新的无约束目标函数 惩罚函数定义在可行域内 在可行域内 序列迭代点逐步逼近约束边界上的最优点 这样 求解无约束问题时的搜索点总是保持在可行域内部 内点法求解时 惩罚函数的形式为 惩罚项的特点 当迭代点在可行域内且远离边界时 两种惩罚项和都是很小的正值 这时候惩罚作用很小 当迭代点靠近边界时 则惩罚项的值急剧增大并趋向无穷大 于是惩罚函数值也随之急剧增大并趋向无穷大 这样等于在约束边界筑起一道 屏障 使迭代点始终不能超出可行域 惩罚因子的特点 内点惩罚函数法的惩罚因子r k 是一个递减的正数序列 c是惩罚因子的缩减系数 即当惩罚因子时 才能求得在约束边界上的最优解 2 初始惩罚因子r 0 的选择初始惩罚因子的选择会影响到迭代计算能否正常进行以及计算效率的高低 r 0 的值应适当 若r 0 太大 则开始几次构造的惩罚函数的无约束极值点会离约束边界很远 将增加迭代次数 使计算效率降低 若r 0 太小 惩罚函数中的障碍项的作用就会很小 使惩罚函数性态变坏 甚至难以收敛到原约束目标函数的极值点 目前 还没有一定的有效方法 往往要经过多次试算 才能确定一个适当的r 0 多数情况下 一般取r 0 1 然后根据试算的结果 加以调整 或按经验公式取值 使惩罚项和原目标函数在惩罚函数中的作用相当 3 罚因子缩减系数C的选择在构造序列惩罚函