机械优化设计约束优化方法PPT课件.ppt

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