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