第五章-约束优化方法PPT课件.ppt

第五章约束优化方法 2020 3 18 1 2 约束随机方向法 3 复合形法 5 罚函数法 约束优化直接解法 约束优化间接解法 1 内点罚函数法 2 外点罚函数法 1 约束坐标轮换法 4 可行方向法 自学 第五章约束优化方法 根据求解方式的不同 可分为直接解法和间接解法两类 机械优化设计的问题 大多属于约束优化设计问题 其数学模型为 直接解法是将迭代点限制在可行域内 可行性 步步降低目标函数值 下降性 直至到达最优点 求出问题的约束最优解 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法 常用方法有 约束坐标轮换法 约束随机方向法 复合形法 可行方向法 线性逼近法等 常用方法有 罚函数法 拉格朗日乘子法等 2 第五章约束优化方法 直接解法是在满足不等式约束的可行设计区域内直接求出问题的约束最优解 属于直接解法的有 随机实验法 随机方向搜索法 复合形法 可行方向法等 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法 由于间接解法可以选用已研究比较成熟的无约束优化方法 并且容易处理同时具有不等式约束和等式约束的问题 因而在机械优化设计得到广泛的应用 间接解法中具有代表性的是惩罚函数法 3 直接解法的基本思想 在由m个不等式约束条件gu x 0所确定的可行域 内 选择一个初始点x 0 然后确定一个可行搜索方向S 且以适当的步长沿S方向进行搜索 取得一个目标函数有所改善的可行的新点x 1 即完成了一次迭代 以新点为起始点重复上述搜索过程 每次均按如下的基本迭代格式进行计算 x k 1 x k k S k k 0 1 2 逐步趋向最优解 直到满足终止准则才停止迭代 4 直接解法的原理简单 方法实用 其特点是 1 由于整个过程在可行域内进行 因此 迭代计算不论何时终止 都可以获得比初始点好的设计点 2 若目标函数为凸函数 可行域为凸集 则可获得全域最优解 否则 可能存在多个局部最优解 当选择的初始点不同 而搜索到不同的局部最优解 3 要求可行域有界的非空集 直接解法的特点 5 a 可行域是凸集 b 可行域是非凸集 6 间接解法的基本思路 将约束函数进行特殊的加权处理后 和目标函数结合起来 构成一个新的目标函数 即将原约束优化问题转化为一个或一系列的无约束优化问题 新目标函数 加权因子 然后对新目标函数进行无约束极小化计算 7 间接解法的基本思路 8 2020 3 18 9 第二节约束坐标轮换法 一 基本思路 可取定步长 加速步长和收缩步长 但不能取最优步长 1 依次沿各坐标轴方向 e1 e2 en方向搜索 2 将迭代点限制在可行域内 对每一迭代点均需进行可行性和下降性检查 2020 3 18 10 二 迭代步骤 2020 3 18 11 三 存在问题 有时会出现死点 导致输出 伪最优点 为辨别真伪 要用K T条件进行检查 3 1随机方向法的基本思路 1 在可行域内选择一个初始点 2 利用随机数的概率特性 产生若干个随机方向 3 从中选一个能使目标函数值下降最快的方向作为搜索方向d 4 从初始点x0出发 沿d方向以一定步长进行搜索 得到新点X 新点X应满足约束条件且f x f x0 至此完成一次迭代 基本思路如图所示 随机方向法程序设计简单 搜索速度快 是解决小型机械优化问题的十分有效的算法 第三节约束随机方向法 坐标轮换法有时会输出 伪最优点 用随机方向法可克服这一缺点 12 随机方向法的基本思路 13 3 2随机方向的构成 1 用RND X 产生n个随机数 2 将 0 1 中的随机数变换到 1 1 中去 归一化 3 构成随机方向 变换得 于是 第二节约束随机方向法 14 从k个随机方向中 选取一个较好的方向 3 3可行搜索方向的产生 第二节约束随机方向法 1 检验k个随机点是否为可行点 除去非可行点 计算余下的可行点的目标函数值 比较其大小 选出目标函数最小的点XL 2 比较XL和X0两点的目标函数值 若f XL f X0 则步长 0缩小 转步骤1 重新计算 直至f XL f X0 为止 如果 0缩小到很小 仍然找不到一个XL 使f XL f X0 则说明X0是一个局部极小点 此时可更换初始点 转步骤1 15 产生可行搜索方向的条件为 则可行搜索方向为 3 3可行搜索方向的产生 第二节约束随机方向法 16 3 4初始点的选择 随机方向法的初始点x0必须是一个可行点 既满足全部不等式约束条件 初始点可以通过随机选择的方法产生 1 输入设计变量的下限值和上限值 即 2 在区间 0 1 内产生n个伪随机数 3 计算随机点x的各分量 第二节约束随机方向法 4 判别随机点x是否可行 若随机点可行 用x代替x0为初始点 若非可行点 转到步骤2 重新产生随机点 只到可行为止 17 3 5 迭代过程 在初始点处产生一随机方向 若该方向适用 可行 则以定步长前进 若该方向不适用 可行 则产生另一方向 若在某处产生的方向足够多 50 100 仍无一适用 可行 则采用收缩步长 若步长小于预先给定的误差限则终止迭代 第二节约束随机方向法 18 3 6 流程图 X0 X F0 F 是 j 0 否 是 是 19 function x1 fx1 gx opt random2 f g cons xl xu TolX TolFun N length xl M size g cons M length M 1 gx ones M 1 whilemax gx 0dir0 rand N 1 x0 xl dir0 xu gx feval g cons x0 feval 执行由串指定的函数end fx0 feval f x0 xk x0 1 fxk feval f xk xmin x0 alpha 1 3 k1 0 flag1 1 whilenorm xk x0 TolX abs fxk fx0 TolFunk1 k1 1 x0 xmin fx0 feval f x0 3 7随机方向法的Matlab程序 20 dir0 rand N 1 2 1 dir0 dir0 norm dir0 xk x0 alpha dir0 gx feval g cons xk ifmax gx 0alpha alpha 0 7 elsefxk feval f xk iffxk fx0ifnorm xk x0 TolX abs fxk fx0 TolFunbreakelse xmin xk alpha 1 3 endx0 xk fx0 fxkelsealpha alpha endendendx1 x0 fx1 feval f x1 gx feval g cons x1 k1end 21 例 求 3 7随机方向法的Matlab程序 functionopt random1 test1 opt random1 test1 mclc clearall f inline x 1 2 x 2 x xl 3 3 xu 33 TolX 1e 8 TolFun 1e 8 x1 fx1 g opt random1 f fun cons xl xu TolX TolFun functiong fun cons x g x 1 2 x 2 2 9x 1 x 2 1 计算结果 x1 0 0076 3 0000 f 2 9999 g 0 0000 4 0076 22 第四节复合形法 复合形法是求解约束优化问题的一种重要的直接解法 基本思路 1 在可行域内构造一个具有k个顶点的初始复合形 2 对该复合形各顶点的目标函数值进行比较 找到目标函数最大的顶点 最坏点 3 然后按一定的法则求出目标函数值有所下降的可行的新点 并用此点代替最坏点 构成新的复合形 复合形的形状每改变一次 就向最优点移动一步 直至逼近最优点 由于复合形的形状不必保持规则的图形 对目标函数和约束函数无特殊要求 因此这种方法适应性强 在机械优化设计中应用广泛 23 4 1基本思路在可行域内选取若干初始点并以之为顶点构成一个多面体 复合形 然后比较各顶点的函数值 去掉最坏点 代之以好的新点 并构成新的复合形 以逼近最优点 第四节复合形法 24 4 2初始复合形生成的方法 1 由设计者决定k个可行点 构成初始复合形 设计变量少时适用 2 由设计者选定一个可行点 其余的k 1个可形点用随机法产生 3 由计算机自动生成初始复合形的所有顶点 第四节复合形法 初始复合形的构成 复合形的移动和收缩 25 26 4 2 1初始复合形的构成 1 复合形顶点数K的选择 建议 小取大值 大取小值 2 初始复合形顶点的确定 用试凑方法产生 适于低维情况 用随机方法产生 4 2初始复合形生成的方法 第四节复合形法 27 将非可行点调入可行域内 K个顶点中要求无一在可行域内 重新产生 K个顶点中有可行点 重新排列 将可行点依次排在前面 如有q个顶点X 1 X 2 X q 是可行点 其它K q个为非可行点 对X q 1 将其调入可行域的步骤是 先用随机函数产生个随机数 然后变换到预定的区间中去 用随机方法产生K个顶点 28 1 计算q个点集的中心X s 2 将第q 1点朝着点X s 的方向移动 按下式产生新的X q 1 即 若仍不可行 则重复此步骤 直至进入可行域为止 按照这个方法 同样使X q 2 X q 3 X K 都变为可行点 这K个点就构成了初始复合形 29 有两种基本运算 1 映射 在坏点的对侧试探新点 先计算除最坏点外各顶点的几何中心 然后再作映射计算 2 收缩 保证映射点的 可行 与 下降 X1为最坏点 映射系数常取 若发现映射点不适用 可行 则将减半后重新映射 4 3复合形法的搜索方法 30 4 4复合形法的迭代步骤 1 构造初始复合形 2 计算各顶点的函数值F X j j 1 2 K 选出好点X L 和坏点X H 3 计算坏点外的其余各顶点的中心点X 0 31 4 计算映射点X R 检查X R 是否在可行域内 若X R 为非可行点 将映射系数减半后再按上式改变映射点 直到X R 进入可行域内为止 5 构造新的复合形计算映射点的函数值F X R 并与坏点的函数值F X H 比较 可能存在两种情况 1 映射点优于坏点F X R F X H 在此情况 用X R 代替X H 构成新的复合形 32 若经过多次的映射系数减半 仍不能使映射点由于坏点 则说明该映射方向不利 此时 应改变映射方向 取对次坏点 的映射 再转回本步骤的开始处 直到构成新的复合形 2 映射点次于坏点F X R F X H 这种情况由于映射点过远引起的 减半映射系数 若有F X R F X H 这又转化为第一种情况 33 4 5判断终止条件1 各顶点与好点函数值之差的均方根值小于误差限 即 2 各顶点与好点的函数值之差的平方和小于误差限 即 3 各顶点与好点函数值差的绝对值之和小于误差限 即 如果不满足终止迭代条件 则返回步骤2继续进行下一次迭代 否则 可将最后复合形的好点X L 及其函数值F X L 作为最优解输出 34 4 6流程图 是 否 是 是 是 否 否 否 35 4 7复合形法的Matlab程序 程序清单 function xo fo go opt complex f g cons x0 xl xu TolX TolFun MaxIter N length x0 M size g cons M length M 1 k1 0 k N 1 单纯形顶点个数gx ones M 1 whilemax gx 0 x0 xl rand N 1 xu gx feval g cons x0 end 36 x1 fx gen complex x0 k f g cons flag1 1 flag2 1 flag3 1 k1 0fxx1fprintf 此处暂停 请按下任意键继续 n pausewhilek1 MaxIterflag1 1 flag2 1 flag3 1 k1 k1 1 fx I sort fx fori 1 kx2 i x1 I i endx1 x2 fmax1 fx k imax1 I k fmin fx 1 imin I 1 fmax2 fx k 1 imax2 I k 1 计算形心xc zeros N 1 fori 1 kxc xc x1 i end xc xc x1 imax1 xc xc k 1 gxc feval g cons xc alpha 1 31 反射xr xc alpha xc x1 imax1 gxr feval g cons xr ifmax gxr 0fxr feval f xr iffxr fmax1fprintf 反射成功 n fmax1 fxrfmax1 fxr fx imax1 fxr x1 imax1 xr flag1 1 else 反射失败flgg1 1 end 37 else 反射失败flag1 1 endgama 0 7 ifflag1 1fprintf 延伸 n xe xr gama xr xc gxe feval g cons xe ifmax gxe 0fxe feval f xe iffxe fmax1fprintf 延伸成功 n fxe fmax1fx imax1 fxe fmax1 fxe x1 imax1 xe flag2 1 else 延伸失败flag2 1 endelse 延伸失败flag2 1 endendbeta 0 7 ifflag1 1endelse 38 收缩失败flag3 1 endendifflag1 1k1 39 function x1 fx gen complex x0 k f g cons N length x0 M size g cons M length M 1 x1 1 x0 fx 1 feval f x0 a 1 3 s rand N k 2 ones N k s s norm s k2 1 whilek2 kx0 x1 1 a s k2 gx feval g cons x0 ifmax gx 0k2 k2 1 x1 k2 x0 fx k2 feval f x0 elsea 0 7 a endend 40 4 7应用复合形法Matlab程序求约束优化问题的最优解 functionopt complex test1 opt complex test1 mclc clearall f inline x 1 5 2 4 x 2 6 2 x TolX 1e 6 TolFun 1e 6 x0 8 14 xl 22 xu 79 MaxIter 65 options optimset LargeScale off xo fxo g opt complex f fun cons x0 xl xu TolX TolFun MaxIter 用复合形法求目标函数最优解和最优值 xo fo fmincon f x0 xl xu fun cons options 通过使用函数fmincon解决有约束的非线性优化问题 function cceq fun cons x c 64 x 1 2 x 2 2 x 1 x 2 10 x 1 10 ceq 应用opt complex函数计算结果 xo 5 21866 0635 fo 0 0639 g 0 0000 9 1551 4 7814 应用fmincon函数计算结果 xo 5 21866 0635 fo 0 0639 41 MATLAB中options optimset LargeScale off Simplex on display iter 这是对寻优函数搜索方式的设定 LargeScale指大规模搜索 off表示在规模搜索模式关闭 Simplex指单纯形算法 on表示该算法打开 display指结果方式 有四种off iter notify final iter是指中间结果每步都显示 一般选择final显示最终结果 在MATLAB运行窗口直接输入optimset可显示所有可设置的参数及对应的可选择的参数值 42 约束优化问题的间接解法 约束优化问题的间接解法是将约束优化问题转化为一系列无约束优化问题来进行求解的方法 约束优化问题的间接解法除拉格朗日乘子法外 常用的方法还有罚函数法及增广乘子法 虽然约束优化问题的间接解法可利用无约束优化问题的求解方法进行求解 但由于增加了拉格朗日乘子或罚因子 其求解过程与常规无约束优化问题有所不同 43 4 1概述 1 基本思想 将约束问题转化成无约束问题求解 构造惩罚函数的基本要求 惩罚项用约束条件构造 到达最优点时 惩罚项的值为0 当约束不满足或未到达最优点时 惩罚项的值大于0 第四节惩罚函数法 44 惩罚函数法是一种很广泛 很有效的间接解法 它的基本原理是将约束优化问题中的不等式和等式约束函数经加权后 和原目标函数结合为新的目标函数 惩罚函数 将约束优化问题转换为无约束优化问题 求解无约束优化问题的极小值 从而得到原约束优化问题的最优解 加权转化项 第四节惩罚函数法 45 惩罚函数法是按一定的法则改变加权因子的值 构成一系列的无约束优化问题 求一系列无约束最优解 并不断地逼近原约束优化问题的最优解 因此又称序列无约束极小化方法 常称SUMT方法 根据它们在惩罚函数中的作用 分别称障碍项和惩罚项 障碍项的作用是当迭代点在可行域内时 在迭代过程中将阻止迭代点越出可形域 惩罚项的作用是当迭代点在非可行域或不满足等式约束条件时 在迭代过程中将迫使迭代点逼近约束边界或等式约束曲面 46 4 2分类 内点法 将迭代点限制在可行域内 外点法 迭代点一般在可行域外 混合法 将外点法和内点法结合起来解GP型问题 按照惩罚函数在优化过程中迭代点是否可行 分为 内点法 外点法及混合法 第四节惩罚函数法 47 4 3SUMT内点法 内点惩罚函数法 障碍函数法 1 惩罚函数的构造 可取 式中 1 当X趋于D的边界时 中间函数B X 趋于无穷大 故又称为障碍 围墙 函数 r称为罚因子 在逐次迭代中越来越小 48 4 3 1基本思想 内点法将新目标函数 x r 构筑在可行域D内 随着惩罚因子r k 的不断递减 生成一系列新目标函数 xk r k 在可行域内逐步迭代 产生的极值点xk r k 序列从可行域内部趋向原目标函数的约束最优点x 例 求下述约束优化问题的最优点 min f x xx R1s tg x 1 x 0 X1 X2 X 4 3SUMT内点法 内点惩罚函数法 障碍函数法 49 4 3 2惩罚函数的形式 其中 惩罚 加权 因子罚因子降低系数 罚因子递减速率 c 0 c 1 4 3SUMT内点法 内点惩罚函数法 障碍函数法 50 4 3 3迭代步骤 选取合适的初始点x 0 以及r 0 c 计算精度 1 2 令k 0 2 构造惩罚 新目标 函数 3 调用无约束优化方法 求新目标函数的最优解xk 和 xk r k 4 判断是否收敛 运用终止准则 前后两次无约束极小点之间的距离 相邻两点罚函数的相对误差 若均满足 停止迭代 有约束优化问题的最优点为x xk 若有一个准则不满足 则令并转入第3步 继续计算 4 3SUMT内点法 内点惩罚函数法 障碍函数法 51 下面介绍内点法中的初始点 惩罚因子初值及其缩减系数的选取和收敛条件的确定 1 初始点的选取 初始点应选离约束边界较远的可行点 程序设计时 一般 考虑具有人工输入和计算机自动生成可行初始点的两种功能 4 3SUMT内点法 52 1 初始点x 0 的选择方法 人工估算 需要校核可行性 计算机随机产生 也需校核可行性 搜索方法 任意给出一个初始点 判断其可行性 若违反了S个约束 求出不满足约束中的最大值 应用优化方法减少违反约束 以求得的设计点作为新初始点 继续其判断可行性 若仍有不满足的约束 则重复上述过程 直至初始点可行 4 3SUMT内点法 内点惩罚函数法 障碍函数法 53 2 惩罚因子的初值的选取 惩罚因子的初值选取应适当 否则会影响迭代计算的正常进行 太大会影响迭代次数 太小会使惩罚函数的形态变坏 难以收敛到极值点 1 取r0 1 根据试算的结果 再决定增加或减少r0值 2 按经验公式 计算r0值 这样选取的r0 可以是惩罚函数中的障碍项和原目标函数的值大致相等 不会因障碍项的值太大则起支配作用 也不会因障碍项的值太小而被忽略掉 54 3 惩罚因子的缩减系数c的选取 在构造序列惩罚函数时 惩罚因子r是一个逐次递减到0的数列 相邻两次迭代的惩罚因子的关系为 惩罚因子的缩减系数通常的取值范围 0 1 0 7之间 55 罚因子 为使与原问题同解 应使 对于一个 求解一个无约束优化问题 前一问题的结果为后一问题的初值 故为系列无约束极小化方法 SequentialUnconstrainedMinimizationTechnique 56 4 收敛条件 前后两次无约束极小点之间的距离 相邻两点罚函数的相对误差 57 5 几个参数选择小结 惩罚因子初始值r 0 的选择 过大 过小均不好 建议考虑选择 2 降低系数c的选择 c的典型值为0 1 0 7 建议先试算 3 初始点x 0 的选择 要求 在可行域内 不要离约束边界太近 方法 人工估算 需要校核可行性 计算机随机产生 也需校核可行性 4 3SUMT内点法 内点惩罚函数法 障碍函数法 58 6 方法评价 用于目标函数比较复杂 或在可行域外无定义的场合下 由于优化过程是在可行域内逐步改进设计方案 故在解决工程问题时 只要满足工程要求 即使未达最优解 接近的过程解也是可行的 初始点和序列极值点均需严格满足所有约束条件 不能解决等式约束问题 4 3SUMT内点法 内点惩罚函数法 障碍函数法 59 4 3SUMT内点罚函数法迭代步骤 60 例 解 惩罚函数 在D内 对于固定的 令 得 4 3SUMT内点法 内点惩罚函数法 障碍函数法 61 62 内点法是将惩罚因数定义于可行域内 而外点法与内点法不同 是将惩罚项函数定义于可行区域的外部 序列迭代点从可行域外部逐渐逼近约束边界上的最优点 4 4外点惩罚函数法 衰减函数法 外点法可以用来求解含不等式和等式约束的优化问题 对于约束优化问题 63 惩罚因子 它是由小到大 惩罚项 由惩罚项可知 当迭代点不可行时 惩罚项的值大于零 当迭代点离约束边界越远时 惩罚项愈大 这可看成是对迭代点不满足约束条件的一种惩罚 转化后的外点惩罚函数的形式为 64 1 基本思想 外点法将新目标函数 x r 构筑在可行域D外 随着惩罚因子r k 的不断递增 生成一系列新目标函数 xk r k 在可行域外逐步迭代 产生的极值点xk r k 序列从可行域外部趋向原目标函数的约束最优点x 例 求下述约束优化问题的最优点 min f x xx R1s tg x 1 x 0 新目标函数 4 4 4外点惩罚函数法 衰减函数法 65 惩罚项是罚因子和中间函数的乘积 内点法中随着设计变量移向约束函数的边界 中间函数值不断增加 罚因子不断减小 在迭代过程中惩罚项最终趋于零 外点法 即在迭代过程中随着设计