《约束优化方法》PPT课件.ppt

1 第五章约束优化方法 5 1约束优化问题的最优解5 2约束优化问题极小点的条件5 3常用的约束优化方法5 3 1约束坐标轮换法5 3 2约束随机方向法5 3 3复合形法5 3 5惩罚函数法 2 概述 约束优化问题 约束最优解和无约束最优解无论是在数学模型上还是几何意义上均是不同的概念 3 等值线 等值线族的中心 无约束最优解解 等值线的共同中心 数学模型 4 数学模型 可行域 约束最优解 5 无约束最优点 约束最优点 6 约束优化问题的类型 1 不等式约束优化问题 IP型 2 等式约束优化问题 EP型 3 一般约束优化问题 GP型 7 约束优化方法分类 约束优化方法 约束坐标轮换法直接法 约束随机方向法复合形法 间接法 惩罚函数法 直接法 设法使每一次迭代产生的新迭代点限制在可行域内 且一步一步的降低目标函数值 直至最后获得一个可行域内的约束最优解 间接法 将约束优化问题通过一定形式的变换 转化为无约束优化问题 然后采用约束优化方法进行求解 8 5 3 1约束坐标轮换法 基本思想 与无约束坐标轮换法类似 依此沿坐标轴方向寻优 逐步逼近最优点 9 任取一个初始点 取初始步长 0 沿e1方向 检查 可行性 适用性 检查 加速步长 检查 可行性 适用性 10 沿e2方向 检查 可行性 适用性 检查 可行性 适用性 检查 可行性 适用性 检查 可行性 适用性 11 沿e1方向 检查 可行性 适用性 检查 可行性 适用性 沿e2方向 检查 可行性 适用性 检查 12 沿坐标轴方向找不到合适的点 缩减初始步长 0 0 5 0继续迭代终止准则 0 约束坐标轮换法与无约束坐标轮换法的区别 步长无约束 最优步长约束 加速步长 对每一个迭代点的检查无约束 检查适用性约束 检查适用性和可行性 终止准则无约束 点距准则约束 步长准则 13 特点 约束坐标轮换法具有算法明了 迭代简单 便于设计者掌握运用等优点 但是 它的收敛速度较慢 对于维数较高的优化问题 例如10维以上 很费机时 另外 这种方法在某些情况下还会出现 死点 的病态 导致输出伪最优点 避免输出伪最优点的办法 1 输入不同的初始点2 用不同的不长多次计算 14 基本原理 典型的 瞎子爬山 式的数值选代解法 在可行域内 任选初始点x 0 以给定的步长a a0 沿按某方法产生的随机方向S 1 取探索点x x 0 aS 1 若该点同时符合下降性 F x F x 0 和可行性 x D 则表示x点探索成功 并以它为新的起始点 继续按上面的迭代公式在S 1 方向上获取新的成功探索点 5 3 2约束随机方向法 15 5 3 2约束随机方向法 任取一个初始点 取初始步长 0 利用随机函数构成随机方向S 1 检查 可行性 适用性 检查 若m个方向都不行 则减小步长 0 0 5 0 终止准则 0 16 说明当在某个转折点处沿m个 预先限定的次数 随机方向试探均失败 则说明以此点为中心 0为半径的圆周上各点都不是适用 可行点 此时 可将初始步长 0缩半后继续试探 直到 0 且沿m个随机方向都试探失败时 则最后一个成功点 如图中的x 3 就是达到预定精度 要求的约束最优点 迭代即可结束 m是预先规定在某转折点处产生随机方向所允许的最大数目 一般可在50 500范围内选取 约束随机方向法的搜索方向比坐标轮换法要灵活得多 当预定的随机方向限定数m足够大时 它不会像约束坐标轮换法那样出现 病态 而导致输出伪最优点 17 随机搜索方向的产生 在 a b 之间的随机数 yi ai bi ai 1 1 之间的随机数 yi 2 1 设是在区间 一l 1 上的两个随机数 将它们分别作为坐标轴上的分量所构成的向量即为相应的二维随机向量 其单位向量 同理 n维问题 随机方向的单位向量 在算法语言所使用的函数库中 有一种随机函数RND X 利用这一随机函数可在程序运行过程中产生一个0到1之间的随机数 i l 2 n 18 约束随机方向搜索法的特点 对目标函数的性态无特殊要求 程序设计简单 使用方便 在维数较少的情况下是一种十分有效的方法 适用于小型问题 19 5 3 3复合形法 基本思想 在可行域中选取K个点作为一复合形 多面体 的K个顶点 比较各点函数值的大小 去掉函数值最大所对应的最坏点 而代之最坏点的映射点构成新的复合形 不断重复上述过程 使复合形不断向最优点移动和收缩 直至满足选代精度为止 1 3 2 X0 X R n l k 2n 20 引例 设有一约束优化问题的数学模型 21 一 复合形法的基本思想 步骤 第一步 初始复合形的构成顶点X 1 X 2 X 3 第二步 对复合形进行调优迭代计算顶点X 1 X 2 X 3 F1 F2 F3 X H X L 坏点好点先求出除坏点外 其余各点构成的图形的形心点X0再求坏点X H 相对于形心点X0的映射点X R 1 3 2 X0 X R 22 步骤 第一步 初始复合形的构成第二步 对复合形进行调优迭代计算形心点X0映射点X R 反射系数 一般开始是取 1 3 1 3 2 检查 可行性 适用性 新复合形 4 点的映射复合形的收缩 23 二 初始复合形的构成 方法一 试凑法方法二 随机产生 1 产生K个随机点 随机数 i l 2 n 2 将非可行点调入可行域 1 2 3 4 24 终止条件 25 例 用复合形法求解下例约束最优化问题 迭代精度取 解 取复合形的顶点数 1 获得初始复合形 本例采用人为给定四个点 检验各点是否可行 将各点的坐标值代入以上三个约束方程 均满足约束要求 这四个点为可行点 用作初始复合形的四个顶点 26 2 迭代计算获得新复合形 计算复合形各顶点目标函数值 定出最坏点最好点计算除坏点外其余各顶点的中心 将代入诸约束条件均满足 可知在可行城内 取 求坏点的映射点 在可行域内 27 计算并与比较 用替换 亦即替换构成新的复合形 比较各点目标函数值 定出最坏点 最好点 3 检验迭代终止条件 28 29 复合形法的特点 对目标函数及约束函数无特殊要求 适应性强 计算量一般 收敛较快 适用中小型问题 是现有解不等式约束优化问题的一种重要的直接法 30 5 3 5惩罚函数法 将约束优化问题通过一定形式的变换 转化为无约束优化问题 然后采用约束优化方法进行求解转化必须满足条件 1 不破坏原约束问题的约束条件 2 最优解必须归结到原约束问题的最优解上去 约束优化问题的间接法有 消元法 拉格朗日乘子法 惩罚函数法等 31 min x r k m k 5 56 x Rn 式中 x r k m k 为增广函数 称为惩罚函数 简称罚函数 将一般约束优化问题数学模型minF x x Rn gu x 0 u l 2 p hv x 0 v 1 2 q 转化成为一个如下的无约束优化问题 构造的新目标函数一般形式为 惩罚函数法 惩罚项 32 按照惩罚函数构成的形式不同 惩罚函数法又分为三种 1 内点惩罚函数法2 外点惩罚函数法3 混合惩罚函数法 33 一 内点惩罚函数法 基本思想 将新目标函数定义于可行域内 序列迭代点在可行域内逐步逼近原目标函数约束边界上的最优点 将约束优化问题 minF x x gu x 0 u 12 m 转化为无约束优化问题其中 r 1 r 2 r 3 r k 0是一个递减的正值数列 r k Cr k 1 0 C 1 k 0 34 内点惩罚函数法的思路 当X由可行域内靠近任一约束边界时 惩罚项值趋于无穷大 所以它就像围墙一样阻止迭代点越出约束边界 条件1 不破坏原约束问题的约束条件 35 min x r k min F x r k 1 gu x 条件2 最优解必须归结到原约束问题的最优解上去 36 解 若用内点法求解此约束最优化问题 由式知惩罚函数为 将函数对求导 得 令 解得无约束极小值的点列为 例 用内点法求解 的约束最优化问题 无约束极小值点列相应的惩罚函数值为 37 38 序列极小点都在可行域内 39 初始点x 0 的确定自定法 搜索法先任取一个设计点x k 计算x k 点的诸约束函数值gu x k u 1 2 p 若 构造 按照该数学模型解出的最优点x 至少比原设计点x k 多满足一个约束条件重复数次 直到所有的约束条件都得到满足 最终可取得在可行域内部的初始点x 0 40 关于几个参数的选择 1 初始罚因子r 0 的选取 一般可取初始罚因子r 0 1 50也有建议取 2 递减系数C的选择通常建议取C 0 1 0 5 41 内点惩罚函数法的特点 在给定一个可行初始方案后 能求出一系列逐步得到改进的可行的设计方案 但只适用于解不等式约束优化问题 且初始点须在可行域内 42 已知约束优化问题 试写出内点罚函数 并选出初始迭代点 内点罚函数 例 43 例 桁架设计问题 minF x 1 57x1x x1x2 T 44 设有不等式约束优化问题 构造外点法惩罚函数的常见形式如下 惩罚因子r k 规定取正 且在优化过程中r k 取为递增数列r k Cr k 1 C 1则将保证 k 二 外点惩罚函数法 基本思想 将新目标函数定义于可行域外 序列迭代点在可行域外逐步逼近原目标函数约束边界上的最优点 45 式中 外点惩罚函数法的思路 可行域内时 新目标函数就是原目标函数 当X位于可行域外时 惩罚项为正值 新目标函数值增大 就构成了对不满足约束条件时的一种 惩罚 且离可行域越远 惩罚就越严厉 当r k 不够大时 罚函数 新目标函数 的极小值在可行域外 即惩罚不够 可加大r k 随着r k 的增大 使新目标函数 的极小点越来越逼近原目标函数极小点 可行域外可行域内 46 对于解不等式约束优化问题minF x xx R1 g1 x x 1 0用外点法构造惩罚函数 具体构造形式如下 写成另一种形式 例 47 令 解得无约束极小值的点列为 无约束极小值点列相应的惩罚函数值为 求惩罚函数极小点 48 由此可见 当惩罚因子为一递增正值数列时 其极值点离约束最优点愈来愈近 的差值与愈来愈小 当时 亦即逼近于真正的约束最优解 无约束极值点列随值递增从可行域外向最优点收敛 49 对几个问题的讨论初始点x 0 的选取 外点法的初始点x 0 可以任选 即在可行域与非可行域选取均可 2 初始罚因子r 0 和递增系数C的选取初始罚因子r 0 选得是否恰当 对算法的成败和计算速度仍有着显著的影响 因此 选取时要谨慎 递增系数C的取值 一般影响不太显著 但也不宜取得过大 通常取C 5 10 3 约束容差带用外点法求解时 由于罚函数的无约束最优点列是从可行域外部向约束最优点逼近的 所以最终取得的最优点一定是在边界的非可行域一侧 严格地说 它是一个非可行点 这对某些工程问题可能是不允许的 为了解决这一问题 可在约束边界的可行域一侧加一条容差带 如图5 21 这就相当于将约束条件改为gu x u 0 u 1 2 p式中的 u是容差量 一般可取 u 10 3 10 4 50 约束容差带 51 外点法不但可以解不等式约束优化问题 而且还可以解等式约束优化问题用外点法求解二维等式约束优化问题 按外点法的基本思想 构造惩罚函数 52 外点法的特点外点法既可解不等式约束优化问题 也能解等式约束优化问题 且其初始点x 0 可任选 即在可行域中或非可行域中均可 其缺点是序列无约束最优点是一系列的非可行点 对于工程设计一般是不可取的 为使最终的迭代点能落入可行域 必须设置约束容差带 53 例 已知约束优化问题 试写出外点罚函数 并选出初始迭代点 外点罚函数 54 三 混合法用罚函数法解决有等式约束和不等式约束的一般约束 GP型 优化问题的方法 把它称为混合惩罚函数法 简称混合法 一般约束优化问题的数学模型 minf x x gu x 0 u 12 p hv x 0 v 12 q q n 55 内点形式的混合型惩罚函数法 r k 递减m k 递增初始点必须是严格的内点为了统一用一个内点法惩罚因子 上式也可写成 不等式约束部分按内点法形式处理 r k 递减 56 r k 递增 外点形式的混合型惩罚函数法 不等式约束部分按外点法形式处理 57 如何判断优化结果的正确性 1 约束优化问题 最优点大多位于边界上 2 输入不同的初始点多次计算 3 用不同的方法解 作业 1 了解各种方法的基本思想和特点2 P130题237 58 机械优化举例 已知给定轨迹曲线 其上 个主要点的坐标见下表 并给定 该机构主要传递运动 对动力特性要求不高 试设计一曲柄摇杆机构 使其连杆上点 的连杆曲线 最佳逼近已知曲线 59 60 61 可以取 5 62 1 对于四杆机构 其各构件的长度应满足 目标函数 设计变量