机械优化设计课件 第6章 约束优化方法
开放 包容 求实 创新机械优化设计第六章 约束优化方法第六章第六章 约束优化方法约束优化方法约束优化问题的数学模型约束优化问题的数学模型 :约束优化问题有解的条件:约束优化问题有解的条件:(1)目标函数和约束函数为连续、可微函数,且存在一个有界的可行域D; (2) 可行域D应是一个非空集,即存在满足约束条件的点列 :第一节第一节 概概 述述约束优化问题的解法:约束优化问题的解法: 直接解法:直接解法:仅含不等式约束的问题等式约束函数不是复杂的隐函数,且易于消元(随机方向法、复合形法) 间接解法:间接解法:同时具有等式和不等式约束的优化问题(惩罚函数法)第六章第六章 约束优化方法约束优化方法第一节第一节 概概 述述直接解法:直接解法:基本思想:在可行域内按照一定的原则直接搜索出它的最优点。步骤:在m个不等式约束条件所确定的可行域内,选择一个 初始点x0,然后决定可行的搜索方向d,再以适当的步长 ,沿着d方向进行搜索,得到一个使目标函数值下降的 可行的新点x1,这就完成了一次迭代。接着以新点x1为 起点,重复上面的搜索过程,满足收敛条件后,终止迭 代。 可行的搜索方向第六章第六章 约束优化方法约束优化方法第一节第一节 概概 述述直接解法:直接解法:第六章第六章 约束优化方法约束优化方法第一节第一节 概概 述述直接解法的特点:直接解法的特点:由于整个求解过程都是在可行域内进行的,所以,迭代 计算无论何时终止,都可获得一个比初始点更好的设计点;若目标函数是凸函数,可行域是凸集,则可保证获得全 域最优解。要求可行域为有界的非空集,即在有界可行域内存在 满足全部约束条件的点,且目标函数有定义。第六章第六章 约束优化方法约束优化方法第一节第一节 概概 述述间接解法:间接解法:基本思路:原目标函数约束函数新的目标函数加权(约束优化问题)(无约束优化问题 )第六章第六章 约束优化方法约束优化方法第一节第一节 概概 述述间接解法:间接解法:迭代过程:第六章第六章 约束优化方法约束优化方法第一节第一节 概概 述述间接解法:间接解法:第六章第六章 约束优化方法约束优化方法第一节第一节 概概 述述间接解法的特点:间接解法的特点:计算效率和数值计算的稳定性有较大提高。可以有效地处理具有等式约束的约束优化问题 。选择加权因子困难。第六章第六章 约束优化方法约束优化方法第一节第一节 概概 述述随机方向法解法内容包括:随机方向法解法内容包括:随机选择初始点随机选择搜索方向随机选取搜索步长等第六章第六章 约束优化方法约束优化方法第二节第二节 随机方向法随机方向法随机方向法基本思路:随机方向法基本思路:在可行域内选择一个初始点,以某种随机的形式在初始点周围产生几个随机方向,从中选择一个使目标函数值下降最快的方向作为可行搜索方向。从初始点出发沿着该可行搜索方向搜索,得到一个新点。若新点满足约束条件,且函数值下降,则完成一次迭代。将始点移到新点,重复上面的过程,最终得到最优解。第六章第六章 约束优化方法约束优化方法第二节第二节 随机方向法随机方向法随机方向法基本思路:随机方向法基本思路:迭代公式:第六章第六章 约束优化方法约束优化方法第二节第二节 随机方向法随机方向法随机数的产生:随机数的产生:第六章第六章 约束优化方法约束优化方法第二节第二节 随机方向法随机方向法初始点的选择:初始点的选择:人为选择随机选择法随机选择法的步骤第六章第六章 约束优化方法约束优化方法第二节第二节 随机方向法随机方向法可行搜索方向的产生:可行搜索方向的产生:第六章第六章 约束优化方法约束优化方法第二节第二节 随机方向法随机方向法可行搜索方向的产生:可行搜索方向的产生:第六章第六章 约束优化方法约束优化方法第二节第二节 随机方向法随机方向法产生可行搜索方向的条件产生可行搜索方向的条件 :法则一:法则一:如果沿着某一方向搜索得到了更大的目标函数,则相反的方向通常会导致较小的目标函数; 法则二:法则二:如果沿着某一特定方向有过连续的成功搜索,则应使下一次搜索偏向这个方向;反之,如果沿着某一方 向连续地有失败搜索则不鼓励下一次在该方向搜索。第六章第六章 约束优化方法约束优化方法第二节第二节 随机方向法随机方向法搜索步长的确定:搜索步长的确定:可由加速步长法确定可由加速步长法确定每次迭代的步长: = (=1.3)第六章第六章 约束优化方法约束优化方法第二节第二节 随机方向法随机方向法随机方向法的步骤:随机方向法的步骤:第六章第六章 约束优化方法约束优化方法第二节第二节 随机方向法随机方向法随机方向法的步骤:随机方向法的步骤:第六章第六章 约束优化方法约束优化方法第三节第三节 复合形法复合形法复合形法的基本思路:复合形法的基本思路: 选择k(n+1k2n)个可行点,构造一个多面体(或多边 形),称为初始复合形。 对复合形进行寻优迭代计算。即利用复合形各顶点处目标函数值的大小关系,判断目标函 数值的下降方向,不断丢掉函数值最大的所谓最坏点(xH), 用一个新点代替最坏点,构成新的复合形。如此重复计算,使新的复合形不断地向可行域的最优点移动 和收缩,直至得到满足收敛准则的近似最优解为止。1)目标函数值下降 2) 可行点(满足所有约束条件 )第六章第六章 约束优化方法约束优化方法第三节第三节 复合形法复合形法x2x4x3x1 xHxLxC初始复合形的形成:初始复合形的形成:1)人为的给定k个顶点,构成初始复合形。 2)给定一个初始顶点,随机产生其他顶点。人为地确定一个初始可行点x1,其余k-1个设计点用随 机的方法产生,即 产生的顶点不一定是可行点。假设已有 q个点满足全部的约束条件,是可行点, 其余k-q个点不是可行点,为了使它们也能 满足所有约束条件,则可先求出所有满足 点(可行点)的中心点: 第六章第六章 约束优化方法约束优化方法第三节第三节 复合形法复合形法然后将不满足约束条件的非可行点向中心点移动: 若新点不可行,则继续移动,直到找到可行点为止 。只要可行域是凸集,它的中心点一定是可行点,那 么向中心点移动,一定能找到一个可行点。如果可行域为非凸集,中心点可能不在可行域内, 可以通过改变设计变量的上限和下限值,重新产生各 顶点来解决。 第六章第六章 约束优化方法约束优化方法第三节第三节 复合形法复合形法初始复合形的形成:初始复合形的形成:3)计算机自动生成初始复合形的全部顶点。首先产生一个可行点,然后照着第二种方法产生其余的k-1个可行点。 第六章第六章 约束优化方法约束优化方法第三节第三节 复合形法复合形法复合形的搜复合形的搜 索方法:索方法:1.反射称为反射系数一般取=1.3第六章第六章 约束优化方法约束优化方法第三节第三节 复合形法复合形法复合形的复合形的 搜索方法搜索方法 :1.反射复合形的搜索方法:复合形的搜索方法:1.反射反射成功的条件: 第六章第六章 约束优化方法约束优化方法第三节第三节 复合形法复合形法复合形的搜索方法:复合形的搜索方法:2.扩张称为扩张系数。一般取=1xc复合形的搜索方法:复合形的搜索方法:3.收缩称为收缩系数一般取=0.7将复合形的各顶点向最好点靠拢。压缩后的各顶点的计算公式是:复合形的搜索方法:复合形的搜索方法:4.压缩第六章第六章 约束优化方法约束优化方法第三节第三节 复合形法复合形法复合形法的计算步骤:复合形法的计算步骤:(1)选择复合形的顶点数k(n+1k2n),在可行域内构造初始复合形。 (2)计算复合形各顶点的目标函数值,比较其大小,找出 最好点,最坏点和次坏点。 (3)计算除去最坏点xH以外的各顶点的中心xC,判别中心 点xC是否可行,若可行转步骤(4);若不可行,则重新确 定设计变量的下限和上限值,令转到步骤(1)重新构造初始复合形。第六章第六章 约束优化方法约束优化方法第三节第三节 复合形法复合形法(4)计算反射点xR,必要时改变反射系数的值(取原 来的一半),直至反射成功。然后,构成新的复合形。 (5)判断是否收敛。若收敛条件得到满足,计算终值,约束最优解为否则转步骤(2)。复合形法的计算步骤:复合形法的计算步骤:第六章第六章 约束优化方法约束优化方法第三节第三节 复合形法复合形法例:第六章第六章 约束优化方法约束优化方法第三节第三节 复合形法复合形法复合形法的流程图复合形法的流程图 :* 其特点是注意到约束最优点通常在约束边界上:为此,可先找出 一个边界点,然后沿边界搜索;-是求解大型约束优化问题的主要方法.一.寻找边界点的方法1.在D内取一初始点,然后沿负梯度 方向搜索,直至使迭代点超越D或落在 边界上;2.若迭代点在D外,则将它调回到 边界上.第六章第六章 约束优化方法约束优化方法第四节第四节 可行方向法可行方向法二.产生适用可行方向的办法(一)适用可行方向的数学条件1. 适用(下降)性条件在迭代点处, 目标函数沿该方向的方向导数应小于0:与负梯度方向的夹角应小于900.第六章第六章 约束优化方法约束优化方法第四节第四节 可行方向法可行方向法2.可行性条件在边界迭代点处, 实时约束函数沿该方向的方向导数应不大于 0:与实时约束函数梯度方向的夹角应不小于900.(1)可行方向迭代公式:只要取适当的 ,能使 仍在D内, 则 称可行方向.(2)可行性条件第六章第六章 约束优化方法约束优化方法第四节第四节 可行方向法可行方向法* 若迭代点 处于J个约束边界的相交处, 应同时成立:综上所述, 适用可行方向的数学条件为:几何解释:第六章第六章 约束优化方法约束优化方法第四节第四节 可行方向法可行方向法(二)最有利的适用可行方向在满足上述适用可行方向的数学条件的同时,使目标函数的 方向导数为负且达到最小(处理为线性规划问题):D :使求* 1) -条件余度(>0,一般取为0.010.001);2) -方向偏离系数(>=0,对线性约束取为0, 其余取为1).-规格化条件第六章第六章 约束优化方法约束优化方法第四节第四节 可行方向法可行方向法三.步长因子的确定1. 最优步长因子(迭代点为内点时使用)下一迭代点如仍为内点, 继续进行, 直至迭代点到边界或域外时止.迭代公式:2. 试验步长因子迭代点在边界附近偏域内一侧时使 用, 采用最有利的适用可行方向.第六章第六章 约束优化方法约束优化方法第四节第四节 可行方向法可行方向法将 在 处作泰勒展开, 仅取到 线性项:(1)定义目标函数相对下降量 :(2)迭代公式 (3)(4)将(2)、(3)代入(1)后整理得:2) 按此法, 直至使迭代点进入约 束容差带或至域外为止.* 1) 为保证 是 的一个邻近 点, 的值不能取得太大. 通常第六章第六章 约束优化方法约束优化方法第四节第四节 可行方向法可行方向法3. 调整步长因子(将已出界的迭代点调 回到边界上) (1) 约束边界容差带在实际计算中,应给约束边界一个允 许的误差限: 式中, 通常取0.01-0.001;只要迭代点进入 容差带, 即认为达到了边界.(2) 调整步长因子因 与 很接近, 可认为 在这两点间按线性变化:(1)为使新迭代点落在容差带中部, 取第六章第六章 约束优化方法约束优化方法第四节第四节 可行方向法可行方向法(2)于是有(3)* 还需检验该点是否在容差带内. 若不满足,则)若 ,则) 若 ,