《机械优化设计之约束优化方法讲义课件(ppt 48页)》由会员分享,可在线阅读,更多相关《机械优化设计之约束优化方法讲义课件(ppt 48页)(48页珍藏版)》请在金锄头文库上搜索。
1、2020 2 22 1 第五章约束优化方法 一 约束坐标轮换法 二 约束随机方向法 三 复合形法 四 可行方向法 五 罚函数法 六 拉格朗日乘子法 七 简约梯度法及广义简约梯度法 2020 2 22 2 5 1优化方法的类型 2 间接法 1 直接法 将迭代点限制在可行域内 可行性 步步降低目标函数值 下降性 直至到达最优点 常用方法有 约束坐标轮换法 约束随机方向法 复合形法 可行方向法 线性逼近法等 通过变换 将约束优化问题转化为无约束优化问题求解 常用方法有 罚函数法 拉格朗日乘子法等 可解IP型问题 可解各类问题 按对约束条件的处理方法分 2020 2 22 3 5 2约束坐标轮换法 一
2、 基本思路 可取定步长 加速步长和收缩步长 但不能取最优步长 1 依次沿各坐标轴方向 e1 e2 en方向搜索 2 将迭代点限制在可行域内 对每一迭代点均需进行可行性和下降性检查 2020 2 22 4 二 迭代步骤 2020 2 22 5 三 存在问题 有时会出现死点 导致输出 伪最优点 为辨别真伪 要用K T条件进行检查 2020 2 22 6 5 3约束随机方向法 基本思路 若该方向适用 可行 则以定步长前进 坐标轮换法有时会输出 伪最优点 用随机方向法可克服这一缺点 若该方向不适用 可行 则产生另一方向 若在某处产生的方向足够多 仍无一适用 可行 则采用收缩步长 若步长小于预先给定的误
3、差限则终止迭代 搜索方向 采用随机产生的方向 2020 2 22 7 二 随机方向的构成 1 用RND X 产生n个随机数 2 将 0 1 中的随机数变换到 1 1 中去 3 构成随机方向 变换得 于是 2020 2 22 8 X0 X F0 F 三 随机方向法的迭代步骤 是 j 0 否 是 是 2020 2 22 9 5 4复合形法 基本思路在可行域内选取若干初始点并以之为顶点构成一个多面体 复合形 然后比较各顶点的函数值 去掉最坏点 代之以好的新点 并构成新的复合形 以逼近最优点 有两种基本运算 1 映射 在坏点的对侧试探新点 先计算除最坏点外各顶点的几何中心 然后再作映射计算 2 收缩
4、保证映射点的 可行 与 下降 X1为最坏点 映射系数常取 若发现映射点不适用 可行 则将减半后重新映射 2020 2 22 10 二 初始复合形的构成 1 复合形顶点数K的选择 2 为避免降维 K应取大些 但过大 计算量也大 1 为保证迭代点能逼近极小点 应使 2020 2 22 11 2 初始复合形顶点的确定 1 用试凑方法产生 适于低维情况 2 用随机方法产生 用随机方法产生K个顶点 先用随机函数产生个随机数 然后变换到预定的区间中去 这便得到了一个顶点 要连续产生K个顶点 2020 2 22 12 将非可行点调入可行域内 检查已获得的各顶点的可行性 若无一可行 则重新产生随机点 若有q个
5、可行 则转下步 计算q个可行点点集的几何中心 将非可行点逐一调入可行域内 若仍不可行 则重复此步骤 直至进入可行域为止 2020 2 22 13 三 终止判别条件 各顶点与好点函数值之差的均方根应不大于误差限 2020 2 22 14 四 复合形法的迭代步骤 是 否 是 是 是 否 否 否 2020 2 22 15 5 5可行方向法 其特点是注意到约束最优点通常在约束边界上 为此 可先找出一个边界点 然后沿边界搜索 是求解大型约束优化问题的主要方法 一 寻找边界点的方法 1 在D内取一初始点 然后沿负梯度方向搜索 直至使迭代点超越D或落在边界上 2 若迭代点在D外 则将它调回到边界上 2020
6、 2 22 16 二 产生适用可行方向的办法 一 适用可行方向的数学条件 1 适用 下降 性条件 在迭代点处 目标函数沿该方向的方向导数应小于0 与负梯度方向的夹角应小于900 2020 2 22 17 2 可行性条件 在边界迭代点处 实时约束函数沿该方向的方向导数应不小于0 与实时约束函数梯度方向的夹角应不大于900 1 可行方向 迭代公式 只要取适当的 能使仍在D内 则称可行方向 2 可行性条件 2020 2 22 18 若迭代点处于J个约束边界的相交处 应同时成立 综上所述 适用可行方向的数学条件为 几何解释 2020 2 22 19 二 最有利的适用可行方向 在满足上述适用可行方向的数
7、学条件的同时 使目标函数的方向导数为负且达到最小 处理为线性规划问题 1 条件余度 0 一般取为0 01 0 001 2 方向偏离系数 0 对线性约束取为0 其余取为1 规格化条件 2020 2 22 20 三 步长因子的确定 1 最优步长因子 迭代点为内点时使用 下一迭代点如仍为内点 继续进行 直至迭代点到边界或域外时止 迭代公式 2 试验步长因子 将在处作泰勒展开 仅取到线性项 1 迭代点在边界附近偏域内一侧时使用 采用最有利的适用可行方向 2 按此法 直至使迭代点进入约束容差带或至域外为止 1 为保证是的一个邻近点 的值不能取得太大 通常 2020 2 22 21 2 调整步长因子 将已
8、出界的迭代点调回到边界上 1 约束边界容差带 在实际计算中 应给约束边界一个允许的误差限 式中 通常取0 01 0 001 只要迭代点进入容差带 即认为达到了边界 2 调整步长因子 因与很接近 可认为在这两点间按线性变化 1 为使新迭代点落在容差带中部 取 3 还需检验该点是否在容差带内 若不满足 则 若 则 若 则 重复以上步骤 直至满足时止 2020 2 22 22 M 0 四 终止迭代准则 采用K T条件 对J个起作用约束 求解线性方程组 五 迭代步骤 2020 2 22 23 5 6惩罚函数法 一 概述 1 基本思想 将约束问题转化成无约束问题求解 构造惩罚函数的基本要求 惩罚项用约束
9、条件构造 到达最优点时 惩罚项的值为0 当约束不满足或未到达最优点时 惩罚项的值大于0 2 分类 内点法 将迭代点限制在可行域内 外点法 迭代点一般在可行域外 混合法 将外点法和内点法结合起来解GP型问题 2020 2 22 24 二 SUMT内点法 1 惩罚函数的构造 可取 式中 1 当X趋于D的边界时 B X 趋于无穷大 故又称为障碍 围墙 函数 2020 2 22 25 2 罚因子 为使与原问题同解 应使 对于一个 求解一个无约束优化问题 前一问题的结果为后一问题的初值 故为系列无约束极小化方法 SequentialUnconstrainedMinimizationTechnique 2
10、020 2 22 26 2 SUMT内点罚函数法迭代步骤 2020 2 22 27 例 解 惩罚函数 在D内 对于固定的 令 得 2020 2 22 28 2020 2 22 29 1 初始点X0的确定 必须为内点 用现有机器参数作初值 用图解法 用随机方法 用内点法求内点 3 应用内点法应注意的问题 X0 r 0 c的确定 2020 2 22 30 I2为空集 2020 2 22 31 2 罚因子的初值 过大 会使的最优点比X0离真正的最优点更远 过小 在域内的惩罚作用小 在接近边界时则突然加大使性态变坏 且有可能使迭代点越出可行域 Fox推荐 3 递减系数C 本书推荐0 1 0 5 202
11、0 2 22 32 三 SUMT外点法 1 惩罚函数的构造 考虑非线性规划问题 惩罚函数可取为 2 罚因子 1 时 惩罚项为0 不惩罚 时 惩罚项大于0 有惩罚作用 因边界时 惩罚项中大括号中的值趋于0 为保证惩罚作用 应取 2020 2 22 33 2 SUMT外点法的迭代步骤 为使迭代点进入可行域 可设约束容差带 2020 2 22 34 例 解 惩罚函数 在D外 对于固定的 令 得 2020 2 22 35 3 外点法与内点法的比较 1 外点法可解各类问题 内点法仅适于IP型问题 2 外点法的初始点可任选 内点法的初始点必须为内点 3 外点法的极小点系列一般在D外 内点法的极小点系列在D
12、内 全为可行点 2020 2 22 36 四 SUMT混合法 有等式约束时内点法不能用 要求迭代点始终满足不等式约束时外点法不能用 此时可将外点法和内点法结合起来解GP型问题 1 迭代点应始终满足 2 Fiacco等人建议 2020 2 22 37 5 7拉格朗日乘子法 一 等式约束问题的拉格朗日乘子法 s t 1 建立拉氏函数 2 在最优点处有如下n q个方程成立 其解为 2020 2 22 38 s t 二 含不等式约束问题的拉格朗日乘子法 1 建立拉氏函数 再用前述方法建立拉氏函数 对不等式约束引入松弛变量 使之成为等式约束 2020 2 22 39 2 在最优点处有如下n q 2p个方
13、程成立 其解为 2020 2 22 40 三 增广拉格朗日乘子法 采用拉格朗日乘子法时求解有难度 而罚函数法当迭代点接近边界时函数常有病态 此法的思路是把两者结合起来 其增广拉格朗日函数为 特点 1 初始点可为非可行点 2 因增加了可调参数 其收敛速度和稳定性都优于罚函数法 2020 2 22 41 5 8简约梯度法及广义简约梯度法 思路 利用约束条件消去非独立变量 使问题简化 再沿简化后的目标函数的负梯度方向搜索 一简约梯度法 1 问题 s t 2 简约梯度 1 将问题降维 基向量 状态 式中 将X分成两部分 2020 2 22 42 非基向量 决策 对应的系数矩阵也分成两部分 式中 B为对
14、应于XB的m阶方阵 且必须为满秩矩阵 C为对应于XN的阶矩阵 故 2020 2 22 43 2 求简约梯度 2 式中 3 迭代计算 1 迭代公式 3 2020 2 22 44 1 在迭代中需保证各分量值大于或等于零 2 当且时 因 必有 不可行 写成分量的形式 4 迭代方向应作修正 当 时 在一般情况下 5 2020 2 22 45 2 步长因子的确定 1 若各分量值大于零 则只要均能保证变量非负 此时可取最优步长 2 若 由于必须使 6 故 于是有 2020 2 22 46 3 确定的方法 由 1 有 通过 3 和 7 可完成一次完整的迭代 7 2020 2 22 47 允许部分变量的上下界为 二广义简约梯度法简介 可引入松弛变量将不等式约束变为等式约束 2 解法特点 1 和之间的关系难以用简单的式子表达 一般采用牛顿迭代法解非线性方程组获得 2 求简约梯度用到的可用复合函数求导的方法求得 精品资料网 成立于2004年 专注于企业管理培训 提供60万企业管理资料下载 详情查看