工程设计中的优化方法教学课件PPT.ppt

第5章工程设计中的优化方法 优化设计的基本概念和步骤优化设计方法的种类和特点优化设计方法的原理和应用 优化设计的数学模型和基本步骤无约束优化方法 重点 内容 优化结构几何参数 使构件质量最轻或用料最省 优化材料配方或成分 使材料的性能最佳 优化工艺参数 使产品性能最佳 用成分不同的原料进行配料 设计成本最低的配料方案 5 1最优化问题概述 0 工程中的最优化设计问题 结构优化 材料优化 工艺优化 配料优化 注 所有设计都要在一定的约束条件下进行 1 优化设计的涵义 一种新的设计方法 应用数学的一个分支 它能使一项设计在一定技术和物质条件下 获得一个技术经济指标最佳的设计方案 应用广泛 在给定的技术 经济等客观条件下选择设计参数 使设计指标达到最优值在一定约束条件下求多变量函数极值的方法 优化设计是研究和解决在一切可能方案中寻求最优方案的科学方法 优化设计主要研究内容建模理论和方法 从实际问题中抽象出最优数学模型 求解最优化问题的理论和方法 优化设计的基本思想从研究对象的整体来考察和解决问题 并从组成整体各个部分的相互联系 相互影响和相互制约中寻求最优方案 优化设计的基本步骤分析实际问题 建立数学模型 选择优化方法 求解最优方案 2 优化设计的数学模型 数学模型是优化设计的基础 要对一个实际设计问题进行优化 首先必须建立问题的数学模型 优化设计问题的数学模型 是指用数学符号和公式描述优化设计问题的一种模型 1 设计变量 一个设计方案可以用一组设计参数来表示 需要在设计过程中优选的独立参数 根据设计要求事先给定的参数 值不变 设计变量表示方法 设计空间 以设计变量为坐标轴所构成的空间设计空间的维数 即设计变量的个数n个设计变量即构成n维设计空间 记为x rn 设计空间及其维数 设计变量的数目 选择余地或影响不大的参数 根据经验定为常量 设计变量个数应尽量减少 选定原则 只把与问题本质有关 对结果影响大的参数定为设计变量 连续变量 值能连续变化 离散变量 值不能连续变化 设计变量的类型 对于离散变量的优化设计问题 通常先按连续变量处理 找到最优解后 再按工艺规范或标准系列调整 在优化设计中 用于评价设计变量好坏的函数 称为目标函数 记作 优化目标函数就是求目标函数的极小值或极大值 即minf x 或maxf x 2 目标函数 对目标函数进行优化 就可以得到最优方案 f x f x1 x2 xn 用效果函数 如性能指标 利润等 作目标函数 则是求极大值 用费用函数 如能源 材料 经费等 作目标函数 则求极小值 单目标优化问题 只包含一个优化目标的问题多目标优化问题 存在两个或两个以上优化目标的问题 单目标和多目标优化问题 一般来讲 目标函数越多 设计结果越趋完善 但优化设计的难度也相应加大 实际中应尽量控制目标函数的数量 抓住问题的主要矛盾 保证重点要求的实现 其余要求可处理成设计约束来加以保证 例如 一个结构应满足的强度和刚度等条件 3 约束条件 约束条件的定义 对设计变量取值的限制条件 约束条件的数目约束条件愈接近实际 则最优解愈接近最优方案 但约束条件数增加时 可行方案数量将大大减少 计算工作量也会增大 约束条件的类型边界约束设计变量的变化范围 如板材厚度范围 性能约束由某种性能设计要求导出的约束条件 如结构设计中 弯曲应力必须小于或等于许用弯曲应力等 hi x hi x1 x2 xn 0i 1 2 m m n 约束条件的类型 不等式约束 等式约束 同一个优化设计问题可同时含有等式和不等式约束 对于不等式约束 0型和 0型可互相转化 方法是改变约束条件的符号 即令gj x gj x gj x gj x1 x2 xn 0或 0j 1 2 p 约束条件把设计空间划分为两个区域 可行域和不可行域 可行域和可行点 可行域域内设计点 设计方案 满足所有约束条件 可行域内的设计点称为可行点 约束优化设计中 最优点一般是约束区域的边界点 即设计点位于某个约束面上 gu x 0 1 u p 优化设计的数学模型是实际设计的数学抽象 任何一个优化设计问题可归结为如下描述 在给定的约束条件下 选择适当的设计变量x 使其目标函数f x 达到最优值 4 数学模型 建立数学模型是解决优化设计的关键 其数学表达式 数学模型 为 优化设计数学模型的简化表示 s t 满足于 或 受约束于 rn n维欧氏空间 利用优化方法求解上述数学模型 可得到一组最优设计参数或一个最优设计方案 x 称为最优点 f x 称为最优值 最优点和最优值构成一个约束最优解 x x1 x2 xn t 优化设计问题的最优解 实际工程的优化设计问题 非线性约束优化问题 优化设计问题的类型 例5 1 已知箱形梁的长度l和载荷f1 f2 许用挠度 f l 700 设梁高为x1 梁宽为x2 腹板厚度为x3 翼缘板的厚度为x4 试设计该箱形梁 使其质量最轻 长度单位为mm 力的单位为n 设计变量取箱形梁横截面待定尺寸x1 x2 x3及x4为设计变量 则 目标函数优化目标为质量最轻 梁的跨度已知 故可用梁的截面面积作为目标函数 截面面积之半可近似为 f x x1x3 x2x4 使质量最轻就是使f x 的值最小 x x1 x2 x3 x4 t x r4 忽略了 2x3x4项 厚度的乘积 约束条件设计的箱形梁需满足一定的强度 刚度 稳定性以及几何要求 推导得 箱形梁优化设计的数学模型 属约束非线性规划问题 选用可行方向法求解 表5 1箱形梁设计结果比铰 优化结果 取出三种跨度的优化结果见表5 1 所用数据为 f1 120kn f2 12kn 140mpa 3 优化设计的计算方法 求解无约束优化问题 求解约束优化问题 解析法用求导数或变分方法求出极值存在的必要条件 再求出它们的解析解 然后按照充分条件或问题的实际物理意义确定最优解 仅适用于目标函数和约束条件较为简单明确的情况 无约束优化方法 数值法利用函数在某一局部区域的性质和一些己知点的数值 确定下一步的计算点 经过迭代搜索 最后达到最优点 可解决复杂的优化设计问题 是优化设计采用的主要方法 无约束优化方法分为解析法和数值计算法两类 根据处理问题的方法 约束优化方法可分为两大类 约束优化方法 直接解法直接从可行域中找出约束最优解x 和f x 如 网格法 随机试验法 随机方向搜索法 复合形法 可行方向法等 间接解法将约束优化设计求解问题 转换成求无约束极值问题 可用于求解同时存在不等式约束和等式约束的优化设计问题 以惩罚函数法应用最为广泛 无约束优化方法的特点和适用范围 约束优化方法的特点和适用范围 4 优化设计的一般步骤 优化设计是一种规格化的设计 一般步骤为 1 分析设计问题 建立数学模型 对生产或试验数据进行统计分析 求出回归方程 对不能实际试验的问题通过模拟建立数学模型 把理论公式或经验公式作为数学模型 根据物理概念和逻辑推理建立数学模型 建模方法 回归设计是建立数学模型的有效方法 它利用正交表等编制试验方案 直接求出回归方程 常用回归设计方法 多元线性回归设计 回归正交设计 回归旋转设计 d 最优设计 混料回归设计等 编制调试计算程序 2 选择优化方法 求解最优方案 正确选择优化方法 计算过程中 要随时注意计算结果 必要时要及时调整输入参数 使解不断得到改善 选择原则 计算程序简单 满足精度要求 稳定可靠 计算效率高 节约时间 尽量利用现有优化程序 当需引用各种图表数据时 应编制查找和捡取这些数据的专门子程序 这是优化设计极为重要的环节 3 分析计算结果 评价优化方案 检查最优点的合理性和可行性 分析目标函数的最优值 分析约束函数值 判断最优点位置 分析设计变量的敏感度 主要内容 排除计算机输出的不合理或不正确的结果 分析判断优化方案优劣 作出圆满的最终决策 主要任务 分析检查的内容 敏感度 设计变量微小变化引起目标函数值变化的程度 对结果分析作出肯定的结论后 一般即可按优化设计方案组织实施 优化方案的实施 重要的工程设计问题生产中不可控因素较多的问题变量不能严格控制的问题 求最优点x x1 x2 t和最优值f x 5 优化设计的几何解释和基本解法 1 几何解释 对于一个二维问题 设计变量x x1 x2 t设计空间维数 2不等式约束数 4二维非线性规划求极小值问题 最优解 二维非线性优化问题的几何解释 同心圆簇 n 1 维立体图 约束最优设计点 可行域内目标函数值最小的点 它是约束边界与目标函数等值线的切点 数值解法的主要思想从一个初始设计点x k 出发 沿着某个搜索方向s k 以适当步长hk的方式实现对x k 的修改 以获得新点x k 1 值 迭代公式为 2 基本解法 求函数f x 极值点的迭代算法 首先选定初始设计点x 0 从x 0 出发沿某一规定方向s 0 求函数f x 的极值点 设此点为x 1 x k 1 x k h k s k x 1 x 0 h 0 s 0 x k 1 x k h k s k 寻求极值点的搜索过程 再从x 1 出发沿某一规定方向s 1 求f x 的极值点 设此点为x 2 如此继续 一般地 从点x出发 沿某一规定方向s k 求函数f x 的极值点x k 1 2 n 这样的搜索过程 组成了求n维函数f x 极值的基本过程 确定搜索方向s k 计算最佳步长hk 求极值的基本过程是通过一系列的搜索过程来完成的 其核心是 搜索过程是逐步逼近最优点而获得近似解的过程 因此需要考虑 优化问题解的收敛性迭代过程的终止条件 求极值的核心问题 由此产生了各种优化方法 收敛性与终止条件 根据收敛条件 可以确定迭代终止准则 迭代终止准则 点距准则相邻两设计点 迭代点 的距离达到充分小时 若用向量模计算长度 则 函数下降量准则当相邻两次迭代点函数值的下降量达到充分小时终止迭代 即 x k 1 x k 预先给定的迭代精度或允许误差 梯度准则当某次迭代点目标函数梯度模达到充分小时终止迭代 即 f x k 若上述准则之一满足 则认为目标函数值已收敛到最小值 这样即求得近似最优解 x x k 1 实际中常将点距和函数下降量准则结合起来使用 即要求两者同时满足 最优解的确定 5 2无约束最优化方法 目标函数或约束条件为非线性函数的规划问题属非线性规划 它是优化设计中最常见的数学形式 中 有一个或多个函数是变量x的非线性函数 则此最优问题称为非线性规划 1 非线性规划 若在数学模型 minf x gi x 0 i 1 2 mm n hj x 0 j 1 2 p x rn 线性规划 f x gi x hj x 为线性函数时 二次规划 f x 为二次函数 gi x hj x 为线性函数时 它是一种特殊的非线性规划 应用最多的求解方法是将非线性规划转换成无约束最优问题来求解 即将有约束的最优化问题化为无约束最优问题 对无约束问题的求解 具有十分重要的意义 非线性规划问题的求解方法 函数的等值线 当函数f x 的值依次等于一系列常数时 自变量取得一系列值的集合 1 函数的等值线 面 2 目标函数的无约束极值问题 当二维函数f x 的值依次取不同的实数时 其相应的水平面与空间曲面的交线为一组椭圆 它们在x1ox2平面上的投影就是一族椭圆曲线 同一曲线上任意点 x1 x2 所对应的函数f x 值都相等 故称这族曲线为函数f x 的等值线 对于三维以上的函数 n维函数 具有共同函数值的点构成一族曲面 称函数f x 的等值面族 函数等值线在极值处聚成一点 并位于等值线族的中心 当该中心为极小值时 离中心越远函数值越大 在极值点附近 n元函数的等值面一般为一族近似的椭球面 它们共同的中心就是n元函数的极值点 求函数极值点亦即求函数最优点问题 可归结为求其等值线 面 同心椭圆 椭球面 族的中心 根据求椭圆 椭球面 族中心的不同途径 就形成了各种不同的优化方法 极值点附近等值线呈椭圆形 等值线较密的部位 目标函数值变化越迅速 目标函数非线性程度越严重 等值线形状越复杂 且可能存在多个极值点 梯度定义 n元函数f x1 x2 xn 的梯度 即梯度是由函数f x 一阶偏导数组成的n维列向量 2 函数的梯度 梯度的模 梯度方向 函数等值线 面 的法线方向 梯度与函数的等值线相互垂直 其方向沿函数等值线的法线指向函数值增加的一侧 梯度正方向是函数值最速上升 增加最快 方向 梯度负方向或负梯度方向是函数值最速下降方向 梯度 f x 是一个向量 其方向是函数f x 具有最大变化率的方向 梯度的主要特征 沿某点的梯度方向 函数值在该点附近增长最快 反之 沿某点的负梯度方向 函数值在该点附近下降最快 多元目标函数可用其在某点的泰勒展开式近似 3 多元函数的泰勒展开式 多元函数f x 在点x k 的泰勒展开式 只取到二阶偏导数项 xi xj 变量x的第i j个分量 n 变量的个数 函数在x k 点处对xi的一阶偏导 函数在x k 点处对xi xj的二阶偏导 即函数f x 在点x k 的一阶偏导数的列向量 矩阵形式 函数f x 在点x k 的二阶偏导数 它是一个n n阶的对称方阵 称为函数f x 在点x k 的海森 hessian 矩阵 梯度 多元函数在极值点附近的等值线簇为同心椭圆簇 即目标函数在极值点附近是二次函数 因此 多元函数常用其泰勒展开式的前三项近似表示 精度已足够 记为 与矩阵形式对应 多元函数的近似表达式 二元二次函数的表达形式 一般二元二次函数 f x mx12 nx22 px1x2 b1x1 b2x2 c 矩阵表达式 a 函数的二阶偏导数矩阵 对称方阵 二次函数的梯度 f x ax b b 函数一次项系数列向量 补充知识 4 多元函数无约束极值条件 对于n元函数f x1 x2 xn 的无约束极值问题 点x 为一个局部极值点的充分必要条件 一阶导数向量 f x 0 即 二阶导数矩阵 2f x 即海森矩阵h x 为正定或负定 且当h x 为正定时x 为极小点 当h x 为负定时x 为极大点 minf x x rn 若矩阵a各阶顺序主子式均大于零 即当a aij 时 则该矩阵a是正定的 不符合正 负定条件的矩阵 是不定矩阵 对于这类矩阵 不可用上述方法判别点x 是否为极值点 而需用更高阶的导数来判定 若各阶顺序主子式呈负 正交替变化 即一切偶数阶的主子式都是正数 一切奇数阶主子式都是负数 则该矩阵a是负定的 判断矩阵a正定或负定的方法 3 无约束最优问题的直接搜索解法 一维搜索法是多维搜索法的基础多维寻优可转化为一维寻优问题求解 基本思想 在搜索过程中逐步缩小搜索区间 直至最优点存在的范围达到允许误差为止 对单变量目标函数f x 寻优 即minf x 亦即求函数f x 的极小点x 和极小值f f x 1 消去法 消去法是搜索单变量函数极值的有效方法 时停止迭代 得到最优解为 再选一个x3 求出f3 f x3 并比较f3和min f1 f2 如此继续下去 直到第n次迭代 满足 x xn f fn 数值迭代法求解过程从一个初始点x1开始 求出f1 f x1 按一定规律 另选一个点x2 求出f2 f x2 比较f1和f2 去掉其中较大者 f x1 f x2 最优点x 在区间 a x2 内 可将区间 x2 b 消去 令b x2 得到已缩小的新搜索区间 a b 若目标函数f x 的极小点x 在 a b 闭区间内 则 消去法搜索过程 在 a b 内选取两个试点x1和x2 x1 x2 分别代入目标函数 求出f1 f x1 和f2 f x2 比较f x1 和f x2 可能有三种情况 f x1 f x2 最优点x 在 x1 b 内 可将区间 a x1 消去 令a x1 得到缩小的新搜索区间 a b f x1 f x2 最优点x 在 x1 x2 内 可消去两侧任意一个区间 如消去 a x1 则搜索范围缩小为 a b a x1 在新的搜索区 a b 内重新选试点 并重复计算 每迭代一次 搜索区就缩短一次 经过n次迭代后 若满足 b a 要求 则可认为最优解 x a b 2 f f x 需要解决的两个问题初始搜索区间 a b 的确定 区间内必须包含极小点 通常采用进退法确定 测试点x1和x2的选取 可按黄金分割法选取 即 x1 a 1 b a x2 a b a 0 618 黄金分割数 确定最优解所在区间的进退法 补充 用数值法求一维函数f x 的极小点x 必须先确定极小值所在区间 确定该区间的算法 称为进退法 一维函数最小值所在区间满足高 低 高的原则 边界是函数值高的两点 只要区间内某点的函数值小于两边界点的函数值 此区间即为所求 进退法定区间的步骤 任意给出自变量的一个初始值x1和前进步长h 从x1出发 可求出x2 x1 h及f x1 f x2 比较f x1 和f x2 f x1 f x2 极值点在x1右边 h的方向正确 步幅可能较小 取h 2h 转入第 步 f x1 f x2 函数极值点在x1左边 h增加方向错误 应取h h 后退 进行计算 为减小计算工作量 将x1与x2 f x1 与f x2 的值互换 转入第 步 计算新的试探点x3 x2 h和函数值f x3 比较f x2 和f x3 f x3 f x2 表明在 x1 x2 之间没有最小值 做代换x1 x2 x2 x3 f x2 f x3 继续计算x3 注 初始步长h一般应取较小的值 如取收敛精度值的10倍左右 取值过大 有可能不收敛 f x3 f x2 表明在 x1 x3 存在最小值 取a min x1 x3 b max x1 x3 输出 a b 即得最小值所在的区间 f x3 f x2 f x3 f x2 进退法确定区间的算法框图 前进 输入初始自变量和步长x1 h 计算f x1 和x2 x1 h f x2 h hx1与x2 f x1 和f x2 互换x3 x2 h 计算f x3 h 2hx3 x2 h计算f x3 x1 x2 x2 x3 f x2 f x3 x3 x2 h 计算f x3 x1 x3 满足高 低 高a min x1 x3 b max x1 x3 结束 f x1 f x2 f x2 f x3 n n y y 后退 黄金分割法基本步骤 1 给出初始搜索区间 a b 和收敛精度 2 在区间 a b 内插入两点x1和x2 并计算函数值f x1 和f x2 使用黄金分割法 相邻两次搜索区间的缩短率为0 618 3 比较f x1 和f x2 大小 缩短搜索区间 进行区间名称代换 4 检查区间是否缩短到足够小 或函数值收敛到足够接近 如果条件不满足 则到步骤5 否则到步骤6 x1 a 1 b a x2 a b a 0 618 黄金分割数 5 在保留区间中计算一个新测试点及相应函数值 转步骤3 6 取最后两次测试点的平均值作为极小点的数值近似解 并计算该点的函数值作为目标函数的最优解 黄金分割法程序框图 a b可用进退法确定 例题 用黄金分割法求单变量函数f x x2 7x 10的极小点 初始搜索区间 a b 2 8 迭代精度 0 35 解 在搜索区间 a b 内取两试点x1和x2 计算它们的函数值 x1 b 0 618 b a 8 0 618 8 2 4 292f1 f x1 4 2922 7 4 292 10 1 6227x2 a 0 618 b a 2 0 618 8 2 5 708f2 f x2 5 7082 7 5 708 10 2 6253 比较函数值f1和f2 缩短搜索区间 由于f1 f2 消去右区间 x2 b 令b x2 5 708 x2 x1 4 292 f2 f1 1 6227 x1 b 0 618 b a 5 708 0 618 5 708 2 3 4165f1 f x1 3 41652 7 3 4165 10 2 2430 x b a 2 3 5971 3 2863 2 3 4417 f f x 2 2466 判断迭代终止条件b a 5 708 2 3 708 不满足迭代终止条件 再取两试点x1和x2 并且比较函数值f1与f2 继续缩短搜索区间 搜索区间经6次缩短后 区间长度为b a 3 5971 3 2863 可以终止迭代 得到近似极小点和最优值 利用若干点的函数值 构造一个低次的插值多项式p x 去逼近要求极小值的函数f x 用解析法求出p x 导数的根 作为目标函数f x 极小值的近似位置 重复应用这一方法进行迭代计算 直到得出符合要求的结果 常用插值多项式有二次和三次的 因此分别称为二次插值法和三次插值法 2 插值法 基本思想 在目标函数f x 的寻优区间 a b 内任取三点x1 x2 x3 且x1 x2 x3 相应的函数值为f1 f x1 f2 f x2 和f3 f x3 过此三点构造一条抛物线 并以此抛物线近似原目标函数 二次插值法 构造的抛物线为二次方程 求待定系数将x1 x2 x3代入上式 可求出系数a1和a2 p x a0 a1x a2x2 令p x 的导数为0 可求出近似抛物线的极小点x0 即 求极小点和极小值 代入目标函数 得 迭代求解去掉f1与f2中较大者 将剩下的两个预选点和x0组成一个新的 三点组 然后重复上述过程 进行二次迭代 直到满足允许误差的要求为止 如果 f2 f0 则选其小者为最优解 若不满足收敛条件 则转下一步 判断终止条件 注 首先要确定初始搜索区间 a b 二次插值法收敛速度快 有效性好 但可靠性差 适用于多维优化的一维搜索迭代 多维优化的一维搜索 在求多维目标函数的极值点时 大多数方法都要进行一系列的一维搜索 多维搜索的迭代格式为x k 1 x k hs k h为步长因子 搜索新点x k 1 时 出发点x k 和搜索方向s k 均已确定 这样 问题就变成了过点x k 沿s k 方向求函数f x 极小点x 的一维搜索问题 沿s k 方向求原函数f x 的极小点x 实际转化为求单变量函数f h f x k hs k 为极小值时的步长因子h 即 通过一维搜索求得的步长因子h 称为最优步长因子 minf x k hs k f x k h k s k 将最优步长h代入迭代式中 即得新点 x k 1 x k hs k 多维优化一维搜索示意图 多维搜索法 其原理是将多维无约束最优化问题转化为一系列沿坐标轴方向的一维问题求解 而一维寻优问题可用消去法或插值法求解 3 坐标轮换法 降维法 首先沿x1方向搜索 即固定x2 0 只改变x1 h1为优化步长 可用一维寻优方法求得 即 第一轮搜索 目标函数转化为单变量x1的函数 可得目标函数沿x1方向的极小点 即 目标函数转化为单变量x2的函数 可得目标函数沿x2方向的极小点 即 再沿x2方向搜索 即固定x1 1 只改变x2 优化步长h2可用一维寻优方法求得 即 至此 第一轮结束 坐标轮换一周 得到两个目标函数值逐次下降的迭代点x1 1 和x2 1 x的上角码表示轮数 下角码i表示该轮中第i个迭代点 完成第一个轮计算后 如满足 则目标函数的极小点x x2 1 否则 进行第二轮搜索 以前一轮得到的第二个迭代点 如x2 1 为新起点进行搜索 进行k轮迭代得到迭代点x2 k 若此时满足精度 则x2 k 即为所求最优点x 第二轮以后的搜索 注意 每轮迭代都依次沿两个坐标方向进行一维搜索 且每轮搜索的次序应一致 本轮终点与始点的距离 先将n 1个变量固定不变 只对一个变量 一般先对x1 进行一维搜索 得到沿该坐标方向的一个目标函数极小点x1 1 然后再将x1轴固定在x1 1 点上 并使变量x3 x4 xn固定不变 仅使x2变化 沿x2轴进行一维搜索 求沿该方向上的最小点x2 1 依次类推 n维函数的寻优 当分别沿坐标方向x1 x2 xn进行一次搜索后 即完成一个轮计算 得到最小点xn 1 判断是否满足精度要求 否则重复上述步骤 总之 每次都固定n 1个变量不便 依次轮换地对一个变量进行一维搜索 这样就把一个n维优化问题转化为求解一系列的一维优化问题 对于第k轮迭代 其迭代公式为 xi 1 k 为第k轮第i次迭代初始点 si k 为第k轮第i次搜索方向 它轮换地取n维坐标的单位向量 即 si k ei 0 1 0 第i个分量为1 其余为0 hi k 为第k轮第i次迭代步长因子 可正可负 一般采用一维优化方法确定 即 1 取初始点x 0 和收敛精度 并令k 1 同时置n个坐标方向矢量为单位坐标矢量e1 100 0 t e2 010 0 t en 000 1 t 2 按迭代公式计算xi k k为迭代轮数的序号 取k 1 2 i为该轮中一维搜索的序号 依次取i 1 2 n 步长hi k 通过一维优化方法求得 迭代步骤 若上式成立 迭代终止 输出最优解x xn k 否则 令k k 1 x0 k 1 xn k 返回步骤 2 进行下一轮搜索 3 按点距准则判断是否收敛 开始 给定x 0 n e1 k 1 x k x 0 i 1 si k ei 沿si k 方向一维搜索求得 i k xi k xi 1 k hi k si k i n xn k x0 k 输出x xn k 1 f f x 结束 i i 1 k k 1x0 k xn k 1 坐标轮换法计算框图 n n 坐标轮换法特点及应用搜索路线较长 计算效率低 一般仅适用于n 10的小型优化问题的求解 此法的效能在很大程度上取决于目标函数的性质 收敛速度慢 应用不普遍 4 共轭方向与鲍威尔法 鲍威尔 powell 法又称方向加速法 它是利用共轭方向可以加快收敛速度的性质形成的一种搜索方法 该法不用对目标函数求导 当目标函数的导数不连续时也能应用 因此 鲍威尔法是一种十分有效的直接搜索法 搜索方向 共轭方向 设a为n阶实对称正定矩阵 若两个n维向量s1和s2满足 则称向量s1与s2对矩阵a共轭 共轭向量的方向称为共轭方向 共轭方向的概念 s1tas2 0 则称向量组s1 s2 sk关于矩阵a共轭 即对于同一实对称正定矩阵a 可以根据需要取不同的对a共轭的方向组 如果非零向量组s1 s2 sk中任意两个向量关于n阶对称正定矩阵a共轭 既满足 sitasj 0i j i j 1 2 k s1tis2 0即s1ts2 0 此时的s1 s2为两正交向量 正交向量的方向称为正交方向 显然 正交是共轭的特例 二次正定函数f x 在坐标平面上的等值线是一族同心的椭圆 共轭方向的几何意义 二次函数的共轭方向 设a为n n阶实对称正定矩阵 s1 s2 sn为对a共轭的n个非零向量 则这组向量线性无关 对于n维优化问题 共轭向量的个数最多等于n 单位坐标向量系是一组线性无关的共轭向量 且它们也是正交向量系 共轭向量的重要性质 设a为n n阶实对称正定矩阵 si i 1 2 n 是关于a的n个互相共轭的非零向量 对于正定二次函数f x 的极小化寻优问题 从任何初始点出发 依次沿si方向经n次一维搜索即可收敛到极小点x x n 搜索次数 二元二次正定函数等值线的中心就是函数的极小点 任意两条平行线与椭圆两个切点x 1 和x 2 的连线必通过极小点 二次函数极小值的搜索 x 0 s1s2x 0 x 1 x 若以x 0 为起始点 分别沿s1 s2方向作两次一维搜索 即可到达二元二次正定函数的极小点 将切线的方向记为s1 连线方向记为s2 则s1与s2为共轭方向 对于n元二次正定函数 沿其n个共轭方向进行n次一维搜索就可到达目标函数的极小点 鲍威尔法的基本算法 s 1 与等值线相切 再沿s 1 方向作一维搜索 求得极小点x3 1 选定一起始点x 0 以坐标轴单位向量e1 1 0 t e2 0 1 t作为初始搜索方向 从x0 1 x 0 出发 沿x1轴作一维搜索 得到搜索点x1 1 再以x1 1 为新的初始点x2轴作一维搜索得到搜索点x2 1 连接x2 1 和x0 1 二点 其连线作为新的方向s 1 即s 1 x2 1 x0 1 x3 1 从x0 2 x3 1 出发 舍去x1方向 沿x2方向作一维搜索 求得极小点x1 2 再以x1 2 为新的始点沿s2 2 s 1 方向进行一维搜索 求得极小点x2 2 连x2 2 与x0 2 点 构成新的方向s 2 则s 2 x2 2 x0 2 再沿s 2 方向进行一维搜索 求得极小点x3 2 第k轮得到的共轭方向 s k xn k x0 k n为维数 x3 2 相当于从x0 1 出发分别沿a的两个共轭方向s 1 s 2 进行两次一维搜索而得到的点 所以点x3 2 即为二维问题的极小点x 符号 x的上角码k表示轮数 下角码i表示该轮中第i个迭代点 s的上角码表示轮数 下角码i表示该轮中第i次搜索方向 从初始点出发时 也可先沿x2方向搜索 再沿x1方向搜索 共轭方向法只适用于目标函数近似于椭圆簇的情况 通常远离极小点处 目标函数的等值线不能用椭圆簇来近似 所以计算机计算时 先用坐标轮换法搜索 然后再用共轭方向法进行精搜索的办法较为有效 对于二维非二次目标函数 按泰勒公式可以用二次函数来逼近 等值线在极小点x 附近呈现近似的有心椭圆簇 因此 x 2 不一定是目标函数的极小点 需要以x 2 为新起点 继续进行第二轮 第三轮迭代 直到满足精度要求 几点说明 对于共轭方向法 初始鲍威尔法 有时新产生n个方向有可能出现线性相关或近似于线性相关的情况 就是向量平行或近似平行 从而导致计算不能收敛 此法不实用 修正的鲍威尔法 在形成新方向组时 有选择地去掉某一方向 不一定去掉前一轮的第一个搜索方向 以避免线性相关性 按照这一原则重置方向就可保证算法是收敛的 这是一种实用的方法 例5 3 设目标函数 从x 0 0 0 t出发搜索 求极小点 该函数的极值点为x 8 6 t f x 8 f x x12 x22 x1x2 10 x1 4x2 60 沿x2轴方向 按坐标轮换法进行一维搜索 求最优步长 令x0 1 x 0 0 0 t s1 1 0 1 t s2 1 1 0 t 第一轮迭代 沿x1轴方向进行一维搜索 求最优步长 x2 1 x1 1 h2s2 1 h2 2 t f x2 1 56 12h2 h22 df x2 1 dh2 12 2h2 0 得h2 2 于是x2 1 6 2 t f x2 1 20 沿x2 1 x0 1 方向进行一维搜索 因s3 1 为单位向量 则 df x3 1 dh3 0 得h3 1 357 于是x3 1 7 238 2 429 t 第一轮迭代到此结束 共进行了三次迭代 s3 1 x0 2 求步长h3和x3 1 以第一轮迭代的终点x3 1 作为起点 即令x0 2 x3 1 先沿x2 轴方向进行一维搜索 令s1 2 s1 1 求出最优步长 得到最优点 第二轮迭代 x1 2 7 286 5 643 t 连接x0 2 和x2 2 得向量x2 2 x0 2 此方向的单位向量s3 2 s3 2 是s3 1 和s2 2 两条平行线切点的连线方向 因此s3 2 和s3 1 对a共轭 可见对二元二次函数 用共轭方向法经过两轮六次迭代即可获得最优点 即极小点 在每轮获得新方向sn 1 k 后 在组成新方向组时 有选择地去掉前一轮方向组中某一个方向sm k 1 m n 以避免新产生的方向组中各方向出现线性相关的情形 修正的鲍威尔法 用sn 1 k 方向组成新的搜索方向组的判别条件 同时成立 则用sn 1 k 方向 并且挤掉sm k 否则仍用原来的n个搜索方向 若 f1 f x0 k 第k轮起始点函数值 f2 f xn k 第k轮方向组一维搜索终点函数值 f3 f 2xn k x0 k x0 k 对xn k 的映射点函数值 修正的鲍威尔法虽然计算稍微复杂一些 但它保证了非线性函数寻优计算可靠的收敛性 第k轮方向组沿诸方向一维搜索所得的各函数下降量中最大者 其相对应的方向即是sm k 1 给定初始点x0和计算精度 令k 1 si k ei i 1 2 n 即取初始方向组为n个单位坐标向量 x0 1 x0 i 1 k 1 3 经计算求出共轭方向和影射点分别为 修正鲍威尔法的计算步骤 4 计算k轮中相邻两点目标函数值的下降量 并求出下降量最大者及其相应的方向 若至少其中之一成立 则由xn k 出发沿s k 方向进行一维搜索 求出目标函数f x 的极小点x k 并作为k 1轮的初始点 即x0 k 1 x k 然后进行第k 1轮搜索 其搜索方向为挤掉sm k 并令s k 1 s k 即 注 新一轮的方向组是在前一轮的方向组中去掉sm k 同时把s k 放在方向组的最后构成 6 若上述判断条件不满足 则置k 1轮的初始点和方向组为 即此时k 1轮的n个搜索方向全部用第k轮的搜索方向 计算框图 min f xi 1 k isi k f xi 1 k hi k si k 4 无约束问题的梯度解法 使用导数的间接寻优法 对于可以求得目标函数导数的多变量寻优问题 这类方法收敛速度快 应优先选用 最速下降法 梯度法 牛顿法共轭梯度法变尺度法 1 最速下降法 梯度法 以负梯度方向作为搜索方向 并在此方向取最优的步长 直观 简单 开头几步下降很快 但越接近极值点收敛越慢 常与其他方法配合使用 是许多优化方法的基础 相邻两个搜索方向 梯度 互相垂直 故搜索路线为 之 形曲折线 形成 锯齿 现象 从x k 出发 搜索方向s k 取该点的负梯度方向 f x 沿此方向搜索 则函数值在该点附近下降最快 迭代公式 k 0 1 2 n x k 1 x k h k s k s k f x k 基本原理 例5 4 用梯度法求f x x12 4x22的极小值 取初始点x 0 1 1 t 初试点函数值为f x 0 5 对h求导并令其等于零 得 则 求minf x 0 hs 0 1 2h 2 4 1 8h 2 68 520h 0 h 0 0 13077 f x 1 0 55385 上式对h求导并令其等于零 得h 0 425 则 梯度法在选取搜索方向时使用了函数的一阶偏导数 而牛顿法则利用了函数的一阶导数和二阶导数 故所求目标函数在rn上必须具有连续的二阶偏导数 2 牛顿法 对于任何正定二次函数 可以从任意初始点出发 按迭代公式一次就可达到目标函数的极小点x 对于非二次函数 虽然不能一步求出极小点 但若以牛顿方向作为近似方向 按迭代式进行迭代 一般也会很快收敛于函数最优点 该法直接代入公式计算 采用定步长1 故不能保证每次迭代中目标函数值一定下降 若初始点选得不好 就不能保证具有良好的收敛性 甚至会收敛到鞍点或不收敛 修正牛顿法 修正方法 由x k 求x k 1 时 沿着x k 点处的牛顿方向进行一维搜索 将该方向上的目标函数最优点作为x k 1 这样就会避免收敛到鞍点或不收敛 修正牛顿法或阻尼牛顿法 1 取初始点x 0 给定收敛精度 令k 0 2 计算目标函数在x k 点的梯度 f x k 3 检验终止条件 若 f x k 则停止迭代 输出最优解x x k 及f x f x k 否则 进行第 4 步 4 计算x k 处的海森矩阵hk 并确定牛顿方向s k hk 1 f x k 修正牛顿法 简称牛顿法 迭代步骤 6 计算第k 1个迭代点 令k k 1 转第 2 步 f x k h k s k minf x k hs k x k 1 x k h k s k 5 求最优步长h k 牛顿法计算框图 对正定二次函数的寻优特别有效 迭代一次即达到极小点 对于一般目标函数 在极小点附近的收敛速度也很快 对函数的性态有较严格要求 函数需要具有一 二阶偏导数 海森矩阵必须处处正定 否则牛顿法将失败 海森矩阵必须为非奇异 否则无法求其逆矩阵 不能构成牛顿方向 计算复杂 需计算梯度 海森矩阵及其逆矩阵 牛顿法优缺点 3 共轭梯度法 属于共轭方向法 也是沿共轭方向进行搜索 但它是利用函数的负梯度方向旋转一个角度寻找共轭方向 搜索方向s k 1 梯度 系数 简化式 s 0 f x 0 s k 1 g k 1 k s k g k f x k g k 1 f x k 1 第1次搜索方向为负梯度方向 1 给定初始点x 0 迭代精度 和维数n 置迭代次数k 0 按梯度法进行第一次搜索 对于k 1 2 3 如果满足条件 f x k 则终止迭代 输出最优解 否则 转向步骤 2 2 计算搜索方向s k 的修正量 构造共轭方向s k 1 进行下一次迭代 3 当k n时 置x 0 x n 返回 1 否则返回 2 迭代过程和算法框图 例5 6 用共轭梯度法求f x x12 4x22的极小值 取初始点x 0 1 1 t 第1次迭代 计算初始点处的梯度 梯度的模和搜索方向 负梯度方向 为解题方便 下面采用解析法求h 0 对于二次函数f x 1 2xtax btx c f x k ax k b 在点x k 处的导数为 在点x 1 处极值存在的条件为 即 a x 0 h 0 s 0 b f x 0 h 0 as 0 0 f x 1 ax 1 b 0 补充 计算新迭代点x 1 的梯度和搜索方向修正量 进行第2次迭代 所以 无约束优化方法小结 迭代格式x k 1 x k h k s k 约束条件 5 3约束最优化方法 约束最优化方法 求解有约束最优化问题的方法 约束最优化问题的一般形式 gi x 0 i 1 2 m hj x 0 j 1 2 s s n minf x x rn 约束优化问题的局部解和全局解 当x 与它邻域的点x之距离 x x 时 总有f x f x 则x 称为该约束优化问题的一个局部最优点 对某些约束优化问题 局部解可能有多个 在所有局部解中 目标函数值最小的那个解称为全局最优解 简称全局解 约束优化问题的全局解一定是局部最优解 而局部最优解不一定是全局最优解 与无约束优化问题相同 二维多谷目标函数的局部最优解与全局最优解 a 无约束极小化问题 b 约束极小化问题 图b约束条件g1 x 0和g2 x 0构成两个可行域d1和d2 d1区域内的最优点为x1 d2区域内最优点为x2 和x3 因f x3 f x2 f x1 故x3 是全局最优点 x1 x2 是局部最优点 对于 从目标函数和不等式约束与等式约束的函数曲线可写出局部解 x1 1 0 t x2 5 0 t 因为x1 邻域内的任一满足约束的点 都有f x1 f x 同理 x2 点亦然 由于f x1 4 f x2 16 所以x1 是全局最优点 局部解与全局解 约束优化方法的分类 主要应用于不等式约束优化问题 无约束优化法求解 等式约束或不等式约束问题 有约束问题转化为无约束问题求解 消元法是将等式约束最优化问题转换为无约束最优化问题的一种最简单方法 1 消元法 2 拉格郎日乘子法 通过引进一个待定系数 乘子 将有约束优化问题转化为无约束优化问题的求解 该法既可用于求等式约束优化问题 也可用于求解不等式约束最优化问题 1 等式约束的拉格郎日乘子法 二维问题求目标函数f x1 x2 在满足等式约束g x1 x2 0条件下的极值 n维问题将二维问题扩展到n维目标函数f x 且具有m个等式约束条件 即gi x 0 i 1 2 m m n 拉格郎日函数的极值点存在的必要条件 拉格郎日函数的极值点就是原问题的最优解 构造拉格郎日函数 l x f x g x 即l x1 x2 f x1 x2 g x1 x2 这样就把有约束问题转化为无约束优化问题 求解方程组可得n m个解 即 x1 x2 xn 所求最优点 1 2 m 拉格郎日函数极小的必要条件 则拉格郎日函数为 例5 8 用拉格朗日法求目标函数 在等式约束g x x1 6 0条件下的最小点 2 不等式约束的拉格郎日乘子法 引入非负松弛变量 2 将不等式约束变为等式约束 把不等式约束变为等式约束后 再用拉格朗日乘子法求解 若有m个不等式约束 则需增加m个松弛变量 因此使计算工作量增大 引入松弛变量 可变为等式约束 基本步骤 如不等式约束 3 罚函数法 罚函数法也是一种将约束问题转换为无约束问题的间接寻优方法 又称代价函数法 罚函数法是应用最广的一种求解非线性规划问题的方法 可用于求解等式约束和不等式约束最优化问题 外点法 内点法 混合法 该法利用目标函数和约束条件 构造一个新的目标函数 罚函数 将有约束问题转化为无约束问题求解 1 等式约束优化问题的罚函数法 约束条件 设最优化问题 gi x 0 i 1 2 mm n minf x x rn 对罚函数求无约束极小值 设rk为第k步迭代所取罚因子 xk 为所得的 x rk 最小点 在第k l步迭代时 使rk 1 rk 则随着迭代过程的进行 xk 将收敛于f x 的最优解 这时必满足约束条件gi x 0 故求罚函的无约束极小值等价于求原问题的最优解 迭代计算 先取一个初始罚因子r1 求罚函数 x r1 极小值 得到无约束最优解x1 然后增大罚因子r2 r1 求 x r2 的极小值 得到x2 这样一直迭代 直到满足精度要求为止 2 不等式约束约束优化问题的罚函数法 外点法将罚函数定义于约束可行域的外面 在寻优过程中 搜索点从可行域外面逐步向最优点逼近 设最优化问题 构造新目标函数 gi x 0 i 1 2 mm n minf x x rn 即可行域内 x rk f x 而罚函数定义于可行域外 罚因子rk为递增数列 即0 r1 r2 rk rk 1 当约束条件gi x 0时 可变换 gi x 0 即罚函数中gi x 的符号由gi x 0或 0决定 由无约束求极值法可求罚函数无约束极小值 得到一系列无约束极小点组成的搜索点列 xk 最后可逼近原问题的最优解 迭代过程和算法框图 1 给定维数n 初始点x 0 初始惩罚因子r 1 0 迭代精