现代设计方法5 优化设计

优化设计 第五章优化设计 传统机械设计中 存在选优的思想 受时间 条件的限制 计算机应用前用数学极小化处理简单问题 随着1946年第一台计算机问世 传统设计转化为优化设计方法 优化设计是以数学规划理论为基础 以计算机为工具优选设计参数的一种现代设计方法 5 1优化设计的数学模型 下面举例说明 用薄钢板制造一体积为5m3 长度不小于4m不带上盖的货箱 要求该货箱的钢板耗费量最小 试确定货箱的长X1 宽X2 高X3 解 钢板的耗费量与货箱的表面积成正比 优化设计的目标是钢板的耗费量最少 即货箱的表面积S最小 不带盖的货箱表面积S X1 X2 2 X2 X3 X1 X3 S是X1 X2和X3的函数 称为目标函数 参数X1 X2和X3称为设计变量 优化设计就是恰当地选择这些参数 设计变量 使货箱表面积S 目标函数 达到最小 选择这些参数受到货箱体积和长 宽 高限制 X1 X2 X3 5 X1 4 X2 0 X3 0以上限制设计变量X1 X2 X3的表达式 称为约束条件 例 直齿圆柱齿轮副的优化设计 已知 传动比i 转速n 传动功率P 大小齿轮的材料 设计该齿轮副 使其重量最轻 分析 1 圆柱齿轮的体积 V 与重量 W 的表达 2 设计参数确定 模数 m 齿宽 b 齿数 z 3 设计约束条件 a 大齿轮满足弯曲强度要求 b 小齿轮满足弯曲强度要求 c 齿轮副满足接触疲劳强度要求 d 齿宽系数要求 e 最小齿数要求 例问题的数学表达 设计变量 x mzb T设计目标 minW rpb mz 2 miz 2 4约束条件 g1 x sF1 s F1 0g2 x sF2 s F2 0g3 x sH s H1 0g4 x b 1 2mz 0g5 x 17 z 0 建立优化设计问题的数学模型步骤 1 根据设计要求 应用专业范围内的现行理论和经验等 对优化对象进行分析 必要时 需要对传统设计中的公式进行改进 并尽可以反映该专业范围内的现代技术进步的成果 2 对结构诸参数进行分析 以确定设计的原始参数 设计常数和设计变量3 根据设计要求 确定并构造目标函数和相应的约束条件 有时要构造多目标函数4 必要时对数学模型进行规范化 以消除诸组成项间由于量纲不同等原因导致的数量悬殊的影响 5 1 1 数学模型的一般形式 优化设计的数学模型由设计变量 目标函数和约束条件三部分组成 统一形式 求变量 x1 x2 xn使极小化函数 f x1 x2 xn 满足约束条件 gu x1 x2 xn 0 u 1 2 m 不等式约束条件hv x1 x2 xn 0 v 1 2 p 等式约束条件 设计变量可用向量表示 X x1 x2 xn TX Rn向量X属于n维实欧氏空间s t subjectto 表示 满足于 优化设计的数学模型可表达为如下的标准形式 minf X X Rns t gu X 0 u 1 2 m hv X 0 v 1 2 p 求极大时将目标函数写为 f X 即可 同样 当不等式约束条件中的不等号为 0 时 只要将不等式两端同时乘以 1 即可得到上述标准形式 最优化问题也称数学规划问题 若目标函数和约束函数均为设计变量的线性函数时 称此设计问题为线性优化问题或线性规划问题 说明 1 设计变量与设计空间选择与目标函数 约束函数密切相关 能表达设计对象特征的独立参数和尺寸 n个设计变量x1 x2 xn 相互独立 形成向量X x1 x2 xn T的全体集合构成一个n维实欧氏空间 称设计空间xn n称为设计空间的维数 n 2时设计空间为二维平面 5 1 2 优化设计的基本要素 约束条件 对设计变量取值时的限制条件 分为 等式约束 hv X 0 v 1 2 p 不等式约束 gu X 0 u 1 2 m 约束边界所包围的区域是设计空间中满足所有不等式约束条件的部分 在这个区域中所选择的设计变量是允许的 称为设计可行域 由是否满足约束条件将设计点分为可行点 内点 和非可行点 外点 2 约束条件与可行域 g1 X x1 x2 2 0g2 X x12 x2 1 0g3 X x1 0 例 g3 x 0 将所追求的设计目标用设计变量的形式表达出来 称为建立目标函数 一组设计变量值在设计空间确定一个设计点 对应这一点有确定的函数值 反之 当函数为某一定值时 如f X c 则可有无限多组设计变量X1 X2 Xn值与之对应 即有无限多个设计点时对应着相同的函数值 因此这些点在设计空间中将组成一个点集 将此点集称为等值曲面或等值超曲面 若为二维设计空间则称为等值域 3 目标函数与等值域 简单二维问题 在平面内作出约束可行域 画出目标函数的等值域 找出最优点 步骤 确定设计空间 约束可行域 目标函数等值线 最优点例 minf X x12 x22 4x1 4s t g1 X x1 x2 2 0g2 X x12 x2 1 0g3 X x1 0 5 1 3优化问题的图解法 图解法 minf X x12 x22 4x1 4s t g1 X x1 x2 2 0g2 X x12 x2 1 0g3 X x1 0 x1 x2 0 1 2 3 4 5 1 2 3 4 g3 x g2 x g1 x 6 5 2优化方法的数学基础 5 2 1梯度 求解出数的最速下降方向 定义下列向量 为函数f X 在X k 点的梯度 简记为 f 也可记作gradf X k 1 函数在一点的梯度是对设计变量Xi i 1 2 n 一阶偏导组成的列向量 表示函数在X k 点的最陡上升方向 是函数的一种局部性质 反映X k 邻近函数的性质 梯度大小是其模长 2 梯度向量 f X k 与过X k 点的等值线 或等值面 的切线是正交的 函数的梯度 f具有如下几个性质 函数的梯度 f具有如下几个性质 3 负梯度向量 f X k 是函数在X k 点的最速下降方向 例 求二元函数f x1 x2 x12 x22 4x1 2x2 5在X0 2 2 T处的梯度及梯度的模 f X 的泰勒二阶近式 其中 2f X k 是由函数在点X k 的所有二阶偏导组成的矩阵 称为函数f X 在点X k 的二阶导数矩阵或Hessian矩阵 H X k 5 2 2多元函数的泰勒展开 函数的近似表达式 函数的二阶偏导值对于变量的偏导次序无关 是一n n阶实对称矩阵 取其前二项 可得函数的泰勒线性近似式 f X f X k f X k T X X k 解 f X 1 3 例 用泰勒展开将函数f X x13 x23 3x12 3x22 9x1在点X 1 1 1 T简化成线性函数和二次函数 代入得简化的线性函数 二次项 简化的二次函数 f X 3x2 6 6 x1 1 2 6x12 12x1 3x2X 1 1 1 T代入线性二次函数都等于 3 与原函数相等 5 2 3 二次函数 形式 f X XTHX 2 BX CH 2 2阶常数矩阵C 常数向量XTHX称为二次型 H称二次型矩阵 相当于函数的二阶导数矩阵 对于非零向量X 若XTHX 0H正定XTHX 0H半正定XTHX 0H负定XTHX 0H半负定XTHX 0H不定若H是正定的 f X 称正定二次函数 矩阵的正定负定分类 判定矩阵正定或负定的方法一般是检验矩阵H的各主子式的行列式之值 若各阶主子式值均大于0 则正定 若各阶主子式值呈负正交替变化 则负定 例 2 0各阶主子式大于0是正定矩阵 无约束优化问题的极值条件 在X 处取得极值 其必要条件是 即在极值点处函数的梯度为n维零向量 为了判断从上述必要条件求得的X 是否是极值点 需建立极值的充分条件 根据函数在X 点处的泰勒展开式 考虑上述极值必要条件 可得相应的充分条件 X 处取得极值充分条件 即要求H X 各阶主子式均大于零 1 概念 对于多变量 多约束非线性优化问题 采用数值迭代法 对于极小化问题 采用下降迭代法 初始X 0 产生点列 X 0 X 1 X 2 X k X k 1 对应目标函数 f X 0 f X 1 f X k f X k 1 下降 且limX k X 目标函数极小点 满足此条件的下降迭代算法具有收敛性 称点列收敛于极小点X 5 2 4下降迭代法 优化迭代算法格式 X k 1 X k aS k 式中S k 搜索方向a 步长因子 2 格式 X k 1 取S k 上的一维极小点 对应于最优步长因子ak 1 给定初始点X k 和收敛精度e 2 选取搜索方向S k 3 确定步长因子ak得到X k 1 4 收敛判断X k 1 满足收敛精度 X k 1 作为最优点终止 否则重复 2 故迭代算法的核心在于 1 确定搜索方向S k 2 确定步长因子a 3 给定收敛准则 5 3一维搜索法 求解一维目标函数f a 的极小点和极小值的数值迭代方法称为一维搜索方法 从点X k 出发 在方向S k 上的一维搜索数学表达式 minf X k aS k f X k akS k X k 1 X k akS k 一维优化目的是在既定的X k 和S k 下寻求最优步长a k 使迭代产生新点X k 1 的函数值最小 一维优化一般分为两大步 1 确定初始搜索区间 a b 该区间应是包括一维函数极小值点的单峰区间 2 在搜索区间 a b 内寻找极小点 进退法思路 由单峰函数性质可知 在极小点a 左边函数值应严格下降 在极小值点右边函数值应严格上升 由此 可以某一个给定的初始点x0出发 以初始步长h0沿着目标函数值下降方向 逐步前进 或后退 直至找到相继的3个试点的函数值按大 小 大变化为止 5 3 1 确定搜索区间的方法 进退法 进退法确定搜索区间的步骤如下 1 给定初始点x0和初始步长h 2 令x1 x0 x2 x1 h得两试点x1 x2计算函数值f1 f x1 f2 f x2 3 比较f1和f2 存在两种情况 f1 f2f1 f2 若存在f1 f2 取第3个试点x3 x2 h 计算函数值f3 f x3 比较f2与f3 若f2 f3 则找到了x1 x2 x3的函数值按大 小 大变化的要求 故有搜索区间 a b x1 x3 若f2 f3 将步长加倍 令h 2h x1 x2 x2 x3 x3 x2 h 如此重复该过程 总能找到相继3试点的函数值符合 大 小 大 变化的要求 取左端点为a 右端点为b 从而找到搜索区间 a b f3 x1 x f x 0 h h f2 f1 x3 x2 2h 若f2 f3 将步长加倍 令h 2h x1 x2 x2 x3 x3 x2 h 如此重复该过程 总能找到相继3试点的函数值符合 大 小 大 变化的要求 取左端点为a 右端点为b 从而找到搜索区间 a b f3 x1 x f x 0 h h f2 f1 x3 x2 若f2 f1作后退计算 令h h 将x1 f1与x2 f2对调 并取第3个试点x3 x2 h 计算其函数值f3 f x3 比较对调后的f2与f3 x1 x f x 0 h f2 f1 x2 若f2 f3 a b x3 x1 若f2 f3 将步长加倍 继续作后退运算 令h 2h x1 x2 x2 x3 x3 x2 h 继续比较f2与f3 直到相继3个试点的函数值按 大 小 大 变化为止 相应的区间为 x3 x1 f3 x1 x f x 0 h h f2 f1 x3 x2 找到搜索区间后 便可运用一维优化算法在区间内找到极小点 例 用进退法确定f x x2 7x 10的初始搜索区间 设初始点x0 0 初始步长h 1 解 x1 x0 0f1 f x1 10 x2 x1 h 1f2 f x2 4比较f1 f2 因f2f3 作前进运算h 2 1 2x1 x2 1f1 f2 4x2 x3 2f2 f3 0 x3 x2 h 4f3 f x3 2 比较f2 f3 因f2 f3 作前进运算h 2 2 4x1 x2 2f1 f2 0 x2 x3 4f2 f3 2x3 x2 h 8f3 f x3 18此时 x1 x2 x3三点的函数值出现了大小的变化 故a x1 2 b x3 8求得初始搜索区间 a b 2 8 是通过不断缩短搜索区间的长度来寻求一维函数f x 的极小点 原理是 在搜索区间 a b 内取两点x1和x2 x1f x2 极小点在x1和b间 消去区间 a x1 得到缩小后新区间 x1 b 不断重复上述过程 当区间长度b a e时 便可将区间中一点作为极小点 缩小区间求极小点原理 黄金分割法又称0 618法 它是按照对称原则取中间点而缩小区间的一种一维搜索算法 设 a b 内中间点x1和x2由一下方式产生 x1 a 1 l b a x2 a l b a 若缩小一次后的新区间为 a x2 新旧区间内中间插入点应具有相同的位置关系 则原区间内点x1和新区间内的点x2为同一点 则有l2 1 l 5 3 2黄金分割法 基本步骤 在搜索区间 a b 内按如下规则取两点 x1 a 0 382 b a x2 a 0 618 b a 函数值f1 f x1 f2 f x2 比较f1与f2的大小 1 若f1 f2 极小点必在区间 x1 b 内 消去区间 a x1 令a x1 产生新区间 x1 b 区间收缩了一次 新区间的x1点与原区间x2点重合 令x1 x2 f1 f2 这样可节省一次函数计算 2 若f1 f2 极小值点在区间 a x2 内 消去区间 x2 b 令b x2产生新区间 a b 区间缩短一次 同时 新区间x2点与原区间的x1点重合 令x2 x1 f2 f1 当缩短的新区间长度小于等于某一精度e 即b a e时取为近似极小点x a b 2 L II 黄金分割法的区间收缩率l 每次缩小所得的新区间长度与缩小前区间长度之比 称为区间收缩率 以l表示 黄金分割法收缩率保持不变 0 6180 618n b a e 解 1 采用上节所求初始区间 a b 2 8 取两计算点并计算出数值 x1 a 0 382 b a 4 292f1 f x1 1 622736x2 a 0 618 b a 5 708f2 f x2 2 625264 2 比较函数值 缩短搜索区间f1 f2b x2 5 708x2 x1 4 292f2 f x2 1 622736x1 a 0 382 b a 3 416456f1 f x1 2 24030 例 采用黄金分割法求出函数f x x2 7x 10的最优解 初始点x0 0 初始步长h 1 取迭代精度e 0 35 b a 5 708 2 3 708 e不满足 继续缩短区间 各次缩短区间有关计算数据如下表 3 判断迭代终止条件 可见 区间缩短6次后 区间长度为 b a 0 3107 e终止迭代f f x f a b 2 2 246 例5 5用黄金分割法求函数f x 3x3 4x 2的极小点 给定x0 0 h 1 e 0 2解 1 确定初始区间x1 x0 0f1 f x1 2x2 x0 h 1f2 f x2 1f1 f2加大步长向前探测 令x3 x0 2h 2f3 f x3 18f2 f3 初始区间找到 a b 0 2 2 用黄金分割法缩小区间1 第一次x1 0 0 382 2 0 0 764f1 0 282x2 0 0 618 2 0 1 236f2 2 72由于f10 2应继续缩小 2 第二次x2 x1 0 764f2 f1 0 282x1 0 0 382 1 236 0 0 472f1 0 317由于f1 f2 a b x1 b 0 472 1 236 b a 1 236 0 472 0 764 0 2应继续缩小 3 第三次f1 f2x1 x2 0 764f2 f1 0 28x2 0 472 0 618 1 236 0 472 0 944f2 0 747f10 24 第四次x2 x1 0 764f2 f1 0 282x1 0 472 0 382 0 944 0 472 0 652f1 0 223f10 2 5 第五次x2 x1 0 652f2 f1 0 223x1 0 472 0 382 0 764 0 472 0 584f1 0 262f1 f2故 a b x1 b 0 584 0 764 b a 0 764 0 584 0 18 e 0 2得到极小点和极小值 x 0 584 0 764 2 0 674 二次插值法又称抛物线法 它的基本思路是 在寻求目标函数f x 极小点的搜索区间内 取三个点的函数值来构造一个二次插值多项式p x 用它的极小点近似地作为原目标函数的极小点 若近似精度不满足要求 反复迭代 随着区间的缩短 二次插值多项式的极小点逼近原目标函数的极小点 5 3 3二次插值法 f x x x1 f1 f2 f3 x2 x3 f x 对一元函数f x 在搜索区间 a b 内取3点 x1 a x2 x3 b计算它们的函数值 f1 f x1 f2 f x2 f3 f x3 且满足f1 f2 f3即满足函数值为 大 小 大 变化 于是可通过原函数曲线上的3个点p1 x1 f1 p2 x2 f2 和p3 x3 f3 作一条二次曲线 抛物线 此二次函数可表示为 I 基本原理 p x a0 a1x a2x2对p x 求导 令其等于零 得函数极小值点 xp a1 2a2 由插值条件 插值函数p x 与原函数f x 在插值法点f1 f2和f3处函数值相等得 f1 a0 a1x1 a2x12f2 a0 a1x2 a2x22f3 a0 a1x3 a2x32 解方程组得 为了便于计算可将上式改写为 xp 0 5 x1 x3 c1 c2 c1 f3 f1 x3 x1 比较xp与x2两点及函数值的大小 在 x1 x3 内的4个点中取3个点 使函数值在呈现 大 小 大 的前提下缩短区间 收敛判断 否则重复上述方法进行二次插值 直到两次插值函数极小值点之间的距离小于收敛精度为止 1 确定初始搜索区间 a b 和精度e 2 在区间 a b 内取3点 x1 a x2 0 5 a b x3 b计算它们的函数值f1 f x1 f2 f x2 f3 f x3 构成3个插值点p1 x1 f1 p2 x2 f2 和p3 x3 f3 3 计算二次插值函数的极小值点xp 计算fp f xp 若本步骤为第一次插值或x2点为初始给定点时 说明x2和xp不代表前后两次插值函数的极小点 不能进行终止判断 进行下一步 否则转 5 II 二次插值法的迭代过程 4 缩小搜索区间比较f2 fp 取其小者所对应点为新的x2点 以此点左右邻点为新的x1 x3 构成新的搜索 x1 x3 x3 xp x2 x1 x3 fp f2 x3 fp f2 xp x2 x1 x3 fp f2 x1 fp f2 b 5 判断是否满足精度要求 x2 xp e f2 fp e停止 取x2与xp中原函数值较小的点作为极小点 否则返回 4 缩短区间直至满足要求 例 用二次插值法求f x x2 7x 10的最优解 已知初始区间为 2 8 取终止迭代点距精度e 0 01 解 1 确定初始插值结点x1 a 2 f1 f x1 0 x3 b 8 f3 f x3 18x2 4 f2 f x2 2 2 计算插值函数极小点xp 0 5 x1 x3 c1 c2 3 5fp f xp 2 25 xp x2 e 需要再次迭代 3 缩短搜索区间由于f2 fp xp x2故x3 x2 5f3 2x2 xp 3 5f2 2 25x1 2f1 0计算xp 3 5fp 2 25xp x2 0 ex xp 3 5f f xp 2 25二次函数用二次插值 只需一次计算 收敛速度快 有效性好 程序复杂 可靠性差 适应于多值优化的一维搜索迭代 例5 6用二次插值法求解f x 3x3 4x 2的极小点 x0 0 h 1 e 0 2解 1 初始区间 0 2 另取中点x2 1 2 用二次插值法逼近最小点 x1 0 x2 1 x3 2得 f1 2 f2 1 f3 18得xp 0 555fp 0 292 fp0 2 作二次插值 在新的区间内 x1 0 x2 0 555 x3 1 f1 2 f2 0 292 f3 1将其代入得 xp 0 607fp 0 243fpx2 a b x2 b 0 555 1 x2 xp 0 555 0 607 0 052 0 2故极小值和极小值点为 x xp 0 607f 0 243二次插值的收敛速度比黄金分割快得多 5 4多维优化方法 多维优化方法是进行多变量优化设计的数值迭代法 有无约束优化和约束优化两方面内容 无约束优化方法可分为两类 利用目标函数的一阶和二阶导数的信息构造搜索方向的算法 称为导数法 如梯度法 共轭梯度法 另一类是通过已知点上函数值的比较构造搜索方向的算法 称为模式法 如Powell法 约束优化方法分为直接法和间接法 迭代过程逐点考察约束 使迭代点始终局限于可行域内的算法称为直接法 如可行方向法 复合形法等 将约束条件引入目标函数 将约束优化问题转化为无约束问题求解的算法称为间接法 如惩罚函数法 5 4 1梯度法 I 基本原理在迭代过程的某一点X k 处 目标函数的负梯度方向 f X k 是函数的最速下降方法 利用这一性质 将n维无约束极小化问题转化为一系列沿目标函数负梯度方向进行一维搜索寻优的一种方法 即是在每一迭代点X k 选取搜索方向S k 为负梯度方向 S k f X k 或 沿S k 进行一维搜索 以确定步长因子a k 找到新的设计点X k 1 X k a k S k 梯度法的迭代公式可写成 X k 1 X k a k f X k 或按照上述迭代公式进行一维搜索 每次迭代的初始点取上次迭代的终点 即可使迭代点逐步逼近目标函数极小点 II 梯度法的特点 每次沿迭代点函数值下降最快的方向搜索 称最速下降法 缺点 曲折 收敛速度慢 对于圆 一次可达 不是圆时 负梯度方向不指向圆心 迭代次数增加 偏心严重 迭代次数多 形成 锯齿现象 开始步长大 愈接近极小点步长小 收敛慢 优点 迭代过程简单 对初始点要求不高 只要计算导数 只求一阶 存储单元少 5 4 2共轭梯度法 I 共轭方向的概念与性质设H为一正定对称矩阵 若有一组非零向量S1 S2 Sn满足 SiTHSj 0称这组向量关于矩阵H共轭 若H为单位阵 SiTSj 0 i j 称向量Si i 1 2 n 正交 X x1 x2 T任选初始点X 0 并沿梯度方向S 0 作一维搜索得 X 1 X 0 a0S 0 X 1 的梯度与S 0 垂直 故 f X 1 TS 0 0 1 求式 1 点X 1 的梯度 f X 1 HX 1 B从X 1 沿某一下降方向S 1 作一维搜索 同理可得 X 2 X 1 a1S 1 f X 2 HX 2 B 例 欲使X 2 成为极小点 则根据极值必要条件 有 f X 2 HX 2 B 0H X 1 a1S 1 B 0 f X 1 a1HS 1 0上式左乘 S 0 T f X 1 a1 S 0 THS 1 0由a1 0得 S 0 THS 1 0即要使迭代点X 2 成为正定二元二次函数的极小点 只需使两次一维搜索方向S 0 和S 1 关于函数的二阶导数矩阵H为共轭 1 若S i i 1 2 n 是以H共轭的n个向量 则对于正定二次函数以任意初始点X 0 出发 依次沿n个方向进行一维搜索 最多n次即可达到极小点 2 以任意两个点X1 0 与X2 0 出发 沿同一方向S 0 进行一维搜索 可得到两个一维极小点X1 1 与X2 1 则两点构成向量S 1 X1 1 X2 1 与原方向S 0 关于该函数的二阶导数共轭 共轭方向性质 X 1 由X k 出发 负梯度方向作一维搜索 S k f X k X k 1 X k akS k 设与S k 共轭的一个方向S k 1 由S k 和X k 1 的负梯度方向的线性组合而成 故有 S k 1 f X k 1 bk S k 3 令f X XTHX 2 BTX C为函数的二次展开式 II 共轭梯度方向 则 f X k HX k B f X k 1 HX k 1 B 4 相减代入X k 1 X k ak S k 得 ak HS k f X k 1 f X k 将 3 式与上式两边相乘 由共轭条件得 f X k 1 bk f X k T f X k 1 f X k 0展开由相邻两点梯度的正交关系 整理得 共轭梯度法迭代基本式以相邻两点的梯度可以构造一个共轭方向 以这种方式产生共轭方向并进行迭代运算的算法称为共轭梯度法 1 给定初始点X 0 和收敛精度e 2 取X 0 的负梯度作为搜索方向S 0 f X 0 置k 0 3 沿方向S k 作一维搜索得 X k 1 X k ak S k 4 收敛判断 若 f X k 1 e则令 X X k 1 f X f X k 1 结束迭代 否则转 5 III 共轭梯度法的迭代步骤 5 若k 1 n 检验迭代次数 对于n值目标函数 理论上通过n次可得最优点 由于计算机舍入误差及目标函数性态的特殊性 往往迭代n次达不到精度要求 此时将X n 作为X 0 返回从第一步计算 有助于消除累积计算误差的影响 并且对非二次目标函数值保证具有良好的收敛性 则令X 0 X k 1 转 2 否则转 6 S k 1 f X k 1 bk S k 令k k 1转 3 6 构造新的共轭 例 用共轭梯度法求解下列无约束优化问题X 0 1 1 T e 0 1minf X x12 2x22 2x1x2 4x1解 第一次沿S 0 方向进行一维搜索 求近似极值点 代入f X 1 4a 0 2 2 1 2a 0 2 2 1 4a 0 1 2a 0 4 1 4a 0 令df a 0 da 0 0 得a 0 0 25 由此得 进行第二次搜索的共轭方向为 再沿S 1 方向进行一维搜索得 代入f x 令df a 1 da 1 0 得a 1 1 因 f X k 1 e X 2 满足极值条件 X 2 是极小点 f X 8共轭梯度法两次迭代可求得二元二次优化问题极小点 5 4 3鲍威尔法 两次平行搜索产生一个共轭方向 Powell法就是利用平行搜索逐渐构造共轭方向和共轭方向组的方法 能在有限步长内极小化一个二次函数 是直接搜索方法中使用效果最佳的一种方法 对于维数n 20的目标函数求最优化问题 此法可获得满意效果 原始的Powell法是沿着逐步产生的共轭方向进行一维搜索的 以二维二次目标函数为例来说明 选定初始点X0 1 初始方向e 0 1 0 T e 1 0 1 T 从X0 0 出发依次沿e 0 e 1 进行一维搜索 求得各自方向上的极值点X0 1 X0 2 连接点X0 0 和最后一个极值点X0 2 构成第三个新方向 S 0 X0 2 X0 0 I 基本迭代格式 原理 x1 x2 X0 3 X1 0 S 0 称为模式方向 再沿S 0 方向进行一维搜索得该方向上的近似极值点X0 3 搜索过程就完成了一个循环 以第一循环迭代的终点X0 3 作为第二循环迭代的起点X1 0 弃去上一个循环向量组中的第一个方向e 0 将新方向S 0 补在最后 构成第二个循环的搜索方向组 e 1 S 0 分别沿e 1 S 0 一维搜索求得近似极值点X1 1 X1 2 连接X1 0 与X1 2 构成第二个循环的一个新方向 S 1 X1 2 X1 0 沿S 1 方向作一维搜索所得的近似极值点X1 3 即为第二循环的最终迭代点 也是下一次迭代的起始点 由图可知点X0 3 X1 0 X1 2 是先后两次沿S 0 方向一维搜索的极小点 由共轭性质知 连接X1 0 X1 2 构成的矢量S 1 与S 0 相共轭 经过二次循环后 迭代点由初始点X0 0 依次沿S 0 S 1 方向一维搜索 经X0 3 X1 0 到达X1 3 从理论上讲 二维二次正定函数经过这组共轭方向的一维搜索 迭代点已达到函数的极小点X 将此结构推广至n维二次正定函数 即依次沿n个 S 0 S 1 S n 1 共轭方向一维搜索就能达到极小点 原始Powell法存在的问题 目前使用修正算法 和原始Powell法的主要区别 在构成第k 1次循环方向组时 不用淘汰前一循环中的第一个方向S1 k 的办法 而是首先解决是否要替换和替换哪个方向的问题 为此 在得到新方向Sk n Xk n Xk 0 后沿Sk n 找出Xk 0 的反射点Xk n 2 Xk n 2 2Xk n Xk 0 计算三点的函数值 f1 f Xk 0 f2 f Xk n f3 f Xk n 2 找出前一轮迭代法中函数值下降最多的方向m及下降量 m 即 m max f Xk i f Xk i 1 f Xk m 1 f Xk m 可以证明 若f3 f1与 f1 2f2 f3 f1 f2 m 2 0 5 m f1 f3 2同时成立 则表明方向Sk n 与原方向组成线性无关 可以用来替换 替换对象就是 m所对应的方向Sk m 替换算式 Sk 1 i Sk i i m Sk 1 i 1 Sk i i m 1 m 2 n 1 Sk 1 n 1 Sk n 新一轮迭代起点 Xk 1 0 Xk n 1 Sk 1 n 1 上述两个条件不成立 则表明与原方向组中某些方向线性相关 因此不进行方向替换 此时仍用原方向组进行第k 1轮搜索 Sk 1 i Sk i i 0 1 n 1 第k 1轮搜索初始点的取法 若f2 f3 Xk 1 0 Xk n 否则 Xk 1 0 Xk n 2 步骤 P177页 例 试用Powell法求f X x12 2x22 4x1 2x1x2的最优解 X0 1 1 T 收敛精度e 0 05 解 f1 f X0 0 3 第一次循环 沿坐标轴方向e 0 进行一维搜索 代入f X f X 1 a0 0 2 2 4 1 a0 0 2 1 a0 0 令df X da0 0 0 得a0 0 2则有 f X0 1 7 以X0 1 为起点 沿坐标轴方向e 1 进行一维搜索 代入f X f X 32 2 1 a0 1 2 4 3 2 3 1 a0 1 令df X da0 1 0 得a0 1 0 5 则有 f X0 2 7 5 计算各个方向的函数下降量 1 f X0 0 f X0 1 3 7 4 2 f X0 1 f X0 2 7 7 5 0 5 m max 1 2 1 4 映射点 f1 f X0 0 3 f2 f X0 2 7 5f3 f X0 4 7 检验是否满足终止迭代条件 替换条件 f3 f1 f1 2f2 f3 f1 f2 m 2 1 25 0 5 m f1 f3 2 32满足 故沿新的搜索方向S 0 作一维搜索 代入f X 令df a0 2 da0 2 0 得a0 2 0 4 故有 故以X1 0 X0 3 为新起点 进行方向替换 以S 0 替换e 0 沿 e 1 S 0 方向搜索 进行第二轮迭代 f X1 0 7 9 f1 沿e 1 方向进行一维搜索 得 按点距准则检验终止条件 以X1 1 为起点沿S 0 方向进行搜索 得 收敛检验 不收敛 继续进行迭代 计算 1 f X1 0 f X1 1 7 9 7 98 0 08 2 f X1 1 f X1 2 7 98 7 996 0 016 m max 1 2 1 0 08 映射点 f3 f1 替换条件不成立 继续迭代时取搜索方向仍为原方向 e 1 S 0 由于f2 f3 取X2 0 X1 2 3 96 1 94 T 以X2 0 为新起点 方向 e 1 S 0 进行第三循环迭代 f X2 0 7 996 f1 沿e 1 方向进行一维搜索 得 以X2 1 为起点沿S 0 方向进行搜索 得 收敛判定 不收敛 继续迭代 f X2 1 7 9992 映射点 1 f X2 0 f X2 1 7 996 7 9992 0 0032 2 f X2 1 f X2 2 7 9992 7 9997 0 0005 m max 1 2 1 0 0032判断搜索方向是否替换 f3 f1 f1 2f2 f3 f1 f2 m 2 1 175 10 9 0 5 m f1 f3 2 11 66 10 9 故新的搜索方向S 1 沿搜索方向S 1 进行搜索 得X2 3 4 0103 2 0016 T 进行方向替换 以S 1 替换e 1 沿 S 0 S 1 方向搜索 进行第四轮迭代 X3 0 X2 3 为起始点 f X3 0 7 9999 沿S 0 方向搜索得 X3 1 3 9992 1 9988 T f X3 1 8 0000 从X3 1 出发沿S 1 方向搜索得 X3 2 4 0002 2 0000 T f X3 2 8 0000 收敛判断 满足收敛条件X X3 2 4 0002 2 0000 T f X f X3 2 8 0000 实际上S 0 S 1 为共轭方向 对二元二次函数 两次搜索就可以得到最优点 5 5惩罚函数法 SUMT 将约束优化问题转化为无约束优化问题的一种解法 约束优化设计的数学模型一般可表示为 minf X X Rns t gu X 0u 1 2 mhv X 0v 1 2 p将上述问题中的约束函数经过加权转化 并和原目标函数构成新的复合函数 构造成无约束问题 r1 k G gu X 和r2 k H hv X 称为惩罚项 r1 k 和r2 k 称为惩罚因子 f X r1 k r2 k 称惩罚函数 简称罚函数 G gu X 和H hv X 分别是由